Nutcracker: an efficient and intelligent channel spacer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Nutcracker: an efficient and intelligent channel spacer

Full text

Pdf (782 KB)

Source

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

Miami Beach, Florida, United States

Pages: 298 - 304

Year of Publication: 1987

ISBN:0-8186-0781-5

Authors

X.-M. Xiong	Electronics Research Laboratory, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA
E. S. Kuh	Electronics Research Laboratory, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 8, Citation Count: 7

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

ABSTRACT

A new algorithm for channel spacing is discussed in this paper. In contrast to existing compaction algorithms, we rely on the geometric method and bypass the constraint graph during the whole spacing process. We propose an efficient way to enumerate all possible jogs. Therefore, for the given channel routing topology, our algorithm yields the minimal channel height with the incorporation of contacts sliding and automatic jog insertion. In the final output, only necessary jogs are inserted, and the total wire length is minimized.

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	Y. Eric Cho, A subjective review of compaction (tutorial session), Proceedings of the 22nd ACM/IEEE conference on Design automation, p.396-404, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317918]
	2	D. D. Mlynski and C. H. Sung, ~'Layout Compaction", Advances in CAD for VLS}, Vol. 4, T. Ohtsuki Editor, North Holland Publ. Co., 1985.
	3	H. H. Chen and E. S. Kuh, "A Variable-Width Gridless Channel Router", Proc. of ICCAD-85, November 1985, pp. 304-306.
	4	M.Y. Hsueh and D. O. Pederson, ~'Computer-Alded Layout of LSI Circuit Building Blocks", Proc. IEEE International Symposium on Circuits and Systems, 1979, pp. 474-477.
	5	M. Schlag, Y. Z. Liao and C. K. Wong, "An Algorithm for Optimal Two-Dimensional Compaction of VLSI Layouts", integration, VLSI Journal, Vol. 1, 1983, pp. 179-209.
	6	D. N. Deutsch, ~'Compacted Channel Routing', Proc. of ICCAD~85, November 1985, pp. 223-225.
	7	J. Nievergelt , F. P. Preparata, Plane-sweep algorithms for intersecting geometric figures, Communications of the ACM, v.25 n.10, p.739-747, Oct 1982 [doi>10.1145/358656.358681]
	8	W.-M. Dai , M. Sato , E. S. Kuh, A dynamic and efficient representation of building-block layout, Proceedings of the 24th ACM/IEEE conference on Design automation, p.376-384, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37945]
	9	W. M. Dai, T. Asano and E. S. Kuh, "Routing Region Definition and Ordering Scheme for Building-Block Layout", IEEE Trans. on Computer.Aided Design of integrated Circuits and Systems, July 1985, pp. 189-197.
	10	H. H. Chen, Routing L-shaped channels in nonslicing-structure placement, Proceedings of the 24th ACM/IEEE conference on Design automation, p.152-158, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37911]

CITED BY 7

	Toru Awashima , Wataru Yamamoto , Masao Sato , Tatsuo Ohtsuki, An optimal chip compaction method based on shortest path algorithm with automatic jog insertion, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.162-165, November 1992, Santa Clara, California, United States
	Christian Masson , Remy Escassut , Denis Barbier , Daniel Winer , Gregory Chevallier, Object oriented Lisp implementation of the CHEOPS VLSI floor planning and routing system, Proceedings of the 28th conference on ACM/IEEE design automation, p.259-264, June 17-22, 1991, San Francisco, California, United States
	Chung-Kuan Cheng , David N. Deutsch, Improved channel routing by via minimization and shifting, Proceedings of the 25th ACM/IEEE conference on Design automation, p.677-680, June 12-15, 1988, Atlantic City, New Jersey, United States
	Jingsheng Cong , D. F. Wong, How to obtain more compactable channel routing solutions, Proceedings of the 25th ACM/IEEE conference on Design automation, p.663-666, June 12-15, 1988, Atlantic City, New Jersey, United States
	David G. Boyer, Symbolic layout compaction review, Proceedings of the 25th ACM/IEEE conference on Design automation, p.383-389, June 12-15, 1988, Atlantic City, New Jersey, United States
	Christian Masson , Denis Barbier , Remy Escassut , Daniel Winer , Gregory Chevallier , Pierre François Zeegers, CHEOPS: an integrated VLSI floor planning and chip assembly system implemented in object oriented LISP, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
	Yang Cai , D. F. Wong, Optimal via-shifting in channel compaction, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland