在現代積體電路設計中，隨著製程技術的進步，同一塊晶片中可以容納的元件數目愈來愈多，種類愈趨多樣化，晶片的面積也愈來愈小。在效能的部份，整體線長對效能的影響很大，較短的線長可以給系統帶來較佳的延遲時間，同時功率的消耗也會比較小。綜合以上的優點，三維積體電路(3D IC)的架構被提出來，對於同樣效能的製程而言，三維積體電路具有較低的技術成本，是目前很熱門的技術。 在這個研究中，運用了整數線性規畫(Integer Linear Programming)的方法，使用兩個階段的微凸塊(micro bump)訊號配置(signal assignment)，以及不規則陣列的重新分配層(redistributed layer, RDL)繞線，針對分布於三維積體電路內，做層與層之間接點的繞線。首先，在繞線框內已被預先定義的陣列中，選擇不會造成繞線交越(crossing)的微凸塊，接下來電路繞線就被分為上下兩層，分別為上重新分配層(upper RDL)及下重新分配層(lower RDL)。以最短線長和沒有交越的情況為目標，分別對這兩層需要被連接的點做繞線，求出最理想的全域繞線(global routing)解。實驗結果顯示，在合理的執行時間內，我們的方法可以達到100%的可繞線度，同時也能得到理想的總線長。 The three dimensional integrated circuit (3D IC) is an emerging technology. It has a great potential on alleviating the long interconnect problems and integrating heterogeneous components for System-on-Chip (SoC) or System-in-Package (SiP) by stacking multiple active layers together. The primary emphasis on 3D-IC routing is the interface issues across dies. To handle the interface issue of connections, the inter-die routing, which uses micro bumps and two RDLs (Re-Distribution Layers) to achieve the connection between adjacent dies, is adopted. In this thesis, we present an inter-die routing algorithm for 3D ICs with a pre-defined netlist. Our algorithm is based on integer linear programming (ILP) and adopts a two-stage technique of micro-bump assignment followed by irregular RDL routing. First, the micro-bump assignment selects suitable micro-bumps for the pre-defined netlist such that no crossing problem exists inside the bounding boxes of each net. After the micro-bump assignment, the netlist is divided into two sub-netlists, one is for the upper RDL and the other is for the lower RDL. Second, the irregular RDL routing determines minimum and non-crossing global paths for sub-netlists of the upper and lower RDLs individually. Experimental results show that our approach can obtain optimal wirelength and achieve 100% routability under reasonable CPU times.
