Cvmbycols - Revision history

Patrices at 17:35, 29 March 2011

2011-03-29T17:35:54Z

Patrices at 23:20, 24 March 2011

2011-03-24T23:20:24Z

Patrices at 23:39, 22 March 2011

2011-03-22T23:39:46Z

Patrices at 20:08, 17 March 2011

2011-03-17T20:08:50Z

Patrices at 19:15, 17 March 2011

2011-03-17T19:15:58Z

Patrices at 18:39, 17 March 2011

2011-03-17T18:39:36Z

Patrices at 18:34, 17 March 2011

2011-03-17T18:34:02Z

Patrices at 18:15, 17 March 2011

2011-03-17T18:15:49Z

Patrices at 22:26, 16 March 2011

2011-03-16T22:26:47Z

Patrices at 02:17, 16 March 2011

2011-03-16T02:17:10Z

@@ Line 292: / Line 292: @@
 Special consideration must be made when running these codes on a high-performance filesystem such as Lustre.
-* Update all Etree *.h/*.c files to include (#include "iobuf.h") following all stdio.h includes
+* Update all Etree *.h/*.c files to include (#include "iobuf.h") following all stdio.h includes. Or apply the patch given below.
 * Execute: module add iobuf
 * Set compiler flag USE_IOBUF_MACROS in Etree Makefile
@@ Line 302: / Line 302: @@
 </pre>
 * Problems persists with writing many (1-2K cores) Etrees at once on a Lustre filesystem.

@@ Line 136: / Line 136: @@
 === Cvmbycols-extract-MPI ===
-Divides the etree region into C 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 queries UCVM for the points in its column and writes a flat-file formatted etree. After program execution, there are N sub-etree files, each locally unsorted. The extractor must be run on 2^Y + 1 cores where Y>0 and (2^Y) > C. The output flat file format is an arbitrary list of octants(24 byte addr, 16 byte key, 12 byte payload).
+Divides the etree region into C 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 queries UCVM for the points in its column and writes a flat-file formatted etree. After program execution, there are N sub-etree files, each locally unsorted. The extractor must be run on 2^Y + 1 cores where Y>0 and (2^Y) < C. The output flat file format is a list of octants(24 byte addr, 16 byte key, 12 byte payload) in arbitrary Z-order.
 === Cvmbycols-sort-MPI ===
-Sorts the sub-etrees produced by cvmbycols-extract-MPI so that each file is in local pre-order. again, the is an embarrassingly parallel operation. Each rank in the job sorts one of the sub-etrees produced by the previous program. The sorter must be run on 2^Y cores where Y>0. The worker pool must be large enough to allow each worker to load all the octants from its assigned file into memory. By default, this is 20M points. The average number of points/core can be estimated as total_num_octants / 2^Y. If the number of points per core exceeds memory storage the extraction job size can simply be increased by a factor of two until all points fit in memory for the sort, or if memory size allows, the buffer size constant may be increased in the cvmbycols_sort_MPI.c source code.
+Sorts the sub-etrees produced by cvmbycols-extract-MPI so that each file is in local pre-order (Z-order). Again, the is an embarrassingly parallel operation. Each rank in the job reads in one of the sub-etrees produced by the previous program, sorts the octants in Z-order, and writes the sorted octants to a new sub-etree. The sorter must be run on 2^Y cores where Y>0. The worker pool must be large enough to allow each worker to load all the octants from its assigned file into memory. By default, this octant limit is 20M octants. If a rank reports that the size of the sub-etree exceeds memory capacity, the 20M buffer size constant may be increased if memory allows, or alternatively, cvmbycols-extract-MPI may be rerun with a larger job size to reduce the number of octants per file.
 === Cvmbycols-merge-MPI ===
-Merges N small flat files into a final, compacted etree. This is essentially a merge sort on the keys from the addresses extracted from the local files. The cores at the lowest level of the merge tree each read in octants from two flat files in pre-order, merge sort the two sets of 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.
+Merges N locally sorted etrees in flat file format into a final, compacted etree. This is essentially a merge sort on the keys from the addresses read from the local files. The cores at the lowest level of the merge tree each read in octants from two flat files in pre-order, merge sort the two sets of 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.
 The program reads in input files that are in flat file format. In can output a merged Etree in either Etree format or flat file format. 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.
@@ Line 153: / Line 155: @@
 === 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 is used to convert the flat file produced by Cvmbycols in flat file mode into Etree format.
@@ Line 234: / Line 236: @@
 # Etree parameters and info
-title=ChinoHills4Hz200ms
+title=ChinoHills4Hz8ppwl200ms
 author=P_Small_and_R_Taborda
 date=03/2011
@@ Line 274: / Line 276: @@
 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

@@ Line 131: / Line 131: @@
 == 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.
+This program is actually three separate MPI programs. One program performs a parallel extraction from UCVM and saves the octants in set of files, the second locally sorts the octants in each file, and the last performs 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 C 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 queries UCVM for the points in its column and writes a flat-file formatted etree in pre-order. After program execution, there are N small files, each locally sorted. The extractor must be run on 2^Y + 1 cores where Y>0 and (2^Y) > C. The worker pool must be large enough to allow each worker to store all the points in its assigned columns in memory. The average number of points/core can be estimated as total_num_octants / 2^Y. If the number of points per core exceeds memory storage the job size can simply be increased by a factor of two until all points fit in memory.
+Divides the etree region into C 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 queries UCVM for the points in its column and writes a flat-file formatted etree. After program execution, there are N sub-etree files, each locally unsorted. The extractor must be run on 2^Y + 1 cores where Y>0 and (2^Y) > C. The output flat file format is an arbitrary list of octants(24 byte addr, 16 byte key, 12 byte payload).
-The output flat file format is a pre-order list of octants(24 byte addr, 16 byte key, 12 byte payload).
@@ Line 186: / Line 189: @@
 = User Guide =
 == Configuring Cvmbycols ==

@@ Line 136: / Line 136: @@
 === 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 flat-file formatted etree in pre-order. After program execution, there are N small files, each locally sorted. The extractor must be run on 2^N + 1 cores.
+Divides the etree region into C 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 queries UCVM for the points in its column and writes a flat-file formatted etree in pre-order. After program execution, there are N small files, each locally sorted. The extractor must be run on 2^Y + 1 cores where Y>0 and (2^Y) > C. The worker pool must be large enough to allow each worker to store all the points in its assigned columns in memory. The average number of points/core can be estimated as total_num_octants / 2^Y. If the number of points per core exceeds memory storage the job size can simply be increased by a factor of two until all points fit in memory.
 The output flat file format is a pre-order list of octants(24 byte addr, 16 byte key, 12 byte payload).

@@ Line 13: / Line 13: @@
-= Algorithm Description =
+= Etree Summary =
 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:
@@ Line 31: / Line 21: @@
 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:
+The funamental unit of data in an Etree is the octant. An octant contains an address (location code) and a payload (material properties). Octants are organized into a tree structure called an octree, where each node has up to eight children. 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:
 <pre>
@@ Line 43: / Line 33: @@
 ticks for level N = 2^N
 </pre>
 And thus the octant size in level N is:
 <pre>
 octant size = (2^N * (max(len x, len y, len z) / 2^31)) m
@@ Line 57: / Line 49: @@
-These relations are important in understanding the algorithm described in the following section.
+These relations are important in understanding the algorithm described in the following sections.
@@ Line 134: / Line 136: @@
 === 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 flat-file formatted etree in pre-order. After program execution, there are N small files. The extractor must be run on 2^N + 1 cores.
+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 flat-file formatted etree in pre-order. After program execution, there are N small files, each locally sorted. The extractor must be run on 2^N + 1 cores.
 The output flat file format is a pre-order list of octants(24 byte addr, 16 byte key, 12 byte payload).

← Older revision		Revision as of 18:39, 17 March 2011
Line 149:		Line 149:

	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 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).
		+
		+
		+	== ecoalesce ==
		+
		+	This utility optimizes an Etree be coalescing sequences of adjacent octants into single octants of a higher level when a set of comparison criteria is met. This serves to reduce the size of the Etree at the cost of resolution. Currently, ecoalesce is setup to combine eight adjacent octants when:
		+
		+	<pre>
		+	Vp is equal
		+	Vs is equal
		+	Density is equal
		+	</pre>
		+
		+	Execute the utility with:
		+
		+	<pre>
		+	% ecoalesce etree.in etree.out
		+	</pre>

@@ Line 258: / Line 258: @@
 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:
+* Update all Etree *.h/*.c files to include (#include "iobuf.h") following all stdio.h includes
 <pre>
 IOBUF_PARAMS='*:count=2:size=64M:verbose';export IOBUF_PARAMS;
 </pre>
 * 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.
+* Problems persists with writing many (1-2K cores) Etrees at once on a Lustre filesystem.

@@ Line 82: / Line 82: @@
 ** 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)
+*** Write this layer to a 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
@@ Line 112: / Line 112: @@
 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.
+Simply put, it is essentially a merge sort performed on 2^N small flat files that contain all of the points needed for the final etree. The flat files 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 flat files 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/flat file for writing in append mode, and simply stream the sorted octants to disk 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.
+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 flat files. 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 file.
@@ Line 124: / Line 124: @@
 == 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.
+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.
@@ Line 134: / Line 134: @@
 === 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.
+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 flat-file formatted etree in pre-order. After program execution, there are N small 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).
+The output 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.
+Merges N small flat files into a final, compacted etree. This is essentially a merge sort on the keys from the addresses extracted from the local files. The cores at the lowest level of the merge tree each read in octants from two flat files in pre-order, merge sort the two sets of 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.
-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.
+The program reads in input files that are in flat file format. In can output a merged Etree in either Etree format or flat file format. 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.
 === 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.
+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).

← Older revision		Revision as of 22:26, 16 March 2011
Line 23:		Line 23:


−	== Etree ~~Ticks, Levels, and Octant Size~~ ==	+	== 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:

@@ Line 87: / Line 87: @@
-Given these relations, the minimum and maximum resolution present in an etree given a certain set of input parameters can be derived as follows:
+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:
 <pre>
 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