跳到主要內容

臺灣博碩士論文加值系統

(44.200.140.218) 您好!臺灣時間:2024/07/18 05:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:尹法軒
研究生(外文):Yin, Fa-Xuan
論文名稱:在線性時間下的元件配置合法化與元件最大位移最佳化
論文名稱(外文):A Linear-Time Algorithm for Placement Legalization with Optimal Maximum Displacement
指導教授:麥偉基
指導教授(外文):Mak, Wai-Kei
口試委員:王廷基何宗易
口試委員(外文):Wang, Ting-ChiHo, Tsung-Yi
口試日期:2020-01-20
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2020
畢業學年度:108
語文別:英文
論文頁數:41
中文關鍵詞:實體設計擺置合法化多重行高元件
外文關鍵詞:legalizationVLSIMulti-row-height cell
相關次數:
  • 被引用被引用:0
  • 點閱點閱:197
  • 評分評分:
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
在現代超大型積體電路設計中,因應不斷縮小的製成設計,多重排大小的標準元件庫變得越來越普及。需要複雜電路、較高能源需求、需要較高面積實作的電路會被設計成行高較高的標準原件,反之將成為行高較矮的原件。同時,因為不同大小的元件,我們不再能夠將每一行各自的擺置合法化問題視為單一子問題,導致擺置合法化的問題變得更加複雜且面臨新的挑戰。在這篇論文中,我們提出一個根據有向無環圖設計的演算法,此演算法可以在固定標準元件的先後順序的情況下得到減少元件位移的最大值的最佳化結果,且能在線性的時間內完成。首先,我們採用一種類似網路流的方法,藉由移動元件位置,盡量減少設計中密度較高的區域。接著藉由將元件移動到可以放置的最左方的位置確認現行的擺放狀況是否可以有合法的結果,也就是不超出設計邊界和不與設計障礙物重疊,之後再使用我們提出的有向無環圖演算法。然而,我們的演算法會因為被多重行高標準元件圍住的無效空間影響,因此必須再應用我們的演算法後重新擺放一些標準元件以達到降低平均元件位移的效果。實驗數據顯示,和 [1] 比較,我們提出的演算法可以降低約60%的最大元件位移量且同時平均元件位移量能有差不多的數值。
In modern VLSI design, standard cells of different row heights become more and more common due to the aggressive scaling of advanced technologies. Such multiple-row-height cells allow cells which are complex, need more power and areas have larger heights while simple cells be shorter. Besides, it also leads to more complicated challenges for legalization problem because we cannot consider legalization problems of each row independently. In this thesis, we propose a DAG-based algorithm which is linear-time for multiple-row-height cells placement legalization with optimal maximum displacement when row assignment and cell ordering are fixed. However, not all of the design can get feasible solution when row assignment and cell ordering are fixed. Thus, we propose a framework to deal with such situation. First, we use a flow-like spreading method to avoid region of undesirably high density and check if the layout can be legalized by pushing each cell to the left most position then examining whether there is any cell overlapped with macros, blockages or out of right boundary before applying our DAG-based algorithm. However, the dead spaces caused by multiple row height cells can limit the solution quality. So, after applying DAG-based algorithm, we use a greedy reassignment method to replace the cells which can moved into dead spaces to reduce average cell displacement. Experimental results show that our proposed algorithm can reduce maximum cell displacement by 60% while having comparable average cell displacement compared to [1].
誌謝v
Acknowledgements vii
摘要ix
Abstract xi
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Preliminaries 5
2.1 Mutiplerowheight
Cells Legalization . . . . . . . . . . . . . . . . . . 5
2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Algorithm 9
3.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 DAGbased
Linear Time Legalization . . . . . . . . . . . . . . . . . . 12
4 Framework 23
4.1 Overall Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Cell Row Reassignment with Flowlike
Method . . . . . . . . . . . . . 24
4.3 Left Aligned Violation Checking And Reassigned Cells Picking . . . . 26
4.4 Maximum Displacementaware
Cell Redistribution . . . . . . . . . . . 27
4.5 Greedy Cell Reassignment . . . . . . . . . . . . . . . . . . . . . . . . 29
4.6 Cell Shifting Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5 Experimental Results 33
5.1 Environment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2 Result of our method and previous work . . . . . . . . . . . . . . . . . 34
6 Conclusion 37
References 39
[1] W. Chow, C. Pui, and E. F. Y. Young, “Legalization algorithm for multiplerow
height standard cell design,” in Proc. of Design Automation Conference, pp. 83:1–
83:6, June 2016.
[2] A. K. Nima Karimpour Darav, Ismail S. Bustany and R. Mamidi, “Iccad2017
cad contest in multideck
standard cell legalization and benchmarks,” in
2017 IEEE/ACM International Conference on ComputerAided
Design (ICCAD),
pp. 13–16, Nov 2017.
[3] G. Wu and C. Chu, “Detailed placement algorithm for vlsi design with doublerow
height standard cells,” IEEE Transactions on ComputerAided
Design of Integrated
Circuits and Systems, vol. 35, no. 9, 2015.
[4] Y. Lin, B. Yu, X. Xu, J.R.
Gao, N. Viswanathan, W.H.
Liu, Z. Li, C. J. Alpert, and
D. Z. Pan, “Mrdp: Multiplerow
detailed placement of heterogeneoussized
cells
for advanced nodes,” in Proc. of International Conference on ComputerAided
Design, pp. 7:1–7:8, Nov 2016.
[5] C. Wang, Y. Wu, J. Chen, Y.W.
Chang, S. Kuo, W. Zhu, and G. Fan, “An effective
legalization algorithm for mixedcellheight
standard cells,” in Proc. of Asia and
South Pacific Design Automation Conference, pp. 450–455, Jan 2017.
[6] J. Chen, Z. Zhu, W. Zhu, and Y.W.
Chang, “Toward optimal legalization for
mixedcellheight
circuit designs,” in Proc. of Design Automation Conference,
pp. 52:1–52:6, 2017.
[7] Z. Zhu, X. Li, Y. Chen, J. Chen, W. Zhu, and Y. Chang, “Mixedcellheight
legalization
considering technology and region constraints,” in 2018 IEEE/ACM International
Conference on ComputerAided
Design (ICCAD), pp. 1–8, Nov 2018.
[8] X. Li, J. Chen, W. Zhu, and Y.W.
Chang, “Analytical mixedcellheight
legalization
considering average and maximum movement minimization,” in Proceedings
of the 2019 International Symposium on Physical Design, ISPD ’19, (New York,
NY, USA), pp. 27–34, ACM, 2019.
[9] “Si2 openaccess.” http://projects.si2.org/oac_index.php/, Mar. 2015.
[10] C.Y.
Hung, P.Y.
Chou, and W.K.
Mak, “Mixedcellheight
standard cell placement
legalization,” in Proc. of Great Lakes Symposium on VLSI, pp. 149–154,
2017.
[11] H. Li, W.K.
Chow, G. Chen, E. F. Y. Young, and B. Yu, “Routabilitydriven
and
fenceaware
legalization for mixedcellheight
circuits,” in Proc. of Design Automation
Conference, pp. 150:1–150:6, 2018.
[12] U. Brenner, “Bonnplace legalization: Minimizing movement by iterative augmentation,”
IEEE Transactions on ComputerAided
Design of Integrated Circuits and
Systems, vol. 32, pp. 1215–1227, Aug 2013.
[13] P. Spindler, U. Schlichtmann, and F. M. Johannes, “Abacus: Fast legalization of
standard cell circuits with minimal movement,” in Proc. of International Symposium
on Physical Design, pp. 47–53, 2008.
[14] S. Dobre, A. B. Kahng, and J. Li, “Mixed cellheight
implementation for improved
design quality in advanced nodes,” in Proc. International Conference on
ComputerAided
Design, pp. 854–860, Nov 2015.
[15] S. Goto, “An efficient algorithm for the twodimensional
placement problem in
electrical circuit layout,” IEEE Transactions on Circuits and Systems, vol. 28,
pp. 12–18, January 1981.
[16] Y. Wu and Y. Chang, “Mixedcellheight
detailed placement considering complex
minimumimplantarea
constraints,” in 2017 IEEE/ACM International Conference
on ComputerAided
Design (ICCAD), pp. 65–72, Nov 2017.
[17] J. Chen, P. Yang, X. Li, W. Zhu, and Y. Chang, “Mixedcellheight
placement with
complex minimumimplantarea
constraints,” in 2018 IEEE/ACM International
Conference on ComputerAided
Design (ICCAD), pp. 1–8, Nov 2018.
[18] Y. Tseng and Y. Chang, “Mixedcellheight
placement considering draintodrain
abutment,” in 2018 IEEE/ACM International Conference on ComputerAided
Design
(ICCAD), pp. 1–6, Nov 2018.
[19] M. Kim, D. Lee, and I. L. Markov, “Simpl: An effective placement algorithm,”
IEEE Transactions on ComputerAided
Design of Integrated Circuits and Systems,
vol. 31, pp. 50–60, Jan 2012.
[20] N. Karimpour Darav, I. S. Bustany, A. Kennings, and L. Behjat, “A fast, robust
network flowbased
standardcell
legalization method for minimizing maximum
movement,” in Proceedings of the 2017 ACM on International Symposium on
Physical Design, ISPD ’17, (New York, NY, USA), pp. 141–148, ACM, 2017.
[21] N. K. Darav, I. S. Bustany, A. Kennings, D. Westwick, and L. Behjat,
“Eh?legalizer: A high performance standardcell
legalizer observing technology
constraints,” ACM Trans. Des. Autom. Electron. Syst., vol. 23, pp. 43:1–43:25,
May 2018.
[22] M. Pan, N. Viswanathan, and C. Chu, “An efficient and effective detailed
placement algorithm,” in ICCAD2005.
IEEE/ACM International Conference on
ComputerAided
Design, 2005., pp. 48–55, Nov 2005.
[23] W.K.
Chow, J. Kuang, X. He, W. Cai, and E. F. Young, “Cell densitydriven
detailed placement with displacement constraint,” in Proceedings of the 2014 on
International Symposium on Physical Design, ISPD ’14, (New York, NY, USA),
pp. 3–10, ACM, 2014.
[24] K.H.
Tseng, Y.W.
Chang, and C. C. C. Liu, “Minimumimplantareaaware
detailed
placement with spacing constraints,” in Proceedings of the 53rd Annual Design
Automation Conference, DAC ’16, (New York, NY, USA), pp. 84:1–84:6,
ACM, 2016.
41
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top