一种OPC友好的迷宫布线算法
|
摘要
超深亚微米集成电路制造中广泛应用OPC技术来减少掩模图形的光刻畸变,改善成像质量。然而在当前的设计流程中,版图设计者并没有考虑版图的OPC友好性问题,从而使一些图形由于原始形状限制无法进行充分的OPC校正处理。本文提出了一种OPC友好的迷宫布线算法:在布线的同时进行快速点光强计算,来预测走线对未来OPC的影响,避免可能导致OPC失败的布线结果,同时尽可能减少OPC需要做出的校正。
OPC is widely employed in deep sub-micron IC manufacture, to alleviate the distortion of printed silicon image. However, the current design flow does not take OPC into consideration during physical design stage. This might result in mask patterns that cannot be corrected by OPC. Thus, we propose an OPC-friendly maze routing algorithm, which links fast lithography simulation with an enhanced maze router, to guarantee the success of OPC and to ease the heavy burden of OPC.
OPC is widely employed in deep sub-micron IC manufacture, to alleviate the distortion of printed silicon image. However, the current design flow does not take OPC into consideration during physical design stage. This might result in mask patterns that cannot be corrected by OPC. Thus, we propose an OPC-friendly maze routing algorithm, which links fast lithography simulation with an enhanced maze router, to guarantee the success of OPC and to ease the heavy burden of OPC.
引文
[1] Allan A., Edenfeld D. and Joyner W.H et al. "2001 technology roadmap for semiconductors", Computer, vol. 35, Issue 1: 42-53
[2] Edenfeld D., Kahng A.B. and Rodgers M. et al. "2003 technology roadmap for semiconductors", Computer, vol. 37, Issue 1: 47-56
[3] David Z. Pan and Martin D. F. Wong, "Manufacturability Aware Physical Layout Optimizations", ICICDT 2005
[4] Li-Da Huang and Martin D. F. Wong, "Optical Proximity Correction (OPC)-Friendly Maze Routing", Proc. of DAC 2004: 186-191
[5] Yun-Ru Wu, Ming-Chao Tsai and Ting-Chi Wang, "Maze routing with OPC consideration", Proc of the ASP-DAC 2005, vol. 1: 198-203
[6] Joydeep Mitra, Peng Yu and David Z. Pan, "RADAR: RET-Aware Detailed Routing Using Fast Lithography Simulations", Proc. of DAC 2005: 369-372
[7] Nick Cobb, Avideh Zakhor and Eugene Miloslavskv, "Mathematical and CAD Framework for Proximity Correction", SPIE 1996, vol. 2726: 208-222
[8] Nicolas Bailey Cobb, "Fast Optical and Process Proximity Correction Algorithms for Integrated Circuit Manufacturing", phd. thesis, UC Berkeley, 1998
[9] Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest et al, "Introduction to Algorithms", 2~(nd) Edition, The MIT Press, 2001: 525-607
[10] W. Grobman, M. Thompson and R. Wang et al, "Reticle enhancement technology: implications and challenges for physical design", Proc. of DAC 2001
[11] Scheffer L. K., "Physical CAD changes to incorporate design for lithography and manufacturability", Proc. of ASP-DAC 2004: 768 -773
[12] Nicolas B. Cobb and Avideh Zakhor, "Fast, low-complexity mask design", SPIE 1995, vol. 2440:313
[13] Gupta P. and Kahng A. B., "Manufacturing-aware physical design", ICCAD 2003:
681～687
[14] Yao-Wen Chang and Shih-Ping Lin, "MR: a new framework for multilevel full-chip routing", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, May 2004, vol. 23, Issue 5:793～800
[15] Tai-Chen Chen and Yao-Wen Chang, "Multilevel full-chip gridless routing considering optical proximity correction", Proc. of ASP-DAC 2005
[16] Yong-Chan Ban, Soo-Han Choi and Ki-Hung Lee et al, "A fast lithography verification framework for litho-friendly layout design", ISQED 2005:169～174
[17] H. Ren, D. Z. Pan and D. S. Kung, "Sensitivity Guided Netweighting for Placement Driven Synthesis", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, May 2005, Vol. 2:1160～1163
[18] G. Xu, L. Huang and D. Z. Pan et al, "Redundant-Via Enhanced Maze Routing for Yield Improvement", Proc. of ASP-DAC 2005
[19] G. Xu, R. Tian, D. Z. Pan and M. D.-F. Wong, "CMP Aware Shuttle Mask Floorplanning", Proc. Asia South Pacific Design Automation Conference (ASPDAC), Jan. 2005.
[20] Nardi A., Sangiovanni-Vincentelli A.L., "Logic synthesis for manufacturability", Design & Test of Computers 2004, vol. 21, Issue 3:192～199
[21] H.T. Heineken, J. Khare and M. d'Abreu, "Manufacturability Analysis of Standard Cell Libraries," Proc.of CICC 1998:321～324
[22] C. Ouyang et al., "Maximizing Wafer Productivity through Layout Optimizations," Proc. of 13th International Conf. VLSI Design 2000:192～197
[23] V.K.R. Chiluvuri and I. Koren, "Layout-Synthesis Techniques for Yield Enhancement," IEEE Trans. Semiconductor Manufacturing May 1995, vol. 8, no. 2:178～187
[24] V.K.R. Chiluvuri and I. Koren, "Yield Enhancement vs. Performance Improvement in VLSI Circuits," Proc. of ISSM 1995:28～31
[25] Yang Yang, Tong Jing and Xianlong Hong et al, "Via-Aware Global Routing for Good VLSI Manufacturability and High Yield", 16th IEEE International Conference on Application-Specific Systems, Architecture Processors, ASAP 2005:198～203
[26] Tyagi A, Bayoum M. A., "ULSI design-for-manufacturability: a yield enhancement approach", Proc. of Third International Conference on the Economics of Design, Test, and Manufacturing 1994:80
[27] Riviere-Cazaux L., Lucas K. and Fitch J., "Integration of design for manufacturability (DFM) practices in design flows", ISQED 2005:102～106
[28] Nardi A., Sangiovanni-Vincentelli A.L., "Synthesis for manufacturability: a sanity check", Proc. of Design, Automation and Test in Europe Conference and Exhibition 2004, vol.2:796～801
[29] Jeong-Taek Kong, "CAD for nanometer silicon design challenges and success", IEEE Transactions of Very Large Scale Integration (VLSI) Systems
[30] Hai Zhou and Wong D.F., "Crosstalk-constrained maze routing based on Lagrangian relaxation", Proc. of ICCD 1997:628～633
[31] Mani N., Quach N.H., "Heuristics in the routing algorithm for circuit layout design", Proc. of Computers and Digital Techniques 2005, vol. 147:59～64
[32] Hill D. and Shugard D., "Global routing considerations in a cell synthesis system", Proc. of DAC 1990:312～316
[33] Huijbregts E.P., Hua Xue and Jess J.A.G., "Routing for reliable manufacturing", IEEE Transactions on Semiconductor Manufacturing 1995, vol.8, issue2:188～194
[34] Kahng A.B., Bao Liu and Mandoiu I.I., "Nontree routing for reliability and yield improvement", ASAP 2005:198～203
[35] Jinjun Xiong and Lei He, "Extended global routing with RLC crosstalk constraints", IEEE Transactions on VLSI Systems 2005, vol.3, issue 3:319～329
[36] Sangiovanni-Vincentelli A., "The tides of EDA", Design & Test of Computers 2003, vol.20, issue 6:59～75
[37] Kahng A.B., "Nanometer design: place your bets", Proc. of DAC 2003
[38] Starikov, Kenneth W. Tobin, "RET-compliant cell generation for sub-130-nm processes", Proc. of SPIE 2002, vol. 4692:529～539
[39] Stan M.R., Hamzaoglu, F. Garrett D., "Non-Manhattan maze routing", 17th Symposium on Integrated Circuits and Systems Design, SBCCI 2004:260～265
[40] Huijbregts E.P., Van Eijndhoven J.T.S., Jess J.A.G., "On design rule correct maze routing", Proc. of European Design and Test Conference, EDAC 1994:407～411
[41] Lee C Y. An algorithm for path connections and its applications. IRE Trans. on Electronic Computers, 1961, 10(3):346.
[42] Soukup J. Fast maze router. Proc. IEEE Design Automation Conference (DAC'78), 1978:100.
[43] Hightower D. A solution to line-routing problems on the continuous plane. Proc. IEEE Design Automation Conference (DAC'69), 1969:1.
[44] Nair R. A simple yet effective technique for global wiring. 1EEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 1987, 6(2): 165.
[45] McMurchie L, Ebeling C. PathFinder: a negotiation-based performance-driven router for FPGAs. Proc. ACM Symposium on Field-Programmable Gate Arrays (FPGA'95), 1995:111.
[46] Meixner G, Lauther U. A new global router based on a flow model and linear assignment. Proc. IEEE International Conference on Computer-Aided Design (ICCAD'90), 1990:44.
[47] Albrecht C. Provably good global routing by a new approximation algorithm for multicommodity flow. Proc. International Symposium on Physical Design (ISPD'00), 2000:19.
[48] Burstein M, Pelavin R. Hierarchical channel router. Proc. IEEE Design Automation Conference (DAC'83), 1983:591.
[49] Lin Y-L, Hsu Y-C, Tsai F-S. Hybrid routing. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 1987, 9(2): 151.
[50] Heisterman J, Lengauer T. The efficient solution of integer programs for hierarchical global routing. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 1991, 10(6):748.
[51] Cong J, Xie M, Zhang Y. An enhanced multilevel routing system. Proc. IEEE International Conference on Computer-Aided Design (ICCAD'02), 2002:51.
[52] Cong J, Fang J, Zhang Y. Multilevel approach to full-chip gridless routing. Proc. IEEE International Conference on Computer-Aided Design (ICCAD'01), 2001:396.
[53] Lin S-P, Chang Y-W. A novel framework for multilevel routing considering routability and performance. Proe. IEEE International Conference on Computer-Aided Design (ICCAD'02), 2002:44.
[54] Ho T Y, Chang Y-W, Chen S J, et al. A fast crosstalk-and performance-driven multilevel routing system. Proc. IEEE International Conference on Computer-Aided Design (ICCAD'03), 2003:382.
[55] Ho T Y, Chang Y-W, Chen S J. Multilevel routing with antenna avoidance. Proc. International Symposium on Physical Design (ISPD'04), 2004:34.
[56] Ho T-Y, Chang C-F, Chang Y-W, et al. Multilevel full-chip routing for the X-based architecture. Proc. IEEE Design Automation Conference (DAC'05), 2005:597.
[57] Chen T-C, Chang Y-W. Multilevel gridless full-chip routing considering optical proximity correction. Proc. IEEE Asia South Pacific Design Automation Conference (ASPDAC'05), 2005:1160.
[58] Kastner R, Bozorgzadeh E, Sarrafzadeh M. Predictable routing. Proc. IEEE International Conference on Computer-Aided Design (ICCAD'00), 2000:110.
[59] Dijkstra E W. A note on two problems in connection with graphs. Numerische Mathematik, 1959, 1:269.
[2] Edenfeld D., Kahng A.B. and Rodgers M. et al. "2003 technology roadmap for semiconductors", Computer, vol. 37, Issue 1: 47-56
[3] David Z. Pan and Martin D. F. Wong, "Manufacturability Aware Physical Layout Optimizations", ICICDT 2005
[4] Li-Da Huang and Martin D. F. Wong, "Optical Proximity Correction (OPC)-Friendly Maze Routing", Proc. of DAC 2004: 186-191
[5] Yun-Ru Wu, Ming-Chao Tsai and Ting-Chi Wang, "Maze routing with OPC consideration", Proc of the ASP-DAC 2005, vol. 1: 198-203
[6] Joydeep Mitra, Peng Yu and David Z. Pan, "RADAR: RET-Aware Detailed Routing Using Fast Lithography Simulations", Proc. of DAC 2005: 369-372
[7] Nick Cobb, Avideh Zakhor and Eugene Miloslavskv, "Mathematical and CAD Framework for Proximity Correction", SPIE 1996, vol. 2726: 208-222
[8] Nicolas Bailey Cobb, "Fast Optical and Process Proximity Correction Algorithms for Integrated Circuit Manufacturing", phd. thesis, UC Berkeley, 1998
[9] Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest et al, "Introduction to Algorithms", 2~(nd) Edition, The MIT Press, 2001: 525-607
[10] W. Grobman, M. Thompson and R. Wang et al, "Reticle enhancement technology: implications and challenges for physical design", Proc. of DAC 2001
[11] Scheffer L. K., "Physical CAD changes to incorporate design for lithography and manufacturability", Proc. of ASP-DAC 2004: 768 -773
[12] Nicolas B. Cobb and Avideh Zakhor, "Fast, low-complexity mask design", SPIE 1995, vol. 2440:313
[13] Gupta P. and Kahng A. B., "Manufacturing-aware physical design", ICCAD 2003:
681～687
[14] Yao-Wen Chang and Shih-Ping Lin, "MR: a new framework for multilevel full-chip routing", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, May 2004, vol. 23, Issue 5:793～800
[15] Tai-Chen Chen and Yao-Wen Chang, "Multilevel full-chip gridless routing considering optical proximity correction", Proc. of ASP-DAC 2005
[16] Yong-Chan Ban, Soo-Han Choi and Ki-Hung Lee et al, "A fast lithography verification framework for litho-friendly layout design", ISQED 2005:169～174
[17] H. Ren, D. Z. Pan and D. S. Kung, "Sensitivity Guided Netweighting for Placement Driven Synthesis", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, May 2005, Vol. 2:1160～1163
[18] G. Xu, L. Huang and D. Z. Pan et al, "Redundant-Via Enhanced Maze Routing for Yield Improvement", Proc. of ASP-DAC 2005
[19] G. Xu, R. Tian, D. Z. Pan and M. D.-F. Wong, "CMP Aware Shuttle Mask Floorplanning", Proc. Asia South Pacific Design Automation Conference (ASPDAC), Jan. 2005.
[20] Nardi A., Sangiovanni-Vincentelli A.L., "Logic synthesis for manufacturability", Design & Test of Computers 2004, vol. 21, Issue 3:192～199
[21] H.T. Heineken, J. Khare and M. d'Abreu, "Manufacturability Analysis of Standard Cell Libraries," Proc.of CICC 1998:321～324
[22] C. Ouyang et al., "Maximizing Wafer Productivity through Layout Optimizations," Proc. of 13th International Conf. VLSI Design 2000:192～197
[23] V.K.R. Chiluvuri and I. Koren, "Layout-Synthesis Techniques for Yield Enhancement," IEEE Trans. Semiconductor Manufacturing May 1995, vol. 8, no. 2:178～187
[24] V.K.R. Chiluvuri and I. Koren, "Yield Enhancement vs. Performance Improvement in VLSI Circuits," Proc. of ISSM 1995:28～31
[25] Yang Yang, Tong Jing and Xianlong Hong et al, "Via-Aware Global Routing for Good VLSI Manufacturability and High Yield", 16th IEEE International Conference on Application-Specific Systems, Architecture Processors, ASAP 2005:198～203
[26] Tyagi A, Bayoum M. A., "ULSI design-for-manufacturability: a yield enhancement approach", Proc. of Third International Conference on the Economics of Design, Test, and Manufacturing 1994:80
[27] Riviere-Cazaux L., Lucas K. and Fitch J., "Integration of design for manufacturability (DFM) practices in design flows", ISQED 2005:102～106
[28] Nardi A., Sangiovanni-Vincentelli A.L., "Synthesis for manufacturability: a sanity check", Proc. of Design, Automation and Test in Europe Conference and Exhibition 2004, vol.2:796～801
[29] Jeong-Taek Kong, "CAD for nanometer silicon design challenges and success", IEEE Transactions of Very Large Scale Integration (VLSI) Systems
[30] Hai Zhou and Wong D.F., "Crosstalk-constrained maze routing based on Lagrangian relaxation", Proc. of ICCD 1997:628～633
[31] Mani N., Quach N.H., "Heuristics in the routing algorithm for circuit layout design", Proc. of Computers and Digital Techniques 2005, vol. 147:59～64
[32] Hill D. and Shugard D., "Global routing considerations in a cell synthesis system", Proc. of DAC 1990:312～316
[33] Huijbregts E.P., Hua Xue and Jess J.A.G., "Routing for reliable manufacturing", IEEE Transactions on Semiconductor Manufacturing 1995, vol.8, issue2:188～194
[34] Kahng A.B., Bao Liu and Mandoiu I.I., "Nontree routing for reliability and yield improvement", ASAP 2005:198～203
[35] Jinjun Xiong and Lei He, "Extended global routing with RLC crosstalk constraints", IEEE Transactions on VLSI Systems 2005, vol.3, issue 3:319～329
[36] Sangiovanni-Vincentelli A., "The tides of EDA", Design & Test of Computers 2003, vol.20, issue 6:59～75
[37] Kahng A.B., "Nanometer design: place your bets", Proc. of DAC 2003
[38] Starikov, Kenneth W. Tobin, "RET-compliant cell generation for sub-130-nm processes", Proc. of SPIE 2002, vol. 4692:529～539
[39] Stan M.R., Hamzaoglu, F. Garrett D., "Non-Manhattan maze routing", 17th Symposium on Integrated Circuits and Systems Design, SBCCI 2004:260～265
[40] Huijbregts E.P., Van Eijndhoven J.T.S., Jess J.A.G., "On design rule correct maze routing", Proc. of European Design and Test Conference, EDAC 1994:407～411
[41] Lee C Y. An algorithm for path connections and its applications. IRE Trans. on Electronic Computers, 1961, 10(3):346.
[42] Soukup J. Fast maze router. Proc. IEEE Design Automation Conference (DAC'78), 1978:100.
[43] Hightower D. A solution to line-routing problems on the continuous plane. Proc. IEEE Design Automation Conference (DAC'69), 1969:1.
[44] Nair R. A simple yet effective technique for global wiring. 1EEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 1987, 6(2): 165.
[45] McMurchie L, Ebeling C. PathFinder: a negotiation-based performance-driven router for FPGAs. Proc. ACM Symposium on Field-Programmable Gate Arrays (FPGA'95), 1995:111.
[46] Meixner G, Lauther U. A new global router based on a flow model and linear assignment. Proc. IEEE International Conference on Computer-Aided Design (ICCAD'90), 1990:44.
[47] Albrecht C. Provably good global routing by a new approximation algorithm for multicommodity flow. Proc. International Symposium on Physical Design (ISPD'00), 2000:19.
[48] Burstein M, Pelavin R. Hierarchical channel router. Proc. IEEE Design Automation Conference (DAC'83), 1983:591.
[49] Lin Y-L, Hsu Y-C, Tsai F-S. Hybrid routing. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 1987, 9(2): 151.
[50] Heisterman J, Lengauer T. The efficient solution of integer programs for hierarchical global routing. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 1991, 10(6):748.
[51] Cong J, Xie M, Zhang Y. An enhanced multilevel routing system. Proc. IEEE International Conference on Computer-Aided Design (ICCAD'02), 2002:51.
[52] Cong J, Fang J, Zhang Y. Multilevel approach to full-chip gridless routing. Proc. IEEE International Conference on Computer-Aided Design (ICCAD'01), 2001:396.
[53] Lin S-P, Chang Y-W. A novel framework for multilevel routing considering routability and performance. Proe. IEEE International Conference on Computer-Aided Design (ICCAD'02), 2002:44.
[54] Ho T Y, Chang Y-W, Chen S J, et al. A fast crosstalk-and performance-driven multilevel routing system. Proc. IEEE International Conference on Computer-Aided Design (ICCAD'03), 2003:382.
[55] Ho T Y, Chang Y-W, Chen S J. Multilevel routing with antenna avoidance. Proc. International Symposium on Physical Design (ISPD'04), 2004:34.
[56] Ho T-Y, Chang C-F, Chang Y-W, et al. Multilevel full-chip routing for the X-based architecture. Proc. IEEE Design Automation Conference (DAC'05), 2005:597.
[57] Chen T-C, Chang Y-W. Multilevel gridless full-chip routing considering optical proximity correction. Proc. IEEE Asia South Pacific Design Automation Conference (ASPDAC'05), 2005:1160.
[58] Kastner R, Bozorgzadeh E, Sarrafzadeh M. Predictable routing. Proc. IEEE International Conference on Computer-Aided Design (ICCAD'00), 2000:110.
[59] Dijkstra E W. A note on two problems in connection with graphs. Numerische Mathematik, 1959, 1:269.