使用降低峰值繞線擁擠度方法之可繞度導向解析擺置

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：19

、訪客IP：3.141.27.244

姓名

王煜勛(Yu-hsun Wang) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

使用降低峰值繞線擁擠度方法之可繞度導向解析擺置
(Analytical-Driven Placement by Reducing Peak Routing Congestion)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

近年隨著超大型積體電路快速的演進，實體設計遇到的困難也越來越嚴重，在擺置階段是電子設計自動化流程中是非常重要的一個環節，需要考量諸多後續可能遇到的問題來決定標準電路元件的擺放位置，其中全域擺置的結果更深深地影響整個擺置階段的結果。
以前以線長最佳化當作考量會導致繞線階段的困難，因此現今許多全域擺置研究重點為可繞度問題，藉由預先考量可繞度使其降低後續繞線階段不可繞的情形發生。目前解析式擺置器（analytical placer）會先以線長最佳化為考量產生初始擺置，再考慮線長、密度（bin density）及可繞度做進一步的優化，其中主流的兩種解析擺置法為多層級（multi-level）解析擺置法與上限下限（upper and lower bound）解析擺置法。
本論文提出一個不同於以往思維的解析擺置法，針對網格密度與繞線擁擠度過高的網格（bin），分析周圍網格的密度與擁擠度，利用網格擴散的概念，慢慢地把網格內部的元件往外推出，得到較為平均分佈的擺置，並利用本論文提出的初始擺置、區分內部與外部連線點障礙物與動態調整網格大小等方法，降低峰值繞線擁擠度，改善可繞度，解決後續繞線階段的問題。

摘要(英)

As the VLSI technology advances, the design complexity has increased rapidly and induces many problems in physical design. Placement, an important stage in electronic design automation, has to consider many issues to determine the placement of standard cells. During cell placement, the global placement results will greatly affect the results of the entire placement stage.
Previous wirelength-driven placement may cause high routing congestion or produce an unroutable placement. Therefore, most of the global placement focus on improving the routability. The quality of placement results will determine the difficulty of routing stage to complete the connection of all segments. State-of-the-art analytical placers guide their placement by a wirelength-driven initial placement, followed by optimizing the objective function consisted of wirelength, density and routability. Multi-level and upper and lower bound analytical placement are two major placement methods.
In this thesis, we propose a different analytical placement method to optimize routability. Using a ripple bin method to spread cells and to solve bin density and routing congestion problems. Besides, using a new initial placement, distinguishing inner and outer pin, and dynamic bin size adjustment methods to reduce peak routing congestion.

關鍵字(中)

★ 擺置
★ 解析
★ 峰值繞線擁擠度

關鍵字(英)

★ placement
★ analytical
★ peak routing congestion

論文目次

摘要 i
Abstract vi
目錄 viii
圖目錄 x
表目錄 xii
第一章、緒論 1
1-1 擺置階段簡介 2
1-2 擺置階段步驟 3
1-2-1 全域擺置（global placement） 3
1-2-2 合法擺置（legalization） 4
1-2-3 細部擺置（detailed placement） 5
1-3 全域擺置前基本知識介紹 6
1-3-1 全域擺置網格（bin） 6
1-3-2 預估可繞度方式 7
1-4 峰值繞線擁擠度（PEAK ROUTING CONGESTION） 9
1-5 論文結構 10
第二章、相關研究 11
2-1 解決可繞度問題的全域擺置器相關研究 11
2-1-1 解析式擺置器 11
2-1-2 多層級解析式擺置器[12][13] 13
2-1-3 上限下限解析式擺置器[15][18] 14
2-2 研究動機 16
2-3 問題定義 16
2-4 本篇特色 17
第三章、擺置器 18
3-1 初始擺置（INITIAL PLACEMENT） 19
3-2 連線關係模型化與連線權重模型 22
3-3 可繞度預估（ROUTABILITY ESTIMATION） 24
3-4 連線點障礙物（PIN BLOCK） 26
3-5 前瞻式擺置合法化核心概念與想法 28
3-5-1 區域網格力(local bin force) 28
3-5-2 增加虛擬定點的位置 30
3-5-3 權重公式 32
3-6 中心網格力(CENTER BIN FORCE) 34
3-7 全域網格力（GLOBAL BIN FORCE） 36
3-8 網格大小動態調整（DYNAMIC BIN SIZE ADJUSTMENT） 38
第四章、實驗結果及分析 39
4-1 實驗環境 39
4-2 實驗結果與比較 41
4-2-1 使用我們提出的初始擺置比較 41
4-2-2 考慮內部與外部連線點障礙物比較 42
4-2-3 使用動態網格大小調整方法比較 42
第五章、結論與未來展望 47
參考文獻 48

參考文獻

[1] DAC 2012 Routability-Driven Placement Contest and Benchmark Suite.
[Online].
Available: http://archive.sigda.org/dac2012/contest/dac2012_contest.html.
[2] ICCAD 2012 Design Hierarchy Aware Routability-Driven Placement.
[Online]. Available: http://cad_contest.cs.nctu.edu.tw/CAD-contest-at-ICCAD2012/problems/default.html
[3] ISPD 2015 Blockage-Aware Detailed Routing-Driven Placement Contest. [Online]. Available: http://www.ispd.cc/contests/15/web/downloads.html
[4] 李培瑜, “基於分割法產生適用於可繞度導向之解析擺置器的初始佈局,” 國立中央大學電機工程研究所碩士論文, July 2014.
[5] Andrew B. Kahng, Igor L. Markov, and Sherief Reda, “On Legalization of Row-based Placements,” Proceedings of Great Lakes symposium on VLSI, pp. 214-219, 2004.
[6] Andrew B. Kahng, Paul Tucke, and Alex Zelikovsky, “ Optimization of Linear Placements for Wirelength Minimization with Free Sites,” Proceedings of Asia and South Pacific Design Automation Conference, pp. 241-244, 1999.
[7] Bo Hu, and Malgorzata Marek-Sadowska, “Multilevel Fixed-Point-Addition-Based VLSI Placement,” Proceedings of Computer-Aided Design of Integrated Circuits and Systems, vol 24, no. 8, pp. 1188-1203, 2005.
[8] Charles Alpert, Andrew Kahng, Gi-joon Nam, Sherief Reda, and Paul Villarrubia, “A semi-persistent clustering technique for vlsi circuit placement,” Proceedings of International of Symposium on Physical Design, pp. 200–207, 2005.
[9] Ismail S. Bustany, David Chinnery, Joseph R. Shinnerl, and Vladimir Yutsis, “ISPD 2015 Benchmarks with Fence Regions and Routing Blockages for Detailed-Routing-Driven Placement,” Proceedings of International of Symposium on Physical Design, pp. 157-164, 2015
[10] Jarrod A. Roy, David A. Papa, Saurabh N. Adya, Haward, H. Chan, Aaron N. Ng, James F. Lu, and Igor L. Markov, “Capo： Robust and scalable open-source min-cut floorplacer,” Proceedings of International Symposium on Physical Design, pp. 224–226, 2005.
[11] Jarrod A. Roy, Natarajan Viswanathan, Gi-Joon Nam, Charles J. Alpert, and Igor L. Markov, “CRISP： Congestion Reduction by Iterated Spreading During Placement,” Proceedings of International Conference on Computer-Aided Design, pp. 357-362, 2009.
[12] Jason Cong, Guojie Luo, Kalliopi Tsota, and Bingjun Xiao, “Optimizing Routability in Large-Scale Mixed-Size Placement,” Proceedings of Asia and South Pacific Design Automation Conference, pp. 441-446, 2013.
[13] Meng-Kai Hsu, Yi-Fang Chen, Chau-Chin Huang, Tung-Chieh Chen, and Yao-Wen Chang, “Routability-Driven Placement for Hierarchical Mixed-Size Circuit Designs,” Proceedings of Design Automation Conference, pp. 1-6, 2013.
[14] Myung-Chul Kim, Dong-Jin Lee, and Igor L. Markov, “SimPL: An Algorithm for Placing VLSI Circuits,” Communication of the ACM, vol 56, no. 6, pp. 105-113, 2013
[15] Myung-Chul Kim, Jin Hu, Dong-Jin Lee, and Igor L. Markov, “A SimPLR Method for Routability-driven Placement,” Proceedings of International Conference on Computer-Aided Design, pp. 67-73, 2011.
[16] Peter Spindler, Ulf Schlichtmann, and Frank M. Johannes, “Abacus：Fast Legalization of Standard Cell Circuits with Minimal Movement,” Proceedings of International Symposium on Physical Design, pp. 47-53, 2008.
[17] Peter Spindler, Ulf Schlichtmann, and Frank M. Johannes, “Kraftwerk2 – A fast force-directed quadratic placement approach using an accurate net model,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,IEEE Transactions on, pp. 1398-1411, 2008.
[18] Tao Lin and Chris Chu, “POLAR: 2.0 An effective routability-driven placer,” Proceedings of Design Automation Conference, pp. 1-6, 2014.
[19] Taraneh Taghavi, Xiaojian Yang, and Bo-Kyung Choi, “Dragon2005： Large Scale Mixed-Sized Placement Tool,” Proceedings of International Symposium on Physical Design, pp. 245-247, 2005.
[20] Tony Chan, Jason Cong, and Kenton Sze, “Multilevel generalized force-directed method for circuit placement,” Proceedings of International of Symposium on Physical Design , pp. 185–192, 2005.
[21] Tony F. Chan, Jason Cong, Joseph R Shinnerl, Kenton Sze, and Min Xie, “mPL6: enhanced multilevel mixed-size placement,” Proceedings of International of Symposium on Physical Design, pp. 212–214, 2006.
[22] Yanheng Zhang and Chris Chu, “Crop： Fast and Effective Congestion Refinement of Placement,” Proceedings of International Conference on Computer-Aided design, pp. 344-350, 2009.
[23] Yaoguang Wei, Cliff Sze, Natarajan Viswanathanm Zhuo Li, Charles J. Alpert, Lakshmi Reddy, Andrew D. Huber, Gustavo E. Tellez, Douglas Keller, and Sachin S. Sapatnekar, “GLARE: Global and Local Wiring Aware Routability Evaluation,” Proceedings of Design Automation Conference, pp. 768-773, 2012.
[24] Yi-Lin Chuang, Gi-Joon Nam, Charles J. Alpert, Yao-Wen Chang, Jarrod Roy, and Natarajan Viswanathan, “Design-hierarchy Aware Mixed-size Placement for Routability Optimization,” Proceedings of International Conference on Computer-Aided Design, pp. 663-668, 2010.
[25] Yu-Min Lee, Tsung-You Wu, and Po-Yi Chiang, “A Hierarchical Bin-Based Legalizer for Standard-Cell Designs with Minimal Disturbance,” Proceedings of Asia and South Pacific Design Automation Conference, pp. 568-573, 2010.
[26] Ulrich Brenner, “VLSI Legalization with Minimum Perturbation by Iterative Augmentation,” Proceedings of Design, Automation & Test in Europe Conference & Exhibition, pp. 1385-1390, 2012.
[27] Ulrich Brenner and Jens Vygen, “Legalizing A Placement with Minimum Total Movement,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 23, no. 12, pp. 1597-1613, 2004

指導教授

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

審核日期

2015-8-17

推文