Design and analysis of physical design algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Design and analysis of physical design algorithms

Full text

Pdf (141 KB)

Source

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

Sonoma, California, United States

Pages: 82 - 89

Year of Publication: 2001

ISBN:1-58113-347-2

Authors

Majid Sarrafzadeh	Computer Science Department, University of California, Los Angeles, Los Angeles, California
Elaheh Bozorgzadeh	Computer Science Department, University of California, Los Angeles, Los Angeles, California
Ryan Kastner	Computer Science Department, University of California, Los Angeles, Los Angeles, California
Ankur Srivastava	Computer Science Department, University of California, Los Angeles, Los Angeles, California

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 34, Citation Count: 1

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

ABSTRACT

We will review a few key algorithmic and analysis concepts with application to physical design problems. We argue that design and detailed analysis of algorithms is of fundamental importance in developing better physical design tools and to cope with the complexity of present-day designs.

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	R. Nair, C. L. Berman, P. S. Hauge, and E. J. Yoffa, "Generation of Performance Constraints for Layout," IEEE Transactions on Computer-Aided Design, CAD- 8(8), pp.860-874, August 1989.
	2	T. Gao, P. M. Vaidya, and C. L. Liu, "A New Performance Driven Placement Algorihm," in Proceedings of International Conference on Computer-Aided Design, pp.44-47, 1991.
	3	H. Youssef and E. Shragowitz, "Timing Constraints for Correct Performance," in Proceedings of International Conference on Computer-Aided Design, pp.24-27, 1990.
	4	G. E. Tellez, D. A. Knol, and M. Sarrafzadeh, "A Graph-Based Delay Budgeting Algorithm for Large Scale Timing-Driven Placement Problems," in Proceedings of fifth ACM/SIGDA Physical Design Workshop, pp.234-240, April 1996.
	5	R. H. Moehring, "Graphs and Orders: the Roles of Graphs in the Theory of Ordered Sets and Its Applications", Published by D. Reidel Publishing Company, Edited by I. Rival, New York and London, pp.41-101, May 1984.
	6	David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
	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	B. W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs", in Bell Systems Technical Journal, 49(2): 291-37, 1970.
	9	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	10	R. C. Prim, "Shortest Connection Networks and Some Generalizations", in Bell System Technical Journal, 36(6):1389-1401, 1957.
	11	Bernhard Korte , László Lovász, Mathematical Structures Underlying Greedy Algorithms, Proceedings of the 1981 International FCT-Conference on Fundamentals of Computation Theory, p.205-209, August 24-28, 1981
	12	C. K. Cheng and Y. C. A. Wei, "An Improved Twoway Partitioning Algorithm with Stable Performance", in IEEE Transactions on Computer Aided Design, 10(12): 1502-1511, 1991.
	13	L. Hagen and A. B. Kahng, "Fast Spectral methods for Ratio Cut Partitioning and Clustering", in IEEE/ACM International Conference on Computer-Aided Design, 1991.
	14	P. R. Suaris and G. Kedem, "Quadrisection: A New Approach to Standard Cell Layout", in IEEE/ACM Design Automation Conference, pp. 474-477, 1987.
	15	P. R. Suaris and G. Kedem, "Standard Cell Placement by Quadrisection", in IEEE/ACM International Conference on Computer-Aided Design, pp. 612-615, 1987.
	16	T. F. Gonzalez, "Clustering to Minimize the Maximum Intercluster Distance", in Theoretical Computer Science, 38:293-306, 1985.
	17	Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	18	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	19	Rajeev Murgai, On the global fanout optimization problem, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.511-515, November 07-11, 1999, San Jose, California, United States
	20	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	21	R. M. Karp, " Reducibility Among Combinatorial Problems", in R. E. Miller and J. W. Thatcher, Complexity of Computer Computations, Plenum Press, pp. 85-103, 1972.
	22	Chunhong Chen , Xiaojian Yang , Majid Sarrafzadeh, Potential slack: an effective metric of combinational circuit performance, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	23	E. F. Moore, "Shortest Path Through a Maze", in Kluwer Proceedings of the International Symposium on Switching Circuits, 1959.
	24	C. Y. Lee, "An Algorithm for Path Connection and its Applications", in IRE Transactions on Electronic Computers, 1961.