Cluster-aware iterative improvement techniques for partitioning large VLSI circuits

ABSTRACT

Move-based iterative improvement partitioning (IIP) methods, such as the Fiduccia-Mattheyses (FM) algorithm [Fidducia and Mattheyses 1982] and Krishnamurthy's Look-Ahead (LA) algorithm [Krishnamurthy 1984], 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/greedy improvement" type, and they generate relatively high-quality results for small and medium-size circuits. However, as VLSI circuits become larger, these algorithms suffer a rapid deterioration in solution quality. We propose new IIP methods CLIP and CDIP 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 mincut, and average mincut improvements of about 35% over all circuits and 47% over large circuits. They also outperform state-of-the-art non-IIP techniques, the quadratic-programming-based method Paraboli [Reiss et al. 1994] and the spectral partitioner MELO [Alpert and Yao 1995], by about 17% and 23%, respectively, with less CPU time. This demonstrates the potential of sophisticated IIP algorithms in dealing with the increasing complexity of emerging VLSI circuits. We also compare CLIP and CDIP to hMetis [Karypis et al. 1997], one of the best of the recent state-of-the-art partitioners that are based on the multilevel paradigm (others include MLc [Alpert et al. 1997] and LSR/MFFS [Cong et al. 1997]). The results show that one scheme of hMetis is 8% worse than CLIP/CDIP and the other two schemes are only 2--4% better. However, CLIP/CDIP have advantages over hMetis and other multilevel partitioners that outweigh these minimal mincut improvements. The first is much faster times-to-solution (for example, one of our best schemes CLIP-LA2 is 6.4 and 11.75 times faster than the two best hMetis schemes) and much better scalability with circuit size (e.g., for the largest circuit with about 162K nodes, CLIP-LA2 is 10.4 and and 21.5 times faster and obtains better solution qualities than the two best hMetis schemes). Second, CLIP/CDIP are "flat" partitioners, while multilevel techniques perform a sequence of node clustering/coarsening before partitioning the circuit. In complex placement applications such as timing-driven placement in the presence of multiple constraints, such circuit coarsening can hide crucial information needed for good-quality solutions, thus making the partitioning process oblivious to them. This, however, is not a problem with flat partitioners like CLIP/CDIP that can take all important parameters into account while partitioning. All these advantages make CLIP/CDIP suitable for use in complex physical design problems for large, deep-submicron VLSI circuits.

REFERENCES

• 1: 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]
• 2: 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
• 3: ALPERT, C. J. AND KAHNG, A. B. 1996. A hybrid multilevel/genetic approach for circuit partitioning. In Physical Design Workshop (1996). 100-105.
• 4: 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]
• 5: 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
• 6: DUTT, S. 1997. A stochastic approach to timing-driven partitioning and placement with accurate net and gain modeling. In IEEE/ACMInternational Workshop on Time. Issues in Digital Systems (TAU '97, Dec. 1997). 246-256.
• 7: DUTT, S. AND DENG, W. 1995. VLSI circuit partitioning by cluster-removal using iterative improvement techniques. Technical report, Department of Electrical Engineering, University of Minnesota, Minneapolis, MN. This report is available online at www.eecs.uic.edu/~ dutt/publ.html.
• 8: 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]
• 9: 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
• 10: Shantanu Dutt , Halim Theny, Partitioning around roadblocks: tackling constraints with intermediate relaxations, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.350-355, November 09-13, 1997, San Jose, California, United States
• 11: 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
• 12: HAGEN, L. AND KAHNG, A. B. 1991. Fast spectral methods for ratio cut partitioning and clustering. In Proceedings of the IEEE International Conference on Computer-Aided Design (1991). 10-13.
• 13: HAUCK, S. AND BORRIELLO, G. 1997. An evaluation of bipartitioning techniques. IEEE Trans. Comput-Aided Des. Integr. Circ. Syst. 16, 8 (Aug.), 849-866.
• 14: 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]
• 15: KERNIGAN, B. W. AND LIN, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, Feb., 291-307.
• 16: KRISHNAMURTHY, B. 1984. An improved min-cut algorithm for partitioning VLSI networks. IEEE Trans. Comput. C-33, May, 438-446.
• 17: Roman Kužnar , Franc Brglez , Krzysztof Kozminski, Cost minimization of partitions into multiple devices, Proceedings of the 30th international conference on Design automation, p.315-320, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164910]
• 18: Jianmin Li , John Lillis , Chung-Kuan Cheng, Linear decomposition algorithm for VLSI design applications, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.223-228, November 05-09, 1995, San Jose, California, United States
• 19: MAREK-SADOWSKA, M. 1993. Issues in timing driven layout. In Algorithmic Aspects of VLSI Layout, M. Sarrafzadeh and D. T. Lee, Eds., World Scientific Publishing Co., Singapore, 1-24.
• 20: 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]
• 21: 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]
• 22: 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]
• 23: WEI, Y. C. AND CHENG, C. K. 1989. Towards efficient hierarchical designs by ratio cut partitioning. In Proceedings of the International Conference on Computer-Aided Design (1989). 298-301.
• 24: WEI, Y. C. AND CHENG, C. K. 1991. An improved two-way partitioning algorithm with stable performance. IEEE Trans. Comput.-Aided Des. 10, 12, 1502-1511.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
Clusters, VLSI circuit partitioning, iterative-improvement, mincut, physical design/layout