FastPlace

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model

Full text

Pdf (238 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: 26 - 33

Year of Publication: 2004

ISBN:1-58113-817-2

Authors

Natarajan Viswanathan	Iowa State University, Ames, IA
Chris Chong-Nuen Chu	Iowa State University, Ames, IA

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): 31, Citation Count: 42

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.981072 What is a DOI?

ABSTRACT

In this paper, we present FastPlace -- a fast, iterative, flat placement algorithm for large-scale standard cell designs. FastPlace is based on the quadratic placement approach. The quadratic approach formulates the wirelength minimization problem as a convex quadratic program, which can be solved efficiently by some analytical techniques. However it suffers from some drawbacks. First, the resulting placement has a lot of overlap among cells. Second, the resulting total wirelength may be long as the quadratic wirelength objective is only an indirect measure of the linear wirelength. Third, existing net models tend to create a lot of non-zero entries in the connectivity matrix, which slows down the quadratic program solver. To handle the above problems we propose: (1) An efficient Cell Shifting technique to remove cell overlap from the quadratic program solution and produce a global placement with even cell distribution. (2) An Iterative Local Refinement technique, to reduce the wirelength according to the half-perimeter measure. (3) A Hybrid Net Model which is a combination of the traditional clique and star models. This net model greatly reduces the number of non-zero entries in the connectivity matrix and results in a significant speedup of the solver. Experimental results show that FastPlace is on average 13.0 and 97.4 times faster than Capo and Dragon respectively. Correspondingly, the average wirelength is just 1.0% and 1.6% higher.

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	http://vlsicad.eecs.umich.edu/BK/ISPD02bench/.
	2	R. Barrett, M. Berry, and et al. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods SIAM, 1994.
	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 F. Chan , Jason Cong , Tianming Kong , Joseph R. Shinnerl, Multilevel optimization for large-scale circuit placement, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	5	Hongyu Chen , Chung-Kuan Cheng , Nan-Chi Chou , Andrew B. Kahng , John F. MacDonald , Peter Suaris , Bo Yao , Zhengyong Zhu, An algebraic multigrid solver for analytical placement with layout based clustering, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776034]
	6	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]
	7	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
	8	C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
	9	K. M. Hall. An r-dimensional quadratic placement algorithm.Management Science 17:219--229, 1970.
	10	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]
	11	Bo Hu , Malgorzata Marek-Sadowska, Fine granularity clustering for large scale placement problems, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640017]
	12	D. S. Kershaw. The incomplete cholesky-conjugate gradient method for the iterative solution of systems of linear equations. Journal of Computational Physics 26:43--65, 1978.
	13	J. Kleinhans, G. Sigl, F. Johannes, and K. Antreich. Gordian: VLSI placement byquadratic programming and slicing optimization. IEEE Trans. Computer-Aided Design 10(3):356--365, 1991.
	14	Fan Mo , Abdallah Tabbara , Robert K. Brayton, A force-directed macro-cell placer, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	15	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
	16	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]
	17	Paul Villarrubia, Important placement considerations for modern VLSI chips, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640004]
	18	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]
	19	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
	20	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]

CITED BY 42

	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
	Andrew B. Kahng , Qinke Wang, A faster implementation of APlace, 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
	Bo Hu , Yue Zeng , Malgorzata Marek-Sadowska, mFAR: fixed-points-addition-based VLSI placement algorithm, 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
	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
	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
	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
	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
	Yongqiang Lu , C. N. Sze , Xianlong Hong , Qiang Zhou , Yici Cai , Liang Huang , Jiang Hu, Navigating registers in placement for clock network minimization, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Ulrich Brenner , Markus Struzyna, Faster and better global placement by a new transportation algorithm, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Zhong Xiu , Rob A. Rutenbar, Timing-driven placement by grid-warping, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, 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
	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
	Chanseok Hwang , Massoud Pedram, Timing-driven placement based on monotone cell ordering constraints, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	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
	Jinjun Xiong , Yiu-Chung Wong , Egino Sarto , Lei He, Constraint driven I/O planning and placement for chip-package co-design, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Sherief Reda , Amit Chowdhary, Effective linear programming based placement methods, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, 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
	Natarajan Viswanathan , Min Pan , Chris Chu, FastPlace 2.0: an efficient analytical placer for mixed-mode designs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Dian Zhou , Rui-Ming Li, Design and verification of high-speed VLSI physical design, Journal of Computer Science and Technology, v.20 n.2, p.147-165, March 2005
	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
	Philip Chong , Christian Szegedy, A morphing approach to address placement stability, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Shiyan Hu , Jiang Hu, Pattern sensitive placement for manufacturability, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Bo Hu, Timing-driven placement for heterogeneous field programmable gate array, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	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
	Bo Hu , M. Marek-Sadowska, Multilevel expansion-based VLSI placement with blockages, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.558-564, November 07-11, 2004
	K. Vorwerk , A. Kennings , A. Vannelli, Engineering details of a stable force-directed placer, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.573-580, 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
	Haifeng Qian , S. S. Sapatnekar, A hybrid linear equation solver and its application in quadratic placement, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.905-909, November 06-10, 2005, San Jose, CA
	T. Luo , H. Ren , C. J. Alpert , D. Z. Pan, Computational geometry based placement migration, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.41-47, 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
	Min Pan , Chris Chu, IPR: an integrated placement and routing algorithm, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	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
	Charles J. Alpert , Chris Chu , Paul G. Villarrubia, The coming of age of physical synthesis, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Brent Goplen , Sachin Spatnekar, Placement of 3D ICs with thermal and interlayer via considerations, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	Tung-Chieh Chen , Ping-Hung Yuh , Yao-Wen Chang , Fwu-Juh Huang , Denny Liu, MP-trees: a packing-based macro placement algorithm for mixed-size designs, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	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
	Jia Wang , Hai Zhou, Exploring adjacency in floorplanning, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Andrew B. Kahng , Bao Liu , Qinke Wang, Stochastic power/ground supply voltage prediction and optimization via analytical placement, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.15 n.8, p.904-912, August 2007