SRP: simultaneous routing and placement for congestion refinement

ABSTRACT

In this paper, an effective simultaneous routing and placement refinement tool called SRP is proposed for routability improvement. SRP is independent of any placer and global router. Based on a given placement layout and global routing result, SRP relocates problematic cells by considering routing and placement simultaneously. Not only overflow from local nets, but overflow from global and semi-global nets can be solved by SRP. A cell will be relocated and its associated nets will be rerouted if its connections go across any congested region, even if the cell is not in the congested region. Therefore, our method can reduce the overflow effectively. Given the layouts generated by the top four routability-driven placers in the DAC Contest 2012, our method can still reduce the total overflow by 32.6% in average while the routed wirelength and HPWL are not increased obviously.

References

1. DAC 2012 Routability-Driven Contest. http://archive.sigda.org/dac2012/contest/dac2012_contest.html.
2. U. Brenner and A. Rohe. An effective congestion-driven placement framework. TCAD, 22(4):387--394, 2003.
3. T. Chan, J. Cong, J. Shinnerl, K. Sze, and M. Xie. mpl6: Enhanced multilevel mixed-size placement. In ISPD, pages 212--214. ACM, 2006.
4. Y. Chuang, G. Nam, C. Alpert, Y. Chang, J. Roy, and N. Viswanathan. Design-hierarchy aware mixed-size placement for routability optimization. In ICCAD, pages 663--668. IEEE, 2010.
5. X. He, T. Huang, L. Xiao, H. Tian, G. Cui, and E. Young. Ripple: An effective routability-driven placer by iterative cell movement. In ICCAD, pages 74--79. IEEE, 2011.
6. W. Hou, H. Yu, X. Hong, Y. Cai, W. Wu, J. Gu, and W. Kao. A new congestion-driven placement algorithm based on cell inflation. In ASP-DAC, pages 605--608. IEEE, 2001.
7. M. Hsu, S. Chou, T. Lin, and Y. Chang. Routability-driven analytical placement for mixed-size circuit designs. In ICCAD, pages 80--84. IEEE, 2011.
8. J. Hu, J. Roy, and I. Markov. Completing high-quality global routes. In ISPD, pages 35--41. ACM, 2010.
9. Z. Jiang, B. Su, and Y. Chang. Routability-driven analytical placement by net overlapping removal for large-scale mixed-size designs. In DAC, pages 167--172. ACM, 2008.
10. A. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. TCAD, 24(5):734--747, 2005.
11. M. Kim, J. Hu, D. Lee, and I. Markov. A simplr method for routability-driven placement. In ICCAD, pages 67--73, 2011.
12. C. Li, M. Xie, C. Koh, J. Cong, and P. Madden. Routability-driven placement and white space allocation. TCAD, 26(5):858--871, 2007.
13. W. Liu, W. Kao, Y. Li, and K. Chao. Multi-threaded collision-aware global routing with bounded-length maze routing. In DAC, pages 200--205. ACM, 2010.
14. M. Pan and C. Chu. Fastroute: A step to integrate global routing into placement. In ICCAD, pages 464--471. ACM, 2006.
15. M. Pan and C. Chu. Ipr: an integrated placement and routing algorithm. In DAC, pages 59--62. ACM, 2007.
16. J. Roy and I. Markov. Seeing the forest and the trees: Steiner wirelength optimization in placement. TCAD, 26(4):632--644, 2007.
17. J. Roy, N. Viswanathan, G. Nam, C. Alpert, and I. Markov. CRISP: congestion reduction by iterated spreading during placement. In ICCAD, pages 357--362. ACM, 2009.
18. P. Spindler and F. Johannes. Fast and accurate routing demand estimation for efficient routability-driven placement. In DATE, pages 1--6. IEEE, 2007.
19. K. Tsota, C. Koh, and V. Balakrishnan. Guiding global placement with wire density. In ICCAD, pages 212--217, 2008.
20. X. Yang, B. Choi, and M. Sarrafzadeh. Routability-driven white space allocation for fixed-die standard-cell placement. TCAD, 22(4):410--419, 2003.
21. Y. Zhang and C. Chu. Crop: Fast and effective congestion refinement of placement. In ICCAD, pages 344--350. IEEE, 2009.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing