GLARE: global and local wiring aware routability evaluation

ABSTRACT

Industry routers are very complex and time consuming, and are becoming more so with the explosion in design rules and design for manufacturability requirements that multiply with each technology node. Global routing is just the first phase of a router and serves the dual purpose of (i) seeding the following phases of a router and (ii) evaluating whether the current design point is routable. Lately, it has become common to use a "light mode" version of the global router, similar to today's academic routers, to quickly evaluate the routability of a given placement. This use model suffers from two primary weaknesses: (i) it does not adequately model the local routing resources, while the model is important to remove opens and shorts and eliminate DRC violations, (ii) the metrics used to represent congestion are non-intuitive and often fail to pinpoint the key issues that need to be addressed. This paper presents solutions to both issues, and empirically demonstrates that incorporating the proposed solutions within a global routing based congestion analyzer yields a more accurate view of design routability.

References

1. C. Alpert et al. What makes a design difficult to route. In Proc. ISPD, pages 7--12, 2010.
2. C. Alpert and G. Tellez. The importance of routing congestion analysis. DAC Knowledge Center Online Article, 2010. http://www.dac.com/back_end+topics.aspx?article=47&topic=2.
3. Y.-J. Chang et al. NTHU-Route 2.0: A fast and stable global router. In Proc. ICCAD, pages 338--343, 2008.
4. H.-Y. Chen et al. High-performance global routing with fast overflow reduction. In Proc. ASPDAC, pages 582--587, 2009.
5. C. Chu and Y.-C. Wong. Flute: Fast lookup table based rectilinear Steiner minimal tree algorithm for VLSI design. IEEE Trans. on CAD, 27(1):70--83, 2008.
6. J. Lou et al. Estimating routing congestion using probabilistic analysis. IEEE Trans. on CAD, 21(1):32--41, 2002.
7. C. Minsik et al. BoxRouter 2.0: Architecture and implementation of a hybrid and robust global router. In Proc. ICCAD, pages 503--508, 2007.
8. M. D. Moffitt. MaizeRouter: Engineering an effective global router. IEEE Trans. on CAD, 27(11):2017--2026, 2008.
9. M. Pan and C. Chu. FastRoute: A step to integrate global routing into placement. In Proc. ICCAD, pages 464--471, 2006.
10. M. Pan and C. Chu. IPR: An integrated placement and routing algorithm. In Proc. DAC, pages 59--62, 2007.
11. J. Roy et al. CRISP: Congestion reduction by iterated spreading during placement. In Proc. ICCAD, pages 357--362, 2009.
12. H. Shojaei et al. Congestion analysis for global routing via integer programming. In Proc. ICCAD, pages 256--262, 2011.
13. J. Westra et al. Probabilistic congestion prediction. In Proc. ISPD, pages 204--209, 2004.
14. T.-H. Wu et al. A parallel integer programming approach to global routing. In Proc. DAC, pages 194--199, 2010.
15. Y. Xu et al. FastRoute 4.0: Global router with efficient via minimization. In Proc. ASPDAC, pages 576--581, 2009.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing