Multilevel generalized force-directed method for circuit placement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multilevel generalized force-directed method for circuit placement

Full text

Pdf (773 KB)

Source

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

San Francisco, California, USA

SESSION: Placement table of contents

Pages: 185 - 192

Year of Publication: 2005

ISBN:1-59593-021-3

Authors

Tony Chan	UCLA
Jason Cong	UCLA
Kenton Sze	UCLA

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 49, Citation Count: 29

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/1055137.1055177 What is a DOI?

ABSTRACT

Automatic circuit placement has received renewed interest recently given the rapid increase of circuit complexity, increase of interconnect delay, and potential sub-optimality of existing placement algorithms [13]. In this paper we present a generalized force-directed algorithm embedded in mPL2's [12] multilevel framework. Our new algorithm, named mPL5, produces the shortest wirelength among all published placers with very competitive runtime on the IBM circuits used in [29]. The new contributions and enhancements are: (1) We develop a new analytical placement algorithm using a density constrained minimization formulation which can be viewed as a generalization of the force-directed method in [16]; (2) We analyze and identify the advantages of our new algorithm over the force-directed method; (3) We successfully incorporate the generalized force-directed algorithm into a multilevel framework which significantly improves wirelength and speed. Compared to Capo9.0, our algorithm mPL5 produces 8% shorter wirelength and is 2X faster. Compared to Dragon3.01, mPL5 has 3% shorter wirelength and is 12X faster. Compared to Fengshui5.0, it has 5% shorter wirelength and is 2X faster. Compared to the ultra-fast placement algorithm: FastPlace, mPL5 produces 8% shorter wirelength but is 6X slower. A fast mode of mPL5 (mPL5-fast) can produce 1% shorter wirelength than Fast-Place1.0 and is only 2X slower. Moreover, mPL5-fast has demonstrated better scalability than FastPlace1.0.

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	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	C. R. Anderson and C. Elion. Accelerated Solutions of Nonlinear Equations Using Stabilized Runge-Kutta Methods, UCLA CAM report, April 2004.
	4	K. Arrow, L. Huriwicz and H. Uzawa. Studies in Nonlinear Programming. Stanford University Press, Stanford, CA, 1958.
	5	A. Brandt. Multiscale Scientific Computation: Review 2001. In T. Barth, R. Haimes, and T. Chan, editors, Multiscale and Multiresolution Methods. Springer Verlag, 2001.
	6	A. Brandt and D. Ron. Multigrid Solvers and Multilevel Optimization Strategies, chapter 1 of Multilevel Optimization and VLSICAD, Kluwer Academic Publishers, Boston, 2002.
	7	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]
	8	R. Chan, T. Chan, M. K. Ng, and A. Yip. Cosine Transform Preconditioner for High Resolution Image Reconstruction. Linear Algebra Appls, 316 (2000), pp. 89--104.
	9	T. Chan, J. Cong, T. Kong, and J. Shinnerl. Multilevel Circuit Placement, chapter 4 of Multilevel Optimization and VLSICAD, Kluwer Academic Publishers, Boston, 2002.
	10	L. C. Evans. Partial Differential Equations, American Mathematical Society, 2002.
	11	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
	12	Tony F. Chan , Jason Cong , Tim Kong , Joseph R. Shinnerl , Kenton Sze, An Enhanced Multilevel Algorithm for Circuit Placement, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.299, November 09-13, 2003 [doi>10.1109/ICCAD.2003.30]
	13	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]
	14	Chin-Chih Chang , Jason Cong , Xin Yuan, Multi-level placement for large-scale mixed-size IC designs, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119835]
	15	J. Cong. An Interconnect-Centric Design Flow for Nanometer Technologies. In Proc. of the IEEE, vol. 89, No. 4, pp. 505--528, April 2001.
	16	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]
	17	Sung Woo Hur , John Lillis, Mongrel: hybrid techniques for standard cell placement, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	18	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]
	19	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]
	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. on Computer-Aided Design, vol. 10, pp. 356--365, March 1991.
	22	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]
	23	C. Li and C.-K. Koh. On Improving Recursive Bipartitioning-based Placement. Technical Report TR-ECE-03-14, Purdue University ECE, 2003.
	24	I. I. Mahmoud, K. Asakura, T. Nishibu and T. Ohtsuki. Experimental Appraisal of Linear and Quadratic Objective Functions Effect on Force Directed Method for Analog Placement. In IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences 4(E77-A), pp. 710--725, 1994.
	25	K. W. Morton , D. F. Mayers, Numerical solution of partial differential equations, Cambridge University Press, New York, NY, 1995
	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	Takuya Ooura. A FFT Package, http://momonga.t.u-tokyo.ac.jp/~ooura/fft.html.
	28	Leonid I. Rudin , Stanley Osher , Emad Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, v.60 n.1-4, p.259-268, Nov. 1, 1992
	29	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]
	30	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
	31	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]
	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	Zhong Xiu , James D. Ma , Suzanne M. Fowler , Rob A. Rutenbar, Large-scale placement by grid-warping, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996669]

CITED BY 30

	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
	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
	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
	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 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
	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
	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
	Zhe-Wei Jiang , Tung-Chieh Cheny , Tien-Chang Hsuy , Hsin-Chen Chenz , Yao-Wen Changyz, NTUplace2: a hybrid placer using partitioning and analytical techniques, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	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
	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
	Jianhua Li , Laleh Behjat, Net cluster: a net-reduction based clustering preprocessing algorithm, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Tung-Chieh Chen , Yi-Lin Chuang , Yao-Wen Chang, X-architecture placement based on effective wire models, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Jianhua Li , Laleh Behjat , Jie Huang, An effective clustering algorithm for mixed-size placement, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Jason Cong , Guojie Luo, Highly efficient gradient computation for density-constrained analytical placement methods, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	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
	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
	Deming Chen , Jason Cong , Peichen Pan, FPGA Design Automation: A Survey, Foundations and Trends® in Electronic Design Automation, v.1 n.3, p.139-169, January 2006
	Peter Spindler , Ulf Schlichtmann , Frank M. Johannes, Abacus: fast legalization of standard cell circuits with minimal movement, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	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
	K. Vorwerk , A. Kennings, Mixed-size placement via line search, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.899-904, 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
	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
	Zhe-Wei Jiang , Bor-Yiing Su , Yao-Wen Chang, Routability-driven analytical placement by net overlapping removal for large-scale mixed-size designs, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Natarajan Viswanathan , Gi-Joon Nam , Charles J. Alpert , Paul Villarrubia , Haoxing Ren , Chris Chu, RQL: global placement via relaxed quadratic spreading and linearization, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	Tung-Chieh Chen , Minsik Cho , David Z. Pan , Yao-Wen Chang, Metal-density driven placement for cmp variation and routability, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	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
	Jason Cong , Guojie Luo, A multilevel analytical placement for 3D ICs, 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
	Yifang Liu , Rupesh S. Shelar , Jiang Hu, Delay-optimal simultaneous technology mapping and placement with applications to timing optimization, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California