應用於晶片、封裝與印刷電路板共同設計之繞線演算法

Routing Algorithms for Chip-Package-Board Co-Design

方家偉(Jia-Wei Fang)

指導教授 ： 張耀文

國立臺灣大學/電機資訊學院/電子工程學研究所/博士(2009年)

https://doi.org/10.6342/NTU.2009.01365

摘要

隨著超大型積體電路設計的日益複雜化，奈米效應已經使得晶片、封裝與印刷電路板的設計變得更加困難。更甚者，由於先進的電路設計擁有較高的功能性，所需的輸入/輸出訊號也急遽增加。為了改善電路中的繞線完成度、設計完善度與設計收斂度，工業界分別提出了兩種晶片封裝方法:球閘陣列封裝(ball-grid-array packaging)與覆晶式封裝(flip-chip packaging)和晶片、封裝與印刷電路板共同設計的概念。在此博士論文中，我們提出了學術界第一個考慮晶片、封裝與印刷電路板共同設計的繞線演算法。該演算法的研發是建構在上述所提的兩大晶片封裝方法。這個繞線演算法不只可以應用在解決(1)封裝與印刷電路板的繞線問題，還可以考慮(2)晶片與封裝共同設計、(3)封裝與印刷電路板共同設計以及(4)晶片、封裝與印刷電路板共同設計。

在關於封裝與印刷電路板的繞線問題方面，我們的繞線演算法採用了一個二階式技術:全域繞線與隨後的細部繞線。在全域繞線中，由於採用了計算幾何學(三角化和 Voronoi 圖示) 、最小成本和最大流量的網路流演算法(minimum-cost maximum-flow network algorithm)與整數和線性規劃(integer and linear
programming)等方法，我們可以得到最佳的全域繞線結果。此外，在全域繞線網路中，我們也額外考慮了繞線擁擠度的問題，所以在細部繞線階段，我們可以產生一個百分之百可繞的繞線順序進而完成繞線。

在關於晶片與封裝共同設計方面，晶片和封裝之間的輸入/輸出訊號繞線 列表會與封裝佈局同時產生。因此，繞線總長度得以縮減。另外在封裝與印刷電路板共同設計中，我們保留了晶片與印刷電路板的繞線資訊來改善繞線完成度。當考慮晶片、封裝與印刷電路板共同設計時，由於擁有極大的設計彈性，除了封裝與印刷電路板的繞線需求外，我們可以額外考慮輸入/輸出訊號的規劃以及封裝的擺置。基於這些優點，設計的成本可以在早期階段就被刪減。我們也更可以縮短總繞線長與提高繞線完成度。

實驗結果皆是基於工業界的測試檔並且展現出我們的繞線演算法可以達到百分之百的繞線完成度、最佳的全域繞線總長度並且滿足所有的設計需求。即使是跟近年來的相關研究相比，我們的繞線演算法依然可以在合理的運算時間下得到較佳的結果。

關鍵字

計算幾何 ； 覆晶式裝置 ； 流量網路 ； 整數規劃 ； 線性規劃 ； 實體設計 ； 擺置與繞線 ； 繞線與佈局 ； 印刷電路

並列摘要

In VLSI deigns, nanometer effects have complicated the designs of chips as well as packages and printed circuit boards. Further, due to higher functionality in modern circuits, the number of I/O’s is also dramatically increased. In order to improve the routability, performance, and convergence of the design, two advanced packaging technologies: ball-grid-array packaging and flip-chip packaging, and chip-package-board co-design are strongly recommended by industry. In this dissertation, we present the first routing algorithms in the literature for chip-package-board co-design based on the two advanced packages. They can not only be applied to complete (1) the routing in the packages and printed circuit boards, but also can consider (2) chip-package co-design, (3) package-board co-design, and (4) chip-package-board co-design.

For the routing in the packages and printed circuit boards, our routing algorithms adopt a two-stage technique of global routing followed by detailed routing. In the global routing, the computational geometry techniques (e.g., the Delaunay triangulation and the Voronoi diagram), minimum-cost maximum-flow network algorithm, and integer and linear programming are used to find an optimal global-routing wirelength for the addressed problems. Since we consider the wire congestion in our global-routing networks, the detailed routing can generate a 100% routable sequence to complete the routing.

For chip-package co-design, an I/O netlist between a chip and a package can be simultaneously generated with the package layout. Therefore, the total wirelength can be reduced. By considering package-board co-design, the routing information from the chip and the printed circuit board can be kept during the package routing. Consequently, the routability can be improved. In chip-package-board co-design, due to the great design flexibility, we can additionally consider the I/O planning of a package except the package routing. Hence, the design cost can further be reduced in the early stage. Further, we can also get much shorter total wirelength and higher routability.

Experimental results based on real industry designs show that our routing algorithms can achieve 100% routability and the optimal global-routing wirelength and satisfy all design constraints, under reasonable CPU times, whereas recent related work results in much inferior solution quality.

並列關鍵字

Computational Geometry ； Flip-chip Devices ； Flow Networks ； Integer Programming ； Linear Programming ； Physical Design ； Placement and Routing ； Routing and Layout ； Printed Circuits

參考文獻

[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.

[5] C. Chiang, Q. Su, and C.-S. Chiang, “Wirelength reduction by using diagonal wire,” Proc. of ACM Great Lakes Symposium on VLSI , pp. 104–107, Washington, District of Columbia, April 2003.

[10] T. S. Ferguson, Linear Programming: A Concise Introduction, Text, Department of Mathematics, University of California at Los Angeles, United States, 2008.

[11] M. R. Garey and D. S. Johnson, A Guide to the Theory of NP-Completeness, Freeman, 1979.

Conference, pp. 1134–1139, New Orleans, Louisiana, May 2003.