A Data-Parallel Implementation of the Geometric Partitioning Algorithm

DSpace/Manakin Repository

A Data-Parallel Implementation of the Geometric Partitioning Algorithm

Citable link to this page

 

 
Title: A Data-Parallel Implementation of the Geometric Partitioning Algorithm
Author: Hu, Yu Charlie; Teng, Shang-Hua; Johnsson, S. Lennart

Note: Order does not necessarily reflect citation order of authors.

Citation: Hu, Yu Charlie, Shang-Hua Teng, and S. Lennart Johnsson. 1996. A Data-Parallel Implementation of the Geometric Partitioning Algorithm. Harvard Computer Science Group Technical Report TR-15-96.
Full Text & Related Files:
Abstract: We present a data-parallel, High Performance Fortran (HPF) implementation of the geometric partitioning algorithm. The geometric partitioning algorithm has provably good partitioning quality. To our knowledge, our implementation is the first data-parallel implementation of the algorithm. Our data-parallel formulation makes extensive use of segmented prefix sums and parallel selections, and provide a data-parallel procedure for geometric sampling. Experiments in partitioning particles for load-balance and data interactions as required in hierarchical N-body algorithms and iterative algorithms for the solution of equilibrium equations on unstructured meshes by the infinite element method have shown that the geometric partitioning algorithm has an efficient data-parallel formulation. Moreover, the quality of the generated partitions is competitive with that offered by the spectral bisection technique and better than the quality offered by other partitioning heuristics.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:25620495
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters