RQL: global placement via relaxed quadratic spreading and linearization

ABSTRACT

This paper describes a simple and effective quadratic placement algorithm called RQL. We show that a good quadratic placement, followed by local wirelength-driven spreading can produce excellent results on large-scale industrial ASIC designs. As opposed to the current top performing academic placers [4, 7, 11], RQL does not embed a linearization technique within the solver. Instead, it only requires a simpler, pure quadratic objective function in the spirit of [8, 10, 23]. Experimental results show that RQL outperforms all available academic placers on the ISPD-2005 placement contest benchmarks. In particular, RQL obtains an average wire-length improvement of 2.8%, 3.2%, 5.4%, 8.5%, and 14.6% versus mPL6 [5], NTUPlace3 [7], Kraftwerk [20], APlace2.0 [11], and Capo10.2 [18], respectively. In addition, RQL is three, seven, and ten times faster than mpL6, Capo10.2, and APlace2.0, respectively. On the ISPD-2006 placement contest benchmarks, on average, RQL obtains the best scaled wirelength among all available academic placers.

REFERENCES

• 1: A. R. Agnihotri, S. Ono, C. Li, M. C. Yildiz, A. Khatkhate, C.-K. Koh, and P. H. Madden. Mixed block placement via fractional cut recursive bisection. TCAD, 24(5):748--761, May 2005.
• 2: C. J. Alpert, G.-J. Nam, and P. G. Villarrubia. Effective free space management for cut-based placement via analytical constraint generation. TCAD, 22(10):1343--1353, Oct. 2003.
• 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: Tony Chan , Jason Cong , Kenton Sze, Multilevel generalized force-directed method for circuit placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055177]
• 5: Tony F. Chan , Jason Cong , Joseph R Shinnerl , Kenton Sze , Min Xie, mPL6: enhanced multilevel mixed-size placement, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123055]
• 6: Tung-Chieh Chen , Tien-Chang Hsu , Zhe-Wei Jiang , Yao-Wen Chang, NTUplace: a ratio partitioning based placement algorithm for large-scale mixed-size designs, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055188]
• 7: Tung-Chieh Chen , Zhe-Wei Jiang , Tien-Chang Hsu , Hsin-Chen Chen , Yao-Wen Chang, A high-quality mixed-size analytical placer considering preplaced blocks and density constraints, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233538]
• 8: 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]
• 9: K. M. Hall. An r-dimensional quadratic placement algorithm. Management Science, 17:219--229, 1970.
• 10: B. Hu and M. Marek-Sadowska. Multilevel fixed-point-addition-based VLSI placement. TCAD, 24(8):1188--1203, Aug. 2005.
• 11: 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
• 12: J. Kleinhans, G. Sigl, F. Johannes, and K. Antreich. GORDIAN: VLSI placement by quadratic programming and slicing optimization. TCAD, 10(3):356--365, Mar. 1991.
• 13: Gi-Joon Nam, ISPD 2006 Placement Contest: Benchmark Suite and Results, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123042]
• 14: Gi-Joon Nam , Charles J. Alpert , Paul Villarrubia , Bruce Winter , Mehmet Yildiz, The ISPD2005 placement contest and benchmark suite, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055182]
• 15: G.-J. Nam, S. Reda, C. J. Alpert, P. G. Villarrubia, and A. B. Kahng. A fast hierarchical quadratic placement algorithm. TCAD, 25(4):678--691, Apr. 2006.
• 16: W. Naylor et al. Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer, Oct. 2001.
• 17: Haoxing Ren , David Z. Pan , Charles J. Alpert , Paul Villarrubia, Diffusion-based placement migration, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065712]
• 18: J. A. Roy, S. N. Adya, D. A. Papa, and I. L. Markov. Min-cut floorplacement. TCAD, 25(7):1313--1326, July 2006.
• 19: Carl Sechen , Alberto Sangiovanni-Vincentelli, TimberWolf3.2: a new standard cell placement and global routing package, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.432-439, July 1986, Las Vegas, Nevada, United States
• 20: Peter Spindler , Frank M. Johannes, Fast and robust quadratic placement combined with an exact linear net model, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233537]
• 21: W.-J. Sun and C. Sechen. Efficient and effective placement for very large circuits. TCAD, 14(5):349--359, 1995.
• 22: Taraneh Taghavi , Xiaojian Yang , Bo-Kyung choi, Dragon2005: large-scale mixed-size placement tool, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055191]
• 23: N. Viswanathan and C. C.-N. Chu. FastPlace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model. TCAD, 24(5):722--733, May 2005.
• 24: N. Viswanathan , Min Pan , C. Chu, FastPlace 3.0: A Fast Multilevel Quadratic Placement Algorithm with Placement Congestion Control, Proceedings of the 2007 conference on Asia South Pacific design automation, p.135-140, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.357975]
• 25: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design

Keywords:
analytical placement, force-vector modulation