Refined single trunk tree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Refined single trunk tree: a rectilinear steiner tree generator for interconnect prediction

Full text

Pdf (190 KB)

Source

International Workshop on System-Level Interconnect Prediction archive
Proceedings of the 2002 international workshop on System-level interconnect prediction table of contents

San Diego, California, USA

SESSION: Using Prediction for Performance Optimization and Estimation table of contents

Pages: 85 - 89

Year of Publication: 2002

ISBN:1-58113-481-9

Authors

Hongyu Chen	University of California, San Diego, La Jolla, CA
Changge Qiao	Synopsys, Inc., Mountain View, CA
Feng Zhou	University of California, San Diego, La Jolla, CA
Chung-Kuan Cheng	University of California, San Diego, La Jolla, CA

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 23, Citation Count: 8

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

ABSTRACT

We devised an efficient and accurate estimation of the rectilinear Steiner minimal tree (SMT), which is an essential building block for on-line and posteriori interconnect prediction. We proposed a new rectilinear Steiner tree generator, Refined Single Trunk Tree (RST-T). Compared with traditional minimal spanning tree based Steiner tree heuristics, RST-T has several advantages. 1. The algorithm runs very fast. Experiments show that RST-T algorithm runs 50 times faster than Prim's minimum spanning tree algorithm for 10-pin nets. 2. The RST-T provides excellent wire length estimation of the optimal solutions. For the nets of no more than 10 pins, the average wire length of RST-T is within 6 percent of the optimal solutions. Actually, for the nets with five or less pins, the wire length of RST-T is optimal. 3. The topology of RST-T remains stable when pin locations deviate. Experiments show that the topologies of routing trees produced by the proposed algorithm is much more stable than the minimum spanning tree and iterative 1-Steiner heuristics.

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	C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, and D. Karger, "Prim-Dijkstra tradeoffs for improved performancedriven routing tree design," IEEE Trans. on CAD 14(7), July 1995, pp.890-896.
	2	M. Borah, R. M. Owens, and M. J. Irwin, "An edge-based heuristic for Steiner routing," in IEEE Trans. on CAD, vol. 13, no. 12, pp.1563-1568, Dec. 1994
	3	A. E. Caldwell, A. B. Kahng, S. Mantic, I. L. Markov, and A. Zelikovsky, "On Wirelength Estimations for Row-Based Placement", IEEE Trans. on CAD 18(9), (1999), pp. 1265- 1278.
	4	A. H. Chao, E. M. Nequist, and T. D. Vuong, "Direct Solution of Performance Constraints During Placement," in Proc. IEEE Custom Integrated Circuits Conference, 1995 pp27.2.1-27.2.4
	5	J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong, "Provably Good Performance-Driven Global Routing", IEEE Trans. on CAD 11(6), June 1992, pp. 739- 752.
	6	M. R. Garey, R. L. Graham, and D. S. Johnson, "The Complexity of computing Steiner minimal Trees," in SIAM Journal on Applied Mathematics 32:835-859, 1977
	7	T. Hamada , C.-K. Cheng , P. M. Chau, A wire length estimation technique utilizing neighborhood density equations, Proceedings of the 29th ACM/IEEE conference on Design automation, p.57-61, June 08-12, 1992, Anaheim, California, United States
	8	M. Hanan, "On Steiner's Problem with Rectilinear Distance", in SIAM J on App Math 14:255-265, 1966
	9	N. Hasan, G. Vijayan, and C. K. Wong, "A Neighborhood Improvement Algorithm for Rectilinear Steiner Trees," in Proc. ICCAS1990 pp2869-2872
	10	F. K. Hwang, "On Steiner minimal trees with rectilinear distance," in SIAM J. Appl. Math., pp. 104-114, Jan. 1976
	11	F. K. Hwang, D. S. Richards, and P. Winter, "The Steiner Tree Problem," North Holland Press, 1992.
	12	A. B. Kahng and G. Robins, "A New Class of Iterative Steiner Tree Heuristics with Good Performance", IEEE Trans. on CAD 11(7), July 1992, pp. 893-902
	13	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	14	J. S. Salowe and D. M. Warme, "Thirty-Five-Point Rectilinear Steiner Minimal Trees in a Day", in Networks: An International Journal, volume 25, 1995
	15	M. Sarrafzadeh and C. K. Wong, "Hierarchical Steiner tree construction in uniform orientations," in IEEE Trans. on CAD, vol. 11, no. 9, pp. 1095-1103, Sept. 1992
	16	J. Soukup, "circuit layout," Proc. IEEE, Oct. 1981, pp. 1281- 1304
	17	A. Srinivasan, K. Chaudhary, and E. S. Kuh, "RITUAL: An Algorithm for Performance-Driven Placement of Cell-Based Ics," IEEE Trans. CAS, vol. CAS-39, pp. 825--840, Nov. 1992
	18	http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/RMST

CITED BY 8

	Saurabh N. Adya , Mehmet C. Yildiz , Igor L. Markov , Paul G. Villarrubia , Phiroze N. Parakh , Patrick H. Madden, Benchmarking for large-scale placement and beyond, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	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
	Hsin-Hsiung Huang , Hui Yu Huang , De-Jing Huang , Tsai-Ming Hsieh, An efficient rectilinear Steiner tree algorithm with obstacles, Proceedings of the 5th WSEAS International Conference on Circuits, Systems, Electronics, Control & Signal Processing, p.54-59, November 01-03, 2006, Dallas, Texas
	Ali Jahanian , Morteza Saheb Zamani, Improved timing closure by early buffer planning in floor-placement design flow, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	Minsik Cho , Hua Xiang , Ruchir Puri , David Z. Pan, TROY: track router with yield-driven wire planning, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	C. Chu, FLUTE: fast lookup table based wirelength estimation technique, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.696-701, November 07-11, 2004
	Ali Jahanian , Morteza Saheb Zamani, Using metro-on-chip in physical design flow for congestion and routability improvement, Microelectronics Journal, v.39 n.2, p.261-274, February, 2008
	Prashant Saxena , Vishal Khandelwal , Changge Qiao , Pei-Hsin Ho , J.-C. Lin , Mahesh A. Iyer, On improving optimization effectiveness in interconnect-driven physical synthesis, Proceedings of the 2009 international symposium on Physical design, March 29-April 01, 2009, San Diego, California, USA