Guiding global placement with wire density

ABSTRACT

This paper presents an efficient technique for the estimation of the routed wirelength during global placement using the wire density of the net. The proposed method identifies congested regions of the chip and incorporates the model of the routed wirelength into the objective function in order to effectively alleviate these regions from congestion. The method is integrated in the analytical placement framework and the two-level structure improves the scalability of the placer and speeds up the algorithm. The proposed analytical placer provides the best-so-far average routed wirelength in the IBM version2 benchmark suite.

REFERENCES

• 1: Chih-Liang Eric Cheng, RISA: accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.690-695, November 06-10, 1994, San Jose, California, United States
• 2: M. Wang, X. Yang, and M. Sarrafzadeh, "Congestion minimization during placement," IEEE Trans. Computer-Aided Design, vol. 19, pp. 1140--1148, Oct. 2000.
• 3: Jinan Lou , Shankar Krishnamoorthy , Henry S. Sheng, Estimating routing congestion using probabilistic analysis, Proceedings of the 2001 international symposium on Physical design, p.112-117, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369749]
• 4: Wenting Hou , Hong Yu , Xianlong Hong , Yici Cai , Weimin Wu , Jun Gu , William H. Kao, A new congestion-driven placement algorithm based on cell inflation, Proceedings of the 2001 conference on Asia South Pacific design automation, p.605-608, January 2001, Yokohama, Japan [doi>10.1145/370155.370560]
• 5: Ulrich Brenner , André Rohe, An effective congestion driven placement framework, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505391]
• 6: Zhuoyuan Li , Weimin Wu , Xianlong Hong, Congestion driven incremental placement algorithm for standard cell layout, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119934]
• 7: X. Yang, R. Kashner, and M. Sarrafzadeh, "Congestion estimation during top-down placement," IEEE Trans. Computer-Aided Design, vol. 21, pp. 72--80, Jan. 2002.
• 8: Bo Hu , Malgorzata Marek-Sadowska, Congestion minimization during placement without estimation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.739-745, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774681]
• 9: Maogang Wang , Majid Sarrafzadeh, Modeling and minimization of routing congestion, Proceedings of the 2000 conference on Asia South Pacific design automation, p.185-190, January 2000, Yokohama, Japan [doi>10.1145/368434.368601]
• 10: Peter Spindler , Frank M. Johannes, Fast and accurate routing demand estimation for efficient routability-driven placement, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 11: A. B. Kahng and Q. Wang, "Implementation and extensibility of an analytic placer," IEEE Trans. Computer-Aided Design, vol. 24, pp. 734--747, May 2005.
• 12: Chen Li , Cheng-Koh Koh, Recursive Function Smoothing of Half-Perimeter Wirelength for Analytical Placement, Proceedings of the 8th International Symposium on Quality Electronic Design, p.829-834, March 26-28, 2007 [doi>10.1109/ISQED.2007.133]
• 13: Chen Li , Min Xie , Cheng-Kok Koh , J. Cong , P. H. Madden, Routability-driven placement and white space allocation, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.394-401, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382607]
• 14: Tony F. Chan , Jason Cong , Michalis Romesis , Joseph R. Shinnerl , Kenton Sze , Min Xie, mPL6: a robust multilevel mixed-size placement engine, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055185]
• 15: J. A. Roy and I. L. Markov, "Seeing the forest and the trees: Steiner wirelength optimization in placement," IEEE Trans. Computer-Aided Design, vol. 26, pp. 632--644, Apr. 2007.
• 16: A. B. Kahng , S. Reda , Qinke Wang, Architecture and details of a high quality, large-scale analytical placer, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.891-898, November 06-10, 2005, San Jose, CA
• 17: W. Naylor, R. Donelly, and L. Sha, "Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer," U.S. Patent 6 301 693, Oct. 09, 2001.
• 18: S. Birbil, S. Fang, H. Frenk, and S. Zhang, "Recursive approximation of the high-dimensional max function," Department of Systems Engineering and Engineering Management SEEM, The Chinese University of Hong Kong, HK, Tech. Rep. SEEM 2002-12, Dec. 2002.
• 19: G. Karypis and V. Kumar, "Multilevel K-way hypergraph partitioning," IEEE Trans. VLSI Syst., vol. 11, pp. 285--300, Jan. 2000.
• 20: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: applications in VLSI domain, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.1, p.69-79, March 1999 [doi>10.1109/92.748202]
• 21: N. Selvakkumaran and G. Karypis, "Multi-objective hypergraph partitioning algorithms for cut and maximum subdomain degree minimization," IEEE Trans. Computer-Aided Design, vol. 25, pp. 504--517, Mar. 2006.
• 22: Ciyou Zhu , Richard H. Byrd , Peihuang Lu , Jorge Nocedal, Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization, ACM Transactions on Mathematical Software (TOMS), v.23 n.4, p.550-560, Dec. 1997 [doi>10.1145/279232.279236]