Taming the complexity of coordinated place and route

ABSTRACT

IC performance, power dissipation, size, and signal integrity are now dominated by interconnects. However, with ever-shrinking standard cells, blind minimization of interconnect during placement causes routing failures. Hence, we develop Coordinated Place-and-Route (CoPR) with (i) a Lightweight Incremental Routing Estimation (LIRE) frequently invoked during placement, (ii) placement techniques that address three types of routing congestion, and (iii) an interface to congestion estimation that supports new types of incrementality. LIRE comprehends routing obstacles and non-uniform routing capacities, and relies on a cache-friendly, fully-incremental routing algorithm. Our implementation extends and improves our winning entry at the ICCAD 2012 Contest.

References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, 2001.
2. L. Dagum and R. Menon, "OpenMP: An Industry Standard API for Shared-memory Programming," Computational Science and Engineering 1998, pp. 46--55.
3. X. He, T. Huang, L. Xiao, H. Tian, G. Cui and E. F. Young, "Ripple: An Effective Routability-driven Placer by Iterative Cell Movement", ICCAD 2011, pp. 74--79.
4. J. Hu, J. A. Roy and I. L. Markov, "Completing High-quality Global Routes", ISPD 2010, pp. 35--41.
5. M.-K. Hsu, S. Chou, T.-H. Lin and Y.-W. Chang, "Routability-driven Analytical Placement for Mixed-size Circuit Designs", ICCAD 2011, pp. 80--84.
6. L. Hsu, R. Iyer, S. Makineni, S. Reinhardt and D. Newell, "Exploring the Cache Design Space for Large Scale CMPs," Computer Architecture News 2005, pp. 24--33.
7. International Technology Roadmap for Semiconductors (ITRS).
8. M.-C. Kim, J. Hu, D.-J. Lee and I. L. Markov, "A SimPLR Method for Routability-driven Placement", ICCAD 2011, pp. 67--73.
9. M.-C. Kim, D.-J. Lee and I. L. Markov, "SimPL: An Effective Placement Algorithm", TCAD 31(1) (2012), pp. 50--60.
10. B. Korte, D. Rautenbach and J. Vygen, "BonnTools: Mathematical Innovation for Layout and Timing Closure of Systems on a Chip", Proc. IEEE 95(3) (2007), pp. 555--572.
11. Z. Li, C. J. Alpert, G.-J. Nam, C. Sze, N. Viswanathan and N. Y. Zhou, "Guiding a Physical Design Closure System to Produce Easier-to-route Designs with More Predictable Timing", DAC 2012, pp. 465--470.
12. W.-H. Liu, W.-C. Kao, Y.-L. Li, K.-Y. Chao, "Multi-threaded Collision-aware Global Routing with Bounded-length Maze Routing", DAC 2010, pp.200--205.
13. W.-H. Liu, Y.-L. Li, C.-K. Kok,"A Fast Maze-free Routing Congestion Estimator With Hybrid Unilateral Monotonic Routing", ICCAD 2012, pp.713--719.
14. M. Pan, Y. Xu, Y. Zhang and C. Chu, "FastRoute: An Efficient and High-quality Global Router", VLSI Design 2012, 18 pages.
15. S. K. Raman, V. Pentkovski and J. Keshava, "Implementing Streaming SIMD Extensions on the Pentium III Processor", Micro 20(4)(2000), pp. 47--57.
16. P. N. Parakh, R. B. Brown and K. A. Sakallah, "Congestion Driven Quadratic Placement, DAC 1998, pp. 275--278.
17. J. A. Roy, N. Viswanathan, G.-J. Nam, C. J. Alpert and I. L. Markov, "CRISP: Congestion Reduction by Iterated Spreading during Placement", ICCAD 2009, pp. 357--362.
18. N. Viswanathan, C. J. Alpert, C. Sze, Z. Li, G.-J. Nam and J. A. Roy, "The ISPD-2011 Routability-driven Placement Contest and Benchmark Suite", ISPD 2011, pp. 141--146.
19. N. Viswanathan, C. J. Alpert, C. Sze, Z. Li, Y. Wei, "The DAC 2012 Routability-driven Placement Contest and Benchmark Suite", DAC 2012, pp. 774--782.
20. N. Viswanathan, C. J. Alpert, C. Sze, Z. Li and Y. Wei, "ICCAD-2012 CAD Contest in Design Hierarchy Aware Routability-driven Placement and Benchmark Suite", ICCAD 2012, pp. 345--348. cad_contest.cs.nctu.edu.tw/CAD-contest-at-ICCAD2012/problems/p2/p2.html
21. Y. Wei, C. Sze, N. Viswanathan, Z. Li, C. J. Alpert, L. N. Reddy, A. D. Huber, G. E. Terez, D. Keller and S. S. Sapatnekar, "GLARE: Global and Local Wiring Aware Routability Evaluation", DAC 2012, pp. 768--773.
22. J. Westra and P. Groeneveld, "Is Probabilistic Congestion Estimation Worthwhile?" SLIP 2005, pp. 99--106.
23. J. Y. Yen, "An Algorithm for Finding Shortest Routes From All Source Nodes to a Given Destination in General Networks", Proc. Quarterly of Applied Mathematics 27 (1970), pp.526--530.
24. Y. Zhang and C. Chu, "CROP: Fast and Effective Congestion Refinement of Placement", ICCAD 2009, pp. 344--350.
25. Y. Zhang and C. Chu, "GDRouter: Interleaved Global Routing and Detailed Routing for Ultimate Routability", DAC 2012, pp. 597--602.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing

  • Emerging technologies

  • Hardware validation

  • Very large scale integration design