Tai-Chen Chen
ABSTRACT
To handle modern routing with nanometer effects, we need to consider designs of variable wire widths and spacings, for which gridless routers are desirable due to their great flexibility. The gridless routing is much more difficult than the grid-based one because the solution space of gridless routing is significantly larger than that of grid-based one. In this paper, we present the first multilevel, full-chip gridless detailed router. The router integrates global routing, detailed routing, and congestion estimation together at each level of the multilevel routing. It can handle non-uniform wire widths and consider routability and optical proximity correction (OPC). Experimental results show that our approach obtains significantly better routing solutions than previous works. For example, for a set of 11 commonly used benchmark circuits, our approach achieves 100% routing completion for all circuits while the famous state-of-the-art three-level routing and multilevel routing (multilevel global routing + flat detailed routing) cannot complete routing for any of the circuits. Besides, experimental results show that our multilevel gridless router can handle non-uniform wire widths efficiently and effectively (still maintain 100% routing completion for all circuits). In particular, our OPC-aware multilevel gridless router archives an average reduction of 11.3% pattern features and still maintains 100% routability for the 11 benchmark circuits.
- C. Albrecht, "Global routing by new approximation algorithms for multicommodity flow," IEEE Trans. CAD, vol. 20, no. 5, pp. 622--632, May 2001. Google Scholar
Digital Library
- C. J. Alpert, J.-H. Huang, and A. B. Kahng, "Multilevel circuit partitioning," IEEE Trans. CAD, vol. 17, no. 8, pp. 655--667, August 1998. Google ScholarDigital Library
- T. Chan, J. Cong, T. Kong, and J. Shinnerl, "Multilevel optimization for large-scale circuit placement," Proc. ICCAD, pp. 171--176, Nov. 2000. Google ScholarDigital Library
- Y.-W. Chang, K. Zhu, and D.-F. Wong, "Timing-driven routing for symmetrical-array-based FPGAs," ACM Trans. Design Automation of Electronic Systems, vol. 5, no. 3, pp. 433--450, July 2000. Google ScholarDigital Library
- Y.-W. Chang and S.-P. Lin, "MR: A new framework for multilevel full-chip routing," IEEE Trans. CAD, vol. 23, no. 5, pp. 793--800, May 2004. Google ScholarDigital Library
- N. Cobb and A. Zakhor, "Large Area Phase-Shift mask Design," SPIE, 2197:348--359, 1994.Google Scholar
- N. Cobb, A. Zakhor, and Eugene Miloslavsky, "Mathematical and CAD Framework for Proximity Correction," SPIE, 2726:208--222, 1996.Google Scholar
- J. Cong, J. Fang, and K. Khoo, "DUNE: A multi-layer gridless routing system with wire planning," Proc. ISPD, pp. 12--18, April 2000. Google ScholarDigital Library
- J. Cong, S. Lim, and C. Wu, "Performance driven multilevel and multiway partitioning with retiming," Proc. DAC, pp. 274--279, June 2000. Google ScholarDigital Library
- J. Cong, J. Fang, and Y. Zhang, "Multilevel approach to full-chip gridless routing," Proc. ICCAD, pp. 396--403, Nov. 2001. Google ScholarDigital Library
- J. Cong, M. Xie, and Y. Zhang, "An enhanced multilevel routing system," Proc. ICCAD, pp. 51--58, Nov. 2002. Google ScholarDigital Library
- C.-C. Fu, T.-S. yang, and Douglas R. Stone, "Enhancement of lithography patterns by using serif features," IEEE Trans. Electron Devices, vol. 38, no. 12, pp. 2599--2603, Dec. 1991.Google ScholarCross Ref
- K. Harazaki, Y. hasegawa, Y. Shichijo, H. Tabuchi, and K. Fujii, "High Accurate Optical Proximity Correction under the Influences of Lens Aberration in 0.15 m Logic Process," International Microprocesses and Nanotechnology Conference, pp. 14--15, 2000.Google Scholar
- M. Hayashi and S. Tsukiyama, "A hybrid hierarchical global router for multi-layer VLSIs," IEICE Trans. Fundamentals, vol. E78-A, no. 3, pp. 337--344, 1995.Google Scholar
- J. Heisterman and T. Lengauer, "The efficient solutions of integer programs for hierarchical global routing," IEEE Trans. CAD, vol. 10, no. 6, pp. 748--753, June 1991.Google ScholarDigital Library
- D. Hightower, "A solution to line routing problems on the continuous plane," Proc. Design Automation Workshop, pp. 1--24, 1969. Google ScholarDigital Library
- T.-Y. Ho, Y.-W. Chang, S.-J. Chen, and D. T. Lee, "A Fast Crosstalk- and Performance-Driven Multilevel Routing System," Proc. ICCAD, pp.382--387, Nov. 2003. Google ScholarDigital Library
- T.-Y. Ho, Y.-W. Chang, and S.-J. Chen, "Multilevel Routing with Antenna Avoidance," Proc. ISPD, pp. 34--40, April 2004. Google ScholarDigital Library
- L.-D. Huang and D.-F. Wong, "Optical Proximity Correction (OPC)-Friendly Maze Routing," Proc. DAC, pp. 186--191, June 2004. Google ScholarDigital Library
- G. Karypis, R. Aggarwal, V. Kumar, and S. shekhar, "Multilevel hypergraph partitioning: Application in VLSI domain," IEEE Trans VLSI Systems, vol. 7, pp. 69--79, March 1999. Google ScholarDigital Library
- R. Kastner, E. Bozorgzadeh and M. Sarrafzadeh, "Predictable routing," Proc. ICCAD, pp. 110--114, Nov. 2000. Google ScholarDigital Library
- Lee, "An algorithm for path connection and its application," IRE Trans. Electronic Computer, EC-10, 1961.Google ScholarCross Ref
- H.-C. Lee, Y.-W. Chang, J.-M. Hsu, and H. Yang, "Multilevel floorplanning/placement for large-scale modules using B*-trees," Proc. DAC, pp. 812--817, June 2003. Google ScholarDigital Library
- Marc D. Levenson, N. S. Viswanathan, and Robert A. Simpson, "Improving Resolution in Photolithography with a Phase-Shifting Mask," IEEE Trans. Electron Devices, vol. 29, no. 12, pp. 1828--1836, Dec. 1982.Google ScholarCross Ref
- Y. L. Lin, Y. C. Hsu, and F. S. Tsai, "Hybrid routing," IEEE Trans. CAD, vol. 9, no. 2, pp. 151--157, Feb, 1990.Google ScholarDigital Library
- S. R. Lin and Y. W. Chang, "A novel framework for multilevel routing considering routability and performance," Proc. ICCAD, pp. 44--50, Nov. 2002. Google ScholarDigital Library
- M. Marek-Sadowska, "Global Router for gate array," Proc. ICCD, pp. 332--337, Oct. 1984.Google Scholar
- M. Marek-Sadowska, "Router planner for custom chip design," Proc. ICCAD, Nov. 1986.Google Scholar
- G. Meixner and U. Lauther, "A new global router based on a flow model and linear assignment," Proc. ICCAD, pp. 44--47, Nov. 1990.Google Scholar
- Y.-C. Pati, Y.-T. Wnag, J.-W Liang, and Thomas Kailiath, "Phase-Shift Masks: Automated Design and Mask Requirements," SPIE, 2197:314--327, 1994.Google Scholar
- J. Soukup, "Fast maze router," Proc. DAC, pp. 100--102, June 1978. Google ScholarDigital Library
- D. Wang and E. Kuh, "A new timing-driven multilayer MCM/IC routing algorithm," Proc. Multi-chip Module Conference, pp. 89--94, Feb. 1997. Google ScholarDigital Library
- K. Yamamoto, S. Kobayashi, T. Uno, T. Kotani, S. Tanaka, S. Inoue, S. Watanabe, and H. Higurashi, "Hierarchical Optical Proximity Correction on contact Hole Layers," International Microprocesses and Nanotechnology Conference, pp. 40--41, 2000.Google Scholar
Recommendations
Multilevel Full-Chip Gridless Routing With Applications to Optical-Proximity Correction
To handle modern routing with nanometer effects, we need to consider designs with variable wire/via widths and spacings, for which gridless-routing approaches are desirable due to its great flexibility. In this paper, we introduce a gridless-routing ...
Novel full-chip gridless routing considering double-via insertion
DAC '06: Proceedings of the 43rd annual Design Automation ConferenceAs the technology node advances into the nanometer era, via-open defects are one of the dominant failures. To improve via yield and reliability, redundant-via insertion is a highly recommended technique proposed by foundries. Traditionally, double-via ...
A novel framework for multilevel full-chip gridless routing
ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation ConferenceDue to its great flexibility, gridless routing is desirable for nanometer circuit designs that use variable wire widths and spacings. Nevertheless, it is much more difficult than grid-based routing because of its larger solution space. In this paper, we ...
Comments