帳號:guest(44.201.199.251)          離開系統
字體大小: 字級放大   字級縮小   預設字形  

詳目顯示

以作者查詢圖書館館藏以作者查詢臺灣博碩士論文系統以作者查詢全國書目
作者(中文):蔡至韋
作者(外文):Tsai, Chih-Wei
論文名稱(中文):考慮元件位移限制與密度的細部電路佈局與佈局合理化之演算法
論文名稱(外文):Density Aware Detailed Placement and Legalization Considering Displacement Constraint
指導教授(中文):麥偉基
指導教授(外文):Mak, Wai-Kei
口試委員(中文):王廷基
黃婷婷
口試委員(外文):Wang, Ting-Chi
Hwang, TingTing
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學號:101062621
出版年(民國):103
畢業學年度:102
語文別:英文
論文頁數:27
中文關鍵詞:電路佈局密度
外文關鍵詞:detailed placementdensitydisplacement
相關次數:
  • 推薦推薦:0
  • 點閱點閱:196
  • 評分評分:*****
  • 下載下載:0
  • 收藏收藏:0
電路佈局在積體電路實體設計中是一個非常重要的步驟,現今的電路佈局程序通常包含到了全域佈局,合理化,細節佈局。全域佈局會產生一個已經最佳化某些目標的佈局結果,目標包含像是導線長度,可繞性,時序問題等等。合理化會移除所有的在佈局上元件的重疊且保證元件放在合法的位置上,細節佈局會根據全域佈局的結果在更進一步最佳化目標,像是導線長度。因為不只一個目標會在全域佈局中最佳化,所以在合理化和細部佈局中應該維護全域佈局結果的品質,在這篇論文中,我們提出了一個兩步驟的演算法架構來更進一步的最佳化導線長度並同時利用限制元件的最大移動距離來維護全域佈局結果的品質,在第一個步驟中,我們會有效的去消除由高單位密度所造成的懲罰因素。在第二個步驟中,我們會更進一步減少導線長度同時不去增加在上一個步驟中所消除的懲罰因素,在最後的實驗結果中,我們會展示出我們的細部佈局演算法在不同的最大移動距離限制和佈局目標使用率之下可以得到平均12.33%至15.12%的改進。
Placement is one of the important steps in physical design. Modern placement process involves global placement, legalization, detailed placement.
Global placement generate a placement solution with optimized objectives such as wire-length, routability, timing.
Legalization removes cells overlap and makes sure the cells on the placement site.
Detailed placement (DP) relocates cells to obtain a better placement solution.
Since objectives are optimized in global placement, legalization and detailed placement should not only optimized its objective, but also preserved the global placement solution quality.
In this thesis, we proposed a two-stage detailed placement algorithm for minimizing wire-length, also can preserve the global placement solution quality by constraining the cell displacement.
In the first stage, we can effectively eliminate the penalty caused by high cell density.
In the second stage, we further reduce wire-length without increasing the penalty.
In experiments, we use ICCAD 2013 detailed placement contest [3] benchmarks, the result shows we could improve the global placement results 12.36% - 15.15% on average under different
displacement constraint and target placement density.
1 Introduction 1
1.1 Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Previous Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Problem Formulation 4
2.1 Wire Length Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Displacement Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Cell Density Formulation : Average Bin Utilization (ABU) . . . . . . . . . 5
3 Algorithm 7
3.1 Eliminate Penalty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Optimal Region . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 Global Move . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.4 Local Move . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.5 Enlarging Optimal Region . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Experiment 18
4.1 The Penalty Elimination Results . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Overall Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3 Comparison and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 20
5 Conclusion 24
Reference 25
[1] M. Pan, N.Viswanathan, and C. Chu. An efficient and effective detail placement algorithm In Proceedings of the International Conference Computer-Aided Design, pages
48-55, 2005.
[2] S. Goto An Efficient Algorithm for the Two-Dimensional Placement Problem in Electrical Circuit Layout. IEEE Transactions on Circuits and Systems, Volume:28, issue:1,
pages 12-18, 1981.
[3] M.-C. Kim. IEEE CEDA/taiwan MOE,ICCAD 2013 contest. Retrieved October 10,2013 from http://cad_contest.cs.nctu.edu.tw/CAD-contest-at-ICCAD2013/problem_b/, 2013.
[4] P. Spindler, U. Schlichtmann, and F. 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, 27(8):1398-1411, 2008.
[5] W.-K. Chow, J.Kuang, X.He, W.Cai, F.Y.Young. Cell density-driven detailed placement with displacement constraint. In Proceedings of the International symposium on
physical design, Pages 3-10, 2014.
[6] S. Popovych, H.-H. Lai, C.-H. Wang, Y.-L. Li, W.-H. Liu, T.-C. Wang. Density-aware Detailed Placement with Instant Legalization. In Proceedings of the 51st Annual Design Automation Conference, pages 1-6, 2014
[7] A.E. Caldwell, Optimal partitioners and end-case placers for standard-cell layout. In IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume:19, Issue:11, pages 1304-1313, 2000
[8] U. Brenner and J. Vygen. Faster optimal single-row placement with fixed ordering. In Proceedings of the conference on Design automation and test in Europe, pages 117-121, 2000.
[9] A. Kahng, P. Tucker, and A. Zelikovsky, Optimization of linear placements for wirelength
minimization with free sites. In Proceedings of the Asia and South Pacific Design Automation Conference, pages 241-244, 1999.
[10] M.-K. Hsu, Y.-F. Chen, C.-C. Huang, T.-C. Chen, and Y.-W. Chang. Routability driven placement for hierarchical mixed-size circuit designs. In Proceedings of the 50th
Annual Design Automation Conference, pages 1-6, 2013.
[11] X. He, T. Huang, W.-K. Chow, J. Kuang, K.-C. Lam, W. Cai, and E. Young. Ripple 2.0: High quality routability-driven placement via global router integration. In Proceedings of the 50th Annual Design Automation Conference, pages 1-6, 2013.
[12] W.-H. Liu, C.-K. Koh, and Y.-L. Li. Optimization of placement solutions for routability. In Proceedings of the 50th Annual Design Automation Conference, pages 1-9, 2013.
[13] A. Agnihotri, S. Ono, C. Li, M. Yildiz, A. Khatkhate, C.-K. Koh, and P. Madden. Mixed block placement via fractional cut recursive bisection. IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems, 24(5):748-761, 2005.
[14] M.-C. Kim, N. Viswanathan, C. J. Alpert, I. L. Markov, and S. Ramji. Maple: multilevel adaptive placement for mixed-size designs. In Proceedings of the International
Symposium on Physical Design, pages 193-200, 2012.
(此全文限內部瀏覽)
電子全文
摘要
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top
* *