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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alpert, C.J.: The ISPD 1998 Circuit Benchmark Suite. In: Proc. International Symposium of Physical Design, pp. 80–85 (1998)
Alpert, C.J., Huang, J.H., Kahng, A.B.: Recent Directions in Netlist Partitioning. Integration, the VLSI Journal 19(1-2), 1–81 (1995)
Caldwell, A.E., Kahng, A.B., Markov, I.L.: Improved Algorithms for Hypergraph Bipartitioning. In: Proc. 2000 ACM/IEEE Conference on Asia South Pacific Design Automation, pp. 661–666 (2000)
Catalyurek, U.V., Aykanat, C.: Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication. IEEE Transactions on Parallel and Distributed Systems 10(7), 673–693 (1999)
Catalyurek. U.V., Aykanat. C.: PaToH: Partitioning Tool for Hypergraphs, Version 3.0 (2001)
Dutt, S., Deng, W.: A Probability-based Approach to VLSI Circuit Partitioning. In: Proc. 33rd Annual Design Automation Conference, pp. 100–105 (1996)
Dutt, S., Deng, W.: VLSI Circuit Partitioning by Cluster-Removal Using Iterative Improvement Techniques. In: Proc. 1996 IEEE/ACM International Conference on Computer-Aided Design, pp. 194–200 (1996)
Dutt, S., Theny, H.: Partitioning Around Roadblocks: Tackling Constraints with Intermediate Relaxations. In: Proc. 1997 IEEE/ACM International Conference on Computer-Aided Design, pp. 350–355 (1997)
Fiduccia, C.M., Mattheyses, R.M.: A Linear Time Heuristic For Improving Network Partitions. In: Proc. 19th IEEE Design Automation Conference, pp. 175–181 (1982)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., New York (1979)
Grama, A., Gupta, A., Karypis, G., Kumar, V.: Introduction to Parallel Computing, 2nd edn. Addison-Wesley, Reading (2003)
Karypis, G.: Multilevel Hypergraph Partitioning. Technical Report, 02-25, University of Minnesota (2002)
Karypis, G., Kumar, V.: hMeTiS: A Hypergraph Partitioning Package, Version 1.5.3. University of Minnesota (1998)
Karypis, G., Kumar, V.: Multilevel k-way Hypergraph Partitioning. Technical Report, 98-036, University of Minnesota (1998)
Karypis, G., Kumar, V.: A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering. Journal of Parallel and Distributed Computing 48, 71–95 (1998)
Karypis, G., Schloegel, K., Kumar, V.: ParMeTiS: Parallel Graph Partitioning and Sparse Matrix Ordering Library, Version 3.0. University of Minnesota (2002)
Knottenbelt, W.J.: Parallel Performance Analysis of Large Markov Models. PhD. Thesis, Imperial College, London, United Kingdom (2000)
Krishnamurthy, B.: An Improved min-cut Algorithm for Partitioning VLSI Networks. IEEE Transactions on Computers 33(C), 438–446 (1984)
Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J.: MPI – The Complete Reference, 2nd edn. MIT Press, Cambridge (1998)
Trifunovic, A., Knottenbelt, W.J.: A Parallel Algorithm for Multilevel k-way Hypergraph Partitioning. In: Proc. 3rd International Symposium on Parallel and Distributed Computing, University College Cork, Ireland (2004)
Trifunovic, A., Knottenbelt, W.J.: Towards a Parallel Disk-Based Algorithm for Multilevel k-way Hypergraph Partitioning. In: Proc. 5th Workshop on Parallel and Distributed Scientific and Engineering Computing, Santa Fe, NM, USA (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Trifunovic, A., Knottenbelt, W.J. (2004). Parkway 2.0: A Parallel Multilevel Hypergraph Partitioning Tool. In: Aykanat, C., Dayar, T., Körpeoğlu, İ. (eds) Computer and Information Sciences - ISCIS 2004. ISCIS 2004. Lecture Notes in Computer Science, vol 3280. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30182-0_79
Download citation
DOI: https://doi.org/10.1007/978-3-540-30182-0_79
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23526-2
Online ISBN: 978-3-540-30182-0
eBook Packages: Springer Book Archive