Distributed Feature Extraction

In our previous work, we have developed a methodology for analyzing time-varying datasets which tracks 3D amorphous features as they evolve in time. However, the implementation is for single-processor non-adaptive grids and for massive multiresolution datasets this approach needs to be distributed and enhanced. Here, we describe extensions to our feature extraction and tracking methodology for distributed AMR simulations. Two different paradigms are described, a "fully distributed" and a "partial-merge" strategy.

1 Algorithm Design

Distributed Feature Extraction (On each processor)

Data Acquisition: If the data is already residing in the processor, skip to step (2); else, each processor must initially read the local data into its own data structures (Cell list).
In each processor, perform region growing algorithm [4] based upon a given threshold value to obtain a list of objects that are local to the processor. The list of the boundary cells, which is part of the Object List, is also determined.
Use either complete-merge algorithm or partial-merge algorithm to merge the features shared across processor boundaries to obtain merge table.
Send the merge results (table form), bounding polygons and/or quantification to the visualization workstation to display the results.

Global Merge on Viz-Server

Receiving partial merge table from each processor (when using partial merge algorithm), combining into global object-merge table. Or receive global merge table when using complete-merge algorithm.
Update the polygons/quantification results.
Display the results.

2 Fully Distributed -- Complete-Merge Implementation

After extracting the features within its own data partition, each processor forms a message including the boundary information it maintains, such as the information for local objects that have boundary cells and the information for those cells.
Processors communicate each other using a binary swap algorithm. ** The communication over log(n) time (n: number of processors)
If a feature is shared across the processor boundary, the object table in the processor is updated.
A global table is formed by the first processor.

Figure 1 shows the complete-merge strategy. The left picture shows the data partitioning processor communication. In the right, an example dataset is shown with the objects contained within each processor. The numbers below each picture give the total object count per processor. In the final image, each object gets its own color (the bounding polygons). There are 27 objects in the final image.

Figure 1: Complete-merge strategy. (click for bigger picture.)

3 Partial Merge Strategy

Partial connectivity. After each processor does its own feature extraction, only neighboring processors communicate with their immediate boundary neighbors to determine how their feature correlate (i.e. using ghosted boundaries). ** Communication time for this algorithm does not depend on the number of processors.
This partial connectivity information (stored as a local object id table by each processor) is then sent along with any other visualization information (such as isosurface polygons) to a visualization server.

Figure 2 shows the partial merge strategy. Each processor computes the locally residing objects, then immediate neighbors are coalesced. This information is passed to the visualization server to compute the full merge. This figure uses the same partition as Figure 1.

Figure 2: Partial merge strategy.

4 Parallel Feature Extraction Extension for Adaptive Mesh Data

For adaptive meshes, individual portions of the data may contain higher resolution data at different levels. At higher resolution:

Feature boundaries may change.

The shape of the boundary may change, the feature may split into one or more components, or it may merge with another neighboring feature. These events are similar to what happens in feature tracking (Referring to Figure below, Object 1 in refinement level A (A1) splits into two pieces in the higher refined dataset C which replaces B. Of the two pieces, C2 is attached to A1, and C3 is not).

If just the boundaries of the objects are desired (Case I), then an algorithm similar to the boundary merge performed earlier will determine that A1 and C2 are connected.

If feature tracking is performed (Case II), the information that C3 is the same as A1 will also be available.

Figure 3: Merging objects at different resolutions

Algorithms (Case I):

For each level , each processor computing its own features.

Obtain the extraction results at each level of resolution (objects are now classified as belonging to a processor and a level).

Determine both data neighbors and level neighbors, and obtain a transformation between levels.

The different levels merge objects, based upon neighboring boundary information. This can be computed during the partial merge strategy described above.

The output consists of a set of objects from the different levels with a table specifying which objects from different levels are connected.

Send the merge information to viz-server to combine a global merge table for each level, and display the results.

Figure 4 gives a feature extraction on the multi-resolution dataset example. The feature extraction results for Level 1 and Level 2 are shown as (A); B is the shown the data neighbors and level neighbors; C is the final merge result (when two objects merge, they get the same color, those who do not merge coloring gray).

Figure 4: Feature extraction on the multi-resolution dataset example.

This work ( PDF PS)was presented at SPIE, Visualization and Data Analysis Symposium, January 2002.