S-HARP: A scalable parallel dynamic partitioner for adaptive mesh-based computations

Andrew Sohn, Horst Simon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Computational science problems with adaptive meshes involve dynamic load balancing when implemented on parallel machines. This dynamic load balancing requires fast partitioning of computational meshes at run time. We present in this report a scalable parallel dynamic partitioner, called S-HARP. The underlying principles of S-HARP are the fast feature of inertial partitioning and the quality feature of spectral partitioning. S-HARP is a universal dynamic partitioner with three distinctive features: (a) fast partitioning from scratch with a global view, requiring no information from the previous iterations, (b) no restriction on the issue of one partition per processor, (c) no imbalance factor issue because of precise bisection using sorting. Two types of parallelism have been exploited in S-HARP, fine-grain loop-level parallelism and coarse-grain recursive parallelism. The parallel partitioner has been implemented in Message Passing Interface on Cray T3E and IBM SP2 for portability. Experimental results indicate that S-HARP can partition a mesh of over 100,000 vertices into 256 partitions in 0.18 seconds on a 64-processor Cray T3E. S-HARP is much more scalable than other dynamic partitioners, giving over 17-fold speedup on 64 processors while ParaMeTiS1.0 gives a few-fold speedup. Experimental results demonstrate that S-HARP is three to 15 times faster than the other dynamic partitioners on computational meshes of size over 100,000 vertices while giving comparable edge cuts.

Original languageAmerican English
Title of host publicationSC 1998 - Proceedings of the ACM/IEEE Conference on Supercomputing
PublisherAssociation for Computing Machinery
ISBN (Electronic)081868707X
DOIs
StatePublished - 1998
Event1998 ACM/IEEE Conference on Supercomputing, SC 1998 - Orlando, United States
Duration: Nov 7 1998Nov 13 1998

Publication series

NameProceedings of the International Conference on Supercomputing
Volume1998-November

Conference

Conference1998 ACM/IEEE Conference on Supercomputing, SC 1998
Country/TerritoryUnited States
CityOrlando
Period11/7/9811/13/98

ASJC Scopus subject areas

  • General Computer Science

Keywords

  • Adaptive meshes
  • Computational science
  • Dynamic load balancing
  • Graph partitioning
  • Mesh partitioning
  • Parallel partitioning

Fingerprint

Dive into the research topics of 'S-HARP: A scalable parallel dynamic partitioner for adaptive mesh-based computations'. Together they form a unique fingerprint.

Cite this