Three-layer bubble-sorting-based nonManhattan channel routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Three-layer bubble-sorting-based nonManhattan channel routing

Full text

Pdf (86 KB)

Source

ACM Transactions on Design Automation of Electronic Systems (TODAES) archive
Volume 5 , Issue 3 (July 2000) table of contents

Pages: 726 - 734

Year of Publication: 2000

ISSN:1084-4309

Author

Jin-Tai Yan

Chung Hua Univ., Taiwan, R.O.C.

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 18, 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/348019.350285 What is a DOI?

ABSTRACT

It is well known that a nonManhattan channel router can use fewer routing tracks, and is never worse than a Manhattan router in a channel. To my knowledge, a three-layer bubble-sorting-based nonManhattan channel routing problem is always solved by the solution in a two-layer bubble-sorintg-based nonManhattan channel routing problem. Recently, an O(kn2) heuristic algorithm [Chaudhary et al. 1991] and an O(kn2) optimal algorithm [Chen et al. 1994] have been proposed, where k is the number of two-layer routing tracks and n is the number of terminals in a bubble-sorintg-based nonManhattan channel. In this paper we propose an optimal three-layer bubble-sorintg-based nonManhattan routing algorithm to minimize the number of three-layer routing tracks. Furthermore, the time complexity of theis optimal algorithm is proven to be in O(hn) time, where h is the number of three-layer routing tracks and n is the number of terminals in a bubble-sorting-based nonManhattan channel.

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	Michael Burstein , Richard Pelavin, Hierarchical channel router, Proceedings of the 20th conference on Design automation, p.591-597, June 27-29, 1983, Miami Beach, Florida, United States
	2	CHAUDHARY, K. AND ROBINSON, P. 1991. Channel routing by sorting. IEEE Trans. Comput.- Aided Des. 10 (June 1991), 754-760.
	3	CHEN, R. C. Y., Hou, C. Y., AND SINGH, U. 1994. Optimal algorithms for bubble sort based non-Manhattan channel routing. IEEE Trans. Comput.-Aided Des. 13, 5 (May 1994), 603-609.
	4	David N. Deutsch, A “Dogleg” channel router, Proceedings of the 13th conference on Design automation, p.425-433, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804843]
	5	Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805069]
	6	LODI, E., LuccIo, F., AND PAGLI, L. 1989. A preliminary study of a diagonal channel-routing model. Algorithmica 4, 585-597.
	7	Ronald L. Rivest , Charles M. Fiduccia, A “greedy” channel router, Proceedings of the 19th conference on Design automation, p.418-424, January 1982
	8	Deborah C. Wang, Novel routing schemes for IC layout part I: Two-layer channel routing, Proceedings of the 28th conference on ACM/IEEE design automation, p.49-53, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127626]
	9	YAN, J. T. 1999. An improved optimal algorithm for bubble-sorting-based non-Manhattan channel routing. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 18, 2, 163-171.
	10	YOSHIMURA, T. AND KUH, E. S. 1982. Efficient algorithms for channel routing. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 1, 1 (Jan.), 25-35.