Automatic layout algorithms for function blocks of CMOS gate arrays

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Automatic layout algorithms for function blocks of CMOS gate arrays

Full text

Pdf (621 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 46 - 52

Year of Publication: 1985

ISBN:0-8186-0635-5

Authors

Shigeo Noda	VLSI Development Division, NEC Corporation, Kawasaki, 211 Japan
Hitoshi Yoshizawa	VLSI Development Division, NEC Corporation, Kawasaki, 211 Japan
Etsuko Fukuda	VLSI Development Division, NEC Corporation, Kawasaki, 211 Japan
Haruo Kato	VLSI Development Division, NEC Corporation, Kawasaki, 211 Japan
Hiroshi Kawanishi	VLSI Development Division, NEC Corporation, Kawasaki, 211 Japan
Takashi Fujii	Faculty of Engineering, Hiroshima University, Higashi-hiroshima, 724 Japan

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 8, 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/317825.317832 What is a DOI?

ABSTRACT

Automatic layout algorithms, placement and routing, for function blocks of CMOS gate arrays are presented. The placement algorithm assigns transistors to basic cells so as to minimize the number of cells used and to minimize the number of interconnections crossing cut-lines. The former objective is achieved by finding a maximum matching and the latter is achieved by iterative interchanges of transistor pairs. A new routing technique based on channel routing methods is introduced to handle the internal cell area. It intends to route with the primary use of the first layer and with the least use of tracks. A program based on the algorithms has been developed and applied to many block designs for up to 200 transistors. The results show that the presented algorithms could realize as good a layout as manual.

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	S. Yabe, et al., "MASTER2:A Hierarchical Layout System for Gate Arrays," Proc. ICCAD, pp46-48, (1983)
	2	H. Miyashita, et al., "Cell Pattern Generation for CMOS Masterslice LSI," Trans. IECE, VoI.J66-C No.12, ppi140-i147 (1983) (in Japanese)
	3	Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
	4	C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
	5	H. Yoshizawa , H. Kawanishi , K. Kani, A heuristic procedure for ordering MOS arrays, Proceedings of the 12th conference on Design automation, p.384-393, January 1975
	6	S. Even, et al., An O(N2"5) Algorithm for Maximum Matching in General Graphs," 16th Annual Symp. on Foundation of Computer Science, ppl00-112 (1975)