考慮繞線資源需求之標準元件擺置合法化

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：51

、訪客IP：52.15.70.136

姓名

劉國鼎(Kuo-Ting Liu) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

考慮繞線資源需求之標準元件擺置合法化
(Standard-Cell Legalization Considering Routing Demand)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

近年來，電子設計自動化軟體隨著積體電路工業越來越發達，合法擺置階段是電子設計自動化軟體中極為重要的部分。合法擺置階段將電路元件擺在合法的位置上，因為在這個階段會決定標準元件（standard cell）的位置，所以如何決定擺置位置是一項很重要的議題。
在目前的擺置階段（placement）較著重的部分是在可繞性（routability）的估測，相較於以往所做的線長（wire-length）考量不同，過短的線長可能會導致擺置地太擁擠，以至於在繞線（routing）階段時可能會導致繞不完的情形產生。因此可繞性問題便在改善當擺置完後能提供一個較高的可繞性擺置結果。而這些可繞性的考量以往都是在全域擺置（global placement）做評估，因此在合法擺置（legalization）間段若只是找尋最短距離擺置或者找尋最短線長擺置時，可能就會犧牲掉在全域擺置時所做的可繞性評估，因此在擺置合法化階段時若能加入可繞性的評估，必能提供較好的可繞性擺置結果。
在本篇論文中，我們提出利用建立擁擠地圖（congestion map）表示擁擠區塊，根據這個地圖提供給標準元件移動的力量，這個力量目的是希望能夠避開溢位邊緣（routing edge），但是為了要保持原本全域擺置的結果，我們給的移動範圍只限於一單位網格（bin），若擺置密度（placement density）可以承受的就會直接移入，否則就會做交換元件的動作。我們採取了網格基準（bin-based）[15]的擺置合法化做擺置，但我們為了要讓標準元件保留在原始的網格，我們給予了一個花費成本（cost）搜尋合法位置。實驗結果顯示，我們提出的方法可以減少溢位（overflow）發生的情形。

摘要(英)

In recent years, several electronic-design automation (EDA) tools for placement are proposed and developed. Legalization is a very important stage for placing cells on legal positions. The existed methods for legalization usually try to minimize the total wire-length of cells. However, considering wire-length only in the placement stage is not sufficient for placing standard cells. A congested placement result may incur the routing difficult due to the congested problem in the placement rows. Therefore, legalization needs to consider the routability instead of the wire-length or displacement minimization.
In this thesis, we adopt a congestion map to indicate the usage of routing edges. Standard cells will be moved by forces to avoid overflow edges. In order to preserve the global placement result, the searching range is limited in the surrounding bins. Then, we use bin-based [15] legalization to find the positions of cells. Finally, we propose a cost function to search optimal position. To evaluate our proposed method, we use the benchmarks provided by ICCAD 2012 placement contest as experimental data. Experimental results show that the proposed method can produce better placement results that incur less overflows in the global routing stage.

關鍵字(中)

★ 擺置合法化
★ 網格
★ 繞線資源

關鍵字(英)

論文目次

摘要 i
Abstract ii
目錄 iv
圖目錄 vi
表目錄 ix
1. 第一章、緒論 1
1-1 擺置階段簡介 1
1-2 擺置階段步驟 3
1-2-1 全域擺置 3
1-2-2 合法擺置 5
1-2-3 細部擺置 6
1-3 全域擺置設計可繞性問題的方法 8
1-4 論文結構 9
2. 第二章、相關研究 10
2-1 考量線長及位移量設計 10
2-2 以網格為基準的設計及考量可繞性設計 14
2-3 本篇的特色 16
3. 第三章、同時考慮溢位與位移最小化之擺放合法化 17
3-1 研究動機 17
3-2 問題描述 18
3-3 演算法流程 20
3-4 建立網格的密度空間 21
3-5 預估繞線擁擠度 22
3-5-1 建立繞線擁擠度地圖 23
3-5-2 給予元件移動力量模型 24
3-6 建立網格的合法擺置法 31
3-6-1 單一網格的擺置 31
3-6-2 擴展網格的擺置 32
3-7 擴展網格時所尋找的空間花費成本 36
3-8 單一網格的合法擺置所要考慮的項目 37
3-8-1 元件的權重 37
3-8-2 單一網格元件分布 39
4. 第四章、實驗結果與分析 41
4-1 工作平台與測試檔說明 41
4-2 實驗結果與比較 42
5. 第五章、結論 50
參考文獻 51

參考文獻

[1] http://www.salilab.org/~drussel/bipartite_matching.html
[2] Ulrich Brenner, “VLSI Legalization with Minimum Perturbation by Iterative Augmentation,” in Proceedings of Design, Automation & Test in Europe Conference & Exhibition, pp. 1385-1390, 2012.
[3] 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, pp. 1597-1613, 2004.
[4] Chris Chu and Yiu-Chung Wong, “FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, pp. 70-83, 2008.
[5] 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”, in Proceedings of International Conference on Computer-Aided Design, pp. 663-668, 2010.
[6] Xu He, Wing-Kai Chow, and Evangeline F.Y. Young, “SRP: Simultaneous Routing and Placement for Congestion Refinement,” in Proceedings of International Symposium on Physical Design, pp. 108-113, 2013.
[7] Xu He, Tao Huang, Linfu Xiao, Haitong Tian, Guxin Cui, and Evangeline F.Y. Young, “Ripple: An Effective Routability-driven Placer by Iterative Cell Movement,” in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 74-79, 2011.
[8] Tsung-Yi Ho and Sheng-Hung Liu, “Fast Legalization for Standard Cell Placement with Simultaneous Wirelength and Displacement Minimization,” in Proceedings of VLSI System on Chip Conference, pp. 369-374, 2010.
[9] 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,” in Proceedings of Design Automation Conference, pp. 1-6, 2013.
[10] Sung-Woo Hur and John Lillis, “Mongrel: Hybrid Techniques for Standard Cell Placement,” in Proceedings of International Conference on Computer-Aided Design, pp. 165-170, 2000.
[11] Zhe-Wei Jiang, Bor-Yiing Su, and Yao-Wen Chang, ” Routability-driven Analytical Placement by Net Overlapping Removal for Large-scale Mixed-size,” in Proceedings of Design Automation Conference, pp. 167-172, 2008.
[12] Andrew B. Kahng, Igor L. Markov, and Sherief Reda, ”On Legalization of Row-based Placements,” in Proceedings of Great Lakes symposium on VLSI, pp. 214-219, 2004.
[13] Andrew B. Kahng, Paul Tucke, and Alex Zelikovsky, ” Optimization of Linear Placements for Wirelength Minimization with Free Sites,” in Proceedings of Asia and South Pacific Design Automation Conference, vol. 1, pp. 241-244, 1999.
[14] Myung-Chul Kim, Jin Hu, Dong-Jin Lee, and Igor L. Markov, “A SimPLR Method for Routability-driven Placement,” in Proceedings of International Conference on Computer-Aided Design, pp. 67-73, 2011.
[15] Yu-Min Lee, Tsung-You Wu, and Po-Yi Chiang, “A Hierarchical Bin-Based Legalizer for Standard-Cell Designs with Minimal Disturbance,” in Proceedings of Asia and South Pacific Design Automation Conference, pp. 568-573, 2010.
[16] Yanheng Zhang and Chris Chu, ” IPR: An Integrated Placement and Routing Algorithm,” in Proceedings of Design Automation Conference, pp. 59-62, 2007.
[17] Jarrod A. Roy, Natarajan Viswanathan, Gi-Joon Nam, Charles J. Alpert, and Igor L. Markov, “CRISP: Congestion Reduction by Iterated Spreading During Placement,” in Proceedings of International Conference on Computer-Aided Design, pp. 357-362, 2009.
[18] Peter Spindler and Frank M. Johannes, “Fast and Accurate Routing Demand Estimation for Efficient Routability-driven Placement,” in Proceedings of Design, Automation & Test in Europe Conference & Exhibition, pp. 1-6, 2007.
[19] Peter Spindler, Ulf Schlichtmann, and Frank M. Johannes, “Abacus: Fast Legalization of Standard Cell Circuits with Minimal Movement,” in Proceedings of International Symposium on Physical Design, pp. 47-53, 2008.
[20] Kalliopi Tsota, Cheng-Kok Koh, and Venkataramanan Balakrishnan, “Guiding global placement with wire density,” in Proceedings of International Conference on Computer-Aided Design, pp. 212-217, 2008.
[21] Yanheng Zhang and Chris Chu, ” Crop: Fast and Effective Congestion Refinement of Placement,” in Proceedings of International Conference on Computer-Aided Design, pp. 344-350, 2009.
[22] Wen-Hao Liu, Cheng-Kok Koh, and Yih-Lang Li, "Case Study for Placement Solutions in ISPD11 and DAC12 Routability-Driven Placement Contests," in Proc. International Symposium on Physical Design, pp.114-119, 2013.
[23] Minsik Cho, Haoxing Ren, Hua Xiang, and Ruchir Puri, “History-based VLSI Legalization using Network Flow,” in Proceedings of Design Automation Conference, pp. 286-291, 2010.
[24] Dwight Hill. Method and system for high speed detailed placement of cells within integrated circuit designs. U.S. Patent 6370673, April 2002.

指導教授

陳泰蓁(Tai-Chen Chen)

審核日期

2013-8-21

推文