A multi-layer router utilizing over-cell areas

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A multi-layer router utilizing over-cell areas

Full text

Pdf (682 KB)

Source

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

Orlando, Florida, United States

Pages: 704 - 708

Year of Publication: 1991

ISBN:0-89791-363-9

Authors

Evagelos Katsadas	Department of Electrical Engineering, University of Rochester, Rochester, New York
Edwin Kinnen	Department of Electrical Engineering, University of Rochester, Rochester, New York

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 10, Citation Count: 0

Additional Information:

abstract references 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/123186.123446 What is a DOI?

ABSTRACT

A new methodology is presented for the solution of the multilayer routing problem that has the potential to outperform channel based multi-layer routing algorithms by expanding the routing regions to include areas over the cells. It is assumed that four routing layers are available. Routing is completed in two steps; a selected group of nets is routed in the between-cell areas using existing channel routing algorithms and the first two routing layers. Then the remaining nets are routed over the entire layout area, between-cell and over-cell areas, using a new two-dimensional router and the next two routing layers. The router used for over-cell routing recognizes arbitrarily sized obstacles, for example, due to power and ground routing or sensitive circuits in the underlying cells. The proposed router was tested on a number of macro-cell layout examples. Advantages of dedicating two routing layers for over-cell routing is illustrated. Results show a significant reduction in total layout area, wire length and number of via when compared to results obtained using two-layer or multi-layer channel routing methods.

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.K. Chen and M. L. Liu, 'Three-layer channel routing," IEEE Transactions on Computer-Aided Design, vol. CAD- 3, no. 2, pp. 156-163, 1984.
	2	T. Yoshimura and E. S. Kuh, "Efficient algorithms for channel routing," 1EEE Transactions on Computer-Aided Design, vol. CAD-I, no. 1, pp. 25-35, 1982.
	3	J. Cong, D. F. Wong, and C. L. Liu, "A new approach to three- or four-layer channel routing," IEEE Transactions on Computer-Aided Design, vol. CAD-7, no. 10, pp. 1094- 1104, 1988.
	4	P. Bruell and P. Sun, "A 'greedy' three layer channel router," in Proe. IEEE Intern. Conf. on Computer-Aided Design, 1985, pp. 298-300.
	5	Ronald L. Rivest , Charles M. Fiduccia, A “greedy” channel router, Proceedings of the 19th conference on Design automation, p.418-424, January 1982
	6	D. Braun et al., '"Techniques for multilayer routing," IEEE Transactions on Computer-Aided Design, vol. CAD-7, no. 6, pp. 698-711, 1988.
	7	R.I. Greenberg and A. L. Sangiovanni-Vincemelli, "MulCh: A multi-layer router using one, two, and tree layer partitions," in Proc. IEEE Intern. Conf. on Computer-Aided Design, 1988, pp. 88-91.
	8	R. J. Enbody , H. C. Du, Near-optimal n-layer channel routing, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.708-714, July 1986, Las Vegas, Nevada, United States
	9	S.E. Hambrusch, "Channel routing algorithms for overlap models," IEEE Transactions on Computer-Aided Design, vol. CAD-4, pp. 23-30, 1986.
	10	C.Y. Lee, "An algorithm.for path connections and its applications," 1RE Transactions on Electronic Computers, vol. EC-10, pp. 346-365, 1961.
	11	Kenneth J. Supowit, A minimum-impact routing algorithm, Proceedings of the 19th conference on Design automation, p.104-112, January 1982
	12	Chi-Ping Hsu, A new two-dimensional routing algorithm, Proceedings of the 19th conference on Design automation, p.46-50, January 1982
	13	Malgorzata Marek-Sadowska, Two-dimensional router for double layer layout, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.117-123, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317844]
	14	M.R. Garey and D. S. Johnson, "The rectilinear Steiner tree problem is NP-complete," SIAM Journal of Applied Mathematics, vol. 32, no. 3, pp. 37-58, 1977.
	15	F. K. Hwang, An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees, Journal of the ACM (JACM), v.26 n.2, p.177-182, April 1979 [doi>10.1145/322123.322124]
	16	J.H. Lee, N.. K. Bose, arid P. K. Hwang, "Use of S teiner's problem in suboptimal routing in rectilinear metric," 1EEE Transactions on Circuits and Systems, vol. CAS-23, no. 7, pp. 470-476, 1976.
	17	K. Lee and C. Sechen, "A new global router for row-based layout," in Proc. IEEE Intern. Conf. on Computer-Aided Design, 1988, pp. 180-183.
	18	L Ho, O. Vijayart, and C. K. Wong, "New algorithms for the. rectilinear Steiner tree problem," IEEE Transactions on Computer-Aided Design, vol. 9, no. 2, pp. 185-193, 1990.
	19	R.C. Prim, "Shortest connection networks and some generalizations," Bell System Techrdcal Journal, vol. 36, no. 6, pp, 1389-1401, 1957.
	20	B. Preas, Benchmarks for cell-based layout systems, Proceedings of the 24th ACM/IEEE conference on Design automation, p.319-320, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37936]