Relaxation and clustering in a local search framework

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Relaxation and clustering in a local search framework: application to linear placement

Full text

Pdf (867 KB)

Source

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

New Orleans, Louisiana, United States

Pages: 360 - 366

Year of Publication: 1999

ISBN:1-58133-109-7

Authors

Sung-Woo Hur	Dept. of Electrical Eng. and Comp. Sci., University of Illinois at Chicago
John Lillis	Dept. of Electrical Eng. and Comp. Sci., University of Illinois at Chicago

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): 5, Downloads (12 Months): 17, Citation Count: 10

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/309847.309958 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	C. K. Cheng and E. S. Kuh, "Module Placement Based on Resistive Network Optimization," IEEE Transactions on CAD, pp. 218-225, 1984.
	2	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]
	3	M. A. B. Jackson , E. S. Kuh, Performance-driven placement of cell based IC's, Proceedings of the 26th ACM/IEEE conference on Design automation, p.370-375, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74444]
	4	J. Frankle and R. M. Karp, "Circuit Placements and Cost Bounds by Eigenvector Decomposition," in IC- CAD, pp. 414-417, 1986.
	5	Melvin A. Breuer, A class of min-cut placement algorithms, Proceedings of the 14th conference on Design automation, p.284-290, January 1977
	6	P. R. Suaris and G. Kedem, "Quadrisection: A New Approach to Standard Cell Layout," in ICCAD, pp. 474-477, 1987.
	7	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
	8	D. Mitra, F. Romeo, and A. Sangiovanni-VincenteIli, "Convergence and Finite-Time Behavior of Simulated Annealing," Advances in Applied Probability, pp. 747- 771, 1986.
	9	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]
	10	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]
	11	Y. G. Saab, "An Improved Linear Placement Algorithm Using Node Compaction," IEEE Trans. on CAD of Intergrated Circuits and Systems, vol. 15, no. 8, pp. 952- 958, 1996.
	12	Jianmin Li , John Lillis , Lung-Tien Liu , Chung-Kuan Cheng, New spectral linear placement and clustering approach, Proceedings of the 33rd annual conference on Design automation, p.88-93, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240536]
	13	Shinji Sato, Simulated quenching: a new placement method for module generation, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.538-541, November 09-13, 1997, San Jose, California, United States
	14	"ftp://ftp.es.ele.tue.nl/pub/lp_solve."
	15	S.-W. Hut and J. LiIlis, "Relaxation and Clustering in a Local Search Framework: Application to Linear Placement," in Technical Report UIC-EECS-99-P, 1999.
	16	Honghua Yang , D. F. Wong, Efficient network flow based min-cut balanced partitioning, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.50-55, November 06-10, 1994, San Jose, California, United States
	17	Huiqun Liu , D. F. Wong, Network flow based multi-way partitioning with area and pin constraints, Proceedings of the 1997 international symposium on Physical design, p.12-17, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267673]
	18	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

CITED BY 10

	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
	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
	Terry Tao Ye , Giovanni De Micheli, Data path placement with regularity, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Fadi A. Aloul , Igor L. Markov , Karem A. Sakallah, Faster SAT and smaller BDDs via common function structure, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Qingzhou (Ben) Wang , Devang Jariwala , John Lillis, A study of tighter lower bounds in LP relaxation based placement, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	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
	Qingzhou (Ben) Wang , John Lillis , Shubhankar Sanyal, An LP-based methodology for improved timing-driven placement, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	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
	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
	Henning Fernau, Parameterized algorithmics for linear arrangement problems, Discrete Applied Mathematics, v.156 n.17, p.3166-3177, October, 2008