A Modified Edge Removal Stiener Tree Heuristic for Global Routing in VLSI Design

Article Sidebar

PDF
Published: Dec 27, 2008
DOI: https://doi.org/10.37936/ecti-eec.201082.172094
Keywords:
Steiner tree Congestion Global Routing Rectilinear Distance

Main Article Content

Apichat Terapasirdsin
Department of Computer Engineering, King Mongkut's University of Technology Thonburi
William F. Rotach
Department of Computer Science, State University of New York at Binghamton
Naruemon Wattanapongsakorn
Department of Computer Engineering, King Mongkut's University of Technology Thonburi
Patrick H. Madden
Department of Computer Science, State University of New York at Binghamton

Abstract

Routing is a key stage for VLSI physical design. Steiner tree construction is a well studied topic in design automation. There have been a number of significant theoretical advances in the past few years. The focus of this paper is on combining the speed and solution quality of a high quality Steiner heuristic with the reality of modern routing. Practical designs contain routing congestion and blockages; routing is implemented across multiple layers. Each routing layer has preferred directions, and connecting vias have significant cost. In a modern design, many trees are in competition with each other for scarce routing resources. The objective is not to simply build trees with the lowest length; they must also be low cost. We present an approach that is as fast as spanning tree construction, while accurately modeling routing costs. Our work extends an earlier Steiner tree heuristic algorithm by adding the ability to minimize the routing congestion without altering the computational complexity of the underlying algorithm. We compare our CAST algorithm with the capacitated minimum spanning tree (CMST) and the ER algorithm finding that our approach offers impressive reduction in congestion cost in average about 23.1% and 63.4%, respectively.

Article Details

How to Cite
Terapasirdsin, A., Rotach, W. F., Wattanapongsakorn, N., & Madden, P. H. (2008). A Modified Edge Removal Stiener Tree Heuristic for Global Routing in VLSI Design. ECTI Transactions on Electrical Engineering, Electronics, and Communications, 8(2), 179–186. https://doi.org/10.37936/ecti-eec.201082.172094
Issue
Vol. 8 No. 2 (2010): Regular Issue
Section
Research Article

This journal provides immediate open access to its content on the principle that making research freely available to the public supports a greater global exchange of knowledge.

- Creative Commons Copyright License

The journal allows readers to download and share all published articles as long as they properly cite such articles; however, they cannot change them or use them commercially. This is classified as CC BY-NC-ND for the creative commons license. 

- Retention of Copyright and Publishing Rights

The journal allows the authors of the published articles to hold copyrights and publishing rights without restrictions.

References

[1] J. Cong, L. He, C.K. Koh, and P.H. Madden, "Performance optimization of VLSI interconnect layout," Integration, the VLSI Journal 21, pp.1-94, 1996.

[2] M.C. Yildiz, and P.H. Madden, "Preferred direction multi-layer Steiner trees," IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems 21, pp.1368-1372, Nov. 2002.

[3] M. Borah, R.M. Owens, and M.J. Irwin, "An edge-based heuristic for Steiner routing," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems 13, pp. 1563-1568, Dec. 1994.

[4] C.Chiang, C.K. Wong, and M. Sarrafzadeh, "A weighted Steiner tree-based global router with simultaneous length and density minimization," Computer-Aided Design of Integrated Circuits and Systems, IEEE Trans, Vol. 13, Issue 12, pp.1461 - 1469, Dec 1994.

[5] R.C. Prim, "Shortest connecting networks," Bell System Technical Journal 31, pp.1398-1401, 1957.

[6] J.B. Kruskal, "On the shortest spanning subtree of a graph," Proc. American Math Society 7, pp.48-50, 1956.

[7] M. Hanan, "On Steiner's problem with rectilinear distance," SIAM Journal of Applied Mathematics 14, pp.255-265, 1966.

[8] A.B. Kahang, and G. Robins, "A new class of iterative Steiner tree heuristics with good performance," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems 11, pp. 893-902, Jul. 1992.

[9] D.M. Warme, P. Winter, and M. Zachariasen, "Exact solutions to large-scale plane Steiner tree problems," In Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA-99). pp.979-980, 1999.

[10] M.M Ozdal, and M.D.F. Wong, "A history-driven global routing algorithm," In Proc. Of IEEE/ACM Int. Conf. on Computer-aided Design, California, pp. 488-495, 2007.

[11] C. Chu, "FLUTE: fast lookup table based wire length estimation technique," In Proc. Int. Conf. on Computer Aided Design, pp. 696-701, 2004.

[12] J. Lou, S. Krishanmoorthy, and H.S. Sheng, "Estimating routing congestion using probabilistic analysis," In Proc. Int. Symp. on Physical Design, pp.112-117, 2001.

[13] R. Linsker, "An iterative-improvement penalty function-driven wire routing system," IBM journal of research and development 28, pp.613-624, Sept. 1984.

[14] E. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik 1, pp.269-271, 1959.

[15] M. Minoux, "E±cient greedy heuristics for Steiner tree problems using reoptimization and supermodularity," INFORMS Journal of Computing 28, pp.221-233, Aug. 1990.

[16] J.Westra, C. Bartels, and P. Groeneveld, "Probabilistic congestion prediction," In Proc. Int. Symp. on Physical Design, pp.204-209. 2004.

[17] A. Agnihotri, and P.H. Madden, "Congestion reduction in traditional and new routing architectures," In Proc. Great Lakes Symposium on VLSI, pp.211-214, 2003.

[18] R.T. Hadsell, and P.H. Madden, "Improved global routing through congestion estimation," In Proc. Design Automation Conf, pp. 28-31, 2003.

[19] M.Cho, and D. Z. Pan, "Box router: a new global router based on box expansion and progressive ILP," In Proc. Design Automation Conf, pp 24-28, Jul. 2006.

[20] X. Yang, M. Wang, R. Kastner, S. Ghiasi and M. Sarrafzadeh, "Congestion Reduction during Placement with Provably Good Approximation Bound," ACM Transactions on Design Automation of Electronic Systems, July 2003.

[21] J. Cong, and P. H. Madden, "Performance driven multi-layer general area routing for PCB/MCM designs," In Proc. Design Automation Conf, pp. 356-361, 1998.

[22] R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh, "An extract algorithm for coupling free routing," In Proc. Int Symp. On Physical Design, pp. 10-15, 2001.

[23] C. Albrecht, "Global routing by new approximation algorithms for multicommodity flow," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems 20(5), pp622-631. May 2001.

[24] A.R Agnihotri ,and P. H. Madden, "Fast analytic placement using minimum cost flow," In Proc. Design Automation Conf ASP-DAC, pp.128-134, Jan. 2007.

[25] J.Westra, P. Groeneveld, T. Yan, and P.H. Madden, "Global routing: Matrices, benchmarks, and tools.," In IEEE DATC Electronics Design Process, Apr. 2005.

[26] R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh, "Pattern routing: use and theory for increasing predictability and avoiding coupling," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems 21, Jul. 2002.

[27] R.C. Prim, "Shortest connecting network," Bell System Technical Journal 31, pp. 1398-1401, 1957.

[28] N. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, 1999.