Partitioning-based standard-cell global placement with an exact objective

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Partitioning-based standard-cell global placement with an exact objective

Full text

Pdf (1.09 MB)

Source

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

Napa Valley, California, United States

Pages: 18 - 25

Year of Publication: 1997

ISBN:0-89791-927-0

Authors

Dennis J.-H. Huang	UCLA Computer Science Dept., Los Angeles, CA
Andrew B. Kahng	UCLA Computer Science Dept., Los Angeles, CA and Cadence Design Systems, Inc., San Jose, CA

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 43, Citation Count: 28

Additional Information:

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

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.

	AHK96	C. J. Alpert, L. W. Hagen, and A. B. Kahng. "A Hybrid Multilevel/Genetic Approach for Circuit Partitioning." In Ptoc. ACM/SIGDA PJ~ydcal Design Workshop, pp. 100-105, 1996.
	Alp96	Charles Jay Alpert , Andrew B. Kahng, Multi-way graph and hypergraph partitioning, 1996
	BCL87	Thang Nguyen Bui , F. Thomson Leighton , Soma Chaudhuri , Michael Sipser, Graph bisection algorithms with good average case behavior, Combinatorica, v.7 n.2, p.171-191, June 1, 1987 [doi>10.1007/BF02579448]
	Bre76	M. A. Breuer. ':Min-cut Placement." Design Automation and Fault-Tolerant Computing, I(4):343-362, 1976.
	Bre77	Melvin A. Breuer, A class of min-cut placement algorithms, Proceedings of the 14th conference on Design automation, p.284-290, January 1977
	DD96a	Shantanu Dutt , Wenyong Deng, VLSI circuit partitioning by cluster-removal using iterative improvement techniques, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.194-200, November 10-14, 1996, San Jose, California, United States
	DD96b	S. Dutt and W. Deng. "VLSI Circuit Partitioning by Cluster-Removal Using Iterative Improvement Techniques." In Proc, A CM/SIGDA Physical Design Workshop, pp. 92-99, 1996. Also see corresponding Technical Report, Dept. of Electrical Engineering, U. Minnesota.
	DJA94	K. Doll, F. M. Johannes, and K. J. Antreich. "Iterative Placement Improvement by Network Flow Methods." IEEE Transactions on Computer- Aided Design, 13:1189-1200, 1994.
	DJS94	K. Doll, F. M. 3ohannes, and G. Sigl. "Iteratire Placement Improvement by Network Flow Methods," IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 13(10):1189-1199, 1994.
	DK85	A.E. Dunlop and B. W. Kernighan. "A Procedure for Placement of Standard Cell VLSI Circuits." IEEE Transactions on Computer-Aided Design, 4(1):92-98, 1985.
	FM82	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
	HHK95	Lars W. Hagen , Dennis J.-H. Huang , Andrew B. Kahng, On implementation choices for iterative improvement partitioning algorithms, Proceedings of the conference on European design automation, p.144-149, September 18-22, 1995, Brighton, England
	KL70	B.W. Kernighan and S. Lin. "An Efficient Heuristic Procedure for Partitioning Graphs." Bell Syst, Tech. J., 49(2):291-307, 1970.
	KSJ91	J. M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich. "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization." IEEE Transactions on Computer-Aided Design, 10(3):356-365, 1991.
	Lau79	Ulrich Lauther, A min-cut placement algorithm for general cell assemblies based on a graph representation, Proceedings of the 16th Conference on Design automation, p.1-10, June 25-27, 1979, San Diego, CA, United States
	Len90	Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
	RE95	B.M. Riess and G. G. Ettelt. ``SPEED: Fast and Efficient Timing Driven Placement." In Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 377-380, 1995.
	San89	L. A. Sanchis, Multiple-Way Network Partitioning, IEEE Transactions on Computers, v.38 n.1, p.62-81, January 1989 [doi>10.1109/12.8730]
	San93	Laura A. Sanchis, Multiple-Way Network Partitioning with Different Cost Functions, IEEE Transactions on Computers, v.42 n.12, p.1500-1504, December 1993 [doi>10.1109/12.260640]
	SDJ91	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]
	SK87a	P.R. Suaris and G. Kedem. "Quadrisection: A New Approach to Standard Cell Layout." in Pracee&'ngs of the IEEE/AUM International Conference on Computer-Aided Design, pp. 474-477, 1987.
	SK87b	P.R. Suaris and G. Kedem. "Standard Cell Placement by Quadrisection." In Proceedings IEEE Intl. Conf. Computer Design, pp. 612-615, 1987.
	SK88	P.R. Suaris and G. Kedem. "An Algorithm for Quadrisection and Its Application to Standard Cell Placement." IEEE Transactions on Circuits and Systems, 35(3}:294-303, 1988.
	SK89	P.R.. Suaris and G. Kedem. "A Quadrisectionbased Combined Place and Route Scheme for Standard Cells." IEEE Transactions on Computer-Aided Design, 8(3):234-244. 1989.
	SM91	K. Shahookar , P. Mazumder, VLSI cell placement techniques, ACM Computing Surveys (CSUR), v.23 n.2, p.143-220, June 1991 [doi>10.1145/103724.103725]
	SS93	Wern-Jieh Sun , Carl Sechen, Efficient and effective placement for very large circuits, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.170-177, November 07-11, 1993, Santa Clara, California, United States
	SS95	William Swartz , Carl Sechen, Timing driven placement for large standard cell circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.211-215, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217531]
	Ste97	G. Stenz. 1997. Personal communication.
	Swa96	W. Swartz, 1996. Personal communication.
	TK91	R.-S. Tsay and E. S. Kuh. "A Unified Approach to Partitioning and Placement." IEEE Transactions on Circuits and Systems, 38(5):521-533, 1991.
	TKH88	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]

CITED BY 28

	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
	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
	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Improved algorithms for hypergraph bipartitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.661-666, January 2000, Yokohama, Japan
	Maogang Wang , Majid Sarrafzadeh, On the behavior of congestion minimization during placement, Proceedings of the 1999 international symposium on Physical design, p.145-150, April 12-14, 1999, Monterey, California, United States
	Andrew B. Kahng, Futures for partitioning in physical design (tutorial), Proceedings of the 1998 international symposium on Physical design, p.190-193, April 06-08, 1998, Monterey, California, United States
	Patrick H. Madden, Reporting of standard cell placement results, Proceedings of the 2001 international symposium on Physical design, p.30-35, April 01-04, 2001, Sonoma, California, United States
	Ke Zhong , Shantanu Dutt, Algorithms for simultaneous satisfaction of multiple constraints and objective optimization in a placement flow with application to congestion control, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Hypergraph partitioning with fixed vertices, Proceedings of the 36th ACM/IEEE conference on Design automation, p.355-359, June 21-25, 1999, New Orleans, Louisiana, United States
	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
	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
	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
	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
	A. B. Kahng , I. Mandoiu , P. Pevzner , S. Reda , A. Zelikovsky, Engineering a scalable placement heuristic for DNA probe arrays, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.148-156, April 10-14, 2003, Berlin, Germany
	Saurabh N. Adya , Mehmet C. Yildiz , Igor L. Markov , Paul G. Villarrubia , Phiroze N. Parakh , Patrick H. Madden, Benchmarking for large-scale placement and beyond, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	C. J. Alpert , A. E. Caldwell , A. B. Kahng , I. L. Markov, Partitioning with terminals: a “new” problem and new benchmarks, Proceedings of the 1999 international symposium on Physical design, p.151-157, April 12-14, 1999, Monterey, California, United States
	Ke Zhong , Shantanu Dutt, Effective partition-driven placement with simultaneous level processing and global net views, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Shyam Ramji , Nagu R. Dhanwada, Design topology aware physical metrics for placement analysis, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA
	Pongstorn Maidee , Cristinel Ababei , Kia Bazargan, Fast timing-driven partitioning-based placement for island style FPGAs, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, 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
	David A. Papa , Saurabh N. Adya , Igor L. Markov, Constructive benchmarking for placement, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Design and implementation of move-based heuristics for VLSI hypergraph partitioning, Journal of Experimental Algorithmics (JEA), 5, p.5-es, 2000
	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
	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
	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
	Jarrod A. Roy , James F. Lu , Igor L. Markov, Seeing the forest and the trees: Steiner wirelength optimization in placemen, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, 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
	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
	Andrew B. Kahng , Ion Mandoiu , Sherief Reda , Xu Xu , Alex Z. Zelikovsky, Evaluation of Placement Techniques for DNA Probe Array Layout, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.262, November 09-13, 2003