擺置階段評估繞線完成度的有效率區域壅塞模型

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：144

、訪客IP：3.17.186.21

姓名

龐立遠(Li-Yuan Pang) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

擺置階段評估繞線完成度的有效率區域壅塞模型
(An Efficient Local-Congestion Model for Routability Estimation in Placement)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

隨著超大型積體電路的快速演進，電路的可繞度（Routability）問題愈趨嚴重。一般在繞線階段時才能準確得知電路可繞度之資訊，然而若此時才發現電路的可繞度不足，在設計上會浪費大量的時間重新進行擺置與再繞線。因此若在擺置階段就考慮電路的可繞度資訊並能及時發現問題，即可避免時間的浪費。
為了精準的預估可繞度，本篇論文採用全域繞線研究做為基底，但目前絕大部分的全域繞線研究皆沒有考慮細部繞線階段可能產生的壅塞問題，這導致即使完成了全域繞線，仍有相當大的機率無法得到無壅塞（Congestion-free）的細部繞線結果。因此，本篇論文提出了適用於擺置階段的快速區域壅塞模型（Local congestion model），搭配適合在擺置階段使用的快速全域繞線器，能夠提早預知區域壅塞的情形，並且提早迴避壅塞區域（Congested region），或者識別不可繞（Unroutable）的電路。實驗結果顯示，本篇論文所提出的方法可以在短時間內預估電路的區域壅塞，使得全域繞線器可以提早得知細部繞線階段之可繞度資訊。

摘要(英)

With the advances of Very-Large-Scale Integration circuits, the routability problem has become more and more significant. Conventionally, circuit routability can only be evaluated precisely after routing stage. However, if the routability is not sufficient, it will waste lots of time to re-place and re-route. Thus, routability evaluating in placement stage is important to discover potential routing problems and avoid redesign efforts.
For accurate routability evaluation, this thesis proposes a method based on global routing. However, most of the global routing researches didn’t consider the possible congestions occurred in the detailed routing stage. It is possible that congestion-free detailed routing results are still not available. Therefore, a fast local congestion model for placement stage is proposed in this thesis. Combined with a fast global router, the proposed fast local congestion model can predict the distribution of routing congestion to avoid congested regions and identify unroutable circuits. Experimental results showed that the proposed model can obtain local congestion information fast in placement stage and help the global router to evaluate the routability of the circuits.

關鍵字(中)

★ 區域壅塞

關鍵字(英)

★ Local Congestion

論文目次

摘要 iii
Abstract iv
致謝 v
目錄 vi
圖目錄 ix
表目錄 xi
第一章、緒論 1
1-1 超大型積體電路的成長與遭遇的困難 1
1-2 擺置階段 2
1-3 繞線階段 3
1-4 研究動機 4
1-5 論文架構 5
第二章、背景知識 6
2-1 繞線背景知識 6
2-1-1 連線（Net） 6
2-1-2 全域繞線階段（Global Routing Stage） 6
2-1-3 細部繞線階段（Detailed Routing Stage） 7
2-2 區域壅塞（Local Congestion） 8
2-2-1 障礙物（Blockage） 8
2-2-2 區域連線（Local Net） 8
2-3 繞線架構介紹與解釋 9
2-3-1 並行繞線（Concurrent Routing）與循序繞線（Sequential Routing） 9
2-3-2 交涉式繞線（Negotiation-based Routing） 10
2-3-3 拔除與再繞線（Rip-up and Reroute） 10
2-4 繞線方法介紹與解釋 10
2-4-1 樣式繞線（Pattern Routing） 10
2-4-2 單調繞線（Monotonic Routing）與單向單調繞線（Unilateral Monotonic Routing） 11
2-4-3 繞線框（Routing Box）設置 12
2-5 相關研究 12
2-5-1 快速之全域繞線相關研究 13
2-5-2 考量區域壅塞之相關研究 14
2-5-3 全域繞線與細部繞線整合之相關研究 17
2-6 問題定義 18
第三章、擺置階段評估繞線完成度的有效率區域壅塞模型 19
3-1 準備階段 19
3-1-1 拆分多端點連線 20
3-1-2 紀錄障礙物 20
3-1-3 二維投影 21
3-2 區域壅塞估計階段 21
3-2-1 分解全域繞線格 21
3-2-2 紀錄障礙物資訊 22
3-2-3 區域連線繞線 23
3-2-4 結果萃取 23
3-3 選擇全域繞線器 25
3-3-1 NCTU-GR 2.0 [5] 25
3-3-2 本篇之全域繞線器 27
第四章、實驗結果與討論 29
4-1 工作平台與實驗說明 29
4-2 數據與討論 29
4-2-1 驗證區域壅塞模型之有效性 29
4-2-2 驗證區域壅塞模型之效率 32
4-2-3 使用NCTU-GR 2.0 [5]繞線 33
第五章、結論與未來展望 36
參考文獻 37

參考文獻

[1] Gate count of Intel CPU available at http://zh.wikipedia.org/wiki/%E8%8B%B1%E7%89%B9%E5%B0%94%E5%BE%AE%E5%A4%84%E7%90%86%E5%99%A8%E5%88%97%E8%A1%A8
[2] Gate count of Intel CPU available at http://ark.intel.com/
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] M. K. Hsu, Y. F. Chen, C. C. Huang, S. Chou, T. H. Lin, T. C. Chen, and Y. W. Chang, “NTUplace4h: A Novel Routability-Driven Placement Algorithm for Hierarchical Mixed-Size Circuit Designs,” IEEE Trans. on Computer-Aided Design and Integrated Circuits and Systems, pp. 1914-1927, Dec. 2014
[8] 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.
[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] M. Pan, C. Chu “FastRoute: A Step to Integrate Global Routing into Placement,” Proc. Intl. Conf. on Computer-Aided Design, pp.464-471, Nov, 2006.
[13] Chu, C.; Yiu-Chung Wong, “FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,” IEEE Trans. on Computer-Aided Design and Integrated Circuits and Systems, pp.70-83, Jan, 2008
[14] 賈立瑋, “考量快速且精確局部壅塞模型之全域繞線,” 國立中央大學電機工程研究所碩士論文, July 2014
[15] Available at http://www.ispd.cc/contests/11/ispd2011_contest.html
[16] Available at http://www.ispd.cc/contests/15/ispd2015_contest.html

指導教授

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

審核日期

2015-7-20

推文