請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63149完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 張耀文(Yao-Wen Chang) | |
| dc.contributor.author | Hsiang-Ting Wen | en |
| dc.contributor.author | 温祥廷 | zh_TW |
| dc.date.accessioned | 2021-06-16T16:25:09Z | - |
| dc.date.available | 2025-06-09 | |
| dc.date.copyright | 2020-06-09 | |
| dc.date.issued | 2020 | |
| dc.date.submitted | 2020-05-18 | |
| dc.identifier.citation | [1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin,Network Flows: Theory, Algo-rithms, and Applications. Prentice Hall, Inc., 1993.
[2] H. Chen, H.-C. Lin, C.-N. Peng, and M.-J. Wang, “Wafer level chip scalepackage copper pillar probing,” inProceedings of International Test Conference,pp. 1–6, Seattle, WA, October 2014. [3] Daniel Yang and Stacy Wegner. Apple watch series 3 teardown. Accessed: 2019-11-25. [Online]. Available: https://www.techinsights.com/zh-tw/node/16538 [4] J.-W. Fang and Y.-W. Chang, “Area-I/O flip-chip routing for chip-package co-design,” inProceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 518–522, San Jose, CA, November 2008. [5] J.-W. Fang, C.-H. Hsu, and Y.-W. Chang, “An integer linear programmingbased routing algorithm for flip-chip design,” inProceedings of ACM/IEEEDesign Automation Conference, pp. 606–611, San Diego, CA, June 2007. [6] J.-W. Fang, C.-H. Hsu, and Y.-W. Chang, “An integer-linear-programming-based routing algorithm for flip-chip designs,”IEEE Transactions onComputer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 1, pp.98–110, 2009. [7] J.-W. Fang, I.-J. Lin, and Y.-W. Chang, “A network-flow-based RDL routingalgorithmz for flip-chip design,”IEEE Transactions on Computer-Aided Designof Integrated Circuits and Systems, vol. 26, no. 8, pp. 1417–1429, 2007. [8] J.-W. Fang, I.-J. Lin, and Y.-W. Chang, “Area-I/O flip-chip routing for chip-package co-design considering signal skews,”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 5, pp. 711–721,2010. [9] J.-W. Fang, I.-J. Lin, P.-H. Yuh, Y.-W. Chang, and J.-H. Wang, “A rout-ing algorithm for flip-chip design,” inProceedings of IEEE/ACM InternationalConference on Computer-Aided Design, pp. 752–757, San Jose, CA, November2005. [10] J.-W. Fang, M. D. F. Wong, and Y.-W. Chang, “Flip-chip routing with uni-fied area-I/O pad assignments for package-board co-design,” inProceedings ofACM/IEEE Design Automation Conference, pp. 336–339, San Francisco, CA,July 2009. [11] Gurobi Optimization, LLC. Gurobi optimizer reference manual. Accessed:2019-11-27. [Online]. Available: https://www.gurobi.com/ [12] 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,”IEEETransactions on Computer-Aided Design of Integrated Circuits and Systems,vol. 33, no. 2, pp. 224–236, 2014. [13] Y.-C. Huang, B.-Y. Lin, C.-W. Wu, M. Lee, H. Chen, H.-C. Lin, C.-N. Peng,and M.-J. Wang, “Efficient probing schemes for fine-pitch pads of info wafer-level chip-scale package,” inProceedings of ACM/IEEE Design AutomationConference, pp. 1–6, Austin, TX, June 2016. [14] IEEE Electronics Packaging Society. Heterogeneous integration roadmap.Accessed: 2019-11-25. [Online]. Available: https://eps.ieee.org/technology/heterogeneous-integration-roadmap.html [15] S.-P. Jeng, D.-J. Chen, H.-T. Lu, H.-W. Liu, C.-H. Lin, S.-T. Hung, and P.-Y.Chuang, “Integrated fan-out packages,” U.S. Patent 10 347 574, Mar 28, 2019. [16] H.-C. Lee, Y.-W. Chang, and P.-W. Lee, “Recent research development inflip-chip routing,” inProceedings of IEEE/ACM International Conference onComputer-Aided Design, pp. 404–410, San Jose, CA, November 2010. [17] P.-W. Lee, H.-C. Lee, Y.-K. Ho, Y.-W. Chang, C.-F. Chang, I.-J. Lin, andC.-F. Shen, “Obstacle-avoiding free-assignment routing for flip-chip designs,”inProceedings of ACM/IEEE Design Automation Conference, pp. 1088–1093,San Francisco, CA, June 2012. [18] P.-W. Lee, C.-W. Lin, Y.-W. Chang, C.-F. Shen, and W.-C. Tseng, “An effi-cient pre-assignment routing algorithm for flip-chip designs,” inProceedings ofIEEE/ACM International Conference on Computer-Aided Design, pp. 239–244,San Jose, CA, November 2009. [19] B.-Q. Lin, T.-C. Lin, and Y.-W. Chang, “Redistribution layer routing for inte-grated fan-out wafer-level chip-scale packages,” inProceedings of IEEE/ACMInternational Conference on Computer-Aided Design, pp. 1–6, Austin, TX,November 2016. [20] C.-W. Lin, P.-W. Lee, Y.-W. Chang, C.-F. Shen, and W.-C. Tseng, “An efficientpre-assignment routing algorithm for flip-chip designs,”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 31, no. 6, pp.878–889, 2012. [21] T.-C. Lin, C.-C. Chi, and Y.-W. Chang, “Redistribution layer routing for wafer-level integrated fan-out package-on-packages,” inProceedings of IEEE/ACMInternational Conference on Computer-Aided Design, pp. 561–568, Irvine, CA,November 2017. [22] C. C. Liu, S.-M. Chen, F.-W. Kuo, H.-N. Chen, E.-H. Yeh, C.-C. Hsieh, L.-H.Huang, M.-Y. Chiu, J. Yeh, T.-S. Lin, T.-J. Yeh, S.-Y. Hou, J.-P. Hung, J.-C.Lin, C.-P. Jou, C.-T. Wang, S.-P. Jeng, and D. C. H. Yu, “High-performanceintegrated fan-out wafer level packaging (InFO-WLP): Technology and systemintegration,” inProceedings of IEEE International Electron Devices Meeting,pp. 14.1.1–14.1.4, San Francisco, CA, December 2012. [23] X. Liu, Y. Zhang, G. K. Yeap, and C. Chu, “Global routing and track assign-ment for flip-chip designs,” inProceedings of ACM/IEEE Design AutomationConference, pp. 90–93, Anaheim, CA, July 2010. [24] T. Ohtsuki, “Gridless routers—new wire routing algorithms based on compu-tational geometry,” inProceedings of International Conference of Circuits andSystems, pp. 802–809, May 1985. [25] K. J. Supowit, “Finding a maximum planar subset of a set of nets in a chan-nel,”IEEE Transactions on Computer-Aided Design of Integrated Circuits andSystems, vol. 6, no. 1, pp. 93–94, 1987. [26] C.-F. Tseng, C.-S. Liu, C.-H. We, and D. Yu, “InFO (wafer level integratedfan-out) technology,” inProceedings of IEEE Electronic Components and Tech-nology Conference, pp. 1–6, Las Vegas, NV, June 2016. [27] J. T. Yan and Z. W. Chen, “IO connection assignment and RDL routing forflip-chip designs,” inProceedings of IEEE/ACM International Conference onComputer-Aided Design, pp. 588–593, Yokohama, Japan, January 2009. [28] T. Yan and M. D. F. Wong, “A correct network flow model for escape routing,”inProceedings of ACM/IEEE Design Automation Conference, pp. 332–335, SanFrancisco, CA, July 2009. [29] T. Yan and M. D. F. Wong, “Correctly modeling the diagonal capacity in escaperouting,”IEEE Transactions on Computer-Aided Design of Integrated Circuitsand Systems, vol. 31, no. 2, pp. 285–293, 2012. [30] D. Yu, “A new integration technology platform: Integrated fan-out wafer-level-packaging for mobile applications,” inProceedings of the Symposium on VLSITechnology, pp. T46–T47, Kyoto, Japan, June 2015. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63149 | - |
| dc.description.abstract | 整合扇出型晶圓級封裝技術 (integrated fan-out wafer-level chip-scale package) 對於要求高輸入/輸出數量、緊密訊號互連、尺寸微型化的現代系統級封裝 (system-in-package) 而言，是一個大有可為的解決方案。整合扇出型晶圓級封裝藉由其中被稱為重分布層 (redistribution layer) 的額外金屬層來達成封裝層級的訊號互連。為了達到兼具設計彈性與緊密的晶片間互連，整合扇出型晶圓級封裝上的重分布層繞線問題已成為近年來實體設計領域的重要問題。
在文獻上有許多重分布層繞線演算法曾被提出，這些文獻分別考慮不同設計上的問題，其中包括覆晶封裝 (flip-chip package)、整合扇出型晶圓級封裝、不同種類的配對繞線問題與重分布層結構。然而，現代的高密度整合扇出型晶圓級封裝設計已可製造並經常使用多層的重分布層與可調整的貫孔 (flexible vias)。另一方面，在封裝中整合不同技術規格的晶片時，也必須將不規則凸塊結構 (irregular pad structures) 納入考慮。據我們所知，目前尚未有針對重分布層繞線問題的論文能夠同時處理設計中的可調整貫孔與不規則凸塊結構。 在本篇論文中，我們提出了在整合扇出型晶圓級封裝中，考慮多層、多晶片、可調整貫孔與不規則凸塊結構的混合型配對繞線問題。為了彌補相關論文的不足之處，我們提出了首個針對此問題的完整繞線流程，並考慮到有限的繞線層數下，繞線率 (routability) 的最大化與總線長的最小化。我們的繞線流程包含一個預處理階段、三個繞線階段以及一個佈局最佳化階段。在預處理階段中，我們分析可用的繞線資源與潛在的繞線壅塞區域。在第一個繞線階段，我們基於有權重的最大不相交弦 (maximum planar subset of chords) 演算法來進行訊號分層 (layer assignment)，從而同時完成儘量多的晶片間連線。接著，在第二個繞線階段，我們藉由切割出八邊形區域來處理佈局中的不規則結構並以此建構立體繞線圖，然後利用A星搜尋演算法 (A*-search algorithm) 完成剩餘的晶片間連線。在第三個繞線階段，我們將立體繞線圖轉換為一個網路流模型，以利用最小成本最大流 (minimum cost maximum flow) 演算法來完成晶片-電路板連線。最後，我們發展了一個基於線性規劃的佈局最佳化演算法以實現線長最小化與調整更佳的貫孔位置。 實驗結果顯示我們的繞線器在限制的層數下可以達到百分之百的繞線率，相較之下，相關發表論文所延伸的演算法仍無法適用於全部電路，且在那些可適用的電路上也無法達到百分之百的繞線率。 | zh_TW |
| dc.description.abstract | The integrated fan-out (InFO) wafer-level chip-scale package (WLCSP) technology is a promising solution for modern system-in-package (SiP) designs with large I/O counts, high interconnection density, and small form factors. In an InFO package, extra metal layers called redistribution layers (RDLs) are constructed for package-level interconnect. To achieve flexible inter-chip connections, the RDL routing problem for InFO packages has become a crucial problem for modern electronic designs.
Techniques for RDL routing have been proposed to deal with different routing issues, including flip-chip and InFO packages, different pad assignments and RDL structures. However, in advanced high-density InFO packages, multiple RDLs with flexible vias are already manufacturable and often adopted. On the other hand, to integrate chips of different technology nodes into one package, irregular pad structures need to be considered. To our best knowledge, however, there is no published work for RDL routing considering flexible vias or irregular pad structures. In this thesis, a new RDL routing problem with unified-assigned pad pairs on the via-based multi-layer multi-chip InFO package with irregular pad structures is formulated. We propose the first complete algorithm for this problem, considering routability maximization under limited RDLs and total wirelength minimization. Our algorithm flow consists of a preprocessing stage, three routing stages, and a layout optimization stage. In the preprocessing stage, we analyze the routing resources and the potential routing congestions. In the first routing stage, we perform layer assignment based on a weighted maximum planar subset of chords (WMPSC) algorithm to concurrently route as much inter-chip nets as possible. Next, in the second routing stage, we construct a 3D routing graph based on partitioning octagonal tiles to handle with the irregular layout structure, and complete the remaining inter-chip routing by performing the A*-search routing. Then, in the third routing stage, we transform the routing graph into a network-flow model to perform concurrent routing for chip-to-board nets by applying the minimum cost maximum flow (MCMF) algorithm. Finally, we develop an efficient linear-programming-based layout optimization algorithm to find solutions with high-quality wirelength and via arrangements. Experimental results show that our router can achieve 100\% routablility for all given test cases under limited RDLs, while the state-of-the-art previous work with extensions is only applicable to partial cases and fails to route those cases too. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T16:25:09Z (GMT). No. of bitstreams: 1 ntu-109-R06943090-1.pdf: 3814257 bytes, checksum: dbeed13840b80f39250299e3967e4873 (MD5) Previous issue date: 2020 | en |
| dc.description.tableofcontents | Acknowledgements iii
Abstract (Chinese) iv Abstract vii List of Figures xii List of Tables xvi Chapter 1. Introduction 1 1.1 Integrated Fan-Out Wafer-Level Chip-Scale Packages . . . . . . . . . . . 1 1.2 Classifications of RDL Routing Problems . . . . . . . . . . . . . . . . . . 5 1.2.1 Traditional Flip-Chip RDL Routing Problems . . . . . . . . . . . . 5 1.2.2 InFO RDL Routing Problems . . . . . . . . . . . . . . . . . . . . . 7 1.2.3 Other Key Concepts in RDL Routing Problems . . . . . . . . . . . 12 1.3 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.1 Free-Assignment RDL Routing . . . . . . . . . . . . . . . . . . . . 13 1.3.1.1 Network-Flow-Based Methods . . . . . . . . . . . . . . . . 13 1.3.1.2 Non-Network-Flow-Based Methods . . . . . . . . . . . . . 16 1.3.1.3 Advanced Tile Models . . . . . . . . . . . . . . . . . . . . 16 1.3.2 Pre-Assignment RDL Routing . . . . . . . . . . . . . . . . . . . . 17 1.3.2.1 ILP-Based Methods . . . . . . . . . . . . . . . . . . . . . 17 1.3.2.2 Non-ILP-Based Methods . . . . . . . . . . . . . . . . . . . 17 1.3.3 Unified-Assignment RDL Routing . . . . . . . . . . . . . . . . . . 18 1.3.4 Integrated Fan-Out Packages RDL Routing . . . . . . . . . . . . . 18 1.4 Emerging Package Considerations and Motivation . . . . . . . . . . . . . 19 1.5 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.6 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Chapter 2. Preliminaries 23 2.1 Design Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Package-Board Codesign . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Terminologies and Notations . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Chapter 3. Our Proposed Algorithm 29 3.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.1 Peripheral I/O Identification . . . . . . . . . . . . . . . . . . . . . 32 3.2.2 Fan-Out Region Partitioning . . . . . . . . . . . . . . . . . . . . . 33 3.2.3 Minimum Spanning Tree and Circular Model Construction . . . . 34 3.3 Concurrent Inter-Chip Routing . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.1 Weighted MPSC-Based Layer Assignment . . . . . . . . . . . . . . 37 3.3.2 Net Weight Computation . . . . . . . . . . . . . . . . . . . . . . . 38 3.3.3 Detailed Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.4 Sequential Inter-Chip Routing . . . . . . . . . . . . . . . . . . . . . . . . 42 3.4.1 Via Insertion and Octagonal Tile Partitioning . . . . . . . . . . . . 42 3.4.2 3D Global Routing Graph Construction . . . . . . . . . . . . . . . 43 3.4.3 A*-Search Global Routing and Detailed Routing . . . . . . . . . . 45 3.5 Chip-to-Board Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.5.1 Capacity Model of the Octagonal Tile . . . . . . . . . . . . . . . . 46 3.5.2 Group-by-Group MCMF-Based Routing . . . . . . . . . . . . . . . 49 3.6 LP-based Layout Optimization . . . . . . . . . . . . . . . . . . . . . . . . 52 3.6.1 Optimization Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.6.2 Layout Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.6.3 Constraint Generation . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.6.4 LP Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 61 3.6.5 Iterative Constraint Generation and LP Solving . . . . . . . . . . . 62 Chapter 4. Experimental Results 63 4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2 Benchmark Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.3 Results and Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Chapter 5. Conclusions and Future Work 74 Bibliography 77 Publication List 82 | |
| dc.language.iso | en | |
| dc.title | 基於貫孔與不規則凸塊之整合扇出型晶圓級封裝繞線系統 | zh_TW |
| dc.title | Via-based Redistribution Layer Routing for InFO Packages with Irregular Pad Structures | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 108-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 江蕙如(Hui-Ru Jiang),方劭云(Shao-Yun Fang),黃婷婷(Ting-Ting Hwang) | |
| dc.subject.keyword | 實體設計,整合扇出型晶圓級封裝,重分佈層繞線,可調整貫孔,不規則凸塊結構, | zh_TW |
| dc.subject.keyword | physical design,integrated fan-out wafer-level chip-scale package,redistribution layer routing,flexible via,irregular pad structure, | en |
| dc.relation.page | 82 | |
| dc.identifier.doi | 10.6342/NTU202000808 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2020-05-18 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-109-1.pdf 目前未授權公開取用 | 3.72 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。