Design and implementation of move-based heuristics for VLSI hypergraph partitioning

ABSTRACT

We summarize the techniques of implementing move-based hypergraph partitioning heuristics and evaluating their performance in the context of VLSI design applications. Our first contribution is a detailed software architecture, consisting of seven reusable components, that allows flexible, efficient and accurate assessment of the practical implications of new move-based algorithms and partitioning formulations. Our second contribution is an assessment of the modern context for hypergraph partitioning research for VLSI design applications. In particular, we discuss the current level of sophistication in implementation know-how and experimental evaluation, and we note how requirements for real-world partitioners - if used as motivation for research - should affect the evaluation of prospective contributions. Two "implicit decisions" in the implementation of the Fiduccia-Mattheyses heuristic are used to illustrate the difficulty of achieving meaningful experimental evaluation of new algorithmic ideas.

REFERENCES

• 1: {1} C. J. Alpert, "Partitioning Benchmarks for VLSI CAD Community", Web page, http://vlsicad.cs.ucla.edu/~cheese/benchmarks.html
• 2: Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274546]
• 3: {3} C. J. Alpert and L. W. Hagen and A. B. Kahng, "A Hybrid Multilevel/Genetic Approach for Circuit Partitioning", <i>Proc. IEEE Asia Pacific Conference on Circuits and Systems</i>, 1996, pp. 298-301.
• 4: Charles J. Alpert , Jen-Hsin Huang , Andrew B. Kahng, Multilevel circuit partitioning, Proceedings of the 34th annual conference on Design automation, p.530-533, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266275]
• 5: 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]
• 6: {6} R. S. Barr, B. L. Golden, J. P. Kelly, M. G. C. Resende and W. R. Stewart, "Designing and Reporting on Computational Experiments with Heuristic Methods", <i>technical report</i> (extended version of <i>J. Heuristics</i> paper), June 27, 1995.
• 7: Franc Brglez, A D&T Special Report on ACM/SIGDA Design Automation Benchmarks: Catalyst or Anathema?, IEEE Design & Test, v.10 n.3, p.87-91, July 1993
• 8: {8} F. Brglez, "Design of Experiments to Evaluate CAD Algorithms: Which Improvements Are Due to Improved Heuristic and Which are Merely Due to Chance?", <i>technical report</i> CBL-04-Brglez, NCSU Collaborative Benchmarking Laboratory, April 1998.
• 9: Thang Nguyen Bui , F. Thomson Leighton , Soma Chaudhuri , Michael Sipser, Graph bisection algorithms with good average case behavior, Combinatorica, v.7 n.2, p.171-191, June 1, 1987 [doi>10.1007/BF02579448]
• 10: {10} A. E. Caldwell, A. B. Kahng and I. L. Markov, <i>manuscript</i>, 1998.
• 11: {11} P. K. Chan and M. D. F. Schlag and J. Y. Zien, "Spectral K-Way Ratio-Cut Partitioning and Clustering", <i>IEEE Transactions on Computer-Aided Design</i>, vol. 13 (8), pp. 1088-1096.
• 12: Jason Cong , Honching Peter Li , Sung Kyu Lim , Toshiyuki Shibuya , Dongmin Xu, Large scale circuit partitioning with loose/stable net removal and signal flow based clustering, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.441-446, November 09-13, 1997, San Jose, California, United States
• 13: Jason Cong , Sung Kyu Lim, Multiway partitioning with pairwise movement, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.512-516, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289079]
• 14: Joel Darnauer , Wayne Wei-Ming Dai, A method for generating random circuits and its application to routability measurement, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.66-72, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228380]
• 15: {15} A. Dasdan and C. Aykanat, "Two Novel Multiway Circuit Partitioning Algorithms Using Relaxed Locking", <i>IEEE Transactions on Computer-Aided Design</i> 16(2) (1997), pp. 169-178.
• 16: {16} W. Deng, <i>personal communication</i>, July 1998.
• 17: {17} A. E. Dunlop and B. W. Kernighan, "A Procedure for Placement of Standard Cell VLSI Circuits", <i>IEEE Transactions on Computer-Aided Design</i> 4(1) (1985), pp. 92-98
• 18: Shantanu Dutt , Wenyong Deng, VLSI circuit partitioning by cluster-removal using iterative improvement techniques, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.194-200, November 10-14, 1996, San Jose, California, United States
• 19: Shantanu Dutt , Halim Theny, Partitioning using second-order information and stochastic-gain functions, Proceedings of the 1998 international symposium on Physical design, p.112-117, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274551]
• 20: 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
• 21: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 22: {22} I. P. Gent, S. A. Grant, E. McIntyre, P. Prosser, P. Shaw, B. M. Smith and T. Walsh, "How Not To Do It", <i>research report</i> 97-27, Univ. of Leeds School of Computer Studies, May 1997.
• 23: {23} M. Chose, M. Zubair and C. E. Grosch, "Parallel Partitioning of Sparse Matrices", <i>Computer Systems Science & Engineering</i> (1995) 1, pp. 33-40.
• 24: {24} D. Ghosh, "Synthesis of Equivalence Class Circuit Mutants and Applications to Benchmarking", <i>summary of presentation at DAC-98 Ph.D. Forum</i>, June 1998.
• 25: {25} M. K. Goldberg and M. Burstein, "Heuristic Improvement Technique for Bisection of VLSI Networks", <i>IEEE Transactions on Computer-Aided Design</i>, 1983, pp. 122-125.
• 26: {26} S. Hauck and G. Borriello, "An Evaluation of Bipartitioning Techniques", <i>IEEE Transactions on Computer-Aided Design</i> 16(8) (1997), pp. 849-866.
• 27: Lars W. Hagen , Dennis J.-H. Huang , Andrew B. Kahng, On implementation choices for iterative improvement partitioning algorithms, Proceedings of the conference on European design automation, p.144-149, September 18-22, 1995, Brighton, England
• 28: Bruce Hendrickson , Robert Leland, A multilevel algorithm for partitioning graphs, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.28-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224228]
• 29: {29} B. Hendrickson and T. G. Kolda, "Partitioning Rectangular and Structurally Nonsymmetric Sparse Matrices for Parallel Processing", <i>manuscript</i>, 1998 (extended version of PARA98 workshop proceedings paper).
• 30: Dennis J.-H. Huang , Andrew B. Kahng, Partitioning-based standard-cell global placement with an exact objective, Proceedings of the 1997 international symposium on Physical design, p.18-25, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267674]
• 31: Michael Hutton , J. P. Grossman , Jonathan Rose , Derek Corneil, Characterization and parameterized random generation of digital circuits, Proceedings of the 33rd annual conference on Design automation, p.94-99, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240537]
• 32: Andrew B. Kahng, Futures for partitioning in physical design (tutorial), Proceedings of the 1998 international symposium on Physical design, p.190-193, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274563]
• 33: {33} G. Karypis and V. Kumar, "Multilevel k-way Partitioning Scheme For Irregular Graphs", Technical Report 95-064, University of Minnesota, Computer Science Department.
• 34: {34} G. Karypis and V. Kumar, "Multilevel Algorithms for Multi-Constraint Graph Partitioning", Technical Report 98-019, University of Minnesota, Department of Computer Science.
• 35: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 36: {36} G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel Hypergraph Partitioning: Applications in VLSI Domain", <i>technical report</i>, University of Minnesota Computer Science Department, March 27, 1998.
• 37: {37} B. W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs", <i>Bell System Tech. Journal</i> 49 (1970), pp. 291-307.
• 38: {38} C. Kring and A. R. Newton, "A Cell-Replicating Approach to Mincut-Based Circuit Partitioning", <i>Proc. IEEE/ACM International Conference on Computer-Aided Design</i>, 1991, pp. 2-5.
• 39: {39} B. Krishnamurthy, "An Improved Min-cut Algorithm for Partitioning VLSI Networks", <i>IEEE Transactions on Computers</i>, vol. C-33, May 1984, pp. 438-446.
• 40: {40} B. Landman and R. Russo, "On a Pin Versus Block Relationship for Partitioning of Logic Graphs", <i>IEEE Transactions on Computers</i> C-20(12) (1971), pp. 1469-1479.
• 41: Lung-Tien Liu , Ming-Ter Kuo , Shih-Chen Huang , Chung-Kuan Cheng, A gradient method on the initial partition of Fiduccia-Mattheyses algorithm, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.229-234, November 05-09, 1995, San Jose, California, United States
• 42: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 43: Laura A. Sanchis, Multiple-Way Network Partitioning with Different Cost Functions, IEEE Transactions on Computers, v.42 n.12, p.1500-1504, December 1993 [doi>10.1109/12.260640]
• 44: {44} G. R. Schreiber and O. C. Martin, "Procedure for Ranking Heuristics Applied to Graph Partitioning", <i>Proc. 2nd International Conference on Metaheuristics</i>, July 1997, pp. 1-19.
• 45: G. R. Schreiber , O. C. Martin, Cut Size Statistics of Graph Bisection Heuristics, SIAM Journal on Optimization, v.10 n.1, p.231-251, 1999 [doi>10.1137/S1052623497321523]
• 46: {46} P. R. Suaris and G. Kedem, "Quadrisection: A New Approach to Standard Cell Layout", <i>Proc. IEEE/ACM International Conference on Computer-Aided Design</i>, 1987, pp. 474- 477.
• 47: Wern-Jieh Sun , Carl Sechen, Efficient and effective placement for very large circuits, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.170-177, November 07-11, 1993, Santa Clara, California, United States
• 48: {48} Y. C. Wei and C. K. Cheng, "Towards Efficient Design by Ratio-cut Partitioning", <i>Proc. IEEE International Conference on Computer-Aided Design</i>, 1989, pp. 298-301.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Hypergraphs

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
VLSI CAD, algorithms, balanced min-cut hypergraph partitioning, experimentation, measurement, performance