[[alternative]]Obstacle-avoiding routing algorithm for redistribution layer

碩士[[abstract]]重分佈層(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)的突破與發展，而大量仰賴重分佈層的輔助，所以重分佈層在未來還是有可觀的存在價值。[[abstract]]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.[[tableofcontents]]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[[note]]學號: 602450073, 學年度: 10