Implementation and extensibility of an analytic placer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Implementation and extensibility of an analytic placer

Full text

Pdf (830 KB)

Source

International Symposium on Physical Design archive
Proceedings of the 2004 international symposium on Physical design table of contents

Phoenix, Arizona, USA

SESSION: Placement techniques table of contents

Pages: 18 - 25

Year of Publication: 2004

ISBN:1-58113-817-2

Authors

Andrew B. Kahng	UCSD, La Jolla, CA
Qinke Wang	UCSD, La Jolla, CA

Sponsors

ACM: Association for Computing Machinery
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 40, Citation Count: 27

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/981066.981071 What is a DOI?

ABSTRACT

Automated cell placement is a critical problem in VLSI physical design. New analytical placement methods that simultaneously spread cells and optimize wirelength have recently received much attention from both academia and industry. A novel and simple objective function for spreading cells over the placement area is described in the patent of Naylor et al. [26]. When combined with a wirelength objective function, this allows efficient simultaneous cell spreading and wirelength optimization using nonlinear optimization techniques. In this work, we implement an analytic placer (APlace) according to these ideas (which have other precedents in the open literature), and conduct in-depth analysis of characteristics and extensibility of the placer. Our contributions are as follows. (1) We perform analysis and empirical studies of relevant characteristics of the objective functions described in [26]. (2) We extend the objective functions with congestion information. (3) We implement a top-down hierarchical (multilevel) placer (APlace) based on the objective functions. The half-perimeter wirelength of APlace outperforms that of Cadence QPlace (SE5.4), UCLA Dragon (v3.01) and Capo (v8.7) respectively by 6.8%, 2.6% and 6.5% on average. When these placements are detail-routed using Cadence WRoute (SE5.4), the average improvement in final wirelength is 8.2%, 4.2% and 10.4% over QPlace, Dragon and Capo, respectively. (4) We extend the placer to perform I/O-core co-placement. I/Os can be evenly distributed without damaging the wirelength figure of merit. (5) We also extend the placer to handle constraints for mixed-signal designs (symmetry, alignment, etc.) and evaluate the impact of such constraints on runtime and wirelength.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	C. J. Alpert, T. Chan, A. B. Kahng, I. Markov and P. Mulet, "Faster Minimization of Linear Wirelength for Global Placement", IEEE Trans. Computer Aided Design 17(1) (1998), pp. 3--13.
	2	Charles J. Alpert , Jen-Hsin Huang , Andrew B. Kahng, Multilevel circuit partitioning, Proceedings of the 34th annual conference on Design automation, p.530-533, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266275]
	3	R. Baldick, A. B. Kahng, A. Kennings and I. L. Markov, "Function Smoothing with Applications to VLSI Layout", Proc. IEEE/ACM Asia and South Pacific Design Automation Conf., Jan. 1999, pp. 225--228.
	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	Andrew E. Caldwell , Andrew B. Kahng , Andrew A. Kennings , Igor L. Markov, Hypergraph partitioning for VLSI CAD: methodology for heuristic development, experimentation and reporting, Proceedings of the 36th ACM/IEEE conference on Design automation, p.349-354, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309955]
	6	A. Caldwell , A. B. Kahng , S. Mantik , I. L. Markov, Implications of Area-Array I/O for Row-Based Placement Methodology, Proceedings of the IEEE Symposium on IC/Package Design Integration, p.93, February 02-03, 1998
	7	UCLA/UMICH Physical Design Tools. http://vlsicad.eecs.umich.edu/BK/PDtools/.
	8	Web site of Dragon. http://er.cs.ucla.edu/Dragon/.
	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	H. Etawil, S. Areibi and A. Vannelli, "ARP: A Convex Optimization Based Method for Global Placement", submitted to IEEE Trans. Computer Aided Design, http://wolfman.eos.uoguelph.ca/~sareibi1/PUBLICATIONS_dr/all-pub-list.html.
	11	Hussein Etawil , Shawki Areibi , Anthony Vannelli, Attractor-repeller approach for global placement, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.20-24, November 07-11, 1999, San Jose, California, United States
	12	T. Gao, C. L. Liu and K. C. Chen, "A Performance Driven Hierarchical Partitioning Placement Algorithm", Proc. European Design Automation Conf., Sep. 1993, pp. 33--38.
	13	D. Hill, "Method and System for High Speed Detailed Placement of Cells within an Integrated Circuit Design", US Patent 6370673, April 2002.
	14	Dennis J.-H. Huang , Andrew B. Kahng, Partitioning-based standard-cell global placement with an exact objective, Proceedings of the 1997 international symposium on Physical design, p.18-25, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267674]
	15	Bo Hu , Malgorzata Marek-Sadowska, FAR: fixed-points addition & relaxation based placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505426]
	16	Web site of IBM-PLACE 2.0 benchmark suites. http://er.cs.ucla.edu/benchmarks/ibm-place2/
	17	Andrew B. Kahng , Xu Xu, Accurate pseudo-constructive wirelength and congestion estimation, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA [doi>10.1145/639929.639942]
	18	George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
	19	A. A. Kennings and I. L. Markov, "Smoothening Max-terms and Analytical Minimization of Half-Perimeter Wirelength", VLSI Design 14(3) (2002), pp. 229--237.
	20	Andrew A. Kennings , Igor L. Markov, Analytical minimization of half-perimeter wirelength, Proceedings of the 2000 conference on Asia South Pacific design automation, p.179-184, January 2000, Yokohama, Japan [doi>10.1145/368434.368600]
	21	J. Kleinhans, G. Sigl, F. Johannes and K. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization", IEEE Trans. Computer-Aided Design 10(3) (1991), pp. 356--365.
	22	C.-K. Koh and C. Li, private communication, Oct. 2003.
	23	Jianmin Li , John Lillis , Lung-Tien Liu , Chung-Kuan Cheng, New spectral linear placement and clustering approach, Proceedings of the 33rd annual conference on Design automation, p.88-93, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240536]
	24	Jianmin Li , John Lillis , Chung-Kuan Cheng, Linear decomposition algorithm for VLSI design applications, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.223-228, November 05-09, 1995, San Jose, California, United States
	25	K. G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Internet Edition, Chapter 10, pp. 389-460. http://ioe.engin.umich.edu/books/murty/linear_complementarity_webbook/.
	26	W. Naylor et al., "Non-Linear Optimization System and Method for Wire Length and Delay Optimization for an Automatic Electric Circuit Placer", US Patent 6301693, Oct. 2001.
	27	Sachin S. Sapatnekar , Sung-Mo Kang, Design Automation for Timing-Driven Layout Synthesis, Kluwer Academic Publishers, Norwell, MA, 1992
	28	Georg Sigl , Konrad Doll , Frank M. Johannes, Analytical placement: A linear or a quadratic objective function?, Proceedings of the 28th conference on ACM/IEEE design automation, p.427-432, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127707]
	29	W.-J. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits", IEEE Trans. Computer-Aided Design 14(3) (1995), pp. 349--359.
	30	Ren-Song Tsay , Ernest S. Kuh , Chi-Ping Hsu, PROUD: A Sea-Of-Gates Placement Algorithm, IEEE Design & Test, v.5 n.6, p.44-56, November 1988 [doi>10.1109/54.9271]
	31	P. Villarrubia, G. Nusbaum, R. Masleid and P. T. Patel, "IBM RISC Chip Design Methodology", Proc. Int. Conf. Computer Design, 1989, pp. 143--147.
	32	Jens Vygen, Algorithms for large-scale flat placement, Proceedings of the 34th annual conference on Design automation, p.746-751, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266360]
	33	A Standard-Cell Placement Tool for Designs with High Row Utilization, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.45, September 16-18, 2002
	34	Xiaojian Yang , Bo-Kyung Choi , Majid Sarrafzadeh, Routability driven white space allocation for fixed-die standard-cell placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505400]
	35	Mehmet Can Yildiz , Patrick H. Madden, Improved cut sequences for partitioning based placement, Proceedings of the 38th conference on Design automation, p.776-779, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379064]

CITED BY 27

	Satoshi Ono , Patrick H. Madden, On structure and suboptimality in placement, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	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
	Bo Yao , Hongyu Chen , Chung-Kuan Cheng , Nan-Chi Chou , Lung-Tien Liu , Peter Suaris, Unified quadratic programming approach for mixed mode placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	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
	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
	Yong Zhan , Yan Feng , Sachin S. Sapatnekar, A fixed-die floorplanning algorithm using an analytical approach, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Tai-Chen Chen , Yao-Wen Chang , Shyh-Chang Lin, A novel framework for multilevel full-chip gridless routing, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Andrew B. Kahng , Sherief Reda , Qinke Wang, APlace: a general analytic placement framework, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	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
	Tony Chan , Jason Congy , 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
	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
	Chih-Yang Peng , Wen-Chang Chao , Yao-Wen Chang , Jyh-Herng Wang, Simultaneous block and I/O buffer floorplanning for flip-chip design, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Jason Cong , Min Xie, A robust detailed placement for mixed-size IC designs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Andrew B. Kahng , Sherief Reda, A tale of two nets: studies of wirelength progression in physical design, Proceedings of the international workshop on System-level interconnect prediction, March 04-05, 2006, Munich, Germany
	Jason Cong , Kirill Minkovich, Optimality study of logic synthesis for LUT-based FPGAs, Proceedings of the internation symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA
	Aaron N. Ng , Igor L. Markov , Rajat Aggarwal , Venky Ramachandran, Solving hard instances of floorplacement, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Andrew B. Kahng , Chul-Hong Park , Puneet Sharma , Qinke Wang, Lens aberration aware timing-driven placement, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
	Zhong Xiu , Rob A. Rutenbar, Mixed-size placement with fixed macrocells using grid-warping, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	A. B. Kahng , Q. Wang, An analytic placer for mixed-size placement and timing-driven placement, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.565-572, November 07-11, 2004
	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
	Min Pan , N. Viswanathan , C. Chu, An efficient and effective detailed placement algorithm, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.48-55, November 06-10, 2005, San Jose, CA
	J. Cong , M. Romesis , J. R. Shinnerl, Robust mixed-size placement under tight white-space constraints, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.165-172, November 06-10, 2005, San Jose, CA
	Kristofer Vorwerk , Andrew Kennings, An Improved Multi-Level Framework for Force-Directed Placement, Proceedings of the conference on Design, Automation and Test in Europe, p.902-907, March 07-11, 2005
	Andrey Ayupov , Alexander Marchenko , Vladimir Tiourin, An analytical approach to placement legalization, Proceedings of the 18th ACM Great Lakes symposium on VLSI, May 04-06, 2008, Orlando, Florida, USA
	Andrew B. Kahng , Chul-Hong Park , Puneet Sharma , Qinke Wang, Lens aberration aware placement for timing yield, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.1, p.1-26, January 2009
	Tao Luo , David Z. Pan, DPlace2.0: a stable and efficient analytical placement based on diffusion, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Jarrod A. Roy , Aaron N. Ng , Rajat Aggarwal , Venky Ramachandran , Igor L. Markov, Solving modern mixed-size placement instances, Integration, the VLSI Journal, v.42 n.2, p.262-275, February, 2009