請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/21999
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張耀文(Yao-Wen Chang) | |
dc.contributor.author | Yu-Hsuan Chang | en |
dc.contributor.author | 張育瑄 | zh_TW |
dc.date.accessioned | 2021-06-08T03:57:11Z | - |
dc.date.copyright | 2018-08-21 | |
dc.date.issued | 2018 | |
dc.date.submitted | 2018-08-14 | |
dc.identifier.citation | [1] IBM ILOG CPLEX Optimizer, http://www-01.ibm.com/software/commerce/optimization/optimizer/index.html.
[2] A. Arunkumar, E. Bolotin, B. Cho, U. Milic, E. Ebrahimi, O. Villa, A. Jaleel, C.-J. Wu, and D. Nellans, MCM-GPU: Multi-chip-module GPUs for continued performance scalability,' in Symp. of ISCA, pp. 320-332, June 2017. [3] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms. MIT press, 2009. [4] J.-W. Fang, C.-H. Hsu, and Y.-W. Chang, An integer linear programming based routing algorithm for flip-chip design,' in Proc. of DAC, pp. 606-611, June 2007. [5] J.-W. Fang, C.-H. Hsu, and Y.-W. Chang, An integer-linear-programming-based routing algorithm for flip-chip designs,' IEEE TCAD, vol. 28, no. 1, pp. 98-110, January 2009. [6] J.-W. Fang, I.-J. Lin, Y.-W. Chang, and J.-H. Wang, A network-flow-based RDL routing algorithm for flip-chip design,' IEEE TCAD, vol. 26, no. 8, pp.1417-1429, August 2007. [7] J.-W. Fang and Y.-W. Chang, Area-I/O flip-chip routing for chip-package co-design,' in Proc. of ICCAD, pp. 518-522, November 2008. [8] J.-W. Fang and Y.-W. Chang, Area-I/O flip-chip routing for chip-package co-design considering signal skews,' IEEE TCAD, vol. 29, no. 5, pp. 711-721, May 2010. [9] J.-W. Fang, I.-J. Lin, P.-H. Yuh, Y.-W. Chang, and J.-H. Wang, A routing algorithm for flip-chip design,' in Proc. of ICCAD, pp. 752-757, November 2005. [10] J.-W. Fang, M. D. F. Wong, and Y.-W. Chang, Flip-chip routing with unified area-I/O pad assignments for package-board co-design,' in Proc. of DAC, pp.336-339, July 2009. [11] Y.-K. Ho, H.-C. Lee, W. Lee, Y.-W. Chang, C.-F. Chang, I.-J. Lin, and C.-F. Shen, Obstacle-avoiding free-assignment routing for flip-chip designs,' IEEE TCAD, vol. 33, no. 2, pp. 224-236, February 2014. [12] H.-C. Lee, Y.-W. Chang, and P.-W. Lee, Recent research development in flipchip routing,' in Proc. of ICCAD, pp. 404-410, November 2010. [13] P.-W. Lee, C.-W. Lin, Y.-W. Chang, C.-F. Shen, and W.-C. Tseng, An efficient pre-assignment routing algorithm for flip-chip designs,' in Proc. of ICCAD, pp.239-244, November 2009. [14] P.-W. Lee, H.-C. Lee, Y.-K. Ho, Y.-W. Chang, C.-F. Chang, I.-J. Lin, and C.-F. Shen, Obstacle-avoiding free-assignment routing for flip-chip designs,' in Proc. of DAC, pp. 1088-1093, November 2012. [15] T.-H. Li, W.-C. Chen, X.-T. Cai, and T.-C. Chen, Escape routing of differential pairs considering length matching,' in Proc. of ASP-DAC, pp. 139-144, January 2012.44 [16] C.-W. Lin, P.-W. Lee, Y.-W. Chang, C.-F. Shen, and W.-C. Tseng, An efficient pre-assignment routing algorithm for flip-chip designs,' IEEE TCAD, vol. 31, no. 6, pp. 878-889, June 2012. [17] X. Liu, Y. Zhang, G. K. Yeap, C. Chu, J. Sun, and X. Zeng, Global routing and track assignment for flip-chip designs,' in Proc. of DAC, pp. 90-93, June 2010. [18] J. W. Poulton, W. J. Dally, X. Chen, J. G. Eyles, T. H. Greer, S. G. Tell, J. M. Wilson, and C. T. Gray, A 0.54 pj/b 20 gb/s ground-referenced single-ended short-reach serial link in 28 nm cmos for advanced packaging applications,' IEEE JSSC, vol. 48, no. 12, pp. 3206-3218, December 2013. [19] P. Pulici, G. P. Vanalli, M. A. Dellutri, D. Guarnaccia, F. L. Iacono, G. Campardo, and G. Ripamonti, Signal integrity flow for system-in-package and package-on-package devices,' Proceedings of the IEEE, vol. 97, no. 1, pp. 84-95, January 2009. [20] K. J. Supowit, Finding a maximum planar subset of a set of nets in a channel,' IEEE TCAD, vol. 6, no. 1, pp. 93-94, January 1987. [21] J. T. Yan and Z. W. Chen, IO connection assignment and RDL routing for flip-chip designs,' in Proc. of ASP-DAC, pp. 588-593, January 2009. [22] J. T. Yan and Z. W. Chen, RDL pre-assignment routing for flip-chip design,' in Proceedings of the Great Lakes Symposium on VLSI, pp. 401-404, May 2009. [23] J.-T. Yan and Z.-W. Chen, Pre-assignment RDL routing via extraction of maximal net sequence,' in Conf. of ICCD, pp. 65-70, October 2011.45 [24] T. Yan and M. D. F. Wong, Correctly modeling the diagonal capacity in escape routing,' IEEE TCAD, vol. 31, no. 2, pp. 285-293, February 2012. [25] T. Yan and M. D. F. Wong, BSG-route: A length-constrained routing scheme for general planar topology,' IEEE TCAD, vol. 28, no. 11, pp. 1679-1690, November 2009. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/21999 | - |
dc.description.abstract | 人工智慧時代的到來,對於平行運算資源的需求日益提升,而傳統的單晶片圖形運算單元(monolithic graphics processing unit) 效能已經無法滿足,因此出現了多晶片模組圖形運算單元(multi-chip-module graphics processing unit)這一個大有可為的新技術,其中因為高速訊號對於時間要求非常嚴苛,因此在覆晶封裝上的重分佈層(redistribution layer) 繞線需要符合一些長度匹配(length-matching) 的條件。據我們所知,目前尚未有論文是針對處理區域輸入/輸出覆晶封裝重分佈層上的長度匹配繞線問題。大部分相關的發表論文著重於考慮覆晶封裝上的單純繞線問題,主要可以分為三類,分別是自由配對繞線問題、非自由配對繞線問題與混合型配對繞線問題。在此篇論文當中, 我們提出了一個新的區域輸入/輸出覆晶式封裝中的重分佈層長度匹配繞線問題。為了彌補相關論文缺乏對於長度匹配繞線的考慮,我們提出了第一個演算法針對處理區域輸入/輸出覆晶封裝重分佈層上的長度匹配繞線問題,此演算法考慮到了訊號線的可繞線性、長度匹配的條件限制以及總線長的最小化。我們的繞線演算法採用了一個二階式技術:全域繞線與隨後的細部繞線。在全域繞線中,由於採用了計算幾何學(三角化和 Voronoi 圖示) 我們可以處理區域輸入/輸出的重分佈層結構,此外,我們也額外考慮了繞線擁擠度的問題。在細部繞現階段,我們利用線段包圍網格(bounded-sliceline grid) ,使用二次規劃(quadratic programming) 調整網格大小以符合長度匹配的條件限制,並維持前步驟的最短繞線長度。實驗結果顯示我們的繞線器可以達到百分之百的繞線率,相較之下,相關發表論文所延伸的演算法無法在符合長度匹配條線的限制下達到百分之百的繞線率,並且會耗費更多總線長。 | zh_TW |
dc.description.abstract | A robust redistribution layer (RDL) router is required for advanced package designs, where the length-matching constraint needs to be considered to preserve good timing properties at the package level. We propose the first lengthmatching routing framework that can simultaneously handle nets with and without equal-length constraints on redistribution layers, based on an equal-length-aware A*-search algorithm and a bounded sliceline grid (BSG) snaking one. To effectively consider the equal-length constraints in an earlier stage, we first profile the routing resource to obtain an approximation of the longest net, and then adopt the equallength-aware A*-search algorithm to extend shorter nets to match the estimated longest net. The BSG-based snaking method is applied to meet the equal-length constraint, while preserving the minimized wirelength of unconstrained nets. Experimental results demonstrate that our framework can solve all benchmarks effectively and efficiently. | en |
dc.description.provenance | Made available in DSpace on 2021-06-08T03:57:11Z (GMT). No. of bitstreams: 1 ntu-107-R05943139-1.pdf: 2701590 bytes, checksum: 46728a8c31c6c991d5016199d213714f (MD5) Previous issue date: 2018 | en |
dc.description.tableofcontents | Acknowledgements iii
Abstract (Chinese) iv Abstract vi List of Tables ix List of Figures x Chapter 1. Introduction 1 1.1 Multi-Chip-Module GPU Packages . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 RDL Routing for the Free-Assignment Routing Problem . . . . . 3 1.2.1.1 Network-Flow-Based Methods . . . . . . . . . . . . . . . . 3 1.2.1.2 Non-Network-Flow-Based Methods . . . . . . . . . . . . . 7 1.2.2 RDL Routing for the Pre-Assignment Routing Problem . . . . . . 7 1.2.2.1 ILP-Based Methods . . . . . . . . . . . . . . . . . . . . . 7 1.2.2.2 Non-ILP-Based Methods . . . . . . . . . . . . . . . . . . . 8 1.2.3 RDL Routing for the Unified-Assignment Routing Problem . . . . 9 1.2.4 Length-Matching Routing . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Differences from the Previous Works . . . . . . . . . . . . . . . . . . . . . 11 1.4 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Chapter 2. Preliminaries 14 2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 vii2.2 Review of Delaunay Triangulation and Voronoi Diagram . . . . . . . . . 16 2.3 Review of Bounded Sliceline Grid . . . . . . . . . . . . . . . . . . . . . . 16 Chapter 3. Algorithms 17 3.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Global Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.1 Delaunay Triangulation and Voronoi Diagram Construction . . . . 19 3.2.2 Equal-Length Group Routing . . . . . . . . . . . . . . . . . . . . . 21 3.3 BSG-Based Snaking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3.1 BSG Embedding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3.2 Cell Sizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.3 Snaking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Chapter 4. Experimental Results 35 4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 Experimental Results and Comparisons . . . . . . . . . . . . . . . . . . . 35 Chapter 5. Conclusions and Future Work 39 Bibliography 42 Publication List 46 | |
dc.language.iso | en | |
dc.title | 針對區域輸入/輸出覆晶式封裝設計考慮長度匹配之繞線系統 | zh_TW |
dc.title | Length-Matching Routing for Area-I/O Flip-Chip Designs | en |
dc.type | Thesis | |
dc.date.schoolyear | 106-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 黃婷婷(Ting-Ting Hwang),李毅郎(Yih-Lang Li),江蕙如(Hui-Ru Jiang) | |
dc.subject.keyword | 實體設計,多晶片模組圖形運算單元,重分佈層,重分佈層繞線,長度匹配繞線, | zh_TW |
dc.subject.keyword | Physical Design,Multi-Chip-Module GPU,Redistribution Layer,RDL Routing,Length-Matching Routing, | en |
dc.relation.page | 46 | |
dc.identifier.doi | 10.6342/NTU201802608 | |
dc.rights.note | 未授權 | |
dc.date.accepted | 2018-08-14 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-107-1.pdf 目前未授權公開取用 | 2.64 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。