Data-Parallel Mesh Connected Components Labeling and Analysis

Harrison, Cyrus; Childs, Hank; Gaither, Kelly P.

Data-Parallel Mesh Connected Components Labeling and Analysis

Files

131-140.pdf (646.47 KB)

Date

2011

Authors

Harrison, Cyrus
Childs, Hank
Gaither, Kelly P.

Publisher

The Eurographics Association

Abstract

We present a data-parallel algorithm for identifying and labeling the connected sub-meshes within a domaindecomposed 3D mesh. The identification task is challenging in a distributed-memory parallel setting because connectivity is transitive and the cells composing each sub-mesh may span many or all processors. Our algorithm employs a multi-stage application of the Union-find algorithm and a spatial partitioning scheme to efficiently merge information across processors and produce a global labeling of connected sub-meshes. Marking each vertex with its corresponding sub-mesh label allows us to isolate mesh features based on topology, enabling new analysis capabilities. We briefly discuss two specific applications of the algorithm and present results from a weak scaling study. We demonstrate the algorithm at concurrency levels up to 2197 cores and analyze meshes containing up to 68 billion cells.

        @inproceedings{:10.2312/EGPGV/EGPGV11/131-140
,
booktitle = {Eurographics Symposium on Parallel Graphics and Visualization
},
editor = {Torsten Kuhlen and Renato Pajarola and Kun Zhou
},
title = {{Data-Parallel Mesh Connected Components Labeling and Analysis
}},
author = {Harrison, Cyrus and 
Childs, Hank and 
Gaither, Kelly P.
},
year = {2011
},
publisher = {The Eurographics Association
},
ISSN = {1727-348X
},
ISBN = {978-3-905674-32-3
},
DOI = {/10.2312/EGPGV/EGPGV11/131-140
}
}