Evaluation of placer suboptimality via zero-change netlist transformations

ABSTRACT

In this paper we introduce the concept of zero-change transformations to quantify the suboptimality of existing placers. Given a netlist and its placement from a placer, we formally define a class of netlist transformations that produce different netlists from the given netlist but have the same Half-Perimeter Wire Length (HPWL). Furthermore, the optimal HPWL value of the new netlists is no less than that of the original netlist. By applying our transformations and re-executing the placer, we can interpret any deviation in HPWL as a lower bound to the deviation from the optimal HPWL value. Such deviation is a measure of suboptimality. Using these transformations, the suboptimality of several existing academic and industrial placers is studied on the IBM benchmarks. Our results show that current placers are sub-optimal for zero-change transformations with deviations in HPWL by up to 32% on the IBM (version 1) benchmarks. The specific nature of our transformations also pinpoints possible directions for improvement in existing placers.

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: Saurabh N. Adya , Mehmet C. Yildiz , Igor L. Markov , Paul G. Villarrubia , Phiroze N. Parakh , Patrick H. Madden, Benchmarking for large-scale placement and beyond, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640022]
• 3: J. Beardwood, J. Halton, and J. Hammersley, "The Shortest Path through Many Points," Proc. Cambridge Philos. Soc. 55, pp. 299--327, 1959.
• 4: 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]
• 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: C.-C. Chang, J. Cong, D. Pan, and X. Yuan, "Multilevel Global Placement with Congestion Control," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22(4), pp. 395--409, 2003.
• 7: 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
• 8: Jason Cong , Michail Romesis , Min Xie, Optimality, scalability and stability study of partitioning and placement algorithms, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640021]
• 9: 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]
• 10: 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]
• 11: M. Hanan and J. M. Kurtzberg, "Placement Techniques," in In Design Automation of Digital Systems, M. A. Breuer Ed., 1972, pp. 213--282.
• 12: Andrew B. Kahng , Stefanus Mantik, On mismatches between incremental optimizers and instance perturbations in physical design tools, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 13: Measurement of Inherent Noise in EDA Tools, Proceedings of the 3rd International Symposium on Quality Electronic Design, p.206, March 18-21, 2002
• 14: Andrew B. Kahng , Sherief Reda, Placement feedback: a concept and method for better min-cut placements, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996670]
• 15: J. M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 10(3), pp. 356--365, 1991.
• 16: Qinghua Liu , Malgorzata Marek-Sadowska, A study of netlist structure and placement efficiency, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981109]
• 17: M. Queyranne, "Performance Ratio of Polynomial Heuristics for Triangle Inequality Quadratic Assignment Problem," Operations Research Letters, vol. 4, p. 1986, 231--342.
• 18: 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]
• 19: W.-J. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14(5), pp. 349--359, 1995.
• 20: 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
• 21: Mehmet Can Yildiz , Patrick H. Madden, Global objectives for standard cell placement, Proceedings of the 11th Great Lakes symposium on VLSI, p.68-72, March 2001, West Lafayette, Indiana, United States [doi>10.1145/368122.368801]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
benchmarking, placer suboptimality, wirelength