Multilevel hypergraph partitioning: application in VLSI domain

ABSTRACT

In this paper, we present a new hypergraph partitioning algorithmthat is based on the multilevel paradigm. In the multilevel paradigm,a sequence of successively coarser hypergraphs is constructed. Abisection of the smallest hypergraph is computed and it is used toobtain a bisection of the original hypergraph by successively projectingand refining the bisection to the next level finer hypergraph.We evaluate the performance both in terms of the size of the hyper-edgecut on the bisection as well as run time on a number of VLSIcircuits. Our experiments show that our multilevel hypergraph partitioningalgorithm produces high quality partitioning in relativelysmall amount of time. The quality of the partitionings produced byour scheme are on the average 4% to 23% better than those producedby other state-of-the-art schemes. Furthermore, our partitioning algorithmissignificantly faster, often requiring 4 to 15 times less timethan that required by the other schemes. Our multilevel hypergraphpartitioning algorithm scales very well for large hypergraphs. Hypergraphswith over 100,000 vertices can be bisected in a few minuteson today's workstations. Also, on the large hypergraphs, ourscheme outperforms other schemes (in hyperedge cut) quite consistentlywith larger margins (9% to 30%).

REFERENCES

• 1: C. Alpert, L. Hagen, and A. Kahng. A hybrid multilevel/genetic approach for circuit partitioning. Technical Report, CS Dept., UCLA, Los Angeles, CA, 1996.
• 2: Charles J. Alpert , Andrew B. Kahng, Recent directions in netlist partitioning: a survey, Integration, the VLSI Journal, v.19 n.1-2, p.1-81, Aug. 1995 [doi>10.1016/0167-9260(95)00008-4]
• 3: T. Bui and C. Jones. A heuristic for reducing fill in sparse matrix factorization. In 6th SlAM Conf. Parallel Processing for Scientific Computing, pages 445-452, 1993.
• 4: Jason Cong , M'Lissa Smith, A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design, Proceedings of the 30th international conference on Design automation, p.755-760, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165119]
• 5: Shantanu Dutt , Wenyong Deng, A probability-based approach to VLSI circuit partitioning, Proceedings of the 33rd annual conference on Design automation, p.100-105, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240538]
• 6: S. Dutt and W. Deng. VLSI circuit partitioning by cluster-removal using iterative improvement techniques. In Proc. Physical Design Workshop, 1996.
• 7: T. Bui , C. Heigham , C. Jones , T. Leighton, Improving the performance of the Kernighan-Lin and simulated annealing graph bisection algorithms, Proceedings of the 26th ACM/IEEE conference on Design automation, p.775-778, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74527]
• 8: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 9: Charles J. Alpert , Andrew B. Kahng, A general framework for vertex orderings with applications to circuit clustering, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.4 n.2, p.240-246, June 1996 [doi>10.1109/92.502195]
• 10: Lars Hagen , Andrew B. Kahng, A new approach to effective circuit clustering, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.422-427, November 1992, Santa Clara, California, United States
• 11: S. Hauck , G. Borriello, An evaluation of bipartitioning techniques, Proceedings of the 16th Conference on Advanced Research in VLSI (ARVLSI'95), p.383, March 27-29, 1995
• 12: Bruce Hendrickson and Robert Leland. A multilevel algorithm for partitioning graphs. Technical Report SAND93-1301, Sandia National Laboratories, 1993.
• 13: Edmund Ihler , Dorothea Wagner , Frank Wagner, Modeling hypergraphs by graphs with the same mincut properties, Information Processing Letters, v.45 n.4, p.171-175, March 22, 1993 [doi>10.1016/0020-0190(93)90115-P]
• 14: G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Hypergraph partitioning: Applications in VLSI domain. Technical Report TR-96-060, CS Dept., University of Minnesota, 1996.
• 15: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 16: G. Karypis and V. Kumar. ME-IS: Unstructured graph partitioning and sparse matrix ordering system. Technical report, CS Dept., University of Minnesota, 1995.
• 17: B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Tech. Jour., 1970.
• 18: B. Krishnamurthy. An improved min-cut algorithm for partitioning VLSI networks. IEEE Trans. on Comp., C-33, May 1984.
• 19: Bernhard M. Riess , Konrad Doll , Frank M. Johannes, Partitioning very large circuits using analytical placement techniques, Proceedings of the 31st annual conference on Design automation, p.646-651, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196602]
• 20: Youssef G. Saab, A Fast and Robust Network Bisection Algorithm, IEEE Transactions on Computers, v.44 n.7, p.903-913, July 1995 [doi>10.1109/12.392848]
• 21: D. G. Schweikert , B. W. Kernighan, A proper model for the partitioning of electrical circuits, Proceedings of the 9th workshop on Design automation, p.57-62, June 26-28, 1972 [doi>10.1145/800153.804930]
• 22: H. Shin and C. Kim. A simple yet effective technique for partitioning. IEEE Transactions on VLSI Systems, 1 (3), 1993.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  C. Computer Systems Organization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory