隨著科技不斷進步，覆晶封裝技術中的訊號數量持續在增加，因此多層結構的覆晶載板也成為連接晶片與印刷電路板的主要介面。本篇論文處理多層結構中連線關係被預先分配的繞線問題，進而提出一個同時考慮多種單源訊號線以及差動對訊號線的多層結構基底層繞線器。本篇論文透過將繞線層分配問題轉換成最長共同子序列問題，進而提出了一個有效率的繞線層分配演算法，實驗結果也表示此方法較基於整數線性規劃的繞線層分配方式來得更有效率，也使用到較少的繞線層數。接著我們將最小化二次位移量的方法應用於基底層繞線演算法，並且考慮到多種線寬及可變的線間距，計算出每條連線的最佳路徑。在兩階段的演算法之後，本篇論文使用了很短的時間最小化總線長以及儘可能使用較少的繞線層數。

As the technology advances, the number of signal in a flip-chip package keeps increasing and multilayer package substrate become the main interface between the chip and printed circuit board (PCB). In this thesis, we consider the pre-assignment routing problem whose connections are predefined by designers in a multilayer structure. We proposed a multilayer substrate router for the pre-assignment routing problem considering multiple wires of single-end signals and differential pair signals. We proposed a very efficient layer assignment algorithm by solving the longest common subsequence problem for a pre-assignment flip-chip package. Experimental results show our algorithm is more efficient and using less routing layers compared with the layer assignment method based on integer linear programming. Then our routing algorithm applies a minimize quadratic movement method to calculate the optimal path for each net considering variable wire widths and variable spacing between different nets. Our multilayer substrate router use routing layers as less as possible and minimize wirelength in each routing layer in a very short time.

[1]. B.-Q. Lin, T.-C. Lin, and Y.-W. Chang, “Redistribution Layer Routing for Integrated Fan-Out Wafer-Level Chip-Scale Packages,” In Proc. of ICCAD., no. 23, pp. 1-8, 2016.
[2]. H.-C. Lee, Y.-W. Chang, and P.-W. Lee, “Recent research development in flip-chip routing,” In Proc. of ICCAD., pp. 404–410, Nov. 2010.
[3]. J.-W. Fang, C.-H. Hsu, and Y.-W. Chang, “An integer linear programming based routing algorithm for flip-chip designs,” IEEE TCAD, vol. 28, no. 1, pp. 98–110, Jan. 2009.
[4]. P. Spindler, U. Schlichtmann, and F.M. Johannes, “Abacus: Fast Legalization of Standard Cell Circuits with Minimal Movement,” In Proc. of ISPD, pp. 47-53, 2008.
[5]. P.-W. Lee, C.-W. Lin and Y.-W. Chang, “An efficient pre-assignment routing algorithm for flip-chip designs,” IEEE TCAD, vol. 31, no. 6, pp. 878–889, May. 2012.
[6]. T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 2nd edition, The MIT Press, 2001.
[7]. Y. Kubo, and A. Takahashi, “A Via Assignment and Global Routing Method for 2-Layer Ball Grid Array Packages,” IEICE Trans. Fundamentals, vol. E88-A, no. 5, pp. 1283-1289, 2005.
[8]. Y. Kubo and A. Takahashi, “Global routing by iterative improvements for 2-layer ball grid array packages,” IEEE TCAD., vol.25, no.4, pp.725–733, Apr. 2006.
[9]. Y. Tomioka and A. Takahashi, “Routability Driven Via Assignment Method for 2-Layer Ball Grid Array Packages,” IEICE Trans. Fundamentals, vol. E92-A, no. 6, pp. 1433-1441, 2009.