A tale of two nets: studies of wirelength progression in physical design

ABSTRACT

At every stage in physical design, engineers are faced with many different objectives and tools to develop, optimize, and evaluate their design. Each choice of a tool or an objective to optimize can potentially lead to a completely different final physically designed circuit. Furthermore, some of the objectives optimized by the tools are not necessarily the best or right objectives, but rather compromised objectives; for example, placers optimize the half-perimeter wirelength rather than the routed wirelength. The contributions of this paper are twofold. First, we define and use a metric to measure the consistency of optimizing wirelength during the different stages of physical design. Our main technique is based on tracing the relative lengths of two nets - or more accurately pairs of nets - as they progress through the physical design flow. Second, we propose a simple method to quantify the similarity between the results of different tools. Our empirical results point out to the physical design stages where vulnerability can occur from optimizing compromised objectives.

REFERENCES

• 1: Saurabh N. Adya , Igor L. Markov , Paul G. Villarrubia, On Whitespace and Stability in Mixed-Size Placement and Physical Synthesis, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.311, November 09-13, 2003 [doi>10.1109/ICCAD.2003.107]
• 2: Ameya R. Agnihotri , Satoshi Ono , Patrick H. Madden, Recursive bisection placement: feng shui 5.0 implementation details, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055186]
• 3: Chuck J. Alpert , Gi-Joon Nam , Paul Villarribua , Mehmet C. YILDIZ, Placement stability metrics, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120926]
• 4: Andrew E. Caldwell , Andrew B. Kahng , Stefanus Mantik , Igor L. Markov , Alex Zelikovsky, On wirelength estimations for row-based placement, Proceedings of the 1998 international symposium on Physical design, p.4-11, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274536]
• 5: Chin-Chih Chang , Jason Cong , Min Xie, Optimality and scalability study of existing placement algorithms, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119914]
• 6: 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
• 7: C. Chu, FLUTE: fast lookup table based wirelength estimation technique, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.696-701, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382665]
• 8: Chris Chu , Yiu-Chung Wong, Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055145]
• 9: Jason Cong , Tim Kong , Joseph R. Shinnerl , Min Xie , Xin Yuan, Large-Scale Circuit Placement: Gap and Promise, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.883, November 09-13, 2003 [doi>10.1109/ICCAD.2003.89]
• 10: J. Cong and S. K. Lim, "Edge Separability-Based Circuit Clustering With Application to Multilevel Circuit Partitioning," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 23(3), pp. 346--357, 2004.
• 11: Jason Cong , Joseph R. Shinnerl , Min Xie , Tim Kong , Xin Yuan, Large-scale circuit placement, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.2, p.389-430, April 2005 [doi>10.1145/1059876.1059886]
• 12: Lars W. Hagen , Dennis J. H. Huang , Andrew B. Kahng, Quantified suboptimality of VLSI layout heuristics, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.216-221, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217532]
• 13: Bo Hu , Malgorzata Marek-Sadowska, Wire length prediction based clustering and its application in placement, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776035]
• 14: Andrew B. Kahng , Qinke Wang, Implementation and extensibility of an analytic placer, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981071]
• 15: Measurement of Inherent Noise in EDA Tools, Proceedings of the 3rd International Symposium on Quality Electronic Design, p.206, March 18-21, 2002
• 16: Andrew B. Kahng , Sherief Reda, Evaluation of placer suboptimality via zero-change netlist transformations, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055180]
• 17: A. B. Kahng, S. Reda, and Q. Wang, "Architecture and Details of a High Quality, Large-Scale Analytical Placer," in Proc. IEEE International Conference on Computer Aided Design, 2005, pp. 891--898.
• 18: A. B. Kahng and S.Reda, "Intrinsic Shortest Path Length: A New, Accurate A Priori Wirelength Estimator," in Proc. IEEE International Conference on Computer Aided Design, 2005, pp. 173--180.
• 19: Qinghua Liu , Malgorzata Marek-Sadowska, Pre-layout wire length and congestion estimation, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996726]
• 20: M. Queyranne, "Performance Ratio of Polynomial Heuristics for Triangle Inequality Quadratic Assignment Problem," Operations Research Letters, vol. 4, p. 1986, 231--342.
• 21: Jarrod A. Roy , David A. Papa , Saurabh N. Adya , Hayward H. Chan , Aaron N. Ng , James F. Lu , Igor L. Markov, Capo: robust and scalable open-source min-cut floorplacer, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055184]
• 22: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 23: Lou Scheffer , Eric Nequist, Why interconnect prediction doesn't work, Proceedings of the 2000 international workshop on System-level interconnect prediction, p.139-144, April 08-09, 2000, San Diego, California, United States [doi>10.1145/333032.333044]
• 24: T. Taghavi, X. Yang, B. K. Choi, M. Wang, and M. Sarrafzadeh, "DRAGON2005: Large-Scale Mixed-Size Placement Tool," in Proc. ACM/IEEE International Symposium on Physical Design, 2001, pp. 245--247.
• 25: Natarajan Viswanathan , Chris Chong-Nuen Chu, FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981072]
• 26: Qingzhou (Ben) Wang , Devang Jariwala , John Lillis, A study of tighter lower bounds in LP relaxation based placement, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA [doi>10.1145/1057661.1057780]
• 27: X. Yan, B. K. Choi, and M. Sarrafzadeh, "Routabtility Driven White Space Allocation for Fixed-Die Standard-Cell Placement," in Proc. ACM/IEEE International Symposium on Physical Design, 2002, pp. 42--47.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Measurement, Performance, Standardization

Keywords:
benchmarking, consistency, placer suboptimality, similarity, wirelength