Sheng-En David Lin
ABSTRACT
Given a set of pins, a Rectilinear Steiner Minimum Tree (RSMT) connects the pins using only rectilinear edges with the minimum wirelength. RSMT construction is heavily used at various design steps such as floorplanning, placement, routing, and interconnect estimation and optimization, so fast algorithms to construct RSMTs have been developed for many years. However, RSMT construction is an NP-hard problem, so even a fast RSMT construction algorithm such as GeoSteiner [7] is too slow to use in electronic design automation (EDA) tools. FLUTE, a lookup-table-based RSMT construction algorithm, builds and uses a routing topology database to quickly construct RSMTs[5]. However, FLUTE outputs only one RSMT for a given set of pin locations. In this paper, we develop an algorithm to build a database of all RSMTs on the Hanan grid for up to nine pins. The database will be able to help minimize routing congestion and maximize the routability in the design of modern very-large-scale integration layouts.
- Manjit Borah, Robert Michael Owens, and Mary Jane Irwin. 1994. An Edge-Based Heuristic for Steiner Routing, Vol. Vol. 13. 1563--1568. Google Scholar
Digital Library
- Zhen Cao, Tong Jing, Jinjun Xiong, Yu Hu, Lei He, and Xianlong Hong. 2007. DpRouter: A Fast and Accurate Dynamic-Pattern-Based Global Routing Algorithm. 256--261.Google Scholar
- Yen-Jung Chang, Yu-Ting Lee, Jhih-Rong Giao, Pei-Ci Wu, and Ting-Chi Wang. 2010. NTHU-Route 2.0: A Robust Global Router for Modern Designs, Vol. Vol. 29. 1931--1944. Google ScholarDigital Library
- Minsik Cho and David Z. Pan. 2007. BoxRouter: A New Global Router Based on Box Expansion and Progressive ILP, Vol. Vol. 26. 2130--2143. Google ScholarDigital Library
- Chris Chu and Yiu-Chung Wong. 2008. FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design, Vol. Vol. 27. 70--83. Google ScholarDigital Library
- M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: Freeman. Google ScholarDigital Library
- GeoSteiner. {n. d.}. Software for Computing Steiner Trees. http://www.geosteiner.com. (. {n. d.}).Google Scholar
- J. Griffith, G. Robins, J. S. Salowe, and Tongtong Zhang. 1994. Closing the Gap: Near-Optimal Steiner Trees in Polynomial Time, Vol. Vol. 13. 1351--1365. Google ScholarDigital Library
- M. Hanan. 1966. On Steiner's Problem with Rectilinear Distance. SIAM Journal on Applied Mathematics, Vol. Vol. 14. 255--265.Google ScholarCross Ref
- F. K. Hwang, D. S. Richards, and P. Winter. 1992. The Steiner Tree Problem. Elsevier.Google Scholar
- Andrew B. Kahng, I. I. Mandoiu, and A. Z. Zelikovsky. 2003. Highly Scalable Algorithms for Rectilinear and Octilinear Steiner Trees. 827--833. Google ScholarDigital Library
- Ion I. Mandoiu, Vijay V. Vazirani, and Joseph L. Ganley. 2000. A New Heuristic for Rectilinear Steiner Trees, Vol. Vol. 19. 1129--1139. Google ScholarDigital Library
- Michael D. Moffitt. 2008. MaizeRouter: Engineering an Effective Global Router, Vol. Vol. 27. 2017--2026. Google ScholarDigital Library
- Muhammet Mustafa Ozdal and Martin D. F. Wong. 2007. Archer: A History-Driven Global Routing Algorithm. 488--495. Google ScholarDigital Library
- Tai-Hsuan Wu, Azadeh Davoodi, and Jeffrey T. Linderoth. 2009. GRIP: Scalable 3D Global Routing Using Integer Programming. 320--325. Google ScholarDigital Library
- Yue Xu, Yanheng Zhang, and Chris Chu. 2009. FastRoute 4.0: Global Router with Efficient Via Minimization. 576--581. Google ScholarDigital Library
- Hai Zhou. 2004. Efficient Steiner Tree Construction Based on Spanning Graphs, Vol. Vol. 23. 704--710. Google ScholarDigital Library
Index Terms
- Construction of All Rectilinear Steiner Minimum Trees on the Hanan Grid
Recommendations
Construction of All Multilayer Monolithic Rectilinear Steiner Minimum Trees on the 3D Hanan Grid for Monolithic 3D IC Routing
ISPD '19: Proceedings of the 2019 International Symposium on Physical DesignMonolithic three-dimensional~(3D) integration enables stacking multiple ultra-thin silicon tiers in a single package, thereby providing smaller footprint area, shorter wirelength, higher performance, and lower power consumption than conventional planar ...
Efficient obstacle-avoiding rectilinear steiner tree construction
ISPD '07: Proceedings of the 2007 international symposium on Physical designGiven a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called Steiner points), and avoids running through any obstacle to ...
Obstacle-avoiding rectilinear Steiner tree construction
ICCAD '08: Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided DesignIn today's VLSI designs, there can be many blockages in a routing region. The obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem has become an important problem in the physical design stage of VLSI circuits. This problem has attracted a ...
Comments