Difference between revisions of "Cvmbycols"

From SCECpedia
Jump to navigationJump to search
Line 1: Line 1:
 
= Overview =
 
= Overview =
  
Cvmbycols is a set of codes for producing compacted Etrees for geographic regions with material properties drawn from a community velocity model. Serial and MPI versions of the program are provided.
+
Cvmbycols is a set of codes for producing compacted Etrees for geographic regions with material properties drawn from a community velocity model. Serial and MPI versions of the program are provided. The tool makes use of several existing software packages, including:
 +
* CMU Euclide Etree, available from http://www.cs.cmu.edu/~euclid/
 +
* Unified California Velocity Model, available from [[UCVM]]
 +
* CVM-H, available from [[CVM-H]]
 +
* CVM-S, available from [[CVM-S]]
 +
* USGS Cencal, available from http://earthquake.usgs.gov/regional/nca/3Dgeologic/
 +
 
 +
 
 +
This SCEC version of cvmbycols is based on an older version originally developed by Tiankai Tu et al. at CMU.
 +
 
  
 
= Algorithm Description =
 
= Algorithm Description =
Line 13: Line 22:
 
** Step the depth down by the resolution of this 2D grid and loop to the next layer.
 
** Step the depth down by the resolution of this 2D grid and loop to the next layer.
 
* Loop to the next column.
 
* Loop to the next column.
 +
  
 
= Programs =
 
= Programs =
 +
 +
The package provides a number of programs and utilities. The Cvmbycols etree creator is described below:
 +
  
 
== Cvmbycols Serial ==
 
== Cvmbycols Serial ==
  
Divides etree region into columns, then extracts each column from the underlying CVM and inserts the octants into the final Etree.
+
This program runs as a single-core command-line application. It works by dividing the etree region into columns, then extracts each column from the underlying CVM and inserts the octants into the final Etree.
  
  
 
== Cvmbycols MPI ==
 
== Cvmbycols MPI ==
  
There are two main steps.
+
This program is actually two separate MPI programs. One program performs a parallel extraction from UCVM, and other other a merge to form the final etree. These are very high performance applications, capable of generating large etrees.
 +
 
 +
 
 +
=== Cvmbycols-extract-MPI ===
 +
 
 +
Divides the etree region into X columns for extraction. This is an embarrassingly parallel operation. A dispatcher (rank 0) farms out each column to a worker in a pool of N cores for extraction. Each worker writes its own local etree. After program execution, there are N small etrees. The extractor must be run on 2^N + 1 cores.
 +
 
  
Extraction: Division of the etree region into X columns for extraction. This is an embarrassingly parallel operation. A dispatcher (rank 0) farms out each column to a worker in a pool of N cores for extraction. Each worker writes its own local etree. After program execution, there are N small etrees. The extractor must be run on 2^N + 1 cores.
+
=== Cvmbycols-merge-MPI ===
  
Merging: Merging of the N small etrees into the final Etree. This is essentially a merge sort on the keys from the Etree addresses extracted
+
Merges N small etrees into a final, compacted etree. This is essentially a merge sort on the keys from the addresses extracted from the local etrees. The cores at the lowest level of the merge tree each read in octants from two etrees with a pre-order traversal, merge sort the addresses, then pass the locally sorted list of addresses to a parent node for additional merging. This proceeds until the points rise to rank 1 which has a completely sorted list of etree addresses. Rank 0 takes this sorted list and performs a transactional append on the final etree. The merger must be run on 2^N cores.
from the local etrees. The cores at the lowest level of the merge tree each read in octants from two etrees with a pre-order traversal, merge sort the addresses, then pass the locally sorted list of addresses to a parent node for additional merging. This proceeds until the points rise to rank 1 which has a completely sorted list of etree addresses. Rank 0 takes this sorted list and performs a transactional append on the final etree. The merger must be run on 2^N cores.
 
  
 
Merging is a very fast opertion. Speeds in excess of 3M points/sec have been achieved on NICS Kraken.
 
Merging is a very fast opertion. Speeds in excess of 3M points/sec have been achieved on NICS Kraken.

Revision as of 21:03, 8 March 2011

Overview

Cvmbycols is a set of codes for producing compacted Etrees for geographic regions with material properties drawn from a community velocity model. Serial and MPI versions of the program are provided. The tool makes use of several existing software packages, including:


This SCEC version of cvmbycols is based on an older version originally developed by Tiankai Tu et al. at CMU.


Algorithm Description

Optimized Etree Resolution Based on Freq, PPWL, and Min Vs

  • Divide region in set of x,y columns, where the length of each column equals its width.
  • Starting at depth = 0m, extract a 2D grid for the column at the resolution needed to support the max frequency, pounts/wavelength, and minimum Vs.
    • If the local minimum Vs is in this 2D grid allows for a lower resolution, and the current z value is divisible by the lower resolution, requery the CVM at the lower resolution. Otherwise, if the local min Vs in this grid needs a higher resolution, increase the resolution to what is required (up to the maximum resolution dictated by the configured global minimum Vs) and requery the CVM.
    • Write this layer to an Etree (either a final etree or an etree local to this core)
    • Step the depth down by the resolution of this 2D grid and loop to the next layer.
  • Loop to the next column.


Programs

The package provides a number of programs and utilities. The Cvmbycols etree creator is described below:


Cvmbycols Serial

This program runs as a single-core command-line application. It works by dividing the etree region into columns, then extracts each column from the underlying CVM and inserts the octants into the final Etree.


Cvmbycols MPI

This program is actually two separate MPI programs. One program performs a parallel extraction from UCVM, and other other a merge to form the final etree. These are very high performance applications, capable of generating large etrees.


Cvmbycols-extract-MPI

Divides the etree region into X columns for extraction. This is an embarrassingly parallel operation. A dispatcher (rank 0) farms out each column to a worker in a pool of N cores for extraction. Each worker writes its own local etree. After program execution, there are N small etrees. The extractor must be run on 2^N + 1 cores.


Cvmbycols-merge-MPI

Merges N small etrees into a final, compacted etree. This is essentially a merge sort on the keys from the addresses extracted from the local etrees. The cores at the lowest level of the merge tree each read in octants from two etrees with a pre-order traversal, merge sort the addresses, then pass the locally sorted list of addresses to a parent node for additional merging. This proceeds until the points rise to rank 1 which has a completely sorted list of etree addresses. Rank 0 takes this sorted list and performs a transactional append on the final etree. The merger must be run on 2^N cores.

Merging is a very fast opertion. Speeds in excess of 3M points/sec have been achieved on NICS Kraken.


Defining properties of an Etree

The following properties are defined:

  • Bounding box of geographic region in lon,lat coordinates
  • Extents of Etree volume in 3D, in km
  • Number of columns in x,y axis to partition 3D space. The resulting columns must be square along the x-y axis.
  • Frequency limit to support in Hz
  • Number of points per wavelength to support
  • Minimum Vs to support
  • Maximum octant size to allow
  • Name of the output etree file
  • CVM to use for material properties (from UCVM)


User Guide

Source Code

SVN: https://source.usc.edu/svn/cvmbycols


Supported CVMs

The cvmbycols utility is built upon UCVM. As a result, it can extract etrees from the following CMV sources:

  • CVM-H
  • CVM-S
  • USGS Cencal (which itself is an etree)
  • 1D