A Priority-Based Weighted Inner Products Matching Coarsening Algorithm on Multilevel Hypergraph Partitioning

Abstract:

Multilevel hypergraph partitioning is an significant and extensively researched problem in combinatorial optimization. Nevertheless, as the primary component of multilevel hypergraph partitioning, coarsening phase has not yet attracted sufficient attention. Meanwhile, the performance of coarsening algorithm is not very satisfying. In this paper, we present a new coarsening algorithm based on multilevel framework to reduce the number of vertices more rapidly. The main contribution is introducing the matching mechanism of weighted inner product and establishing two priority rules of vertices. Finally, the effectiveness of our coarsening algorithm was indicated by experimental results compared with those produced by the combination of different sort algorithms and hMETIS in most of the ISPD98 benchmark suite.

• Periodical: Advanced Materials Research (Volume 717)
• Pages: 466-474
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.717.466
• Online since: July 2013
• Authors: Yao Yuan Zeng, Wen Tao Zhao, Zheng Hua Wang
• Keywords: Coarsening Algorithm, Multilevel Hypergraph Partitioning, Priority Rule of Vertices, Weighted Inner Product

References

[1] Bisseling, R., T. van Leeuwen and U.V. Catalyurek. Combinatorial Problems in High-Performance Computing: Partitioning. in Dagstuhl Seminar Proceedings. 2009. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany.

[2] Leinweber, L. and S. Bhunia. Fine-grained supply gating through hypergraph partitioning and Shannon decomposition for active power reduction. in Proceedings of the conference on Design, automation and test in Europe. 2008: ACM.

DOI: 10.1109/date.2008.4484709

[3] Dong, C., et al., Partition-Based Global Placement Considering Wire-Density Uniformity for CMP Variations. Tsinghua Science & Technology, 2011. 16(1): pp.41-50.

DOI: 10.1016/s1007-0214(11)70007-4

[4] Bichot, C.E. A metaheuristic based on fusion and fission for partitioning problems. in Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. 20th International. 2006: IEEE.

DOI: 10.1109/ipdps.2006.1639518

[5] Burdescu, D., et al., New algorithm for segmentation of images represented as hypergraph hexagonal-grid. Pattern Recognition and Image Analysis, 2011: pp.395-402.

DOI: 10.1007/978-3-642-21257-4_49

[6] Gary, M.R. and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness. 1979, WH Freeman and Company, New York.

[7] Arafeh, B., K. Day and A. Touzene, A multilevel partitioning approach for efficient tasks allocation in heterogeneous distributed systems. Journal of Systems Architecture, 2008. 54(5): pp.530-548.

DOI: 10.1016/j.sysarc.2007.10.001

[8] Leng, M. and S. Yu, An effective multi-level algorithm for bisecting graph. Advanced Data Mining and Applications, 2006: pp.493-500.

DOI: 10.1007/11811305_54

[9] Holtgrewe, M. and P. Sanders, A scalable coarsening phase for a multi-level graph partitioning algorithm. Master's thesis, University of Karlsruhe, 2009.

[10] Brillout, R., A Multi-Level Framework for Bisection Heuristics. 2009.

[11] Hendrickson, B. and R. Leland, A multilevel algorithm for partitioning graphs. 1993, Citeseer.

[12] Karypis, G. and V. Kumar, Multilevel k-way hypergraph partitioning. VLSI design, 2000. 11(3): pp.285-300.

DOI: 10.1155/2000/19436

[13] Vastenhouw, B. and R.H. Bisseling, A two-dimensional data distribution method for parallel sparse matrix-vector multiplication. SIAM review, 2005. 47(1): pp.67-95.

DOI: 10.1137/s0036144502409019

[14] Alpert, C.J. The ISPD98 circuit benchmark suite. in Proceedings of the 1998 international symposium on Physical design. 1998: ACM.

DOI: 10.1145/274535.274546

[15] Karypis, G. and V. Kumar, hMETIS 1.5: A hypergraph partitioning package. 1998, Technical report, Department of Computer Science, University of Minnesota, 1998. Available on the WWW at URL http://www. cs. umn. edu/metis.