系統識別號 | U0002-1108201511144800 |
---|---|
DOI | 10.6846/TKU.2015.00274 |
論文名稱(中文) | 重分佈層之避障繞線演算法 |
論文名稱(英文) | Obstacle-Avoiding Routing Algorithm for Redistribution Layer |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 電機工程學系碩士班 |
系所名稱(英文) | Department of Electrical and Computer Engineering |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 103 |
學期 | 2 |
出版年 | 104 |
研究生(中文) | 王偉丞 |
研究生(英文) | Wei-Cheng Wang |
學號 | 602450073 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2015-07-13 |
論文頁數 | 33頁 |
口試委員 |
指導教授
-
饒建奇(116686@mail.tku.edu.tw)
委員 - 楊維斌(113157@mail.tku.edu.tw) 委員 - 陳信全(robin@mail.sju.edu.tw) |
關鍵字(中) |
繞線 重分佈層 覆晶技術 避障 |
關鍵字(英) |
routing RDL flip-chip obstacle-avoiding |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
重分佈層(RDL,Redistribution Layer)目前多使用在覆晶技術(Flip-Chip)上,而覆晶技術是一種將IC與基板(substrate)相互連接,基於小尺寸晶片、高I/O密度的封裝(Packging)方法。在封裝的過程中,先將晶片的墊片(pad)長出凸塊(bump),然後將其翻覆過來,以面朝下的方式讓晶片上的墊片透過金屬導體與基板的接合點相互連接的封裝技術。 然而,覆晶技術最初的I/O接點並不具有面陣列(area array)的設計,使得此技術在早期受到不小的阻礙,於是才出現了重分佈層這樣的技術來解決這個問題,重分佈層是在晶圓表面沉積金屬層和介質層並形成相應的金屬佈線,來對晶片的I/O接點進行重新佈局,將其以面陣列形式佈置到較寬鬆的區域。 雖然截至今日,覆晶技術已不算是陌生的新技術了,探討重分佈層繞線演算法的論文數量也不在話下,而本篇論文則是在探討,當重分佈層中的繞線工程遇到了不可抗力的障礙(obstacle)而影響了繞線路徑時,線路該如何規劃以避開障礙。本論文從近期論文裡所討論到的模組下去做改善,並運用更為簡易之演算法省去較為複雜的步驟。 繞線演算法之目的為,讓晶片四個邊緣的I/O接腳(I/O pad)重新分布到平面陣列的凸塊墊片(bump pad)上。 大致的步驟分為:全域繞線與細部繞線兩種,而全域繞線又分成四個步驟:1)區塊分割2)區塊合併3)建立路網圖4)分配線路。其中所談到的「區塊模組」探討的是:當一個矩形區塊的四個周圍有數條線路須經過此區塊時,該如何正確的分配線路的空間與走位。 鑑於「區塊合併」的步驟中限制了區塊每邊不可超過兩個障礙物阻擋,在演算法上更加深了其複雜度,且此步驟雖有益處,但也有其弊端,故省略此步驟以達到更快速的要求;也因此,在「區塊模組」的演算法上收到了簡化之效果,前者演算法需考慮區塊的四個周圍是否有障礙物的包覆,但若省去「區塊合併」的步驟便不用考慮到這樣的問題。 最後的研究成果與前篇相較之下,若是在障礙物較少的狀況下,多數的測試結果都能以稍快的速度與更短的路徑達成繞線問題;而若是在障礙物較多的狀況下,雖繞線路徑相較前篇較不明顯,但在演算的速度上卻能快上非常多。 未來,重分佈層將有可能因三維晶片技術(3D-IC)的突破與發展,而大量仰賴重分佈層的輔助,所以重分佈層在未來還是有可觀的存在價值。 |
英文摘要 |
RDL, redistribution layer, mostly applies on Flip-Chip technology in recent years. Here is the mention of Flip-Chip technology, which connecting both integrated circuit and the substate together, based on small-size chip and high-IO-density packaging. In the package process, first, deposits solder balls on each of the pads. And then, flipped and positioned, so that the solder balls will facing the connectors on the external circuitry. However, in the early, Flip-Chip's I/O ports doesn't have plane array designing. So it receives a big difficulty when developing. To solve this problem, the designing of redistribution layer is came out. Redistribution layer is a re-routing layer between deposited metal layer and medium layer. It redistributes I/O port into plane array at wider area. Though, Flip-Chip technology is getting more mature nowadays, the amount of related papers are also getting much more. And this paper is focused on when the obstacles exist in the redistribution layer and affect the routing process, how we plan the new routing against it. There has a previous work "Obstacle-Avoiding Free-Assignment Routing for Flip-Chip Designs." Then we refer their model and improve it with simpler method to reduce its complexity. The purpose of the routing algorithm is to redistribute the route from the I/O pads which aroundding the origin chip to the bump pads which scattering in the plan area. The method of previous work is divided into two parts: Global Routing and Detail Routing. Then, Global Routing is divided into four steps: 1) tile partition, 2) tile merging, 3) flow-network, and 4) minimum-cost-flow solving. Step one, the routing plane is partitioned into a number of local regions called "tiles". Step two, merge some tiles based on a dynamic programming algorithm to improve solution quality and reduce the problem size. Step three, connect all models together, producing a global flow network. Step four, apply the minimum-cost maximum-flow algorithm to the network. Finally, transform the network-flow result into global routing topology. Then, based on the routing topology, detailed routing determines the specific wiring locations and completes the routing procedure. Comparing to the previous work, our method omitted the second part. Because this step restrict that the edge of each tile can only have one opening at most, which means that the edge cannot have more than two obstacle aside. In consequence, this step cannot guaranteed that the result will be better. So, if we omit this step, not also reduce the complexity of algorithm, but also avoid the case that even worse. |
第三語言摘要 | |
論文目次 |
Chapter 1 緒論...............................................1 1.1 研究背景與動機........................................1 1.2 論文總覽..............................................4 Chapter 2 基本概念與理論.....................................5 2.1 全域規劃與細部規劃....................................5 2.1.1 全域規劃..........................................6 2.1.2 細部規劃..........................................6 2.2 設計規則與限制........................................7 2.3 A* 搜尋演算法.........................................7 2.4 最小成本流問題........................................9 Chapter 3 前者方法論........................................10 3.1 完整繞線流程.........................................10 3.1.1 區塊劃分.........................................10 3.1.2 區塊合併.........................................11 3.1.3 流通路網結構.....................................12 3.1.4 最小成本問題應用.................................12 3.1.5 細部規劃.........................................13 3.2 障礙感知流通路網模組.................................14 3.3 現有預分配繞線方法...................................18 Chapter 4 提出的新方法......................................20 4.1 問題描述.............................................20 4.2 方法分析與改進.......................................20 4.3 提出的新模組.........................................23 4.4 程式碼規劃流程圖.....................................25 4.4.1 區塊劃分.........................................25 4.4.2 建立流通路網結構.................................26 4.4.3 細部規劃.........................................27 Chapter 5 實驗結果..........................................28 Chapter 6 總結..............................................31 參考文獻....................................................32 圖 1.1 覆晶技術架構圖........................................1 圖 1.2 覆晶技術封裝流程......................................2 圖 2.1 全域規劃與細部規劃....................................5 圖 2.2 最小成本流問題示例....................................9 圖 3.1 區塊劃分.............................................10 圖 3.2 最佳化缺失...........................................11 圖 3.3 區塊中心點與中間點...................................13 圖 3.4 交叉點與軌道.........................................13 圖 3.5 含有六個變數的r-vector...............................14 圖 3.6 OA-model與九個容量變數...............................16 圖 3.7 現有預分配繞線方法流程...............................19 圖 4.1 優化後的區塊劃分.....................................21 圖 4.2 五種區塊類型.........................................22 圖 4.3 全邊通行的三種佈線狀況...............................23 圖 4.4 簡化後的新模組.......................................24 圖 4.5 區塊劃分流程圖.......................................25 圖 4.6 流通路網結構的建立流程圖.............................26 圖 4.7 細部規劃流程圖.......................................27 圖 5.1 結果比較折線圖.......................................29 圖 5.2 佈線結果圖...........................................30 表 5.1 結果比較表格.........................................28 |
參考文獻 |
[1] 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 Trans. Comput. Aided Design Integr. Circuits Syst., vol. 26, no. 8, pp. 1417–1429, Aug. 2007. [2] Y. K. Ho, H. C. Lee, P. W. Lee, Y. W. Chang, C. F. Chang, I J. Lin, C. F. Shen, "Obstacle-Avoiding Free-Assignment Routing for Flip-Chip Designs," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , vol.33, no.2, pp.224,236, Feb. 2014. [3] J. T. Yan, Z. W. Chen, "Pre-Assignment RDL Routing via Extraction of Maximal Net Sequence" Computer Design (ICCD), 2011 IEEE 29th International Conference on , vol., no., pp.65,70, 9-12 Oct. 2011. [4] J. T. Yan, Z. W. Chen, "IO connection assignment and RDL routing for flip-chip designs," Asia and South Pacific Design Automation Conference, pp.588-593, 2009. [5] J. T. Yan and Z. W. Chen, "RDL pre-assignment routing for flip-chip designs," ACM Great Lakes Symposium on VLSI, pp.401-404, 2009. [6] J. W. Fang, I J. Lin, P. H. Yuh, Y. W. Chang, J. H. Wang, "A routing algorithm for flip-chip design," Computer-Aided Design, 2005. ICCAD-2005. IEEE/ACM International Conference on , vol., no., pp.753,758, 6-10 Nov. 2005. [7] X. D. Liu, Y. F. Zhang, G.K. Yeap, C. L. Chu, J. Sun, X. Zeng, "Global routing and track assignment for flip-chip designs," Design Automation Conference (DAC), 2010 47th ACM/IEEE , vol., no., pp.90,93, 13-18 June 2010. [8] T. Yan; Wong, M.D.F., "A correct network flow model for escape routing," Design Automation Conference, 2009. DAC '09. 46th ACM/IEEE , vol., no., pp.332,335, 26-31 July 2009. [9] A. Levitin, Introduction to The Design and Analysis of Algorithms, 2nd ed. Pearson, 2009. [10] L. T. Wang, Y. W. Chang, K. T. Cheng, Electronic Design Automation: Synthesis, Verification, and Test (Systems on Silicon), 1st ed. Morgan Kaufmann, 2009, ch.9~11. [11] 鄭榮淇. 1999, June 10. IC載板產業展望 [Online]. Available: http://money.hinet.net/z/zd/zdc/zdcz/zdcz_C87A5222-EA76-4F94-9ADE-F500B3297AA9.djhtm |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信