基於分割法產生適用於可繞度 導向之解析擺置器的初始佈局

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：10

、訪客IP：3.139.70.131

姓名

李培瑜(Pei-Yu Lee) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

基於分割法產生適用於可繞度導向之解析擺置器的初始佈局
(Partition-Based Initial Placement for Routability-Driven Analytical Placer)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

隨著科技不斷進步，積體電路的設計複雜度愈來愈高，實體設計面臨的問題愈來愈多。擺置階段是電子設計自動化軟體中極重要的一環，需要能經由考量多目標來決定標準元件的實際位置，而擺置階段最重要的就是全域擺置，因為全域擺置的結果深深地影響整個擺置階段的效果。
現今許多的擺置器將重點放在可繞度的預估上，因為在擺置的下一階段即是繞線。而用以前線長最佳化的考量會造成繞線階段的困難，小則浪費時間，大則根本無法成功完成繞線，因此在擺置階段預先考量此擺置是否能比較容易地被繞線完成是一門很重要的課題。目前的解析式擺置器（analytical placer）會先以線長為考量產生初始擺置，經過對於線長以及密度的優化後再作對可繞度做優化。為了得到易於繞線的擺置，一個能以可繞度為考量並且能夠增加解析式擺置器對於可繞度優化的初始擺置亟需被提出並應用於解析式擺置器上。
本篇論文提出了一個改善傳統分割法的擴展式分割法，藉由上到下擴展式分割法配合擴展順序決定產生一個對於可繞度優化的初始擺置。實驗數據顯示以擴展式分割法所產生的可繞度導向初始擺置能夠有效地提升解析式擺置器的可繞度。

摘要(英)

As technology advances, the complexity of integrated circuits has increased rapidly. Placement, an important stage in physical design, requires more effective algorithms to handle multiple objectives, such as timing, power, routability, and wirelength.
Recently, placers focus on improving routability due to a wirelength-driven placer may cause high routing congestion or produce an unroutable placement. Therefore, how to optimize routability during placement stage is an important issue. State-of-the-art analytical placers guide their placement by a wirelength-driven initial placement, followed by optimizing the objective function which consists of wirelength, density and routability. At last, an optimization that only concerns routability is applied. To get a more routable placement, a routability-driven initial placement that benefits analytical placer’s routability is urgently needed.
In this thesis, we propose a new partition method which improves traditional partition method to produce a better initial placement for analytical placers by using a top-down recursive expansion partition. Experimental results show that using the proposed algorithm will effectively improve the routability of analytical placer.

關鍵字(中)

★ 超大型積體電路
★ 分割法擺置
★ 可繞度導向擺置
★ 初始擺置

關鍵字(英)

★ VLSI
★ Partition-based Placement
★ Routability-driven Placement
★ Initial Placement

論文目次

摘要 i
Abstract ii
致謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章、緒論 1
1-1 簡介 1
1-1-1 擺置階段簡介 2
1-2 擺置階段步驟 3
1-2-1 全域擺置 3
1-2-2 合法擺置 4
1-2-3 細部擺置 5
1-3 論文結構 6
第二章、相關知識 7
2-1 全域擺置設計可繞度問題的方法 7
2-2 初始擺置 9
2-3 研究動機 10
2-4 問題定義 12
2-5 本篇的特色 12
第三章、分割法初始擺置 13
3-1 演算法流程 13
3-2 平均網格內元件面積 15
3-3 擴展式分割法 15
3-3-1 元件面積預留計算 16
3-3-2 分割花費計算 16
3-3-3 端點傳播 17
3-3-4 擴展順序決定 18
3-4 困難以及解決 20
第四章、實驗結果與分析 23
4-1 工作平台與測試檔說明 23
4-2 實驗結果與比較 24
4-2-1 與NTUPlace4比較 25
4-2-2 與傳統二分法比較 25
4-2-3 採用多核心加速 25
第五章、結論 29
參考文獻 30

參考文獻

[1] 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 ﬂoorplacer,” in Proceedings of International Symposium on Physical Design, pp. 224–226, 2005.
[2] Taraneh Taghavi, Xiaojian Yang, Bo-Kyung Choi, Maogang Wang and Majid Sarrafzadeh, “Dragon2005： Large Scale Mixed-Sized Placement Tool,” in Proceedings of International Symposium on Physical Design, pp. 42-47, 2005.
[3] 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.
[4] 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.

[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] 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, pp. 241-244, 1999.
[12] Ulrich Brenner, “VLSI Legalization with Minimum Perturbation by Iterative Augmentation,” in Proceedings of Design, Automation & Test in Europe Conference & Exhibition, pp. 1385-1390, 2012.
[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] 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 Proceedings of International Conference on Computer-Aided Design, pp. 74-79, 2011.
[18] Jason Cong, Guojie Luo, Kalliopi Tsota, and Bingjun Xiao, “Optimizing Routability in Large-Scale Mixed-Size Placement,” in Proceedings of　 Asia and South Pacific Design Automation Conference, pp. 441-446, 2013.
[19] Ümit Çatalyürek and Cevdet Aykanat, “PaToH（Partitioning Tool for Hypegraphs）,” Encyclopedia of Parallel Computing, pp. 1479-1487, 2011.
[20] Wen-Hao Liu, Cheng-Kok Koh, and Yih-Lang Li, “Case Study for Placement Solutions in ISPD11 and DAC12 Routability-Driven Placement Contests,” in Proceedings of International Symposium on Physical Design, pp.114-119, 2013.
[21] George Karypis and Vipin Kumar, “Multilevel k-way Hypergraph Partitioning,” in Proceedings of Design Automation Conference, pp.343-348, 1999.
[22] A. E. Caldwell, A. B. Kahng, and I. L. Markov, “Can recursive bisection a lone produce routable placements,” in Proceedings of Design Automation Conference., pp.260-263, 2000.
[23] Natarajan Viswanathan, Charles J. Alpert, Cliff C. N. Sze, Zhuo Li and Yaoguang Wei, “The DAC 2012 Routability-driven Placement Contest and Benchmark Suite,” in Proceedings of Design Automation Conference, pp. 774-782, 2012.

指導教授

劉建男(Chien-Nan Liu)

審核日期

2014-7-24

推文