VLSI circuit partitioning by cluster-removal using iterative improvement techniques

ABSTRACT

Move-based iterative improvement partitioning methods such as the Fiduccia-Mattheyses (FM) algorithm and Krishnamurthy's Look-Ahead (LA) algorithm are widely used in VLSI CAD applications largely due to their time efficiency and ease of implementation. This class of algorithms is of the "local improvement" type. They generate relatively high quality results for small and medium size circuits. However, as VLSI circuits become larger, these algorithms are not so effective on them as direct partitioning tools. We propose new iterative-improvement methods that select cells to move with a view to moving clusters that straddle the two subsets of a partition into one of the subsets. The new algorithms significantly improve partition quality while preserving the advantage of time efficiency. Experimental results on 25 medium to large size ACM/SIGDA benchmark circuits show up to 70% improvement over FM in cutsize, with an average of per-circuit percent improvements of about 25%, and a total cut improvement of about 35%. They also outperform the recent placement-based partitioning tool Paraboli and the spectral partitioner MELO by about 17% and 23%, respectively, with less CPU time. This demonstrates the potential of iterative improvement algorithms in dealing with the increasing complexity of modern VLSI circuitry.

REFERENCES

• 1: B. W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs", Bell System Tech. Journal, vol. 49, Feb. 1970, pp. 291-307.
• 2: 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]
• 3: 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
• 4: B. Krishnamurthy, "An improved min-cut algorithm for partitioning VLSI networks", IEEE Trans. on Comput., vol. C-33, May 1984, pp. 438-446.
• 5: M. Marek-Sadowska and S.E Lin, "Timing driven placement", Proc. IEEE/ACM International Conference on CAD, 1989, pp. 94-97.
• 6: Y.C. Wei and C.K. Cheng, "Towards efficient hierarchical designs by ratio cut partitioning", Proc. Int'l. Conf. Computer-Aided Design, 1989, pp. 298-301.
• 7: M.A.B. Jackson, A. Srinivasan and E.S. Kuh, "A fast algorithm for performance driven placement", Proc. IEEE/ACM International Conference on CAD, 1990, pp. 328-331.
• 8: Y. C. Wei and C. K. Cheng, "An Improved Two-way Partitioning Algorithm with Stable Performance", IEEE Trans. on Computer-Aided Design, 1990, pp. 1502-1511.
• 9: L. Hagen and A. B. Kahng, "Fast Spectral Methods for Ratio Cut Partitioning and Clustering", Proc. IEEE Intl. Conf. Computer-Aided Design, 1991, pp. 10-13.
• 10: 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]
• 11: Shantanu Dutt, New faster Kernighan-Lin-type graph-partitioning algorithms, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.370-377, November 07-11, 1993, Santa Clara, California, United States
• 12: C. J. Alpert , A. B. Kahng, A general framework for vertex orderings, with applications to netlist clustering, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.63-67, November 06-10, 1994, San Jose, California, United States
• 13: 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]
• 14: Charles J. Alpert , So-Zen Yao, Spectral partitioning: the more eigenvectors, the better, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.195-200, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217529]
• 15: 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
• 16: 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]
• 17: S. Dutt and W. Deng, "VLSI Circuit Partitioning by Cluster-Removal Using Iterative Improvement Techniques", Technical Report, Department of Electrical Engr., University of Minnesota, Nov. 1995. This report is available at ftp site ftp-mount.ee.umn.edu in file pappdw96-ext.ps in directory/pub/faculty/dutt/vlsi-cad/papers.
• 18: 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]

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:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design, Experimentation, Theory

Keywords:
ACM/SIGDA benchmark circuits, CAD, Fiduccia-Mattheyses algorithm, VLSI, VLSI circuit partitioning, cluster-removal, iterative improvement techniques, look-ahead algorithm, partition quality, spectral partitioner MELO