Cell density-driven detailed placement with displacement constraint

ABSTRACT

Modern placement process involves global placement, legalization, and detailed placement. Global placement produce a placement solution with minimized target objective, which is usually wire-length, routability, timing, etc. Legalization removes cell overlap and aligns the cells to the placement sites. Detailed placement further improves the solution by relocating cells. Since target objectives like wire-length and timing are optimized in global placement, legalization and detailed placement should not only minimize their own objectives but also preserve the global placement solution. In this paper, we propose a detailed placement algorithm for minimizing wire-length, while preserving the global placement solution by cell displacement constraint and target cell density objective. Our detailed placer involves two steps: Global Move that allocates each cell into a bin/region that minimizes wire-length, while not overflowing the target cell density. Local Move that finely adjust the cell locations in local regions to further minimize the wire-length objective. With large-scale benchmarks from ICCAD 2013 detailed placement contest, the results show that our detailed placer, RippleDP, can improve the global placement results by 13.38% - 16.41% on average under displacement constraint and target placement density objective.

References

1. A. Agnihotri, S. Ono, C. Li, M. Yildiz, A. Khatkhate, C.-K. Koh, and P. Madden. Mixed block placement via fractional cut recursive bisection. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 24(5):748--761, 2005.
2. U. Brenner and J. Vygen. Faster optimal single-row placement with fixed ordering. In Proceedings of the conference on Design, automation and test in Europe, DATE '00, pages 117--121, New York, NY, USA, 2000. ACM.
3. J. Cong and M. Xie. A robust mixed-size legalization and detailed placement algorithm. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 27(8):1349--1362, 2008.
4. X. He, T. Huang, W.-K. Chow, J. Kuang, K.-C. Lam, W. Cai, and E. Young. Ripple 2.0: High quality routability-driven placement via global router integration. In Design Automation Conference (DAC), 2013 50th ACM / EDAC / IEEE, pages 1--6, 2013.
5. M.-K. Hsu, Y.-F. Chen, C.-C. Huang, T.-C. Chen, and Y.-W. Chang. Routability-driven placement for hierarchical mixed-size circuit designs. In Design Automation Conference (DAC), 2013 50th ACM / EDAC / IEEE, pages 1--6, 2013.
6. A. Kahng, P. Tucker, and A. Zelikovsky. Optimization of linear placements for wirelength minimization with free sites. In Design Automation Conference, 1999. Proceedings of the ASP-DAC '99. Asia and South Pacific, pages 241--244 vol.1, 1999.
7. M.-C. Kim IEEE CEDA / Taiwan MOE, textsc{ICCAD 2013}contest. Retrieved October 10, 2013 from http://cad_contest.cs.nctu.edu.tw/CAD-contest-at-ICCAD2013/problem_b, 2013.
8. M.-C. Kim, D. Lee, and I. L. Markov. Simpl: An effective placement algorithm. IEEE Trans. on CAD of Integrated Circuits and Systems, 31(1):50--60, 2012.
9. M.-C. Kim, N. Viswanathan, C. J. Alpert, I. L. Markov, and S. Ramji. Maple: multilevel adaptive placement for mixed-size designs. In Proceedings of the 2012 ACM international symposium on International Symposium on Physical Design}, ISPD '12, pages 193--200, New York, NY, USA, 2012. ACM.
10. S. Li and C.-K. Koh. Mixed integer programming models for detailed placement. In Proceedings of the 2012 ACM international symposium on International Symposium on Physical Design, ISPD '12, pages 87--94, 2012.
11. W.-H. Liu, C.-K. Koh, and Y.-L. Li. Optimization of placement solutions for routability. In Proceedings of the 50th Annual Design Automation Conference, DAC '13, pages 153:1--153:9, 2013.
12. M. Pan, N. Viswanathan, and C. Chu. An efficient and effective detailed placement algorithm. In Computer-Aided Design, 2005. ICCAD-2005. IEEE/ACM International Conference on, pages 48--55, 2005.
13. P. Spindler, U. Schlichtmann, and F. Johannes. Kraftwerk2 -- a fast force-directed quadratic placement approach using an accurate net model. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 27(8):1398--1411, 2008.
14. T. Taghavi, X. Yang, and B.-K. choi. Dragon2005: large-scale mixed-size placement tool. In Proceedings of the 2005 international symposium on Physical design, ISPD '05, pages 245--247, New York, NY, USA, 2005. ACM.
15. N. Viswanathan, M. Pan, and C. Chu. Fastplace 3.0: A fast multilevel quadratic placement algorithm with placement congestion control. In Design Automation Conference, 2007. ASP-DAC '07. Asia and South Pacific, pages 135--140, 2007.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing