Recursive bisection placement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Recursive bisection placement: feng shui 5.0 implementation details

Full text

Pdf (1.03 MB)

Source

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

San Francisco, California, USA

SESSION: 2005 ISPD placement contest table of contents

Pages: 230 - 232

Year of Publication: 2005

ISBN:1-59593-021-3

Authors

Ameya R. Agnihotri	SUNY Binghamton CSD, Binghamton, NY
Satoshi Ono	University of Kitakyushu, Binghamton, NY
Patrick H. Madden	University of Kitakyushu, Binghamton, NY

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 53, Citation Count: 14

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

ABSTRACT

In this paper, we summarize circuit placement techniques and algorithms developed by the BLAC CAD research group; these have been integrated into our recursive bisection based placement tool feng shui. We also briefly describe current research interests.

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	Saurabh N. Adya , Igor L. Markov , Paul G. Villarrubia, On Whitespace and Stability in Mixed-Size Placement and Physical Synthesis, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.311, November 09-13, 2003 [doi>10.1109/ICCAD.2003.107]
	2	Ameya Agnihotri , Mehmet Can YILDIZ , Ateen Khatkhate , Ajita Mathur , Satoshi Ono , Patrick H. Madden, Fractional Cut: Improved Recursive Bisection Placement, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.307, November 09-13, 2003 [doi>10.1109/ICCAD.2003.72]
	3	Melvin A. Breuer, A class of min-cut placement algorithms, Proceedings of the 14th conference on Design automation, p.284-290, January 1977
	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	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]
	6	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]
	7	A. E. Dunlop and B. W. Kernighan. A procedure for placement of standard-cell VLSI circuits. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, CAD-4(1):92--98, January 1985.
	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	D. Hill. US patent 6,370,673: Method and system for high speed detailed placement of cells within an integrated circuit design, 2002.
	10	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]
	11	Andrew B. Kahng , Sherief Reda, Placement feedback: a concept and method for better min-cut placements, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996670]
	12	Ateen Khatkhate , Chen Li , Ameya R. Agnihotri , Mehmet C. Yildiz , Satoshi Ono , Cheng-Kok Koh , Patrick H. Madden, Recursive bisection based mixed block placement, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981084]
	13	S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671--680, May 1983.
	14	J. Kleinhans, G. Sigl, F. Johannes, and K. Antreich. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 10(3):356--365, 1991.
	15	C. Li and C.-K. Koh. On improving recursive bipartitioning-based placement. Technical Report TR-ECE-03-14, Purdue University ECE, 2003.
	16	Chen Li , Min Xie , Cheng-Kok Koh , J. Cong , P. H. Madden, Routability-driven placement and white space allocation, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.394-401, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382607]
	17	Chen Li , Cheng-Kok Koh , Patrick H. Madden, Floorplan management: incremental placement for gate sizing and buffer insertion, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120867]
	18	Patrick H. Madden, Partitioning by iterative deletion, Proceedings of the 1999 international symposium on Physical design, p.83-89, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300030]
	19	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 [doi>10.1145/1120725.1120864]
	20	C. E. Radke, A justification of, and an improvement on, a useful rule for predicting circuit-to-pin ratios, Proceedings of the 6th annual conference on Design Automation, p.257-267, January 1969 [doi>10.1145/800260.809030]
	21	Pradeep Ramachandaran , Ameya R. Agnihotri , Satoshi Ono , Purushothaman Damodaran , Krishnaswami Srihari , Patrick H. Madden, Optimal placement by branch-and-price, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120865]
	22	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
	23	P. R. Suaris and G. Kedem. An algorithm for quadrisection and its application to standard cell placement. IEEE Trans. on Circuits and Systems, 35(3):394--303, 1988.
	24	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]
	25	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]
	26	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
	27	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]
	28	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 14

	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
	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
	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
	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
	Kristofer Vorwerk , Andrew Kennings , Doris T. Chen , Laleh Behjat, Floorplan repair using dynamic whitespace management, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	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
	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
	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
	Chao-Yang Yeh , M. Marek-Sadowska, Timing-aware power noise reduction in layout, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.627-634, November 06-10, 2005, San Jose, CA
	Hsin-Chen Chen , Yi-Lin Chuang , Yao-Wen Chang , Yung-Chung Chang, Constraint graph-based macro placement for modern mixed-size circuit designs, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Cheng-Yu Wang , Wai-Kei Mak, Signal skew aware floorplanning and bumper signal assignment technique for flip-chip, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan