請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38376
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張耀文 | |
dc.contributor.author | Jia-Wei Fang | en |
dc.contributor.author | 方家偉 | zh_TW |
dc.date.accessioned | 2021-06-13T16:31:49Z | - |
dc.date.available | 2005-07-27 | |
dc.date.copyright | 2005-07-27 | |
dc.date.issued | 2005 | |
dc.date.submitted | 2005-07-11 | |
dc.identifier.citation | [1] R. K. Ahuja, A. V. Goldberg, J. B. Orlin, and R. E. Tarjan, Finding minimum-cost
flows by double scaling, Math. Program., vol. 53 , pp. 243-266, 1992. [2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, N.J., 1993. [3] D. Chang, T. F. Gonzalez, and O. H. Ibarra, “A flow based approach to the pin redistribution problem for multi-chip modules,” Proc. GVLSI , pp.114-119, 1994. [4] B. cherkasssky, “Efficient Algorithms for the Maximum Flow Problem,” Mathemat- ical Methods for the Solution of Economical Problems, vol. 7 , pp.117-126, 1977. [5] S.-S. Chen, J.-J. Chen, S.-J. Chen, and C.-C. Tsai, “An Automatic Router for the Pin Grid Array Package,” Proc. ASP-DAC, pp.133-136, 1999. [6] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms. Cam- bridge, MA: MIT Press, 2000. [7] M.-F. Yu and W.-M. Dai, “Pin Assignment and Routing on a Single-Layer Pin Grid Array,” Proc. ASPDAC, pp.203-208, 1995. [8] C.-P. Hsu , “General River Routing Algorithm,” Proc. DAC, pp.578-583, 1983. [9] J. Hu and S. S. Sapatnekar, “A Timing-constrained Algorithm for Simultaneous Global Routing of Multiple Nets,” Proc. ICCAD, pp.99-103, 2000. [10] Kennington, Helgason, Algorithms for Network Programming, John Wiley & Sons, 1980. [11] Y. Kubo and A. Takahashi, “A Global Routing Method for 2-Layer Ball Grid Array Packages,” Proc. ISPD, pp.36-43, 2005. [12] E. S. Kuh, T. K. Kashiwabara, and T. Fujisawa, “On optimum single row routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 26 , pp. 361-368, 1979. [13] A. Titus, B. Jaiswal, T. J. Dishongh, and A. N. Cartwright, “Innovative Circuit Board Level Routing Designs for BGA Packages,” IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, vol. 27 , pp. 630-639, 2004. [14] C.-C. Tsai, C.-M. Wang, and S.-J. Chen, “NEWS: A Net-Even-Wiring System for the Routing on a Multilayer PGA Package,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17 , pp.182-189, 1998. [15] S.-S. Chen, J.-J. Chen, C.-C. Tsai, and S.-J. Chen, “An Even Wiring Approach to the Ball Grid Array Package Routing,” Proc. ICCD, pp.303-306, 1999. [16] UMC, “0.13μm Flip Chip Layout Guideline,” pp.6, 2004. [17] D. Wang, P. Zhang, C.-K. Chang, and A. Sen, “A Performance-Driven I/O Pin Routing Algorithm,” Proc. ASP-DAC, pp.129-132, 1999. [18] X. Xiang, X. Tang, and D.-F. Wang, “Min-Cost Flow-Based Algorithm for Simulta- neous Pin Assignment and Routing,” IEEE Transactions on Computer-Aided De- sign of Integrated Circuits and Systems, Vol. 22 , pp.870-878, 2003. [19] M.-F. Yu and W.-M. Dai, “Single-Layer Fanout Routing and Routability Analysis for Ball Grid Arrays,” Proc. ICCAD, pp.581-586, 1995. [20] M.-F. Yu, J. Darnauer and W.-M. Dai, “Interchangeable Pin Rouing with Applica- tion to Package Layout,” Proc. ICCAD, pp.668-673, 1996. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38376 | - |
dc.description.abstract | 覆晶式(flip-chip)封裝(package)提供了最高密度的封裝方式,用來支援受
接合點(pad)限制的特殊應用積體電路(ASIC)設計。在此論文中,我們提供了第 一個應用於覆晶式封裝的繞線器(router)。此繞線器能將打線接合點(wirebonding pads)重新分配到凸塊接合點(bump pads)上然後完成每一個接合點的繞 線。先執行全域繞線(global routing)再執行細部繞線(detailed routing)的兩 階段技術是此繞線器的核心概念。在全域繞線中,我們使用了網路流演算法 (network flow algorithm)來解決將打線接合點重新分配到凸塊接合點上的問題 並且產生每一條訊號線的全域繞線路徑。在細部繞線中,我們使用了三個方法來 逐步完成細部繞線。這三個方法分別是越過點分派法(cross point assignment)、繞線順序決定法(net ordering determination)和軌道分派法 (track assignment)。在實驗方面,我們使用了七個來自工業界的測試檔案來證 明我們的繞線器演算法比工業界的繞線器演算法在總線長(total wirelength) 減少了10.2%、關鍵線長(critical wirelenght)減少了13.4%而在訊號歪斜 (signal skew)更是減少了13.9%。 | zh_TW |
dc.description.abstract | The flip-chip package gives the highest chip density of any packaging method
to support the pad-limited Application-Specific Integrated Circuit (ASIC) designs. In this thesis, we propose the first router for the flip-chip package. The router can redistribute nets from wire-bonding pads to bump pads and then route each of them. The router adopts a two-stage technique of global routing followed by detailed routing. In global routing, we use the network flow algorithm to solve the assignment problem from the wire-bonding pads to the bump pads, and then create the global routing path for each net. The detailed routing consists of three stages, cross point assignment, net ordering determination, and track assignment, to complete the routing. Experimental results based on seven real designs from the industry demonstrate that the router can reduce the total wirelength by 10.2%, the critical wirelength by 13.4%, and the signal skews by 13.9%, compared with a heuristic algorithm currently used in industry. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T16:31:49Z (GMT). No. of bitstreams: 1 ntu-94-R92943077-1.pdf: 946341 bytes, checksum: 4ee8668ddd96a35dd7f52445920e8d08 (MD5) Previous issue date: 2005 | en |
dc.description.tableofcontents | Chapter 1. Introduction 1
1.1 Flip-Chip Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Previous Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Pin Grid Arrays and Ball Grid Arrays . . . . . . . . . . . . . . . . 4 1.2.2 Multi-layer Router . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.3 Single-layer Fanout Routing and Routability Analysis . . . . . . . 6 1.2.4 Multi-layer Fanout Routing and Routability Analysis . . . . . . . . 7 1.3 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Chapter 2. Preliminaries 11 2.1 Minimum-cost Maximum-flow Network Algorithm . . . . . . . . . . . . . 11 2.2 General River Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . 13 Chapter 3. Problem Formulation 18 Chapter 4. The RDL Routing Algorithm 22 4.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 Global Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2.1 Basic Network Formulation . . . . . . . . . . . . . . . . . . . . . . 24 4.2.2 Capacity Assignment and Node Construction . . . . . . . . . . . . 27 4.2.3 The Cost of Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.2.4 Multi-pin Net Handling . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3 Detailed Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3.1 Cross Point Assignment . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3.2 Net Ordering Determination . . . . . . . . . . . . . . . . . . . . . 33 4.3.3 Track Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.4 Time Complexity Analysis of RDL Routing Algorithm . . . . . . . . . . . 36 Chapter 5. Experiment Results 39 Chapter 6. Conclusion and Future Work 44 Bibliography 45 | |
dc.language.iso | en | |
dc.title | 覆晶式設計中繞線系統之研發 | zh_TW |
dc.title | An RDL Routing System for Flip-Chip Design | en |
dc.type | Thesis | |
dc.date.schoolyear | 93-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 林永隆,黃世旭,王志恆 | |
dc.subject.keyword | 繞線系統, | zh_TW |
dc.subject.keyword | RDL Routing System, | en |
dc.relation.page | 46 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2005-07-11 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 924.16 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。