Author | M. L. Simone, R. M. Loy, M. S. Shephard and J. E. Flaherty |
---|---|
Title | A Distributed Octree Structure and Its Application to Parallel Mesh Generation |
Year | 1996 |
Abstract | A distributed octree data structure was developed to support efforts in parallel mesh generation. The distributed octree augments a basic hierarchical octree structure to include interprocessor links to off processor octants, and also includes lateral links between octants of the same level which share common faces in the octree topology. These lateral links, known as face neighbor links, support O (1) neighborhood queries during mesh generation. Two basic algorithms are needed to construct a distributed octree with face neighbor links. An octant migration procedure supports an arbitrary redistribution of octants across the processors while maintaining the octree connectivity. An octant refinement algorithm allows octants to be allocated in parallel while maintaining local tree links, and interprocessor tree links between remote octree face neighbors. We describe how the distributed octree and algorithms are implemented inside an octree-based parallel mesh generator. Performance results for all of the algorithms are presented on a 32 processor IBM SP2. |
PDF File | Download |