Difference between revisions of "Cvmbycols"
m |
|||
Line 23: | Line 23: | ||
− | == Etree | + | == Etree Properties == |
In order to understand how cvmbycols works, some knowledge of the Etree data structure is required. The fundamental unit of measure in an Etree is the tick. This is a distance expressed in meters, and is derived from the length of the longest side of the geographic region: | In order to understand how cvmbycols works, some knowledge of the Etree data structure is required. The fundamental unit of measure in an Etree is the tick. This is a distance expressed in meters, and is derived from the length of the longest side of the geographic region: |
Revision as of 22:26, 16 March 2011
Contents
Overview
Cvmbycols is a set of codes for producing compacted Etrees containing 3D 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 Euclid Etree Library, available from http://www.cs.cmu.edu/~euclid/
- Unified California Velocity Model, available from UCVM
- Community Velocity Models, including one or more of these:
- 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 and Ricardo Taborda from the Quake Group at CMU.
Algorithm Description
This program uses several algorithmic approaches to increase extraction speed and minimize the amount of disk space required to store the Etree. These are described in the following sections.
Gridding of Geographic Coordinates
Gridding of the geographic bounding box is performed using bilinear interpolation of the four corners specified in the configuration file. No map projection is used. Grid points are located at cell center.
Etree Properties
In order to understand how cvmbycols works, some knowledge of the Etree data structure is required. The fundamental unit of measure in an Etree is the tick. This is a distance expressed in meters, and is derived from the length of the longest side of the geographic region:
tick size = (max(len x, len y, len z) / 2^31) m
In essence, the geographic region is divided up into a set of 2^31 ticks.
The octants in an Etree are organized in an octree. Each level in this octree represents an octant size (alternatively: edge size, or resolution). Moving from level N to level N+1 in the octree increases resolution by 2x. Moving from level N to level N-1 reduces resolution by 2x. The resolution for a level can be determined with:
res from level N = (max_len / 2^N) m
The number of ticks in an octant of level N is:
ticks for level N = 2^N
And thus the octant size in level N is:
octant size = (2^N * (max(len x, len y, len z) / 2^31)) m
Given a particular resolution, the appropriate level to represent it in the etree can be determined with:
level N from res = (int)(log(max_len/res)/log(2)) + 1 (rounded up to next integer)
These relations are important in understanding the algorithm described in the following section.
Optimized Etree Resolution Based on Frequency, PPWL, and Minimum Vs
One of the strengths of the Etree (octree) representation is that resolution can be adjusted so that a particular region is sampled at a lower/higher interval than surrounding areas. You are able to achieve high resolution in just those places where it is needed, and the rest of the region can be sampled at a much lower rez thereby saving considerable disk space.
With this flexibility comes the difficulty of determining what resolution is needed at all points within a meshing region to support Computational Seismology simulations. Cvmbycols uses an algorithm to deduce this resolution based off of three input parameters: maximum frequency to support, the number of points per wavelength that is desired, and the minimum Vs to support. The following relation is used to derive the resolution for a region:
res = vs_min / (ppwl * max_freq) where: res: resolution for the region with vs_min, in meters vs_min: Minimum Vs found in region, in meters/sec ppwl: desired points per wavelength max_freq: maximum frequency to support, in Hz
Using the above relation, the 3D space is decomposed into small columns, and the resolution in each column is tailored to the vs values found at each depth. The algorithm can be summarized as follows:
- Divide region in set of x,y columns, where the length of each column equals its width.
- For each column:
- 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, with a depth that is one-half the current octant edge size (that is, Z axis is cell center as well).
- 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/flat file (a single file when run serially, or a file local to this core when run in parallel)
- Step the depth down by the resolution of this 2D grid and loop to the next layer in the column.
- Loop to the next column
- 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, with a depth that is one-half the current octant edge size (that is, Z axis is cell center as well).
The cvmbycols software enforces a minimum and maximum resolution for octants. Given a certain set of input parameters, these resolutions can be derived as follows:
If vs_min = 200 m/s, max_freq = 4.0 Hz, and ppwl = 8, max_dim_length = 180000.0 m, max_cellsize = 500.0 m, then Maximum Resolution: res = 200.0 / (8.0 * 4.0) = 6.25 m (minimum resolution needed to support Vs=200 m/s) N = (log(180000.0/6.25)/log(2)) + 1 = 15 max_res = 180000.0 / 2^15 ticks ~= 5.49 m Therefore, maximum resolution (minimum edge size) for these parameters is 5.49 m. Minimum Resolution: res = 500.0 m (the maximum cell size to support) N = (log(180000.0/500.0)/log(2)) + 1 = 9 min_res = 180000.0 / 2^9 ticks ~= 351.56 m Therefore, minimum resolution (maximum edge size) for these parameters is 351.56 m.
- Minimum resolution represents a floor on the possible resolution of an etree. This is protection against very large octants from being formed by high Vs values.
High-performance Etree merging and compaction
Generation of an Etree in a parallel environment is challenging since the Euclid etree interface only allows serial write access to the etree file. Points may only be inserted, or they may be appended in key order, by a single writer. This makes etee construction and compaction time consuming. To circumvent this issue, a high performance etree merge/compaction algorithm has been developed.
Simply put, it is essentially a merge sort performed on 2^N small etrees that contain all of the points needed for the final etree. The small etrees contain material properties previously extracted from UCVM. This extraction may be done serially or in parallel as described in the sections below. Once these small, local etrees exist on disk, an MPI job of 2^N cores is then able to sort these octants by their keys in O(n*log n) time. Once all the octants are sorted, a single core may then open the final etree for writing in append mode, and simply stream the sorted octants to the final etree efficiently.
Conceptually, the cores in this 2^N MPI job are organized into a tree-like structure with each node containing two children. The bottom layer of this tree has nodes that each do a pre-order traversal on two local etrees. They sort the combined octants read from each etree in pre-order, and then pass them up to a parent node. The nodes from the top layer to the second to bottom layer each receive locally sorted lists of octants from their two children and once again sort the combined list of octants in pre-order. This newly sorted list is passed upward in this manner until the root node of the tree receives two locally sorted halves of the entire set of etree points. It then sorts them, and appends the fully sorted stream of octants to the final etree file.
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/flat file.
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 in pre-order. After program execution, there are N small etree files. The extractor must be run on 2^N + 1 cores.
The program can provide the etrees in one of two output formats: standard Etree format, or flat file format. Flat file format is a pre-order list of octants(24 byte addr, 16 byte key, 12 byte payload).
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 etree/flat files 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/flat file. The merger must be run on 2^N cores.
The program can read in input files that are in one of two formats: standard Etree format, or flat file format. In can output a merged Etree in either of those formats as well, although due to space considerations, it strips the output flat file format to a pre-order list ot octants(16 byte key, 12 byte payload). The missing addr field is redundant and can be regenerated from the key field. Cvmbycols-merge-MPI can only operate in one mode at a time for both input and output. For example, it cannot read in Etrees and output a flat file.
ff2etree
This utility is used to convert the flat file produced by cvmbycols in flat file mode into Etree format. This is predominately used when the extraction and merge have been performed on a Lustre filesystem (see Technical Notes section below). This utility should not write its Etree output to a Lustre filesystem.
Defining properties of a CVM Etree
The following properties are needed in order to produce a CVM Etree:
- 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 and its format (Etree or flat files are supported)
- CVM to use for material properties (from UCVM)
User Guide
Configuring Cvmbycols
An example configuration file follows:
# Domain corners coordinates (degrees): proj=geo-bilinear lon_0=-119.288842 lat_0=34.120549 lon_1=-118.354016 lat_1=35.061096 lon_2=-117.780976 lat_2=33.096503 lon_3=-116.846030 lat_3=34.025873 # Domain dimensions (meters): x-size=180000.0000 y-size=135000.0000 z-size=61875.0000 # Blocks partition parameters: nx=256 ny=192 # Max freq, points per wavelength max_freq=4.0 ppwl=8.0 # Etree min/max resolution as power of 2 max_cellsize=500.0 # Etree parameters and info title=ChinoHills4Hz200ms author=P_Small_and_R_Taborda date=03/2011 outputfile=/lustre/scratch/patricks/cvmbycols/trunk/src/cvmbycols/etree_cvmh_chino_4hz_200ms.e format=etree # CVM to use #cvm=cvms cvm=cvmh ucvmconf=../../conf/kraken/ucvm.conf # Min Vs, Vp vs_min=200.0 # Scratch dir scratch=/lustre/scratch/patricks/tmp
Running Cvmbycols MPI
The following PBS script for NICS Kraken illustrates how cvmbycols may be submitted to the batch scheduler:
#!/bin/sh #PBS -q medium #PBS -l size=1548 #PBS -l walltime=08:00:00 #PBS -o /lustre/scratch/${USER}/cvmbycols/trunk/pbs/kraken/chino_cvmh_4hz_200ms.out #PBS -e /lustre/scratch/${USER}/cvmbycols/trunk/pbs/kraken/chino_cvmh_4hz_200ms.err #PBS -V HOME_DIR=/lustre/scratch/${USER}/cvmbycols/trunk/src/cvmbycols cd ${HOME_DIR} echo "Starting jobs" date aprun -n 1025 -S 4 ./cvmbycols-extract-MPI -f ../../conf/kraken/chino_cvmh_4hz_200ms.conf aprun -n 1024 -S 4 ./cvmbycols-merge-MPI -f ../../conf/kraken/chino_cvmh_4hz_200ms.conf echo "Jobs done" date exit 0
Note that one additional core is needed as a dispatcher for the extractor.
Technical Note for Lustre Filesystems
Special consideration must be made when running these codes on a high-performance filesystem such as Lustre.
- On lustre filesystems, enable the Cray IOBUF module when compiling cvmbycols. In the PBS submit scripts for the extraction and merge, declare the following environment variable:
IOBUF_PARAMS='*:count=2:size=64M:verbose';export IOBUF_PARAMS;
- It is recommended that cvmbycols be run in flat file mode on Lustre filesystems. This mode is enabled by setting "format=flatfile" in the cvmbycols configuration file. This flat file can later be converted to an etree with the ff2etree utility.
- Be wary of running cvmbycols in Etree mode as there have been reports of Etree read/write operations placing heavy load on Lustre OSTs.
One possible way to improve etree performance on Lustre:
- Update includes of stdio.h to iobuf.h in all Etree codes
- Execute: module add iobuf
- Set compiler flag USE_IOBUF_MACROS
- Recompile cvmbycols
- Set IOBUF_PARAMS environment variable as described above
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
References
- Ricardo Taborda, Julio Lopez, David O'Hallaron, Tiankai Tu and Jacobo Bielak (2007): A review of the current approach to CVM-Etrees", SCEC Annual Meeting, Palm Springs, CA, USA, September 8–12 (Abstract and poster).
- Tiankai Tu, David R. O'Hallaron, and Julio Lopez (2003): The Etree Library: A System for Manipulating Large Octrees on Disk. Technical Report CMU-CS-03-174, School of Computer Science, Carnegie Mellon University, July, 2003. ( ps, pdf, ppt, bib ).
- Tiankai Tu, David R. O'Hallaron, and Julio Lopez (2002): Etree: A Database-Oriented Method for Generating Large Octree Meshes. In Proceedings of the Eleventh International Meshing Roundtable (Ithaca, NY, Sept. 2002), pp. 127-138. ( ps, pdf, ppt, bib )
- David R. O'Hallaron (2003): Database Methods for Scientific Computing, Northwestern University, Feb, 2003. This is an overview of the Euclid project. ( ppt, MPEG animation on title slide )