考量快速且精確局部壅塞模型之全域繞線

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：100

、訪客IP：3.128.168.69

姓名

賈立瑋(Li-Wei, Jia) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

考量快速且精確局部壅塞模型之全域繞線
(Global Routing with a Fast and Accurate Model of Local Congestion)

相關論文

★ 運算放大器之自動化設計流程及行為模型研究	★ 高速序列傳輸之量測技術
★ 使用低增益寬頻率調整範圍壓控震盪器之1.25-GHz八相位鎖相迴路	★ 類神經網路應用於高階功率模型之研究
★ 使用SystemC語言建立IEEE 802.3 MAC 行為模組之研究	★ 以回填法建立鎖相迴路之行為模型的研究
★ 高速傳輸連結網路的分析和模擬	★ 一個以取樣方式提供可程式化邏輯陣列功能除錯所需之完全觀察度的方法
★ 抑制同步切換雜訊之高速傳輸器	★ 以行為模型建立鎖相迴路之非理想現象的研究
★ 遞迴式類神經網路應用於序向電路之高階功率模型的研究	★ 用於命題驗証方式的除錯協助技術之研究
★ Verilog-A語言的涵蓋率量測之研究	★ 利用類神經模型來估計電源線的電流波形之研究
★ 5.2GHz CMOS射頻接收器前端電路設計	★ 適用於OC-192收發機之頻率合成器和時脈與資料回復電路

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

隨著超大型積體電路的快速演進，電路繞線的問題也愈趨龐大。為解決日漸複雜的繞線問題，傳統上常習慣將繞線分為兩大階段進行處理，分別為全域繞線階段（Global Routing Stage）與細部繞線階段（Detailed Routing Stage）。
現今已經有相當大量的全域繞線相關文獻，但其中絕大部分皆沒有考慮細部繞線階段可能產生的壅塞問題，這將導致即使完成了全域繞線，仍有相當大的機率無法得到無壅塞（Congestion-Free）的細部繞線結果。因此，本篇提出了適用於全域繞線階段的局部壅塞模型（Local Congestion Model），將局部壅塞的資訊帶入全域繞線進行考量；並且調整了傳統全域繞線的演算法流程，使其更能夠應對考量局部壅塞時產生的額外溢出。加入此一局部壅塞模型的全域繞線器將能夠提早預知局部壅塞的情形，並且提早迴避壅塞區域（Congested Region），或者識別不可繞（Unroutable）的電路。
實驗結果顯示，本篇所提出的方法可以在短時間內建立局部壅塞模型，藉此可於全域繞線階段提早得知細部繞線階段的壅塞情形。

摘要(英)

As the integrated circuit advances, the problem size of ASIC routing grows fast. To solve such complex problem of routing, it is traditionally separated into global routing stage and detailed routing stage.
There is a large amount of global routing works, but most of them did not consider the possible congestion occurred in the detailed routing stage, incurring that a congestion-free detailed routing result cannot be generated. As a result, a local congestion model for global routing stage is proposed to translate local congestion information into global routing stage. On the other hand, the global routing flow is also adjusted to handle the overflows induced by local congestion. After adding this local congestion model, global routers can predict the local congestion distribution to avoid it or identify unroutable circuits.
Experimental results showed that the proposed method can construct local congestion model in a short time and obtain local congestion information earlier in the global routing stage.

關鍵字(中)

★ 電子設計自動化
★ 實體設計
★ 繞線
★ 全域繞線
★ 細部繞線
★ 局部壅塞

關鍵字(英)

★ EDA
★ Physical Design
★ Routing
★ Global Routing
★ Detailed Routing
★ Local Congestion

論文目次

摘要 i
Abstract ii
致謝 iii
目錄 iv
圖目錄 viii
表目錄 x
1 第一章、緒論 1
1-1 超大型積體電路繞線 1
1-1-1 連線（Net） 2
1-1-2 全域繞線階段（Global Routing Stage） 2
1-1-3 細部繞線階段（Detailed Routing Stage） 3
1-2 局部壅塞（Local Congestion） 3
1-2-1 障礙物 4
1-2-2 局部連線 4
1-2-3 堆疊鑽孔 4
1-3 研究動機 5
1-4 論文結構 6
2 第二章、背景知識 7
2-1 繞線方法介紹與解釋 7
2-1-1 交涉式繞線（Negotiation-Based Routing） 7
2-1-2 並行繞線（Concurrent Routing）與循序繞線（Sequential Routing） 7
2-1-3 樣式繞線（Pattern Routing）與三維俯視樣式繞線（3D Aerial Pattern Routing） 8
2-1-4 單調繞線（Monotonic Routing）與單向單調繞線（Unilateral Monotonic Routing） 9
2-1-5 迷宮繞線（Maze Routing）與A*搜尋迷宮繞線（A*-Search Maze Routing） 10
2-1-6 拔除與再繞線（Rip-up and Reroute） 10
2-1-7 繞線框（Routing Box）設置 10
2-2 相關研究 11
2-2-1 全域繞線相關研究 11
2-2-2 考量堆疊鑽孔之相關研究 12
2-2-3 考量局部連線之相關研究 13
2-2-4 全域繞線格調整之相關研究 14
2-2-5 全域繞線與細部繞線整合之相關研究 15
2-3 問題定義 16
3 第三章、考量快速且精確局部壅塞模型之全域繞線 17
3-1 預估階段 19
3-1-1 拆分多端點連線 19
3-1-2 局部子線繞線 20
3-1-3 軌道容量估算 21
3-2 繞線階段 24
3-2-1 二維投影 24
3-2-2 二維全域繞線 24
3-2-3 層指定 24
3-2-4 繞線權重調整 26
3-3 參數設定 27
3-3-1 繞線演算法設置 27
3-3-2 繞線框設置 27
3-3-3 權重方程式設置 28
4 第四章、實驗結果與討論 29
4-1 工作平台與實驗說明 29
4-2 數據與討論 30
5 第五章、結論與未來展望 35
6 參考文獻 36

參考文獻

[1] M. Cho and D. Z. Pan, "BoxRouter: a new global router based on box expansion and progressive ILP," Proc. ACM/IEEE Design Automation Conf., pp.373-378, Jul. 2006.
[2] Z. Cao, T. Jing, J. Xiong, Y. Hu, L. He, and X. Hong, "DpRouter: A Fast and Accurate Dynamic-Pattern-Based Global Routing Algorithm," Proc. Asia and South Pacific Design Automation Conf., pp.256-261, Jan. 2007.
[3] C.-H. Hsu, H.-Y. Chen, and Y.-W. Chang, "Multi-layer Global Routing Considering Via and Wire Capacities," Proc. Intl. Conf. on Computer-Aided Design, pp.350–355, Nov. 2008.
[4] W.-H. Liu, W.-C. Kao, Y.-L. Li, and K.-Y. Chao, "NCTU-GR 2.0: Multithreaded Collision-Aware Global Routing With Bounded-Length Maze Routing," IEEE Trans. on Computer-Aided Design and Integrated Circuits and Systems, pp.709-722, May 2013.
[5] W.-H. Liu, Y.-L. Li, and C.-K. Koh, "A Fast Maze-Free Routing Congestion Estimator With Hybrid Unilateral Monotonic Routing," Proc. Intl. Conf. on Computer-Aided Design, pp.713-719, Nov. 2012.
[6] L. Nunes, T. Reimann, and R. Reis, "GR-PA: A cost pre-allocation model for global routing," Proc. Intl. Conf. on Very Large Scale Integration, Oct. 2013.
[7] H. Shojaei, A. Davoodi, and J. T. Linderoth, "Planning for Local Net Congestion in Global Routing," Proc. ACM/SIGDA Intl. Symp. on Physical Design, pp.85-92, Mar. 2013.
[8] Y. Wei, C. Sze, N. Viswanathan, Z. Li, C. J. Alpert, L. Reddy, A. D. Huber, G. E. Tellez, D. Keller, and S. S. Sapatnekar, "GLARE: Global and Local Wiring Aware Routability Evaluation," Proc. ACM/IEEE Design Automation Conf., pp.768-773, Jun. 2012.
[9] Y. Xu , Y. Zhang, and C. Chu , "FastRoute 4.0: Global Router with Efficient Via Minimization," Proc. Asia and South Pacific Design Automation Conf., pp.576-581, Jan. 2009.
[10] Y. Zhang and C. Chu, "RegularRoute: An efficient detailed router with regular routing patterns," Proc. ACM/SIGDA Intl. Symp. on Physical Design, pp.146-151, Mar. 2011.
[11] Y. Zhang and C. Chu, "GDRouter: Interleaved global routing and detailed routing for ultimate routability," Proc. ACM/IEEE Design Automation Conf., pp.597-602, Jun. 2012.
[12] available on http://www.ispd.cc/contests/11/ispd2011_contest.html

指導教授

劉建男、陳泰蓁
(Chien-Nan, Liu、Tai-Chen, Chen)

審核日期

2014-7-24

推文