請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46518
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張耀文(Yao-Wen Chang) | |
dc.contributor.author | Chin-Hsiung Hsu | en |
dc.contributor.author | 許欽雄 | zh_TW |
dc.date.accessioned | 2021-06-15T05:13:18Z | - |
dc.date.available | 2010-07-26 | |
dc.date.copyright | 2010-07-26 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-07-22 | |
dc.identifier.citation | [1] C. Albrecht, “Global routing by new approximation algorithms for multicommodityflow,” IEEE Trans. on Computer-Aided Design of Integrated Circuitsand Systems, vol. 20, no. 5, pp. 622–631, May 2001.
[2] W. Arnold, M. Dusa, and J. Finders, “Manufacturing challenges in doublepatterning lithography,” in Proc. of IEEE Intl. Symp. on Semiconductor Manufacturing,pp. 283–286, Tokyo, Japan, September 2006. [3] G. E. Bailey, A. Tritchkov, J.-W. Park, L. Hong, V. Wiaux, E. Hendrickx,S. Verhaegen, P. Xie, and J. Versluijs, “Double pattern EDA solutions for32nm HP and beyond,” in Proc. of Society of Photo-Optical InstrumentationEngineers, vol. 6521, pp. 65211K-1–65211K-12, San Jose, CA, February 2007. [4] P. Berman, A. B. Kahng, D. Vidhani, H. Wang, and A. Zelikovsky, “Optimalphase conflict removal for layout of dark field alternating phase shiftingmasks,” in Proc. of ACM Intl. Symp. on Physical Design, pp. 121–126, Monterey,CA, April 1999. [5] P. Bishop, “Viewpoint: Routing is key to implementing DFM within the designflow,” EE Times, August 1, 2007. [6] D. G. Boyer, “Symbolic layout compaction review,” in Proc. of ACM/IEEEDesign Automation Conf., pp. 383–389, Atlantic City, NJ, June 1988. [7] Cadence Design Systems, Inc., http://www.cadence.com/. [8] Y.-W. Chang, J.-M. Lin, and D. F. Wong, “Matching-based algorithm forFPGA channel segmentation design,” IEEE Trans. on Computer-Aided Designof Integrated Circuits and Systems, vol. 20, no. 6, pp. 784–791, June 2001. [9] Y.-J. Chang, Y.-T. Lee, and T.-C.Wang, “NTHU-Route 2.0: A fast and stableglobal router,” in Proc. of IEEE/ACM Intl. Conf. on Computer-Aided Design,pp. 338–343, San Jose, CA, November 2008. [10] T. Chen and A. Cengiz, “Measuring routing congestion for multi-layer globalrouting,” in Proc. of ACM Great Lakes Symp. on VLSI, pp. 59–62, Chicago,IL, March 2000. [11] H.-Y. Chen, M.-F. Chiang, Y.-W. Chang, L. Chen, and B. Han, “Novel fullchipgridless routing considering double-via insertion, ” in Proc. of ACM/IEEEDesign Automation Conf., pp. 755–760, San Francisco, CA, June 2006. [12] T.-C. Chen and Y.-W. Chang, “Multilevel full-chip gridless routing with applicationsto optical proximity correction,” IEEE Trans. on Computer-AidedDesign of Integrated Circuits and Systems, vol. 26, no. 6, pp. 1041–1053, June2007. [13] H.-Y. Chen, S.-J. Chou, S.-L. Wang, and Y.-W. Chang, “Novel wire densitydriven full-chip routing for CMP variation control,” in Proc. of IEEE/ACMIntl. Conf. on Computer Aided Design, pp. 831–838, San Jose, CA, November2007. [14] H.-Y. Chen, C.-H. Hsu, and Y.-W. Chang, “High-performance global routingwith fast overflow reduction,” in Proc. of ACM/IEEE Asia and South PacificDesign Automation Conf., pp. 582–587, Yokohama, Japan, January 2009. [15] H.-Y. Chen, Modern VLSI Routing Considering Reliability and Manufacturability,Doctoral Dissertation, Graduate Institute of Electronics Engineering,National Taiwan University, 2009. [16] T.-B. Chiou, R. Socha, H. Chen, L. Chen, S. Hsu, P. Nikolsky, A. van Oosten,and A. C. Chen, “Development of layout split algorithms and printability evaluation for double patterning technology,” in Proc. of Society of Photo-Optical Instrumentation Engineers, vol. 6924, pp. 69243M-1–69243M-10, SanJose, CA, February 2008. [17] Y. E. Cho, A. J. Kroenjak, and D. E. Stockton, “Floss: An approach toautomated layout for high-volume designs,” in Proc. of ACM/IEEE DesignAutomation Conf., pp. 138–141, New Orleans, LA, June 1977. [18] M. Cho and D. Z. Pan, “BoxRouter: A new global router based on box expansionand progressive ILP,” in Proc. of ACM/IEEE Design Automation Conf.,pp. 373–378, San Francisco, CA, June 2006. [19] M. Cho, D. Z. Pan, H. Xiang, and R. Puri, “Wire density driven global routingfor CMP variation and timing,” in Proc. of IEEE/ACM Intl. Conf. onComputer-Aided Design, pp. 487–492, San Jose, CA, November 2006. [20] M. Cho, K. Lu, K. Yuan, and D. Z. Pan, “BoxRouter 2.0: Architecture andimplementation of a hybrid and robust global router,” in Proc. of IEEE/ACMIntl. Conf. on Computer-Aided Design, pp. 503–508, San Jose, CA, November 2007. [21] M. Cho, Y. Ban, and D. Z. Pan, “Double patterning technology friendly detailedrouting,” in Proc. of IEEE/ACM Intl. Conf. on Computer Aided Design,pp. 506–511, San Jose, CA, November 2008. [22] J. Cong, J. Fang, and K.-Y Khoo, “An implicit connection graph maze routingalgorithm for ECO routing,” in Proc. of IEEE/ACM Intl. Conf. on Computer-Aided Design, pp. 163–167, San Jose, CA, November 1999. [23] C. Chu, “FLUTE: Fast lookup table based wirelength estimation technique,”in Proc. of IEEE/ACM Intl. Conf. on Computer-Aided Design, pp. 696–701,San Jose, CA, November 2004. [24] G. W. Clow, “A global routing algorithm for general cells,” in Proc. ofACM/IEEE Design Automation Conf., pp. 45–51, Albuquerque, NM, June1984. [25] J. Cong, M. Xie and Y. Zhang, “An enhanced multilevel routing system,” inProc. of IEEE/ACM Intl. Conf. on Computer-Aided Design, pp. 51–58, SanJose, CA, November 2002. [26] M. Drapeau, V. Wiaux, E. Hendrickx, S. Verhaegen, and T. Machida, “Doublepatterning design split implementation and validation for the 32nm node,” inProc. of Society of Photo-Optical Instrumentation Engineers, vol. 6521, pp.652109-1–652109-15, San Jose, CA, February 2007. [27] FGR: A Fairly Good Router, http://vlsicad.eecs.umich.edu/BK/FGR/. [28] J. Finders and S. H. M. Dusa, “Double patterning lithography: The bridgebetween low k1 ArF and EUV,” Microlithography World, February 1, 2008. [29] J.-R. Gao, P.-C. Wu, and T.-C. Wang, “A new global router for moderndesigns,” in Proc. of ACM/IEEE Asia and South Pacific Design AutomationConf., pp. 232–237, Seoul, Korea, January 2008. [30] M. R. Garey and D. S. Johnson, A Guide to the Theory of NP-Completeness,Freeman, 1979. [31] R. S. Ghaida, G. Torres, and P. Gupta, “Single-mask double-patterning lithography,”in Proc. of Society of Photo-Optical Instrumentation Engineers, vol.7488, pp. 74882J-1–74882J-11, Monterey, CA, September 2009. [32] K. Golshan, Physical Design Essentials: An ASIC Design ImplementationPerspective, Springer, 2007. [33] M. Heins, “In the eye of the DFM/DFY storm,” EE Times, May 25, 2007. [34] F.-L. Heng, Z. Chen, and G. E. Tellez, “A VLSI artwork legalization techniquebased on a new criterion of minimum layout perturbation,” in Proc. of ACMIntl. Symp. on Physical Design, pp. 116–121, Napa Valley, CA, April 1997. [35] F.-L. Heng, L. Liebmann, and J. Lund, “Application of automated designmigration to alternating phase shift mask design,” inProc. of ACMIntl. Symp.on Physical Design, pp. 38–43, Sonoma, CA, April 2001. [36] C.-H. Hsu, H.-Y. Chen, and Y.-W. Chang, “Multi-layer global routing consideringvia and wire capacities,” in Proc. of IEEE/ACM Intl. Conf. onComputer-Aided Design, pp. 350–355, San Jose, CA, November 2008. [37] J. Hu and S. S. Sapatnekar, “A survey on multi-net global routing for integratedcircuits,” Integration, the VLSI Journal, vol. 31, no. 1, pp. 1–49,November 2001. [38] Intl. Technology Roadmap for Semiconductors, http://public.itrs.net/. [39] ISPD 2007 Global Routing Contest, http://www.sigda.org/ispd2007/rcontest/. [40] ISPD 2008 Global Routing Contest, http://www.ispd.cc/contests/ispd08rc.html/. [41] A. B. Kahng, S. Vaya, and A. Zelikovsky, “New graph bipartizations fordouble-exposure, bright field alternating phase-shift mask layout,” in Proc.of ACM/IEEE Asia and South Pacific Design Automation Conf., pp. 133–138, Yokohama, Japan, January 2001. [42] A. B. Kahng, C.-H. Park, X. Xu, and H. Yao, “Layout decomposition for doublepatterning lithography,” in Proc. of IEEE/ACM Intl. Conf. on ComputerAided Design, pp. 465–472, San Jose, CA, November 2008. [43] R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh, “Pattern routing: Use andtheory for increasing predictability and avoiding coupling,” IEEE Trans. onComputer-Aided Design of Integrated Circuits and Systems, vol. 21, no. 7,pp. 777–790, July 2002. [44] C. Y. Lee, “An algorithm for path connection and its application,” IRE Trans.on Electronic Computer, vol. 10, pp. 346–365, September 1961. [45] Y.-H. Lin and Y.-L. Li, “Double patterning lithography aware gridless detailedrouting with innovative conflict graph,” in Proc. of ACM/IEEE DesignAutomation Conf., pp. 398–403, Anaheim, CA, June 2010. [46] W.-H. Liu, W.-C. Kao, Y.-L. Li, and K.-Y. Chao, “Multi-threaded collisionawareglobal routing with bounded-length maze routing,” in Proc. ofACM/IEEE Design Automation Conf., pp. 200–2005, Anaheim, CA, June2010. [47] M. J. Lorenzetti and D. S. Baeder, Routing in Physical Design Automation ofVLSI Systems, Benjamin/Cummings, 1988. [48] L. McMurchie and C. Ebeling, “PathFinder: A negotiation-basedperformance-driven router for FPGAs,” in Proc. of Intl. ACM Symp. on Field-Programmable Gate Arrays, pp. 111–118, Monterey, CA, February 1995. [49] M. D. Moffitt, “MaizeRouter: Engineering an effective global router,” in Proc.of ACM/IEEE Asia and South Pacific Design Automation Conf., pp. 226–231,Seoul, Korea, January 2008. [50] M. D. Moffitt, “MAIZEROUTER: Engineering an effective global router,”IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems,vol. 27, no. 11, pp. 2017–2026, November 2008. [51] A. van Oosten, P. Nikolsky, J. Huckabay, R. Goossens, and R. Naber, “Patternsplit rules! A feasibility study of rule based pitch decomposition for doublepatterning,” in Proc. of Society of Photo-Optical Instrumentation Engineers,vol. 6730, pp. 67301L-1–67301L-7, San Jose, CA, February 2007. [52] J. K. Ousterhout, “Corner stitching: A data-structuring technique for VLSIlayout tools,” IEEE Trans. on Computer-Aided Design of Integrated Circuitsand Systems, vol. 3, no. 1, pp. 87–100, January 1984. [53] M. M. Ozdal, “ARCHER: A history-driven global routing algorithm,” in Proc.of IEEE/ACM Intl. Conf. on Computer-Aided Design, pp. 488–495, San Jose,CA, November 2007. [54] M. M. Ozdal and M. D. F. Wong, “Archer: A history-based global routingalgorithm,” IEEE Trans. on Computer-Aided Design of Integrated Circuitsand Systems, vol. 28, no. 4, pp. 528–540, April 2009. [55] M. Pan and C. Chu, “FastRoute: A step to integrate global routing intoplacement,” in Proc. of IEEE/ACM Intl. Conf. on Computer-Aided Design,pp. 464–471, San Jose, CA, November 2006. [56] M. Pan and C. Chu, “IPR: An integrated placement and routing algorithm,”in Proc. of IEEE/ACM Design Automation Conf., pp. 59–62, San Diego, CA,June 2007. [57] M. Pan and C. Chu, “FastRoute 2.0: A high-quality and efficient globalrouter,” in Proc. of ACM/IEEE Asia and South Pacific Design AutomationConf., pp. 250–255, Yokohama, Japan, January 2007. [58] Y. Pan, H. Zhang, and Y. Chen, “A new OPC method for double patterningtechnology,” in Proc. of Society of Photo-Optical Instrumentation Engineers ,vol. 6924, pp. 692422-1–692422-10, San Jose, CA, February 2008. [59] J. Park, S. Hsua, D. Van Den Broekea, J. F. Chena, M. Dusab, R. Sochab,J. Findersc, B. Vleemingc, A. van Oostenc, P. Nikolskyc, V. Wiauxd, E. Hendrickxd,J. Bekaertd, and G. Vandenberghed, “Application challenges withdouble patterning technology (DPT) beyond 45 nm,” in Proc. of Society ofPhoto-Optical Instrumentation Engineers, vol. 6349, pp. 634922-1–634922-12,Monterey, CA, September 2006. [60] J. K. Qusterhout, “Corner stitching: A data structuring technique for VLSIlayout tools,” IEEE Trans. on Computer-Aided Design of Integrated Circuitsand Systems, vol. 3, no. 1, pp. 87–100, January 1984. [61] J. A. Roy and I. L. Markov, “High-performance routing at the nanometerscale,” in Proc. of IEEE/ACM Intl. Conf. on Computer-Aided Design,pp. 496–502, San Jose, CA, November 2007. [62] J. A. Roy and I. L. Markov, “High-performance routing at the nanometerscale,” IEEE Trans. on Computer-Aided Design of Integrated Circuits andSystems, vol. 27, no. 6, pp. 1066–1077, June 2008. [63] J. Rubinstein and A. R. Neureuther, “Post-decomposition assessment of doublepatterning layouts,” in Proc. of Society of Photo-Optical InstrumentationEngineers, vol. 6924, pp. 69240O-1–69240O-12, San Jose, CA, February 2008. [64] S. M. Sait, H. Youssef, S. Tanvir, and M. S. T. Benten, “Timing influencedgeneral-cell genetic floorplanner,” in Proc. of ACM/IEEE Asia and SouthPacific Design Automation Conf., pp. 135–140, Chiba, Japan, August 1995. [65] L. Scheffer, “Routing,” in EDA for IC Implementation, Circuit Design, andProcess Technology, Taylor & Francis, 2006. [66] M. Schiag, Y. Z. Liao, and C. K. Wong, “An algorithm for optimal twodimensionalcompaction of VLSI layouts,” in Proc. of IEEE/ACM Intl. Conf.on Computer Aided Design, pp. 88–89, San Jose, CA, November 1983. [67] A. Sezginer, B. Yenikaya, and W. Staud, “Double patterning technology:Process-window analysis in a many-dimensional space,” in Proc. of Societyof Photo-Optical Instrumentation Engineers, vol 6607, pp. 66072S-1–66072S-9, San Jose, CA, February 2007. [68] N. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer, 3rdEd., 2002. [69] W. Swartz, “Issues in global routing,” in Proc. of ACM Intl. Symp. on PhysicalDesign, pp. 142–147, Portland, OR, April 2008. [70] Synopsys, Inc., http://www.synopsys.com/. [71] T. G. Szymanski, “Dogleg channel routing is NP-complete,” IEEE Trans.on Computer-Aided Design of Integrated Circuits and Systems, vol. 4, no. 1,pp. 31–41, January 1985. [72] X. Tang and X. Yuan, “Technology migration techniques for simplified layoutswith restrictive design rules,” in Proc. of IEEE/ACM Intl. Conf. on ComputerAided Design, pp. 655–660, San Jose, CA, November 2006. [73] UMC Free Library, http://freelibrary.faraday-tech.com/. [74] Y. Xu and C. Chu, “GREMA: Graph reduction based efficient mask assignmentfor double patterning technology,” in Proc. of IEEE/ACM Intl. Conf.on Computer-Aided Design, pp. 601–606, San Jose, CA, November 2009. [75] Y. Xu, Y. Zhang, and C. Chu, “FastRoute 4.0: Global router with efficientvia minimization,” in Proc. of ACM/IEEE Asia and South Pacific DesignAutomation Conf., pp. 576–581, Yokohama, Japan, January 2009. [76] Y. Yang, T. Jing, X. Hong, Y. Hu, Q. Zhu, X. Hu, and G. Yan, “Via-awareglobal routing for good VLSI manufacturability and high yield,” in Proc. ofIEEE Intl. Conf. on Application-Specific Systems, Architecture Processors, pp.198–203, Samos, Greece, July 2005. [77] J.-S. Yang, K. Lu, M. Cho, K. Yuan, and D. Z. Pan, “A new graph-theoretic,multi-objective layout decomposition framework for double patterning lithography,”in Proc. of IEEE/ACM Asian and South Pacific Design AutomationConf., pp. 637–644, Taipei, Taiwan, January 2010. [78] K. Yuan, J.-S. Yang, and D. Z. Pan, “Double patterning layout decompositionfor simultaneous conflict and stitch minimization,” in Proc. of ACM Intl.Symp. on Physical Design, pp. 107–114, San Diego, CA, March 2009. [79] K. Yuan, K. Lu, and D. Pan, “Double patterning lithography friendly detailedrouting with redundant via consideration,” in Proc. of IEEE/ACM DesignAutomation Conf., pp. 63–66, San Francisco, CA, July 2009. [80] Y. Zhang, Y. Xu, and C. Chu, “FastRoute 3.0: A fast and high qualityglobal router based on virtual capacity,” in Proc. of IEEE/ACM Intl. Conf.on Computer-Aided Design, pp. 344–349, San Jose, CA, November 2008. [81] S. Q. Zheng, J. S. Lim, and S. S. Iyengar, “Finding obstacle-avoiding shortestpaths using implicit connection graphs,” IEEE Trans. on Computer-AidedDesign of Integrated Circuits and Systems, vol. 15, no. 1, pp. 103–110, January1996. [82] H. Zhou and D. F. Wong, “Global Routing with Crosstalk Constraints,” inProc. of IEEE/ACM Design Automation Conf., pp. 374–377, San Francisco,CA, June 1998. [83] J. Zhu, F. Fang, and Q. Tang, “Calligrapher: A new layout-migration enginefor hard intellectual property libraries,” IEEE Trans. on Computer-Aided Designof Integrated Circuits and Systems, vol. 24, no. 9, pp. 1347–1361, September2005. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46518 | - |
dc.description.abstract | 隨著積體電路技術的不斷進步,由於可印刷性和可製造性的問題,微影製程遇到了瓶頸。雙圖案微影技術近來備受注目而且被視為最適用於32 奈米製程的技術,因為雙圖案微影技術可以在目前的基礎設施上,加大最小圖案距離(高達二倍),從而將193i 光源波長的使用延伸到32 奈米節點,甚至可能到16 奈米節點。雙圖案微影技術將一個佈局分解到二個光罩上,然後使用雙重圖案曝光技術以加大最小圖案距離並提升圖案的可印刷性。雙圖案微影技術的圖案衝突(conflict)是指佈局無法被完整地分解;雙圖案微影技術的縫合圖案(stitch)是指一個佈局圖案被切割成二個圖案並分解到不同的光罩上。但是,現有的設計流程與雙圖案微影技術無法相容,因為所產生的電路佈局無法完整地分解到二片光罩上。因此,開發相容於雙圖案微影技術的設計流程是非常重要的,尤其是那些與雙圖案微影技術強烈相關的設計步驟,包括:(1)以佈局遷移為基礎的電路單元設計、(2)全域繞線、以及(3)細部繞線。此外,光罩成本的倍數成長也是雙圖案微影技術所引起一個重要的問題,所以我們的相容於雙圖案微影技術的設計流程會最小化光罩的使用量。
當積體電路的微影製程不斷演進,手動設計電路單元卻因為非常花時間而漸漸跟不上微影製程的腳步,因此,以佈局遷移為基礎的電路單元設計變得非常熱門。佈局遷移和雙圖案微影技術的佈局分解成為兩個密切相關的問題。因此,我們提出文獻上第一個同時完成電路佈局的遷移和分解之問題,並使用整數線性規劃方法以得到最終電路佈局。 晶片繞線是一個非常複雜的過程,現代的晶片繞線通常分為全域繞線和細部繞線;全域繞線先產生一個概略的繞線路徑,而細部繞線決定實際的詳細繞線路徑,也就是產生電路佈局。全域繞線是一個重要的實體設計步驟,但現有的全域繞線的繞線模型沒有考慮雙圖案微影技術的影響,也忽略了多重金屬層需要合理的導通孔(via)分佈。因此,我們提出了一個新的全域繞線模型與全域繞線器,並考慮合理的導通孔分布與雙圖案微影技術的影響。 在考量雙圖案微影技術的情況下,細部繞線是很重要的一環,因為它決定金屬層的佈局;同時,細部繞線也提供了一個很好的機會,去減少雙圖案微影技術所使用的光罩數量。我們提出了第一個在雙圖案微影技術下,讓不同的晶片設計能夠共享光罩的設計方法,以達到減少光罩使用量之目的。我們所提出的設計方法首先設計好模版光罩再完成考慮模版光罩的細部繞線,而且我們的細部繞線演算法所產生的繞線結果可以符合雙圖案微影技術與模版光罩的限制。 實驗結果顯示,相對於傳統的設計流程,我們的相容於雙圖案微影技術的設計流程所得到的結果擁有較小的電路佈局面積、較少的縫合圖案與較短的線長,雖然使用較多的導通孔與運算時間,但皆在合理範圍之內。此外,我們的相容於雙圖案微影技術的設計流程可以得到無衝突(conflict-free)的電路佈局,並總共節省了八片光罩;而傳統的設計流程不僅產生的電路佈局有衝突,也無法節省任何光罩。結果顯示了我們的相容於雙圖案微影技術的設計流程的有效性和我們所提的相關技術與現有的電子設計自動化(EDA)工具的相容性。 | zh_TW |
dc.description.abstract | As IC technology continues to advance, lithography process meets the bottleneck due to printability and manufacturability. Double patterning technology (DPT) has recently gained much attention and is viewed as the most promising solution for the sub-32-nm node process, since it can increase the half-pitch resolution by up to two times using current infrastructures, thereby extending 193i wavelength beyond the 32-nm node and potentially down to the 16-nm node. DPT decomposes a layout into two masks and applies double exposure patterning to increase the pitch size and thus printability; conflict arises if layouts are not decomposable, and a stitch is induced if two touching sub-patterns of the same pattern are decomposed into different masks. However, the existing design flow is not compatible with DPT since resulting layouts with patterns are not decomposable. Therefore, it is desirable to develop a DPT-compliant design flow that focuses on strongly DPT-related stages, including (1) layout-migration-based cell design, (2) global routing, and (3) detailed routing. Besides, the cost of doubling masks is also an important problem for DPT, so our DPT-compliant design flow would minimize the number of masks for DPT.
Layout-migration-based cell design becomes very popular as IC technology continues to advance very quickly and manual cell design is very time-consuming. Layout migration and DPT layout decomposition become two closely related problems for DPT-aware cell design. Therefore, we present the first algorithm in the literature for the simultaneous layout migration and decomposition (SMD) problem. Our algorithm first constructs a potential conflict graph and DPT-aware constraint graphs, and then applies integer linear programming (ILP) corresponding to the graphs to obtain a decomposed and migrated layout. We further present an effective graph-based reduction technique to prune the ILP solution space. In addition, we present an approach to generate DPT-aware standard cells by considering the DPT effects on the cell boundaries to handle the DPT issues in the weakly-pattern-related placement stage. Routing is a very complex process in a modern chip, so routing is often divided into global routing and detailed routing; global routing generates a loose route for each net while detailed routing finds the actual geometric layout of nets. Global routing is an important step for physical design, but existing global routing congestion models ignore DPT effects and reasonable via usage for routing through multiple metal layers. Such simplified models would easily cause fatal routability and DPT-compliant problems in the subsequent detailed routing. To remedy this deficiency, a more effective congestion metric that considers both the DPT effects and the reasonable via usage for global routing is presented. With this metric, we develop a new multi-layer global router that features two novel routing algorithms, namely aerial-monotonic routing and escaping-point routing. Detailed routing is an important step to make layouts DPT-compliant since it decides actual geometric layout of nets; besides, it also has an opportunity to reduce the number of masks for DPT. We proposes the first mask-sharing methodology for DPT, which can share masks among different designs, to reduce the number of costly masks for double patterning. The design methodology consists of two tasks: template-mask design and template-mask-aware detailed routing. A graph matching-based algorithm is developed to design a flexible template mask that tries to accommodate as many design patterns as possible. We also present a template-mask- aware detailed routing (TMR) algorithm, focusing on DPT-related issues to generate routing solutions that satisfy the constraints induced from double pattern ing and template masks. Experimental results show that, compared with the non-DPT-compliant design flow, our DPT-compliant design flow can achieve smaller layout area, fewer stitches, and shorter wirelength with reasonable via and runtime overheads. In addition, our DPT-compliant design flow can obtain conflict-free layouts and totally save eight masks for DPT while the non-DPT-compliant design flow cannot. The results show the effectiveness of our DPT-compliant design flow and the compatibility between our DPT-related techniques and existing electronic design automation (EDA) tools. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T05:13:18Z (GMT). No. of bitstreams: 1 ntu-99-F94943075-1.pdf: 3728784 bytes, checksum: 34c7579b37b3765df88f9bffe02d3836 (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | Acknowledgements ii
Abstract x List of Tables xvi List of Figures xvii Chapter 1. Introduction 1 1.1 Double Patterning Technology . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 DPT-Compliant Design Flow . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Cell Design Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 Cell Design Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.2 Cell Design Challenges . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4 Global Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.1 Global Routing Basics . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.4.2 Global Routing Challenges . . . . . . . . . . . . . . . . . . . . . . 22 1.5 Detailed Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.5.1 Detailed Routing Basics . . . . . . . . . . . . . . . . . . . . . . . . 24 1.5.2 Detailed Routing Challenges . . . . . . . . . . . . . . . . . . . . . 25 1.6 Overview of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.6.1 DPT-Aware Cell Redesign with Simultaneous Layout Migration and Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.6.2 DPT-Aware Multi-Layer Global Routing with Via/Wire Capacity Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.6.3 DPT-Aware Detailed Routing with Template Mask Consideration 29 1.7 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . 30 Chapter 2. DPT-Aware Cell Redesign with Simultaneous Layout Migration and Decomposition 31 2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.2 ProblemFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3 Simultaneous Layout Migration and Decomposition Flow . . . . . . . . . 37 2.3.1 Potential DPT-Conflict Graphs and Pattern Splitting . . . . . . . 38 2.3.2 DPT-aware Constraint Graphs . . . . . . . . . . . . . . . . . . . . 39 2.3.3 Basic ILP Formulation. . . . . . . . . . . . . . . . . . . . . . . . . 41 2.3.4 ILP Problem-Size Reduction . . . . . . . . . . . . . . . . . . . . . 48 2.3.5 DPT-aware Standard Cells . . . . . . . . . . . . . . . . . . . . . . 51 2.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Chapter 3. DPT-Aware Multi-Layer Global Routing with Via/Wire Capacity Considerations 58 3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.2 ProblemFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.3 RoutingMethodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.4 Planar 2D Global Routing . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.4.1 Prerouting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.4.2 Initial IterativeMonotonic Routing . . . . . . . . . . . . . . . . . . 72 3.4.3 Iterative Forbidden-Region Rip-up/Rerouting (IFR) . . . . . . . . 73 3.5 Multi-Layer 3D Rip-Up and Rerouting . . . . . . . . . . . . . . . . . . . 81 3.5.1 Layer Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.5.2 3D Routing Cost Function . . . . . . . . . . . . . . . . . . . . . . 82 3.5.3 3D Routing Techniques . . . . . . . . . . . . . . . . . . . . . . . . 83 3.6 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3.6.1 Global Routing Results without Considering Via Capacity . . . . . 96 3.6.2 Via-Aware Global Routing Results . . . . . . . . . . . . . . . . . . 98 3.6.3 DPT-Aware Global Routing Results . . . . . . . . . . . . . . . . . 101 3.6.4 Efficiency of Aerial-Monotonic Routing . . . . . . . . . . . . . . . 108 Chapter 4. DPT-Aware Detailed Routing with Template Mask Consideration 109 4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 4.2 ProblemFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 4.3 Template Mask Design Methodology . . . . . . . . . . . . . . . . . . . . 114 4.3.1 Template Mask Design . . . . . . . . . . . . . . . . . . . . . . . . 116 4.3.2 Template-Mask-Aware Routing Flow . . . . . . . . . . . . . . . . . 119 4.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 4.5 Comparisons between DPT-Compliant and Non-DPT-Compliant Design Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 Chapter 5. Concluding Remarks and Future Work 132 Bibliography 137 Vita 147 Publication List 148 | |
dc.language.iso | en | |
dc.title | 雙圖案微影技術之晶片設計方法 | zh_TW |
dc.title | Design Methodology for Double Patterning Technology | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-2 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 郭斯彥(Sy-Yen Kuo),林永隆(Youn-Long Lin),黃婷婷(Ting-Ting Hwang),王廷基(Ting-Chi Wang),李毅郎(Yih-Lang Li) | |
dc.subject.keyword | 雙圖案微影技術,可製造性,實體設計,繞線,超大型積體電路, | zh_TW |
dc.subject.keyword | Double Patterning,Manufacturability,Physical Design,Routing,VLSI, | en |
dc.relation.page | 149 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2010-07-23 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 3.64 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。