Wire length prediction based clustering and its application in placement

ABSTRACT

In this paper we introduce a metric to evaluate proximity of connected elements in a netlist. Compared to connectivity [8] and edge separability [4], our metric is capable of predicting short connections more accurately. We show that the proposed metric can also predict relative wire length in multi-pin nets. We develop a fine-granularity clustering algorithm based on the new metric and embed it into the Fast Placer Implementation (FPI) framework [10]. Experimental results show that the new clustering algorithm produces better global placement results than the net absorption [10] algorithm, connectivity [8], and edge separability [4] based algorithms. With the new clustering algorithm, FPI achieves up to 50% speedup compared to the latest version of Capo8.5 [19], without placement quality losses.

REFERENCES

• 1: Srinivas Bodapati , Farid N. Najm, Pre-layout estimation of individual wire lengths, Proceedings of the 2000 international workshop on System-level interconnect prediction, p.93-98, April 08-09, 2000, San Diego, California, United States [doi>10.1145/333032.333038]
• 2: A.E. Caldwell, A.B. Kahng, S. Mantik, I.L. Markov and A. Zelikovsky, "On wire length estimations for row-based placement", IEEE Trans. on Computer-Aided Design, pp. 1265--1278, Sep 1999.
• 3: Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
• 4: 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]
• 5: Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
• 6: J. Garbers, H. J. Promel, and A. Steger, "Finding clusters in VLSI circuits,", In Proc. Int. Conf. Computer-Aided Design, 1990, pp. 520--523.
• 7: T. Hamada, C.K. Cheng and P.M. Chau, "A wire length estimation technique utilizing neighborhood density equations", IEEE Trans. on Computer-Aided Design, vol. 15. pp. 912--922, August 1996.
• 8: S. Hauck and G. Borriello, "An evaluation of bipartitioning techniques", IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol 16, No. 8, 1997.
• 9: H.T. Heineken and W. Maly, "Standard Cell Interconnect Length Predication from Structural Circuit Attributes", Proc. Custom Integrated Circuits Conference, pp. 167--170, 1996.
• 10: Bo Hu , Malgorzata Marek-Sadowska, Fine granularity clustering for large scale placement problems, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640017]
• 11: D. J. -H. Huang , A. B. Kahng, When clusters meet partitions: new density-based methods for circuit decomposition, Proceedings of the 1995 European conference on Design and Test, p.60, March 06-09, 1995
• 12: M. Pedram and B.T. Preas, "Interconnection Length Estimation for Optimized Standard Cell Layouts", Proc. ICCAD, pp. 390--393. 1989.
• 13: Kalapi Roy , Carl Sechen, A timing driven N-way chip and multi-chip partitioner, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.240-247, November 07-11, 1993, Santa Clara, California, United States
• 14: Donald M. Schuler , Ernst G. Ulrich, Clustering and linear placement, Proceedings of the 9th workshop on Design automation, p.50-56, June 26-28, 1972 [doi>10.1145/800153.804929]
• 15: 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
• 16: Maogang Wang , Xiaojian Yang , Majid Sarrafzadeh, Dragon2000: standard-cell placement tool for large industry circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 17: Y.C. Wei and C.K. Cheng, "Ratio cut partitioning for hierarchical designs", IEEE Trans. on Computer-Aided Design, pp. 911-921, 1992.
• 18: IBM-place benchmarks: http://gigascale.org/bookshelf/.
• 19: Latest Capo (version 8.5): http://vlsicad.ucsd.edu/Resources/Software Links/PDtools/

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
clustering, placement, wire length prediction