重分佈層之避障繞線演算法

淡江大學機構典藏 > 工學院 > 電機工程學系暨研究所 > 學位論文 > Item 987654321/105812

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/105812

题名:	重分佈層之避障繞線演算法
其它题名:	Obstacle-avoiding routing algorithm for redistribution layer
作者:	王偉丞;Wang, Wei-Cheng
贡献者:	淡江大學電機工程學系碩士班饒建奇;Rau, Jiann-Chyi
关键词:	繞線;重分佈層;覆晶技術;避障;routing;RDL;flip-chip;obstacle-avoiding
日期:	2015
上传时间:	2016-01-22 15:05:57 (UTC+8)
摘要:	重分佈層(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.
显示于类别:	[電機工程學系暨研究所] 學位論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	96	检视/开启

在機構典藏中所有的数据项都受到原著作权保护.

TAIR相关文章

数据加载中.....