Jin Hu
Igor L. Markov
ABSTRACT
To ensure chip manufacturability, all routes must be completed without violations. Furthermore, the chip's power consumption and performance are determined by the length of its routed wires. Therefore, our work focuses on minimizing wirelength. Our key innovations include: (1) a novel branch-free representation (BFR) for routed nets, (2) a trigonometric penalty function (TPF), (3) dynamic adjustment of Lagrange multipliers (DALM), (4) cyclic net locking (CNL), and (5) aggressive lower-bound estimates (ALBE) for A*-search, resulting in faster routing. We complete all routable ISPD 2008 contest benchmarks and re-placed adaptec suite without violation and produce shorter routes.
- T. F. Chan, J. Cong, J. Shinnerl, K. Sze, M. Xie, "mPL6: Enhanced Multilevel Mixed-size Placement with Congestion Control," Modern Circuit Placement, pp. 247--288, 2007.Google Scholar
Cross Ref
- Y.-J. Chang, Y.-T. Lee, T.-C. Wang, "NTHU-Route 2.0: A Fast and Stable Global Router," ICCAD, pp. 338--343, 2008. Google ScholarDigital Library
- H.-Y. Chen, C.-H. Hsu, Y.-W. Chang, "High-performance Global Routing with Fast Overflow Reduction," ASPDAC, pp. 582--587,2009. Google ScholarDigital Library
- M. Cho, K. Lu, K. Yuan, D. Z. Pan, "BoxRouter 2.0: Architecture and Implementation of a Hybrid and Robust Global Router," ICCAD, pp. 503--508, 2007. Google ScholarDigital Library
- R. Hadsell, P. Madden, "Improved Global Routing through Congestion Estimation," DAC, pp. 28--31, 2003. Google ScholarDigital Library
- J. Hu, J. A. Roy, I. L. Markov, "Sidewinder: A Scalable ILP-based Router," SLIP, pp. 73--80, 2008. Google ScholarDigital Library
- ISPD 2007 Global Routing Contest and benchmark suite. http://www.sigda.org/ispd2007/rcontest/Google Scholar
- ISPD 2008 Global Routing Contest and benchmark suite. http://www.sigda.org/ispd2008/contests/ispd08rc.htmlGoogle Scholar
- Z.-W. Jiang, B.-Y. Su, Y.-W. Chang, "Routability-driven Analytic Placement by Net Overlapping Removal for Large-scale Mixed-size Designs," DAC, pp. 167--172, 2008. Google ScholarDigital Library
- S. Lee, M. D. F. Wong, "Timing-driven Routing for FPGAs based on Lagrangian Relaxation," IEEE TCAD, vol. 22(4), pp. 506--510, 2003. Google ScholarDigital Library
- T.-H. Lee, T.-C. Wang, "Robust Layer Assignment for Via Optimization in Multi-layer Global Routing," ISPD, pp. 159--166, 2009. Google ScholarDigital Library
- L. McMurchie, C. Ebeling, "PathFinder: A Negotiation-based Performance-driven Router for FPGAs," FPGA, 1995. Google ScholarDigital Library
- M. Moffitt, "MAIZEROUTER: Engineering an Effective Global Router," IEEE TCAD, vol. 27(11), pp. 2017--2026, 2008. Google ScholarDigital Library
- D. Muller, "Optimizing Yield in Global Routing," ICCAD, pp. 480--486, 2006. Google ScholarDigital Library
- M. Pan, C. Chu, "FastRoute: A Step to Integrate Global Routing into Placement," ICCAD, pp. 464--471, 2006. Google ScholarDigital Library
- M. Pan, C. Chu, "IPR: An Integrated Placement and Routing Algorithm," DAC, pp. 59--62, 2007. Google ScholarDigital Library
- M. Pan, C. Chu, "FastRoute 2.0: A High-quality and Efficient Global Routing," ASPDAC, pp. 250--255, 2007. Google ScholarDigital Library
- J. A. Roy, I. L. Markov, "High-performance Routing at the Nanometer Scale," TCAD, vol. 27(6), pp. 1066--1077, 2008. Google ScholarDigital Library
- J. A. Roy, I. L. Markov, "Seeing the Forest and the Trees: Steiner Wirelength Optimization and Placement," TCAD, vol. 26(4), pp. 632--644, 2007. Google ScholarDigital Library
- P. Spindler, U. Schlichtmann, F. M. Johannes, "Kraftwerk2 -- A Fast Force-Directed Quadratic Placement Approach Using an Accurate Net Model," TCAD, vol. 27(8), pp. 1398--1411, 2008. Google ScholarDigital Library
- Y. Xu, Y. Zhang, C. Chu, "FastRoute 4.0: Global Router with Efficient Via Minimization," ASPDAC, pp. 576--581, 2009. Google ScholarDigital Library
Index Terms
- Completing high-quality global routes
Recommendations
Congestion-Constrained Layer Assignment for Via Minimization in Global Routing
In this paper, we study the problem of layer assignment for via minimization, which arises during multilayer global routing. In addressing this problem, we take the total overflow and the maximum overflow as the congestion constraints from a given one-...
Multi-threaded collision-aware global routing with bounded-length maze routing
DAC '10: Proceedings of the 47th Design Automation ConferenceModern global routers use various routing methods to improve routing speed and the quality. Maze routing is the most time-consuming process for existing global routing algorithms. This paper presents two bounded-length maze routing (BLMR) algorithms (...
A Timing Driven Congestion Aware Global Router
EAIT '11: Proceedings of the 2011 Second International Conference on Emerging Applications of Information TechnologyThe multi-net Global Routing Problem (GRP) is a problem of routing a set of nets subject to resources and delay constraints. Many modern routers use FLUTE (Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design) as the basic ...
Comments