跳到主要內容

臺灣博碩士論文加值系統

(34.204.169.230) 您好!臺灣時間:2024/02/28 08:12
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林政強
研究生(外文):Cheng-Chiang Lin
論文名稱:考量電子漂移和障礙物限制之電流導向線路佈線設計
論文名稱(外文):Electromigration Aware Obstacle-Avoiding Current-Driven Wire Planning for Analog Circuits
指導教授:謝財明謝財明引用關係
指導教授(外文):Tsai-Ming Hsieh
學位類別:碩士
校院名稱:中原大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:64
中文關鍵詞:整數線性規劃電流佈線電子漂移
外文關鍵詞:ElectromigrationCurrent-Driven Wire PlanningInteger Linear Programming
相關次數:
  • 被引用被引用:0
  • 點閱點閱:167
  • 評分評分:
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
隨著電路製程技術進入深次微米,電子漂移造成連線開路或是短路的現象越來越嚴重,如何避免電子漂移的問題是一個重要的問題。
本論文針對類比電路之電流導向佈線問題,探討何針對電流源和電流端點進行繞線,避免電子漂移(electromigration)的現象,以最小化電流佈線總面積。本論文將以線性規劃方法,研究電子漂移和障礙物限制的類比電路中電流導向線路佈線規劃問題,以較全面性的方式進行最小化電流導向佈線之總面積。
本演算法包含下列幾個步驟:第一步,將所有的障礙物加一個使用者決定之外框,以避免連線與障礙物的干擾(interference);第二步計算所有起點到端點的連線長度和連線路徑,並將這些長度資料與起點和端點的電流資訊轉成線性規劃條件(ILP formulations);第三步使用ILP的方法來選擇最佳的連線拓樸和每條連線的寬度。第四步將曼哈頓繞線轉成X架構繞線,以進一步降低電流佈線總面積。
本論文提出方法具有以下優點:第一,在考量電子漂移但不具障礙物限制,所提線性規劃為基礎的演算法,可最佳化電流導向佈線之總面積。第二,同時考量避開障礙物所需的連線長度以及連線流經電流的大小,進行最小化線路佈線之總面積。實驗結果發現:針對最大的電路,ILP的方法可比採用貪婪演算法的結果降低總面積達16.8%;平均而言,ILP的方法可比採用貪婪演算法的結果降低總積達12%。
The electromigration issue becomes one of the most important problems in the modern physical design as the manufacture technique enters the deep sub-micro.
In the paper, we study the current-driven wire planning problem with the electromigration and obstacles. The objective of the paper is to minimize the total wire area by using the integer linear programming based approach.
The proposed algorithm contains the following steps. First, the reservation space technique is used for all obstacles to avoid the interference between the wires and obstacles. Second, we calculate the wirelengths of all source-targets pairs with consideration the obstacles. The wirelengths for all sources and targets and the current values of all sources and targets are integrated into the ILP formulations. Third, the wire widths of the topology are determined the Lingo tool. Finally, the X-architecture wire planning is obtained by transforming each wires of the topology. The total wiring area will be further improved.
The advantages of the proposed paper are as follows. First, our proposed approach achieves the optimal wiring area by using the linear programming without obstacles. Second, our approach which simultaneously considers the obstacle-avoiding length and the current density of each wire minimizes the total wiring area. Compared to the results of the greedy method, the results of our proposed ILP-based method are significantly improved by up to 16.8% for the largest testcase and 12% in average.
摘要.................................... I
ABSTRACT...............................III
致謝................................... IV
目錄.............................V
圖目錄.......................... VII
表格目錄.............................X
第一章 前言...........................................1
第二章 相關研究介紹...................................3
2.1 類比電路中電流導向佈線之相關研究..................3
2.2 數位電路自動化技術之相關研究......................15
第三章 研究動機與問題定義.............................26
3.1 研究動機..........................................26
3.2 問題定義..........................................28
第四章 研究方法.......................................30
4.1. 方法一 : 以線性規劃為基礎之電流導向佈線..........30
4.1.1. 將所有障礙物加上一個使用者決定之外框...........31
4.1.2. 障礙物限制下計算連線長度.......................32
4.1.3. 依照最佳化目標設定ILP限制條件,決定拓樸........35
4.1.4. 將曼哈頓繞線轉成X架構繞線......................38
4.2. 方法二 : 以貪婪演算法為基礎之電流導向佈線........40
第五章 實驗結果.......................................42
5.1 實驗平台與測試電路................................42
5.2 實驗結果..........................................43
第六章 結論與未來展望.................................50
參考文獻..............................................51
作者簡介..............................................54
圖1.不同貫穿孔陣列配置的方法..........................4
圖2.不同角度下的電流密度..............................5
圖3.最後布局結果的修正................................6
圖4.電流導向的繞線樹..................................7
圖5.可以加入Steiner-Point的情況.......................8
圖6.考量電子漂移的Steiner tree........................8
圖7.電路上的每個terminal對應的電流值..................9
圖8.mesh graph的建立..................................9
圖9.選擇起始邊........................................10
圖10.建立繞線樹.......................................10
圖11.Detail routing...................................11
圖12.對電路先做電流分析(Current Characterization).....12
圖13.建立steiner tree.................................13
圖14.經過CDR後的結果..................................13
圖15.最後結果.........................................14
圖16.Obstacle penalty.................................16
圖17.子樹合併.........................................16
圖18.修改迂迴線段.....................................17
圖19.演算法例子流程(a)-(f)............................17
圖20.(a)障礙物和(b)腳位所形成的區域(Search region)....18
圖21.演算法例子和流程.................................19
圖22.45度的多層繞線系統...............................20
圖23.TOA-XSMT 構建和重新繞線(a)-(h)...................22
圖24.不同電壓指派的結果...............................23
圖25.BoxRouter 演算法流程.............................25
圖26.優先改善最擁擠區.................................25
圖27.演算法例子說明(a)-(c)............................25
圖28.不具障礙物下連線總面積的比較.....................26
圖29.具障礙物下的佈線.................................27
圖30.避開障礙物與連線間的干擾.........................27
圖31.端點上對應的RMS電流值............................28
圖32.改變模組大小的說明...............................31
圖33.上L、下L穿越障礙物的判斷.........................32
圖34.所有起點至所有端點L-pattern route的連線路徑......32
圖35.建立Spanning graph...............................33
圖36.列出所有起點至所有端點的連線路徑.................33
圖37.考量電子漂移之連線拓樸...........................37
圖38.考量電子漂移之M-架構電流導向佈線.................37
圖39.X架構下的pattern route...........................38
圖40.考量電子漂移之X-架構電流導向佈線.................38
圖41.移除障礙物外框結果...............................39
圖42.連線合併後的結果.................................39
圖43.線性規劃與貪婪演算法流程比較.....................40
圖44.建立所有電流起點到所有電流端點的雙分圖...........41
圖45.分析障礙物的分布.................................47
圖46.具障礙物下比較Greedy與ILP的面積(以RC5為例).......49
表1.測試平台..........................................42
表2.兩實驗所用的測試電路..............................42
表3.不具障礙物下比較貪婪法與ILP的電流總面積...........44
表4.具障礙物下比較貪婪法與ILP的電流總面積.............45
表5.比較貪婪法分別在不具和具障礙物之電流總面積........46
表6.比較ILP分別在不具和具障礙物之電流總面積...........46
表7.比較不同方法下電流總面積..........................48
[1]T. Adler and E. Barke, “Single Step Current Driven Routing of Multiterminal Signal Nets for Analog Applications,” in Proc. of Design, Automation and Test in Europe, pp. 446-450, 2000.
[2]T. Adler, H. Brocke, L. Hedrich and E. Barke, “A Current Driven Routing and Verification Methodology for Analog Applications,” in Proc. of ACM/IEEE Design Automation Conference, pp. 385-389, 2000.
[3]J. R. Black, “Electromigration Failure Models in Aluminum Metallization for Semiconductor Devices,” in Proc. of the IEEE, pp. 1587-1594, 1969.
[4]J. R. Black, “Physics of Electromigration,” in Proc. of IEEE 12th Annual Reliability Physics Symposium, pp.142-149, 1974.
[5]M. Cho and Z. Pan, “BoxRouter: A New Global Router Based on Box Expansion and Progressive ILP” in Proc. of ACM/IEEE Design Automation Conference, pp. 373 - 378, 2006.
[6]T.Y. Ho, C.F. Chang, Y.W. Chang and S. J. Chen, “Multilevel Full-Chip Routing for the X-Based Architecture,” in Proc. of ACM/IEEE Design Automation Conference, pp. 597-602, 2005.
[7]H.H. Huang, S.P. Chang, Y.C. Lin and T.M. Hsieh, “Timing-Driven X-Architecture Router among Rectangular Obstacles,” in Proc. of IEEE International Symposium on Circuits and Systems, pp. 1804-1807, 2008.
[8]G. Jerke, and J. Lienig, “Hierarchical Current-Density Verification in Arbitrarily Shaped Metallization Patterns of Analog Circuits,” in IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, pp. 80–90, 2004.
[9]G. Jerke, J. Lienig, and J. Scheible, “Reliability-Driven Layout Decompaction for Electromigration Failure Avoidance in Complex Mixed-Signal IC Designs,” in Proc. of ACM/IEEE Design Automation Conference, pp. 181–184, 2004.
[10]J. Lienig, “Introduction to Electromigration-Aware Physical Design,” in Proc. of ACM International Symposium on Physical Design, pp.39-46, 2006.
[11]J. Lienig and G. Jerke, “Current-Driven Wire Planning for Electrimigration Avoidance in Analog Circuits,” in Proc. of ACM/IEEE Asia and South Pacific Design Automation Conference, pp. 783-788, 2003.
[12]J. Lienig, G. Jerke, T. Adler, “Electromigration Avoidance in Analog Circuits: Two Methodologies for Current-Driven Routing,” in Proc. of IEEE International Symposium on VLSI Design, pp. 372-37, 2002.
[13]J. Lienig, G. Jerke and T. Adlert, “AnalogRouter: A New Approach of Current-Driven Routing for Analog Circuits,” in Proc. of Design Automation and Test in Europe, pp. 819-819, 2001.
[14]C.W. Lin, S.Y. Chen, C.F. Li, Y.W. Chang, and C.L. Yang, “Obstacle-Avoiding Rectilinear Steiner Tree Construction based on Spanning Graphs,” in IEEE Transactions Computer-Aided Design, pp. 643--653, 2008.
[15]P.H. Lin and S.C. Lin, “Analog Placement Based on Novel Symmetry-Island Formulation,” in Proc. of the ACM/IEEE Design Automation Conferenc, pp. 465-470, 2007.
[16]Y.C. Lin, H.H. Huang, C.C. Lin and T.M. Hsieh, “Optimal Voltage Assignment Approach for Low Power Using ILP,” WSEAS Transaction on Circuits and Systems, pp. 728-737, 2008.
[17]Z. Shen, C.N. Chu and Y.M. Li, “Efficient Rectilinear Steiner Tree Construction with Rectilinear Blockages,” in Proc. of IEEE of International Conference on Computer Design, pp.38-44, 2005.
[18]P.C. Wu, J.R. Gao, and T.C. Wang, “A Fast and Stable Algorithm for Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction,” in Proc. of ACM/IEEE Asia and South Pacific Design Automation Conference, pp. 262-267, 2007.
[19]J.T. Yan Z.W. Chen and D.H. Hu, “Electromigration-Aware Rectilinear Steiner Tree Construction for Analog Circuits,” in Proc. of 18th VLSI Design and CAD Symposium, CD-ROM, 2008.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top