A fast parallel graph partitioner for shared-memory inspector/executor strategies

Christopher D. Krieger, Michelle Mills Strout

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

1 Scopus citations


Graph partitioners play an important role in many parallel work distribution and locality optimization approaches. Surprisingly, however, to our knowledge there is no freely available parallel graph partitioner designed for execution on a shared memory multicore system. This paper presents a shared memory parallel graph partitioner, ParCubed, for use in the context of sparse tiling run-time data and computation reordering. Sparse tiling is a run-time scheduling technique that schedules groups of iterations across loops together when they access the same data and one or more of the loops contains indirect array accesses. For sparse tiling, which is implemented with an inspector/executor strategy, the inspector needs to find an initial seed partitioning of adequate quality very quickly. We compare our presented hierarchical clustering partitioner, ParCubed, with GPart and METIS in terms of partitioning speed, partitioning quality, and the effect the generated seed partitions have on executor speed. We find that the presented partitioner is 25 to 100 times faster than METIS on a 16 core machine. The total edge cut of the partitioning generated by ParCubed was found not to exceed 1.27x that of the partitioning found by METIS.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 25th International Workshop, LCPC 2012, Revised Selected Papers
Number of pages15
StatePublished - 2013
Externally publishedYes
Event25th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2012 - Tokyo, Japan
Duration: Sep 11 2012Sep 13 2012

Publication series

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


Conference25th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2012


  • Graph partitioning
  • Inspector/executor strategies
  • Irregular applications
  • Sparse tiling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A fast parallel graph partitioner for shared-memory inspector/executor strategies'. Together they form a unique fingerprint.

Cite this