Circuit-simulated obstacle-aware Steiner routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Circuit-simulated obstacle-aware Steiner routing

Full text

Pdf (439 KB)

Source

ACM Transactions on Design Automation of Electronic Systems (TODAES) archive
Volume 12 , Issue 3 (August 2007) table of contents

Article No. 28

Year of Publication: 2008

ISSN:1084-4309

Authors

Yiyu Shi	University of California, Los Angeles, Los Angeles, CA
Paul Mesa	University of California, Los Angeles, Los Angeles, CA
Hao Yu	University of California, Los Angeles, Los Angeles, CA
Lei He	University of California, Los Angeles, Los Angeles, CA

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	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/1255456.1255465 What is a DOI?

ABSTRACT

This article develops circuit-simulated routing algorithms. We model the routing graph by an RC network with terminals as inputs, and show that the faster an output reaches its peak, the higher the possibility for the corresponding Hanan or escape node to become a Steiner point. This enables us to select Steiner points and then apply any minimum spanning tree algorithm to obtain obstacle-free or obstacle-aware Steiner routing. Compared with existing algorithms, our algorithms have significant gain on either wirelength or runtime for obstacle-free routing, and on both wirelength and runtime for obstacle-aware routing.

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	Akers, S. B. 1967. A modification of Lee's path connection algorithm. IEEE Trans. Electron. Comput. 16, 4, 97--98.
	2	Christoph Albrecht, Provably good global routing by a new approximation algorithm for multicommodity flow, Proceedings of the 2000 international symposium on Physical design, p.19-25, May 2000, San Diego, California, United States [doi>10.1145/332357.332368]
	3	Atkinson, D. and van Steenwijk, F. J. 1999. Infinite resistive lattices. Am. J. Phys., 486--492.
	4	Chris Chu , Yiu-Chung Wong, Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055145]
	5	Ganley, J. L. and Cohoon, J. P. 1994. Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles. In Proceedings of the ISCAS.
	6	Garey, M. R. and Johnson, D. S. 1977. The rectilinear Steiner tree problem is NP-complele. SIAM J. Appl. Math., 826--834.
	7	Hadlock. 1977. A shortest path algorithm for grid graphs. Networks, 323--334.
	8	David W. Hightower, A solution to line-routing problems on the continuous plane, Proceedings of the 6th annual conference on Design Automation, p.1-24, January 1969 [doi>10.1145/800260.809014]
	9	Yu Hu , Tong Jing , Xianlong Hong , Zhe Feng , Xiaodong Hu , Guiying Yan, An-OARSMan: obstacle-avoiding routing tree construction with good length performance, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120732]
	10	Hwang, F. K., Richards, D. S., and Winter, P. 1992. The Steiner tree problem. of Annals of Discrete Mathematcis, vol. 53, North-Holland, Amsterdam, The Netherlands.
	11	Andrew B. Kahng , Ion I. Măndoiu , Alexander Z. Zelikovsky, Highly scalable algorithms for rectilinear and octilinear Steiner trees, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119955]
	12	Kahng, A. B. and Robins, G. 1992. A new class of iterative Steiner tree heuristics with good performance. IEEE Trans. Comput. Aided Des. 11, 7, 893--902.
	13	Kahng, A. B. and Robins, G. 1995. On Optimal Interconnections for VLSI. Kluwer Academic, Boston, MA.
	14	Magma. 2007. The Magma Website. http://www:magma--da:com/c/@ei_ci_2hsu:41ji/pages/productsintro:html.
	15	Mandoiuand, I. I., Vazirani, V. V., and Ganley, J. L. 2000. A new heuristic for rectilinear Steiner trees. IEEE Trans. Comput. Aided Des.
	16	Mikami, K. and Tabuchi, K. 1968. A computer program for optimal routing printed circuit connectors. In Proceedings of the IFIPS.
	17	Odabasioglu, A., Celik, M., and Pileggi, L. 1998. PRIMA: Passive reduced-order interconnect macro-modeling algorithm. IEEE Trans. Comput. Aided Des., 645--654.
	18	Haifeng Qian , Sani R. Nassif , Sachin S. Sapatnekar, Random walks in a supply network, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775860]
	19	F. Rubin, The Lee Path Connection Algorithm, IEEE Transactions on Computers, v.23 n.9, p.907-914, September 1974 [doi>10.1109/T-C.1974.224054]
	20	Yiyu Shi , Paul Mesa , Hao Yu , Lei He, Circuit simulation based obstacle-aware Steiner routing, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147011]
	21	J. Soukup, Fast maze router, Proceedings of the 15th conference on Design automation, p.100-102, June 19-21, 1978, Las Vegas, Nevada, United States
	22	Warme, D. W. et al. Geosteiner 3.1. package.
	23	Martin Zachariasen , Pawel Winter, Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An Exact Algorithm, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.282-295, January 15-16, 1999
	24	Zelikovsky, A. 1993. An 11/6-approximation for the network Steiner tree problem. Algorithmica, 463--470.
	25	Zheng, S. Q., Lim, J. S., and Iyengar, S. S. 1996. Finding obstacle-avoiding shortest paths using implicit connection graphs. IEEE Trans. Comput. Aided Des., 103--110.
	26	Hai Zhou, Efficient Steiner tree construction based on spanning graphs, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640034]