S-HARP: A parallel dynamic spectral partitioner (A short summary)

Andrew Sohn, Horst Simon

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

2 Scopus citations

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 rtm time. We present in this report a scalable parallel 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 partitions a graph from scratch, requiring no partition information from previous iterations. 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.2 seconds on a 64-processor Cray T3E. S-HARP is much more scalable than other dynamic partitioners, giving over 15-fold speedup on 64 processors while ParaMeTiS 1.0 gives a few-fold speedup. Experimental results demonstrate that S-HARP is three to 10 times faster than the dynamic partitioners ParaMeTiS and Jostle on six computational meshes of size over 100,000 vertices.

Original languageEnglish (US)
Title of host publicationSolving Irregularly Structured Problems in Parallel - 5th International Symposium, IRREGULAR 1998, Proceedings
PublisherSpringer Verlag
Pages376-385
Number of pages10
ISBN (Print)3540648097, 9783540648093
DOIs
StatePublished - 1998
Event5th International Symposium on Solving Irregularly Structured Problems in Parallel, IRREGULAR 1998 - Berkeley, CA, United States
Duration: Aug 9 1998Aug 11 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1457 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Symposium on Solving Irregularly Structured Problems in Parallel, IRREGULAR 1998
CountryUnited States
CityBerkeley, CA
Period8/9/988/11/98

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'S-HARP: A parallel dynamic spectral partitioner (A short summary)'. Together they form a unique fingerprint.

Cite this