Prim-Dijkstra Revisited: Achieving Superior Timing-driven Routing Trees

ABSTRACT

The Prim-Dijkstra (PD ) construction [1] was first presented over 20 years ago as a way to efficiently trade off between shortest-path and minimum-wirelength routing trees. This approach has stood the test of time, having been integrated into leading semiconductor design methodologies and electronic design automation tools. PD optimizes the conflicting objectives of wirelength (WL) and source-sink pathlength (PL) by blending the classic Prim and Dijkstra spanning tree algorithms. However, as this work shows, PD can sometimes demonstrate significant suboptimality for both WL and PL. This quality degradation can be especially costly for advanced nodes because (i) wire delays form a much larger component of total stage delay, i.e., timing-driven routing is critical, and (ii) modern designs are severely power-constrained (e.g., mobile, IoT), which makes low-capacitance wiring important. Consequently, achieving a good timing and power tradeoff for routing is required to build a market-leading product[2]. This work introduces a new problem formulation that incorporates the total detour cost in the objective function to optimize the detour to every sink in the tree, not just the worst detour. We then propose a new PD-II construction which directly improves upon the original PD construction by repairing the tree to simultaneously reduce both WL and PL. The PD-II approach achieves improvement for both objectives, making it a clear win over PD, for virtually zero additional runtime cost. PD-II is a spanning tree algorithm (which is useful for seeding global routing); however, since Steiner trees are needed for timing estimation, this work also includes a post-processing algorithm called DAS to convert PD-II trees into balanced Steiner trees. Experimental results demonstrate that this construction outperforms the recent state-of-the-art academic tool, SALT [36], for high-fanout nets, achieving up to 36.46% PL improvement with similar WL on average for 20K nets of size ≥ 32 terminals from DAC 2012 contest benchmark designs [37].

References

1. C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng and D. Karger, "Prim-Dijkstra Tradeoffs for Improved Performance-driven Routing Tree Design", IEEE TCAD 14(7) (1995), pp. 890--896.
2. ITRS 2013 Edition Report - Interconnect, https://www.semiconductors.org/clientuploads/Research_Technology/ITRS/2013/2013Interconnect.pdf, 2013.
3. S. K. Rao, P. Sadayappan, F. K. Hwang and P. W. Shor,"The Rectilinear Steiner Arborescence Problem", Algorithmica 7(2) (1992), pp. 277--88.
4. C. J. Alpert, Personal Communication, Nov. 2016.
5. R. C. Prim,"Shortest Connecting Networks and Some Generalizations", Bell System Tech. J. 36 (1957), pp. 1389--1401.
6. E. W. Dijkstra,"A Note on Two Problems in Connexion with Graphs", Numerische Mathematik 1 (1959), pp. 269--271.
7. J. M. Ho, G. Vijayan and C. K. Wong,"New Algorithms for the Rectilinear Steiner Tree Problem", IEEE TCAD 9(2) (1990), pp. 185--193.
8. J. B. Kruskal Jr.,"On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem", Proc. Amer. Math. Soc. 7(1) (1956), pp. 48--50.
9. C. J. Alpert, A. B. Kahng, C. N. Sze and Q. Wang,"Timing-driven Steiner Trees are (Practically) Free", Proc. DAC, 2006, pp. 389--392.
10. J. Cong, A. B. Kahng, G. Robins and M. Sarrafzadeh,"Provably Good Performance-driven Global Routing", IEEE TCAD 11(6) (1992), pp. 739--752.
11. G. Kortsarz and D. Peleg,"Approximating Shallow-light Trees", Proc. SODA, 1997, pp. 103--110.
12. S. Khuller, B. Raghavachari and N. Young,"Balancing Minimum Spanning Trees and Shortest-path Trees", Proc. SODA, 1993, pp. 243--250.
13. J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh and C.K. Wong,"Performance-driven Global Routing for Cell Based ICs", Proc. ICCD, 1991, pp. 170--173.
14. A. Lim, S.-W. Cheng and C.-T. Wu,"Performance Oriented Rectilinear Steiner Trees", Proc. DAC, 1993, pp. 171--175.
15. A. B. Kahng and G. Robins,"A New Class of Iterative Steiner Tree Heuristics with Good Performance", IEEE TCAD 11(7) (1992), pp. 893--902.
16. M. Borah, R. M. Owens and M. J. Irwin,"An Edge-based Heuristic for Steiner Routing", IEEE TCAD 13(12) (1994), pp. 1563--1568.
17. W. Shi and C. Su, "The Rectilinear Steiner Arborescence Problem is NP-complete", SIAM J. Comp. 35(3) (2006), pp. 729--740.
18. J. Cong, K. S. Leung and D. Zhou,"Performance-driven Interconnect Design Based on Distributed RC Delay Model", Proc. DAC, 1993, pp. 606--611.
19. A. B. Kahng and G. Robins, On Optimal Interconnections for VLSI, Kluwer Academic Publishers,1995.
20. M. Hanan,"On Steiner's Problem with Rectilinear Distance", SIAM J. Appl. Math. 14(2) (1966), pp. 255--265.
21. L. Scheffer, Bookshelf RMST code,http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/RMST/.
22. L. J. Guibas and J. Stolfi, "On Computing All Northeast Nearest Neighbors in the L1 Metric", Information Processing Letters 17 (1983), pp. 219--223.
23. A. Naamad, D. T. Lee and W.-L. Hsu,"On the Maximum Empty Rectangle Problem", Discrete Applied Mathematics 8 (1984), pp. 267--277.
24. J. Griffith, G. Robins, J. S. Salowe and T. Zhang,"Closing the Gap: Near-optimal Steiner Trees in Polynomial Time", Proc. TCAD, 1994, pp. 1351--1365.
25. L. He, S. Yao, W. Deng, J. Chen and L. Chao,"Interconnect Routing Methods of Integrated Circuit Designs", US Patent 8386984, Feb. 2013.
26. S. Bose,"Methods and Systems for Placement and Routing", US Patent 8332793, Dec. 2012.
27. R. F. Hentschke, M. de Oliveira Johann, J. Narasimhan and R. A. de Luz Reis,"Methods and Apparatus for Providing Flexible Timing-driven Routing Trees", US Patent 8095904, Jan. 2012.
28. G. M. Furnish, M. J. LeBrun and S. Bose, "Tunneling as a Boundary Congestion Relief Mechanism", US Patent 7921393, Apr. 2011.
29. G. M. Furnish, M. J. LeBrun and S. Bose,"Node Spreading Via Artificial Density Enhancement to Reduce Routing Congestion", US Patent 7921392, Apr. 2011.
30. P. Saxena, V. Khandelwal, C. Qiao, P-H. Ho, J. C. Lin and M. A. Iyer,"Interconnect-driven Physical Synthesis using Persistent Virtual Routing", US Patent 7853915, Dec. 2010.
31. C. J. Alpert, J. Hu and P. H. Villarrubia,"Practical Methodology for Early Buffer and Wire Resource Allocation", US Patent 6996512, Feb. 2006.
32. C. J. Alpert, R. G. Gandham, J. Hu, S. T. Quay and A. J. Sullivan,"Apparatus and Method for Determining Buffered Steiner Trees for Complex Circuits", US Patent 6591411, Jul. 2003.
33. C. Chu and Y.C. Wong, "FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design", IEEE TCAD 27(1) (2008), pp.70--83.
34. M. Elkin and S. Solomon, "Steiner Shallow-light Trees are Exponentially Lighter than Spanning Ones", SIAM J. Comp. 44(4) (2015),pp. 996--1025.
35. R. Scheifele, "Steiner Trees with Bounded RC-delay", Algorithmica78(1) (2017), pp. 86--109.
36. G. Chen, P. Tu and E. F. Y. Young, "SALT: Provably Good Routing Topology by a Novel Steiner Shallow-Light TreeAlgorithm", Proc. ICCAD, 2017.
37. N. Viswanathan, C. J. Alpert, C. C. N. Sze, Z. Li and Y. Wei, "The DAC 2012 Routability-driven Placement Contest and Benchmark Suite", Proc. DAC, 2012, pp. 774--782.
38. J. Lu, H. Zhuang, P. Chen, H. Chang, C.-C. Chang, Y.-C. Wong, L. Sha, D. Huang, Y. Luo, C.-C. Teng and C.-K. Cheng, "ePlace-MS: Electrostatics based Placement for Mixed-Size Circuits", IEEE TCAD 34(5) (2015), pp. 685--698.

Index Terms

• Hardware

  • Electronic design automation

    • Modeling and parameter extraction

    • Physical design (EDA)

      • Wire routing