Algorithms for large-scale flat placement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for large-scale flat placement

Full text

Pdf (1.99 MB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 34th annual Design Automation Conference table of contents

Anaheim, California, United States

Pages: 746 - 751

Year of Publication: 1997

ISBN:0-89791-920-3

Author

Jens Vygen

Research Institute for Discrete Mathematics, University of Bonn Lennéstr. 2, 53113 Bonn, Germany

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 36, Citation Count: 37

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

ABSTRACT

This is a survey on the algorithms which are part ofa program for flat placement of large-scale VLSI processorchips. The basis is a quadratic optimization approachcombined with a new quadrisection algorithm.In contrast to most previous quadratic placement methods,no min-cut objective is used at all. Based on aquadratic placement, a completely new algorithm findsa four-way partitioning meeting capacity constraintsand minimizing the total movement.

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	U. Fassnacht , J. Schietke, Timing analysis and optimization of a high-performance CMOS processor chipset, Proceedings of the conference on Design, automation and test in Europe, p.325-330, February 23-26, 1998, Le Palais des Congrés de Paris, France
	2	W. Hackbusch : Iterative Solution of Large Sparse Systems, Springer, 1994
	3	A. Hetzel : Verdrahtung im VLSI-Design: Spezielle Teilprobleme und ein sequentielles L6sungsverfahren, Ph.D. thesis, University of Bonn, 1995 {in German}
	4	J. M. Kleinhans, G. Sigl, F. M. Johannes, K. J. Antreich : GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization, IEEE Transactions on Compute~Aided Design of lntegrated Circuits and Systems 10 (1991), 356-365
	5	J. Koehl , U. Baur , T. Ludwig , B. Kick , T. Pflueger, A flat, timing-driven design system for a high-performance CMOS processor chipset, Proceedings of the conference on Design, automation and test in Europe, p.312-320, February 23-26, 1998, Le Palais des Congrés de Paris, France
	6	Hidetoshi Onodera , Yo Taniguchi , Keikichi Tamaru, Branch-and-bound placement for building block layout, Proceedings of the 28th conference on ACM/IEEE design automation, p.433-439, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127708]
	7	James B. Orlin, A faster strongly polynomial minimum cost flow algorithm, Operations Research, v.41 n.2, p.338-350, March–April 1993 [doi>10.1287/opre.41.2.338]
	8	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]
	9	J. Vygen : Plazierung im VLSI-Design und ein zweidimensionales Zerlegungsproblem, Ph.D. thesis, University of Bonn, 1997 {in German}

CITED BY 37

	U. Fassnacht , J. Schietke, Timing analysis and optimization of a high-performance CMOS processor chipset, Proceedings of the conference on Design, automation and test in Europe, p.325-330, February 23-26, 1998, Le Palais des Congrés de Paris, France
	J. Vygen, Algorithms for detailed placement of standard cells, Proceedings of the conference on Design, automation and test in Europe, p.321-324, February 23-26, 1998, Le Palais des Congrés de Paris, France
	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
	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
	David E. Lackey , Paul S. Zuchowski , Juergen Koehl, Designing mega-ASICs in nanogate technologies, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Chuck J. Alpert , Gi-Joon Nam , Paul Villarribua , Mehmet C. YILDIZ, Placement stability metrics, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	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
	J. Koehl , U. Baur , T. Ludwig , B. Kick , T. Pflueger, A flat, timing-driven design system for a high-performance CMOS processor chipset, Proceedings of the conference on Design, automation and test in Europe, p.312-320, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Charles J. Alpert , Gi-Joon Nam , Paul G. Villarrubia, Free space management for cut-based placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.746-751, November 10-14, 2002, San Jose, California
	Juergen Koehl , David E. Lackey , George Doerre, IBM's 50 Million gate ASICs, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	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
	G. W. Doerre , D. E. Lackey, The IBM ASIC/SoC methodology--A recipe for first-time success, IBM Journal of Research and Development, v.46 n.6, p.649-660, November 2002
	Ulrich Brenner , André Rohe, An effective congestion driven placement framework, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Bernd Obermeier , Frank M. Johannes, Quadratic placement using an improved timing model, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, 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
	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
	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
	Oluf Faroe , David Pisinger , Martin Zachariasen, Local search for final placement in VLSI design, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Andrew B. Kahng , Igor L. Markov , Sherief Reda, On legalization of row-based placements, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
	Andrew B. Kahng , Igor L. Markov , Sherief Reda, Boosting: Min-Cut Placement with Improved Signal Delay, Proceedings of the conference on Design, automation and test in Europe, p.21098, February 16-20, 2004
	H. Chang , E. Shragowitz , J. Liu , H. Youssef , B. Lu , S. Sutanthavibul, Net criticality revisited: an effective method to improve timing in physical design, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Taraneh Taghavi , Soheil Ghiasi , Abhishek Ranjan , Salil Raje , Majid Sarrafzadeh, Innovate or perish: FPGA physical design, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	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
	Maogang Wang , Abhishek Ranjan , Salil Raje, Multi-Million Gate FPGA Physical Design Challenges, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.891, November 09-13, 2003
	Jens Vygen, New theoretical results on quadratic placement, Integration, the VLSI Journal, v.40 n.3, p.305-314, April, 2007
	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
	S. N. Adya , S. Chaturvedi , J. A. Roy , D. A. Papa , I. L. Markov, Unification of partitioning, placement and floorplanning, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.550-557, November 07-11, 2004
	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
	Stefan Thomas Obenaus , Ted H. Szymanski, Gravity: Fast placement for 3-D VLSI, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.3, p.298-315, July 2003
	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
	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
	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
	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
	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
	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
	Jason Cong , Tim Kong , Joseph R. Shinnerl , Min Xie , Xin Yuan, Large-Scale Circuit Placement: Gap and Promise, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.883, November 09-13, 2003
	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