進階搜尋


下載電子全文  
系統識別號 U0026-1908201515501800
論文名稱(中文) 基於動態規劃演算法且以可繞度為導向之電源網路規劃方法
論文名稱(英文) A Routability-Driven Powerplanning Methodology Based in the Dynamic Programming Algorithm
校院名稱 成功大學
系所名稱(中) 電機工程學系
系所名稱(英) Department of Electrical Engineering
學年度 103
學期 2
出版年 104
研究生(中文) 翁子清
研究生(英文) Tzu-Ching Weng
學號 N26021343
學位類別 碩士
語文別 中文
論文頁數 52頁
口試委員 指導教授-林家民
口試委員-李毅郎
口試委員-張順志
口試委員-趙家佐
中文關鍵字 電源網路規劃  電壓下降  可繞度  繞線擁擠 
英文關鍵字 Powerplanning  IR-Drop  Routability  Routing Congestion 
學科別分類
中文摘要 在積體電路(IC)設計流程當中,電源網路規劃(Powerplanning)是實體設計(Physical Design)中非常重要的步驟。但是隨著半導體產業製程技術的進步,積體電路中的電晶體元件大幅增加,導致元件之間的連線關係更為複雜,使得繞線難度大幅度提高,故在電源網路規劃時必須考慮積體電路可繞度(Routability)的議題。目前工業界的做法大多是透過經驗豐富的工程師利用設計自動化工具手動完成電源網路規劃,為了滿足電壓下降(IR-Drop)的限制,往往會使用大量的金屬線佈滿整個晶片,如此的做法會讓電源網路使用過多不必要的繞線面積且佔用許多繞線資源,因而增加設計成本。倘若做到繞線階段發現有不可繞的區域,才會斟酌對電源網路線段做刪減,然而此做法則相當耗費實體設計的時間。過去的學術研究當中,有關於電源網路規劃的研究,多半是調整電源網路線段的粗細來滿足電壓下降的限制,鮮少提及有關可繞度的議題。不同於以往的研究,本論文使用一個可以估計電源網路金屬層面積的等效電路模型來滿足電壓下降的限制,再使用適當的線寬讓電源網路線段佔據較少的繞線資源;本論文亦考量繞線擁擠程度,並使用動態規劃(Dynamic Programming)的演算法去決定每一條電源線段的擺放位置,使整體設計具有良好的可繞度。實驗結果顯示,本論文的方法不僅可以滿足電壓下降的限制,並且使用較少的繞線資源,進而提高繞線階段的可繞度。
英文摘要 In modern IC design flow, powerplanning plays a crucial role in the stage of physical design. Due to advance in manufacture technology, the number of transistors have been increased substantially and the netlists have been more complicated in a chip. Thus, it caused the difficulty in routing stage. It became an important issue considering routability during powerplanning. In most industrial practice, experienced engineers complete the power network through EDA tools manually. In order to satisfy with the constraint of IR-drop, they always use a large amount of metal stripes to cover the whole chip. Such method will cause power network using too many unnecessary areas and routing resources, the cost of the design will increase. Additionally, some power strips will be removed when finding out un-routable regions during routing stage. However, such method may delay design cycle. Nevertheless, most of the previous researches concern about wire sizing to satisfy with the constraint of IR-drop, but few of them mention about routability issue. Unlike these previous works, this thesis adopts an equivalent circuit model to estimate the total usage area of power network to meet the constraint of IR-drop, and use such a suitable width that power stripes take less routing resources. Also, we consider the routing congestion, determine the location of each power stripes based on the dynamic programming algorithm, and make the whole design have good routability. The experimental results validate our method can not only satisfy with the constraint of IR-drop, but also make designs very routable.
論文目次 摘要 I
誌謝 VII
目錄 VIII
表格目錄 X
圖片目錄 XI
第一章. 簡介 1
1.1 電源網路的結構 2
1.1.1電源環 3
1.1.2 電源線段 4
1.1.3 電源軌道 5
1.2 相關文獻探討 6
1.3 研究貢獻 7
1.4 論文架構 8
第二章. 電源網路設計議題與問題描述 9
2.1. 電壓下降 9
2.2. 可繞度(ROUTABILITY) 10
2.2.1 可用繞線軌道(Available Routing Track) 10
2.2.2 繞線迂迴(Routing Detour) 14
2.3. 問題描述 16
第三章. 相關研究回顧[1] 18
3.1 非冗餘線寬 18
3.2 動態規劃演算法 21
第四章. 本論文的電源網路設計方法 23
4.1 本論文電源網路設計流程 23
4.2 決定電源網路金屬層的總線寬 24
4.3 挑選高效能線寬 27
4.4 估計繞線擁擠程度與成本值 30
4.4.1 繞線擁擠程度 31
4.4.2 以繞線擁擠程度當做成本值 34
4.5 考量繞線擁擠程度的動態規劃演算法 37
4.5.1 本論文的動態規劃演算法 38
4.5.2 電源網路的後優化 40
第五章. 實驗結果 41
5.1 可用繞線軌道量的比較 42
5.2 電壓下降與可繞度的比較 43
第六章. 結論 50
第七章. 參考文獻 51
參考文獻 [1] W.-H. Chang, M.C.-T. Chao and S.-H. Chen, “Practical Routability-Driven Design Flow for Multilayer Power Networks Using Aluminum-Pad Layer,” IEEE Trans. on VLSI Systems, vol. 22(5), pp. 1069-1081, Jun. 2013.
[2] H. Chen, C.-K. Cheng, A.B. Kahng, M. Mori and Q. Wang, “Optimal Planning for Mesh-Based Power Distribution,” in Proc. ASP-DAC, pp. 444-449, 2004.
[3] C. Chu and Y.-C. Wong, “FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,” IEEE Trans. on CAD, vol. 27(1), pp. 70-83, Jan 2008.
[4] P. Falkenstern, Y. Xie, Y.-W Chang and Y. Wang, “Three-Dimensional Integrated Circuits (3D IC) Floorplan and Power/Ground Network Co-Synthesis,” in Proc. ASP-DAC, pp. 169-174, 2010.
[5] C.-C. Huang, C.-T. Lin, W.-S. Liao, C.-J. Lee, H.-M. Chen, C.-H. Lee and D.-M. Kwai, “Improving Power Delivery Network Design by Practical Methodologies,” in Proc. ICCD, pp. 237-242, 2014.
[6] W.-P. Lee and Y.-W. Chang, “Post-Floorplanning Power/Ground Ring Synthesis for Multiple-Supply-Voltage Designs,” in Proc. ISPD, pp. 5-12, 2009.
[7] C.-C. Lin, “Placement Density Aware Power Switch Insertion Algorithm for Power Gating Designs,” Thesis for Master of Science, 2014.
[8] S.S.-Y. Liu, C.-J. Lee, C.-C. Huang, H.-M. Chen, C.-T. Lin and C.-H. Lee, “Effective Power Network Prototyping via Statistical-Based Clustering and Sequential Linear Programming,” in Proc. DATE, pp. 1701-1706, 2013.
[9] C.-J. Lee, S.S.-Y. Liu, C.-C. Huang, H.-M. Chen C.-T. Lin and C.-H. Lee, “Hierarchical Power Network Synthesis for Multiple Power Domain Designs,” in Proc. ISQED, pp. 477-482, 2012.
[10] W.-K. Mak and J.-W. Chen, “Voltage Island Generation under Performance Requirement for SoC Designs,” in Proc. ASP-DAC, pp. 798-803, 2007.
[11] X.-D. Tan, C.-J.R. Shi, D. Lungeanu, J.-C. Lee and L.-P. Yuan, “Reliability-Constrained Area Optimization of VLSI Power/Ground Networks via Sequence of Linear Programmings,” in Proc. DAC, pp. 78-83, 2003.
[12] X.-D.S. Tan and C.-J.R. Shi, “Fast Power/Ground Network Optimization Based on Equivalent Circuit Modeling,” in Proc. DAC, pp. 550-554, 2001.
[13] T.-Y. Wang and C.-C. Chen, “Optimization of the Power/Ground Network Wire-Sizing and Spacing Based on Sequential Network Simplex Algorithm,” in Proc. ISQED, pp. 157-162, 2002.
[14] X. Wang, Y. Cai, X. Hong and S.-X. Tan, “Optimal Wire Sizing for Early Stage Power/Ground Grid Planning,” in Proc. ICCCAS, pp. 2406-2410, 2006.
[15] S.-W. Wu and Y.-W. Chang, “Efficient Power/Ground Network Analysis for Power Integrity Driven Design Methodology,” in Proc. DAC, pp. 177-180, 2004.
[16] Y. Zhong and M.D.-F. Wong, “Thermal-Aware IR Drop Analysis in Large Power Grid,” in Proc. ISQED, pp. 194-199, 2008.
[17] P. Zhou, K. Sridharan and S.S. Sapatnekar, “Congestion-Aware Power Grid Optimization for 3D Circuits Using MIM and CMOS Decoupling Capacitors,” in Proc. ASP-DAC, pp. 179-184, 2009.
[18] “https://www.apache-da.com/products/redhawk”
[19] “http://www.cadence.com/products/di/soc_encounter/pages/default.aspx”
[20] “https://www.synopsys.com/apps/support/training/iccompiler_fcd.html”
[21] “http://www.synopsys.com/Tools/Implementation/SignOff/Pages/PrimeRail.aspx”
[22] “http://www.globalfoundries.com”
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2020-08-02起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2020-08-02起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw