Guiding a physical design closure system to produce easier-to-route designs with more predictable timing

ABSTRACT

Physical synthesis has emerged as one of the most important tools in design closure, which starts with the logic synthesis step and generates a new optimized netlist and its layout for the final signoff process. As stated in [1], "it is a wrapper around traditional place and route, whereby synthesis-based optimization are interwoven with placement and routing." A traditional physical synthesis tool generally focuses on design closure with Steiner wire model. It optimizes timing/area/power with the assumption that each net can be routed with optimal Steiner tree. However, advanced design rules, more IP and hierarchical design styles for super-large billion-gate designs, serious buffering problems from interconnect scaling and metal layer stacks make routing a much more challenging problem [2]. This paper discusses a series of techniques that may relieve this problem, and guide the physical design closure system to produce not only easier to route designs, but also better timing quality. Open challenges are also overviewed at the end.

References

1. Z. Li and C. J. Alpert, "What is Physical Synthesis," ACM/SIGDA E-Newsletter, vol. 41, no. 1, Jan 2011.
2. C. J. Alpert et al., "What makes a design difficult to route," in Proc. ISPDPD, 2010, pp. 7--12.
3. C. J. Alpert et al., "Techniques for fast physical synthesis," Proceedings of the IEEE, vol. 95, no. 3, pp. 573--599, 2007.
4. Y. Xu et al., "FastRoute 4.0: Global router with efficient via minimization," in Proc. ASPDAC, 2009, pp. 576--581.
5. Y.-J. Chang et al., "NTHU-Route 2.0: A fast and stable global router," in Proc. ICCAD, 2008, pp. 338--343.
6. C. Minsik et al., "BoxRouter 2.0: Architecture and implementation of a hybrid and robust global router," in Proc. ICCAD, 2007, pp. 503--508.
7. H.-Y. Chen et al., "High-performance global routing with fast overflow reduction," in Proc. ASPDAC, 2009, pp. 582--587.
8. H. Shojaei et al., "Congestion analysis for global routing via integer programming," in Proc. ICCAD, 2011, pp. 256--262.
9. J. Hu, J. A. Roy, and I. L. Markov, "Completing high-quality routes," in Proc. ISPD, 2010, pp. 35--41.
10. Y. Wei et al., "GLARE: Global and Local wiring Aware Routability Evaluation," in Proc. DAC, 2012, to appear.
11. T. Taghavi et al., "New Placement Prediction and Mitigation Techniques For Local Routing Congestion," in Proc. ICCAD, 2010, pp. 621--624.
12. C. C. N. Chu, Y. C. Wong, "FLUTE: Fast lookup table based rectilinear Steiner minimal tree Algorithm for VLSI Design," IEEE Trans. on CAD, vol. 27, no. 1, pp. 70--83, 2008.
13. J. Roy et al., "CRISP: Congestion reduction by iterated spreading during placement," in Proc. ICCAD, 2009, pp. 357--362.
14. Z. Li et al., "Fast interconnect synthesis with layer assignment," in Proc. ISPD, 2008, pp. 71--77.
15. S. I. Ward et al., "Keep it straight: teaching placement how to better handle designs with datapaths," in Proc. ISPD, 2012, pp. 79--86.
16. T. Jindal et al., "Detecting tangled logic structures in VLSI netlists," in Proc. DAC, 2010, pp. 603--608.
17. H. Xiang et al., "Logical and physical restructuring of fan-in trees," in Proc. ISPD, 2010, pp. 67--74.
18. G.-J. Nam et al., "The ISPD2005 placement contest and benchmark suite," in Proc. ISPD, 2005, pp. 216--220.
19. G.-J. Nam, C. J. Alpert, and P. Villarrubia, "ISPD 2006 placement contest: Benchmark suite and results," in Proc. ISPD, 2006, pp. 167--167.
20. Y. Zhang and C. Chu, "CROP: Fast and effective congestion refinement of placement," in Proc. ICCAD, 2009, pp. 344--350.
21. C. Li et al., "Routability-driven placement and white space allocation," IEEE Trans. on CAD, vol. 26, no. 5, pp. 858--871, 2007.
22. U. Brenner and A. Rohe, "An effective congestion-driven placement framework," IEEE Trans. on CAD, vol. 22, no. 4, pp. 387--394, 2003.
23. W. Hou et al., "A new congestion-driven placement algorithm based on cell inflation," in Proc. ASPDAC, 2001, pp. 723--728.
24. N. Viswanathan et al., "The ISPD-2011 Routability-driven placement contest and benchmark suite," in Proc. ISPD, 2011, pp. 141--146.
25. N. Viswanathan et al., "The DAC 2012 Routability-driven placement contest and benchmark suite," in Proc. DAC, 2012, to appear.
26. M. Pan and C. Chu, "IPR: An integrated placement and routing algorithm," in Proc. DAC, 2007, pp. 59--62.
27. M.-C. Kim et al., "A SimPLR method for routability-driven placement," in Proc. ICCAD, 2011, pp. 67--73.
28. N. Viswanathan, M. Pan and C. C. N. Chu, "FastPlace 3.0: A fast multilevel quadratic placement algorithm with placement congestion control," in Proc. ASP-DAC, 2007, pp. 135--140.
29. D. A. Papa et al., "Physical Synthesis with Clock-Network Optimization for Large Systems on Chips," IEEE Micro, vol. 31, no. 4, pp. 51--62, 2011.
30. W. Shi and Z. Li, "A fast algorithm for optimal buffer insertion," IEEE Trans. on CAD, vol. 24, no. 6, pp. 879--891, June 2005.
31. Z. Li, Y. Zhou and W. Shi, "O(mn) Time Algorithm for Optimal Buffer Insertion of Nets With m Sinks", IEEE Trans. on CAD, vol. 31, no. 3, pp. 437--441, March 2012.
32. S. Hu, Z. Li and C. J. Alpert, "A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion," in Proc. DAC, 2009, pp. 424--429.
33. S. Hu, Z. Li and C. J. Alpert, "A faster approximation scheme for timing driven minimum cost layer assignment," in Proc. ISPD, 2009, pp. 167--174.
34. Z. Li and W. Shi, "An O(bn²) time algorithm for optimal buffer insertion with b buffer types", IEEE Trans. on CAD, vol. 25, no. 3, pp. 484--489, March 2006.
35. M. Waghmode, Z. Li and W. Shi, "Buffer insertion in large circuits with constructive solution search techniques," in Proc. DAC, 2006, pp. 296--301.
36. C. C. N. Sze et al., "Path based buffer insertion," in Proc. DAC, 2005, pp. 509--514.
37. Y. Zhou et al., "Shedding Physical Synthesis Area Bloat," VLSI Design, Article ID 503025, 2011.
38. N. Viswanathan et al., "ITOP: integrating timing optimization within placement," in Proc. ISPD, 2010, pp. 83--90.
39. B. Dougherty and M. Kazda, "Rapids: Post-Routing Timing Closure," in DAC 2010 User track Poster 1U.5.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing