成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	李思庭 Li, Szu-Ting
論文名稱：	考慮巨集電路間接連線關係且以設計階層為導向之擺置樣板方法 Design Hierarchy-Guided Placement Prototyping Approach Considering Indirect Connectivity Between Macros
指導教授：	林家民 Lin, Jai-Ming
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2018
畢業學年度：	107
語文別：	英文
論文頁數：	36
中文關鍵詞：	叢集、設計階層、間接連線關係、巨集電路、擺置
外文關鍵詞：	clustering, design hierarchy, indirect connectivity, macro, placement
相關次數：	點閱：48 下載：0
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

隨著製程技術的進步，現今電路設計通常包含數百個模塊（巨集電路）以及數百萬個標準邏輯閘。擺置樣板（placement prototyping）為三階段混合擺置中最為重要的一個階段，因為模塊和標準邏輯閘的相對位置會在這個階段被決定，且這個位置會影響到後續其它階段的進行；然而另一方面來說，擺置樣板也相當地耗時。為了降低設計複雜度並提高結果品質，過去的研究會將叢集（clustering）演算法加到他們的擺置方法中。儘管如此，隨著電路日趨複雜，傳統叢集演算法所考慮的因素已經遠遠不夠。本篇論文的研究主要集中在擺置樣板中的粗化（coarsening）階段，以便提供後續全域擴散（global distribution）階段一組適當的叢集組去散佈。透過對電路網表建立階層樹（hierarchy tree），本論文提出一個全新的叢集分數函數，它額外考慮了電路的設計階層與模塊間的間接連線關係。此外，本論文也提出重疊定界框約束（overlapping bounding box constraint）以更準確地處理電路的實體資訊。在執行整體擺置樣板方法之後，實驗結果證明本論文的方法可以進一步地改善線長與可繞度。

Due to advance in manufacture technology, a modern design usually contains hundreds of macros and millions of standard cells. Placement prototyping is the most important stage because the relative positions of macros and standard cells are determined in this stage, and the results are followed by later stages. However, placement prototyping is also time-consuming. In order to reduce the design complexity and improve outcome quality, previous works integrate clustering algorithm into the placement framework. Nevertheless, the factors which traditional clustering algorithms have considered are far from enough. Our research mainly focuses on bottom-up coarsening in our placement prototyping approach, in order to provide an appropriate set of clusters for initial global distribution and let top-down refinement be effective. With the construction of a hierarchy tree from a netlist, we proposed a score function to additionally consider the design hierarchy of all blocks and the indirect connectivity between macros. Also, we propose the overlapping bounding box constraint to deal with the physical information. After the execution of our overall placement prototyping approach, the experimental results show that our approach can further improve routing wire-length and routability.

摘要 .............................................................................. I
Abstract ......................................................................... II
誌謝 ............................................................................. III
Table of Contents ................................................................ IV
List of Tables ................................................................... VI
List of Figures .................................................................. VII
Chapter 1 Introduction ........................................................... 1
1.1 Previous Works ............................................................... 3
1.1.1 Traditional Clustering Algorithm ........................................... 3
1.1.2 Hierarchy-Aware Clustering Algorithm ....................................... 4
1.2 Motivations .................................................................. 5
1.3 Our Contributions ............................................................ 7
1.4 Thesis Organization .......................................................... 8
Chapter 2 Preliminaries .......................................................... 9
2.1 Multilevel Framework ......................................................... 9
2.2 Analytical-Based Approach .................................................... 10
2.3 Area Function ................................................................ 11
Chapter 3 Problem Formulation .................................................... 13
Chapter 4 Design Hierarchy-Guided Clustering Algorithm ........................... 14
4.1 Overview of Our Proposed Methodology ......................................... 14
4.2 Introduction of Hierarchy Tree ............................................... 16
4.3 Score Function Considering Design Hierarchy and Indirect Connectivity ........ 17
4.3.1 Hierarchy Function ......................................................... 18
4.3.2 Connectivity Function ...................................................... 19
4.3.3 Relation Function .......................................................... 19
4.4 Physical Constraint for Clustering Two Objects ............................... 20
4.5 Details of Our Clustering Algorithm .......................................... 21
4.5.1 Limitations of Choosing Objects to Cluster ................................. 21
4.5.2 Clustering Score Constraint ................................................ 23
4.5.3 Modification of Hierarchy Tree ............................................. 23
Chapter 5 Experimental Results ................................................... 26
5.1 Environment .................................................................. 26
5.2 Results ...................................................................... 27
Chapter 6 Conclusion ............................................................. 33
Bibliography ..................................................................... 34
                                    

[1] C. J. Alpert, J.-H. Huang, and A. B. Kahng, “Multilevel circuit partitioning,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 17, no. 8, pp. 655–667, Aug 1998.
[2] S. N. Adya, S. Chaturvedi, J. A. Roy, D. A. Papa, and I. L. Markov, “Unification of partitioning, placement and floorplanning,” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), pp. 550–557, 2004.
[3] C. Alpert, A. Kahng, G.-J. Nam, S. Reda, and P. Villarrubia, “A semi-persistent clustering technique for VLSI circuit placement,” in Proc. of ACM International Symposium on Physical Design (ISPD), pp. 200–207, 2005.
[4] Y. Cheon and D. F. Wong, “Design hierarchy-guided multilevel circuit partitioning,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 22, no. 4, pp. 420–427, 2003.
[5] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, “NTUplace3: An analytical placer for large-scale mixed-size designs with pre-placed blocks and density constraints,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 27, no. 7, pp. 1228–1240, July 2008.
[6] T.-C. Chen, P.-H. Yuh, Y.-W. Chang, F.-J. Huang, and T.-Y. Liu, “MP-trees: A pack-ing-based macro placement algorithm for modern mixed-size designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuit and Systems (TCAD), vol. 27, no. 9, pp. 1621–1634, September 2008.
[7] Y.-L. Chuang, G.-J. Nam, C. J. Alpert, Y.-W. Chang, J. Roy, and N. Viswanathan, “Design-hierarchy aware mixed-size placement for routability optimization,” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), San Jose, CA, USA, pp. 663–668, 2010.
[8] Y.-F. Chen, C.-C. Huang, C.-H. Chiou, Y.-W. Chang, and C.-J. Wang, “Routability-driven blockage-aware macro placement,” in Proc. of ACM/IEEE Design Automation Conference (DAC), pp. 1–6, 2014.
[9] C.-L. Ding, C.-Y. Ho, and M.J. Irwin, “A new optimization driven clustering algorithm for large circuits,” in Proc. of European Design Automation Conference, pp. 20–24, 1993.
[10] Y.-L. Deng, “A Routability-Driven Macro Placer Following Design Hierarchy Based on Simulated Evolution Algorithm,” M.S. Thesis, National Cheng Kung University, Tainan, Taiwan, 2018.
[11] L. Hagen, A. B. Kahng, F. J. Kurdahi, and C. Ramachandran, “On the intrinsic Rent parameter and spectra-based partitioning methodologies,” IEEE Transactions on Com-puter-Aided Design of Integrated Circuits and Systems (TCAD), vol. 13, no. 1, pp. 27–37, 1994.
[12] M.-K. Hsu and Y.-W. Chang, “Unified analytical global placement for large-scale mixed-size circuit designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuit and Systems (TCAD), vol. 31, no. 9, pp. 1366–1378, September 2012.
[13] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel hypergraph partitioning: applications in VLSI domain,” IEEE Transactions on Very Large Scale Integration Systems (TVLSI), vol. 7, no. 1, pp. 69–79, March 1999.
[14] G. Karypis and V. Kumar, “Multilevel k-way hypergraph partitioning,” in Proc. of ACM/IEEE Design Automation Conference (DAC), pp. 343–348, 1999.
[15] A. B. Kahng and Q. Wang, “A faster implementation of APlace,” in Proc. of ACM International Symposium on Physical Design (ISPD), pp. 218–220, April 2006.
[16] M.-C. Kim, D.-J. Lee, and I. L. Markov, “SimPL: An effective placement algorithm,” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), pp. 649–656, 2010.
[17] M. Kuwano and Y. Takashima, “Stable-LSE based analytical placement with overlap removable length,” in Proc. of Synthesis And System Integration of Mixed Information Technologies, pp. 115–120, 2010.
[18] J.-M. Lin, B.-H. Yu, and L.-Y. Chang, “Regularity-aware routability-driven placement prototyping algorithm for hierarchical mixed-size circuits,” in Proc. of IEEE/ACM Asia and South Pacific Design Automation Conference (ASP-DAC), Tokyo, Japan, pp. 438–443, Jan 2017.
[19] T. K. Ng, J. Oldfield, and V. Pitchumani, “Improvements of a mincut partition algorithm,” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), pp. 470–473, 1987.
[20] W. C. Naylor, R. Donelly and L. Sha, “Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer,” U.S. Patent 6 301 693 B1, December 16, 1998.
[21] J. Z. Yan, N. Viswanathan, and C. Chu, “Handling complexities in modern large-scale mixed-size placement,” in Proc. of ACM/IEEE Design Automation Conference (DAC), pp. 436–441, 2009.
[22] Himax Technologies, Inc. About Himax. Accessed: August 24, 2018. [Online]. Available: http://www.himax.com.tw/company/about-himax/
[23] Synopsys Inc. IC Compiler, Place and Route System. Accessed: October 15, 2018. [Online]. Available: https://www.synopsys.com/implementation-and-signoff/physical-implementation/ic-compiler.html

校內：2023-12-31公開
校外：不公開電子論文尚未授權公開，紙本請查館藏目錄

簡易檢索 / 詳目顯示

相關論文