Optimal folding of standard and custom cells

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal folding of standard and custom cells

Full text

Pdf (375 KB)

Source

ACM Transactions on Design Automation of Electronic Systems (TODAES) archive
Volume 1 , Issue 1 (January 1996) table of contents

Pages: 123 - 143

Year of Publication: 1996

ISSN:1084-4309

Authors

Venkat Thanvantri	University of Florida
Sartaj Sahni	University of Florida

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 23, 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/225871.225897 What is a DOI?

ABSTRACT

We study the problem of folding an ordered list of standard and custom cells into rows of a chip so as to minimize either the routing area or the total chip area. Nine versions of the folding problem are formulated and fast polynomial time algorithms are obtained for each. Two of our formulations correspond to problems formulated in Paik and Sahni [1993] for the folding of a stack of bit-slice components. Our algorithms for these two formulations are asymptotically superior to those of Paik and Sahni [1993].

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	Glenn W. Cox , B. D. Carroll, The Standard Transistor Array (star) (Part II automatic cell placement techniques), Proceedings of the 17th conference on Design automation, p.451-457, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804569]
	2	FREDERICKSON, a.N. 1992. Optimal parametric search algorithms in trees I: Tree partitioning. Purdue Univ., Tech. Rep. CSD-TR-1029.
	3	Greg N. Frederickson, Optimal algorithms for tree partitioning, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.168-177, January 28-30, 1991, San Francisco, California, United States
	4	FREDERICKSON, a. N. AND JOHNSON, D. B. 1983. Finding kth paths and p-centers by generating and searching good data structures. J. Algorithms 4, 61-80.
	5	FREDERICKSON, a. N. AND JOHNSON, D.B.1984. Generalized selection and ranking: sorted matrices. SIAM J. Comput. 13, 14-30.
	6	W. R. Heller , W. F. Michail , W. E. Donath, Prediction of wiring space requirements for LSI, Proceedings of the 14th conference on Design automation, p.32-42, January 1977
	7	Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
	8	Ellis Horowitz , Sartaj Sahni, Fundamentals of data structures in PASCAL, Computer Science Press, Inc., New York, NY, 1984
	9	Sungho Kang, Linear ordering and application to placement, Proceedings of the 20th conference on Design automation, p.457-464, June 27-29, 1983, Miami Beach, Florida, United States
	10	PAIK, D. AND SAHNI, S. 1993. Optimal folding of bit sliced stacks. IEEE Trans. CAD Integrated Circuits Syst. 12, 11 (Nov.), 1679-1685.
	11	Eugene Shragowitz , Jong Lee , Sartaj Sahni, Place-router for “Sea-of Gates” design style, Progress in computer-aided VLSI design: techniques, Ablex Publishing Corp., Norwood, NJ, 1990
	12	E. Shragowitz , L. Lin , S. Sahi, Models and algorithms for structured layout, Computer-Aided Design, v.20 n.5, p.263-271, June 1988 [doi>10.1016/0010-4485(88)90072-3]