Computing Publications

Publications Home » Parkway 2.0: A Parallel Multileve...

Parkway 2.0: A Parallel Multilevel Hypergraph Partitioning Tool

Aleksandar Trifunovic, William J. Knottenbelt

Conference or Workshop Paper
19th International Symposium on Computer and Information Sciences (ISCIS 2004)
October, 2004
Lecture Notes in Computer Science
Volume 3280
pp.789–800
Springer-Verlag
Abstract

We recently proposed a coarse-grained parallel multilevel algorithm for the k-way hypergraph partitioning problem. This paper presents a formal analysis of the algorithm's scalability in terms of its isoefficiency function, describes its implementation in the Parkway 2.0 tool and provides a run-time and partition quality comparison with state-of-the-art serial hypergraph partitioners.

The isoefficiency function (and thus scalability behaviour) of our algorithm is shown to be of a similar order as that for Kumar and Karypis' parallel multilevel graph partitioning algorithm. This good theoretical scalability is backed up by empirical results on hypergraphs taken from the VLSI and performance modelling application domains. Further, partition quality in terms of the k-1 metric is shown to be competitive with the best serial hypergraph partitioners and degrades only minimally as more processors are used.

Keywords
AESOP
PDF of full publication (210 kilobytes)
(need help viewing PDF files?)
BibTEX file for the publication
N.B.
Conditions for downloading publications from this site.
 

pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.