考量障礙物間通道寬度限制及避免電子遷移效應的繞線樹建構之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：23

、訪客IP：3.139.72.152

姓名

蔡昀芷(Yun-Chih Tsai) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

考量障礙物間通道寬度限制及避免電子遷移效應的繞線樹建構之研究
(Electromigration- and Obstacle-Avoiding Routing Tree Construction)

相關論文

★ 三維積體電路的微凸塊分配與晶粒間繞線之研究	★ 考慮製造限制之繞線研究
★ 使用次序關係配置三維積體電路微凸塊	★ 考慮線長匹配的平行匯流排之逃脫繞線
★ 用於三維積體電路之溫度導向平面規劃的散熱型矽晶穿孔面積融合方法	★ 雙圖案微影技術下考慮原生衝突之電路軌道繞線
★ 三維積體電路中同步降低熱點溫度與電源雜訊之研究	★ 使用延遲決策技術於類比電路之可繞度導向擺置方法
★ 提升聚焦離子束對訊號探測能力之細部繞線方法	★ 考慮障礙物閃避及電荷分享之鑽孔數量最小化跳線插入演算法
★ 模組化層級三維積體電路之矽晶穿孔規劃與線長最佳化	★ 降低不匹配效應之力導向電容擺置方法
★ 考慮繞線資源需求之標準元件擺置合法化	★ Simultaneous escape routing for mixed-pattern signals on staggered pin arrays
★ 面積與最大線長最佳化之類比積體電路佈局產生器	★ 含多重檢查機制之實體驗證自動化工具

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

隨著類比積體電路佈局的複雜度提高，設計者必頇花費更多時間在處理繞線（routing）問題，其中一項重要的課題即是導線電流密度的限制。因為設計者疏失或是電路平面上障礙物之間的通道寬度限制而導致電路導線過細，使得導線上的電流密度過高，而造成電子遷移（electromigration）現象，進而產生開路或短路的情況，使電路產生永久性的損毀。但是如果恣意地放大導線寬度以降低電流密度，又會導致導線面積過大、佔用過多的繞線資源。
目前的相關研究多著重在無障礙物的情況下，避免導線電子遷移現象並達到導線面積最佳化的目的。但是對於電路平面存在障礙物，或是障礙物之間存在通道寬度限制的情況，卻尚未有合適的處理技術。
本論文提出一個考量電子遷移現象以及障礙物之間通道寬度限制的類比積體電路繞線自動化技術。首先，根據起始節點、目標節點以及障礙物建立一個修正的生成圖（modified spanning graph）。接著，利用此生成圖快速找到每對起始節點與目標節點的最短路徑。針對最短路徑，我們提出一個路經編碼方式以便快速找出通道寬度限制的區域。再來，找出每對起始節點與目標節點的備用路徑，此路徑會用來避免繞線經過最壅擠的通道寬度限制區域。最後，利用線性規劃（linear programming）分配每對起始節點與目標節點的繞線路徑及決定其導線寬度以找出符合通道寬度限制且導線面積最小的繞線結果。

摘要(英)

As the complexity of the layout of analog ICs increases, designers must spend more effort in dealing with the routing problem. A main issue is the constraint of wire current density. Because the negligence of circuit designers or the channel width constraints between obstacles lead to the width of a wire too small, making the current density of the wire is too high. This condition causes electromigration phenomenon and a permanent failure (e.g., open- or short-circuit defect). However, widening wire widths arbitrarily to reduce the current density leads to larger wire area and routing resource.
Related researches focus on avoiding the electromigration phenomenon and the wire area optimization without considering obstacles. However, there does not exist suitable methods to handle obstacles and the channel width constraints between obstacles in circuits.
This thesis proposes a routing automation technology for analog integrated circuits with considering obstacles and the channel width constraints between obstacles. First, a modified spanning graph is constructed according to sources, targets, and obstacles. The modified spanning graph is used to find a shortest path for each pair of a source and a target. For the shortest path, we propose an edge encoding method to detect rapidly the channel width constraints between obstacles. Then, a reserved path is found for each pair of a source and a target. The reserved path is a shortest path with avoiding pass the most congested region. Finally, linear programming is used to distribute the flow for each path to find the routing result. The routing result is satisfied the channel width constraints between obstacles with minimum wire area.

關鍵字(中)

★ 電子遷移效應
★ 繞線
★ 障礙物

關鍵字(英)

★ obstacle
★ routing
★ electromigration

論文目次

第一章、緒論.....................................................................................................................1
1-1 電子遷移現象.....................................................................................................1
1-2 考慮電子遷移之繞線問題.................................................................................2
1-3 相關研究.............................................................................................................2
1-4 研究動機.............................................................................................................9
1-5 論文組織........................................................................................................ ...10
第二章、預備知識...........................................................................................................11
2-1 符號定義...........................................................................................................11
2-2 電流描述...........................................................................................................12
2-3 線性規劃...........................................................................................................13
2-4 問題描述 ...........................................................................................................13
第三章、演算法..............................................................................................................16
3-1 演算法流程圖...................................................................................................16
3-2 修正生成圖的建立...........................................................................................18
3-2-1 生成圖建立方法....................................................................................18
3-2-2 修正生成圖............................................................................................20
3-3 線段編碼...........................................................................................................21
3-3-1 一般編碼................................................................................................21
3-3-2 電流端點編碼........................................................................................23
3-4 通道寬度限制 ...................................................................................................24
3-5 找出最短路徑 ...................................................................................................25
3-6 路徑分析 ...........................................................................................................26
3-6-1 障礙物對障礙物限制檢查....................................................................27
3-6-2 障礙物對邊界限制檢查........................................................................30
3-7 備用路徑...........................................................................................................31
3-7-1 避開障礙物對邊界限制的路徑............................................................32
3-7-2 避開障礙物對障礙物限制的路徑 ...................................................34
3-8 線性規劃...................................................................................................36
第四章、實驗結果與分析...............................................................................................37
4-1 實驗環境與測詴檔資訊...................................................................................37
4-2 實驗結果與分析...............................................................................................39
第五章、結論與未來方向...............................................................................................44
第六章、參考文獻...........................................................................................................45

參考文獻

[1] 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,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 27, no. 4, pp. 643—653, Apr. 2008.
[2] D. Young and A. Christou, “Failure mechanism models for electromigration,” IEEE Transactions on Reliability, Vol. 43, no. 2, pp.186—192, Jun. 1994.
[3] E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, 1: 269—271, 1959.
[4] F. M. D’Heurle, “Electromigration and failure in electronics: an introduction,” Proceeding of the IEEE, Vol. 59, no. 10, pp.1409—1417, 1971.
[5] Iris H.-R. Jiang, H.-Y. Chang, C.-L. Chang, “Optimal wiring topology for electromigration avoidance considering multiple layers and obstacles,” in Proc. Int. Symp. Phys. Des, pp. 177—184, 2010.
[6] IBM ILPG CPLEX Optimizer, http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
[7] J.-T. Yan and Z.-W. Chen, “Electromigration-aware rectilinear Steiner tree construction for analog circuits,” in Proc. Asia Pacific Conf. Circuits Syst, pp. 1692—1695, 2008.
[8] J.-T. Yan and Z.-W. Chen, “Obstacle-aware multiple-source rectilinear Steiner tree with electromigration and IR-drop avoidance,” in Proc. Design, Automation and Test in Europe, pp. 1—6, 2011.
[9] J. Lienig, “Introduction to electromigration-aware physical design,” in Proc. Int. Symp. Phys. Des, pp. 39—46, 2006.
[10] J. Lienig, G. Jerke and T. Adler, “Electromigration avoidance in analog circuits: two methodologies for current-driven routing,” in Proc. Asia and South pacific Design Automation Conference, pp.372—378, 2002.
[11] J. Lienig and G. Jerke, “Current-driven wire planning forelectrimigration avoidance in analog circuits,“ in Proc. Asia and South pacific Design Automation Conference, pp. 783—788, 2003
[12] J. R. Black, “Electromigration—A brief survey and some recent results,” IEEE Transactions on Electron Devices, Vol. 16, no. 4, pp. 338—347, Apr. 1969.
[13] T. Adler and E. Barke, “Single step current driven routing of multiterminal signal nets for analog applications,” in Proc. Design, Automation and Test in Europe, pp.446—450, 2000.
[14] T. Adler, H. Brocke, L. Hedrich and F. Barke, “A current-driven routing and verification methodology for analog applications,” in Proc. Design Automation Conference, pp.385—389, 2000.
[15] R. Black, “Physics of electromigration,” in Proc. IEEE International Reliability Physics Symposium, pp.142—149, 1983.

指導教授

陳泰蓁(Tai-Chen Chen)

審核日期

2011-8-20

推文