Performance driven multi-level and multiway partitioning with retiming

ABSTRACT

In this paper, we study the performance driven multiw ay circuit partitioning problem with consideration of the significant difference of local and global interconnect delay induced by the partitioning. We develop an efficient algorithm HPM (Hierarc hicalP erformance driven Multi-level partitioning) that simultaneously considers cutsize and delay minimization with retiming. HPM builds a multi-lev el cluster hierarc hy and performs various refinement while gradually decomposing the clusters for simultaneous cutsize and delay minimization. We provide comprehensive experimental justification for each step involv ed in HPM and in-depth analysis of cutsize and delay tradeoff existing in the performance driven partitioning problem. HPM obtains (i) 7% to 23% better delay compared to the state-of-the-art cutsize driven hMetis [11] at the expense of 19% increase in cutsize, and (ii) 81% better cutsize compared to the state-of-the-art delay driven PRIME [2] at the expense of 6% increase in delay.

REFERENCES

• 1: J. Cong. An interconnect-centric design flow for nanometer technologies. In Proc. of Int'l Symp. on VLSI Technology, Systems, and Applications, pages 54- 57, 1999.
• 2: Jason Cong , Honching Li , Chang Wu, Simultaneous circuit partitioning/clustering with retiming for performance optimization, Proceedings of the 36th ACM/IEEE conference on Design automation, p.460-465, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309980]
• 3: 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
• 4: 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]
• 5: Jason Cong , Sung Kyu Lim, Edge separability based circuit clustering with application to circuit partitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.429-434, January 2000, Yokohama, Japan [doi>10.1145/368434.368728]
• 6: Jason Cong , Sung Kyu Lim , Chang Wu, Performance driven multi-level and multiway partitioning with retiming, Proceedings of the 37th conference on Design automation, p.274-279, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337418]
• 7: J. Cong, S. K. Lira, and C. Wu. Performance-driven multi-level and multi-way partitioning. Technical Report 990046, UCLA CS Dept, Oct. 1999.
• 8: Jason Cong , David Zhigang Pan, Interconnect estimation and planning for deep submicron designs, Proceedings of the 36th ACM/IEEE conference on Design automation, p.507-510, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309988]
• 9: 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
• 10: J. Hwang and A. E1 Gamal. Min-cut replication in partitioned networks. IEEE Trans. on Computer-Aided Design, pages 96-106, 1995.
• 11: 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]
• 12: E. L. Lawler, K. N. Levitt, and J. Turner. Module clustering to minimize delay in digital networks. IEEE Trans. on Computer-Aided Design, pages 47-57, 1969.
• 13: C. E. Leiserson and J. B. Saxe. Retiming synchronous circuitry. Algorithmica, pages 5-35, 1991.
• 14: L. Liu, M. Kuo, C. K. Cheng, and T. C. Hu. Performance driven partitioning using a replication graph approach. In Proc. A CM Design Automation Conf., pages 206-210, 1995.
• 15: Lung-Tien Liu , Minshine Shih , Nan-Chi Chou , Chung-Kuan Cheng , Walter Ku, Performance-driven partitioning using retiming and replication, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.296-299, November 07-11, 1993, Santa Clara, California, United States
• 16: R. Murgai, R. K. Brayton, and A. Sangiovanni Vincentelli. On clustering for minimum delay/area. In Proc. Int. Conf. on Computer-Aided Design, pages 6-9, 1991.
• 17: P. Pan, A. K. Karandikar, and C. L. Liu. Optimal clock period clustering for sequential circuits with retiming. IEEE Trans. on Computer-Aided Design, pages 489- 498, 1998.
• 18: Rajmohan Rajaraman , D. F. Wong, Optimal clustering for delay minimization, Proceedings of the 30th international conference on Design automation, p.309-314, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164907]
• 19: M. Shih , E. S. Kuh , R.-S. Tsay, Performance-driven system partitioning on multi-chip modules, Proceedings of the 29th ACM/IEEE conference on Design automation, p.53-56, June 08-12, 1992, Anaheim, California, United States
• 20: Honghua Yang , D. F. Wong, Circuit clustering for delay minimization under area and pin constraints, Proceedings of the 1995 European conference on Design and Test, p.65, March 06-09, 1995

INDEX TERMS

Primary Classification:
  J. Computer Applications

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

  C. Computer Systems Organization

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

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