Quantified suboptimality of VLSI layout heuristics

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quantified suboptimality of VLSI layout heuristics

Full text

Pdf (221 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 32nd annual ACM/IEEE Design Automation Conference table of contents

San Francisco, California, United States

Pages: 216 - 221

Year of Publication: 1995

ISBN:0-89791-725-1

Authors

Lars W. Hagen	Cadence Design Systems, Inc., San Jose, CA
Dennis J. H. Huang	UCLA Department of Computer Science, Los Angeles, CA
Andrew B. Kahng	UCLA Department of Computer Science, Los Angeles, CA

Sponsors

EDAC : Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/217474.217532 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.

	1	David H. Ackley, A connectionist machine for genetic hillclimbing, Kluwer Academic Publishers, Norwell, MA, 1987
	2	C. J. Alpert , A. B. Kahng, A general framework for vertex orderings, with applications to netlist clustering, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.63-67, November 06-10, 1994, San Jose, California, United States
	3	Charles J. Alpert , Andrew B. Kahng, Recent directions in netlist partitioning: a survey, Integration, the VLSI Journal, v.19 n.1-2, p.1-81, Aug. 1995 [doi>10.1016/0167-9260(95)00008-4]
	4	E. B. Baum, "Iterated Descent: A Better Algorithm for Local Search in Combinatorial Optimization Problems", Proc. Neural Information Processing Systems, D. Touretzky, ed., 1987.
	5	K. D. Boese, personal communication, January 1994.
	6	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]
	7	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
	8	J. Garbers, H. J. Promel, and A. Steger, "Finding Clusters in VLSI Circuits", Proc. IEEE Intl. Conf. on Computer- Aided Design, 1990, pp. 520-523. Extended version.
	9	L. Hagen and A. B. Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering", IEEE Trans. on CAD 11(9), Sept. 1992, pp. 1074-1085.
	10	L. Hagen, A. B. Kahng, F. J. Kurdahi, and C. Ramachandran. "On the Intrinsic Rent Parameter and Spectra-Based Partitioning Methodologies." IEEE Trnns. Computer- Aided Design, 13(1):27-37, 1994.
	11	Shigetoshi Nakatake , Yoji Kajitani, Channel-driven global routing with consistent placement (extended abstract), Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.350-355, November 06-10, 1994, San Jose, California, United States
	12	B. M. Riess, personal communication, January 1995.
	13	C. Sechen, Placement and Global Routing of Integrated Circuits Using Simulated Annealing, PhD thesis, Univ. of California, Berkeley, 1986.
	14	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]
	15	W. J. Sun, K. Roy and C. Sechen, "Fast, High-Quality Placement for Large Circuits", Proc. ~th A CM/SIGDA Physical Design Workshop, Lake Arrowhead, April 1993, pp. 11-12.
	16	Ren-Song Tsay , Ernest S. Kuh , Chi-Ping Hsu, Proud: a fast sea-of-gates placement algorithm, Proceedings of the 25th ACM/IEEE conference on Design automation, p.318-323, June 12-15, 1988, Atlantic City, New Jersey, United States
	17	Y. C. Wei and C. K. Cheng, "Towards Efficient Hierarchical Designs by Ratio Cut Partitioning", Proc. IEEE Intl. Conf. on Computer-Aided Design, 1989, pp. 298-301.

CITED BY 13

	C. J. Alpert , T. Chan , D. J.-H. Huang , I. Markov , K. Yan, Quadratic placement revisited, Proceedings of the 34th annual conference on Design automation, p.752-757, June 09-13, 1997, Anaheim, California, United States
	Jason Cong , Michail Romesis , Min Xie, Optimality, scalability and stability study of partitioning and placement algorithms, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	A. E. Caldwell , A. B. Kahng , I. L. Markov, Optimal partitioners and end-case placers for standard-cell layout, Proceedings of the 1999 international symposium on Physical design, p.90-96, April 12-14, 1999, Monterey, California, United States
	Frank M. Johannes, Partitioning of VLSI circuits and systems, Proceedings of the 33rd annual conference on Design automation, p.83-87, June 03-07, 1996, Las Vegas, Nevada, United States
	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
	Kenneth D. Boese , Andrew B. Kahng , Stafanus Mantik, On the relevance of wire load models, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.91-98, March 31-April 01, 2001, Sonoma, California, United States
	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
	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
	Andrew B. Kahng , Sherief Reda, Evaluation of placer suboptimality via zero-change netlist transformations, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	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
	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
	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
	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