針對晶片、封裝與印刷電路板共同設計之自動錫球配置與定址以及訊號指定與繞線

Automatic Bump Ball Allocation/Placement and Signal Assignment/Routing for Chip-Package-PCB Co-design

王政程(Cheng-Cheng Wang)

指導教授 ： 王廷基

國立清華大學/電機資訊學院/資訊工程學系/碩士(2008年)

https://doi.org/10.6843/NTHU.2008.00634

摘要

The nanometer process technology comes with increasing I/O count and shrinking feature
size. The number of I/O pins of a die often exceeds hundreds, or even thousands. To connect
a large number of I/O pins to a printed circuit board (PCB), a Ball Grid Array (BGA)
package is typically used as a bridge for helping realize such high connections because the
number of bump balls available in the BGA package can be customized.
In this thesis, we study the problem of bump ball allocation/placement and signal assignment/
routing for chip-package-PCB co-design, which aims to allocate and place bump
balls of a BGA package for the die, complete signal assignment for each finger, and perform
BGA and PCB routing. To solve the aforementioned problem, we propose a flexible and
robust algorithm for it. Our algorithm consists of five main stages: (1) bump ball allocation,
(2) BGA routing, (3) BGA placement, (4) PCB routing, and (5) signal assignment. Both
the BGA routing problem and the PCB routing problem are solved based on repeated mincost
max-flow computations. In addition, it is very easy to do signal assignment after PCB
routing, because it can be readily derived from both the BGA and PCB routing results.
Experimental results show that our algorithm achieves 100% routability for each test case.

關鍵字

球閘陣列封裝 ； 印刷電路板 ； 繞線

並列摘要

隨著奈米製程的進步，在一個晶片上的輸入/輸出針腳數量與之增加；此外，
晶片的特徵尺寸亦與之減小。在一個晶片上通常有數百、甚至超過數千個輸入/
輸出針腳。由於在球閘陣列封裝中，錫球的數量可以依照客戶需求進行客製化，
所以現今通常使用球閘陣列封裝來實現數量如此之多的輸入/輸出針腳與印刷電
路板之間的連線。在本篇論文中，我們討論針對晶片、封裝與印刷電路板共同設
計之自動錫球配置與定址以及訊號指定與繞線，在這個問題中，我們的目標為針
對一個晶片，為這個晶片配置一個內含足夠數量錫球的球閘陣列封裝，並且決定
錫球的位置；針對每個指位針腳指定一個不同的訊號；完成指位針腳與錫球間的
連線；以及元件針腳與錫球間的連線。針對上述的問題，我們提出一個彈性且可
靠的演算法。我們的演算法分為五個主要的步驟： (1) 錫球配置，(2) 球閘陣
列封裝的繞線，(3)球閘陣列封裝的定位，(4)印刷電路板的繞線，(5) 指位針腳
上的訊號指定。針對球閘陣列封裝以及印刷電路板，我們提出一個應用重複計算
最小成本、最大流量的演算法來解決繞線問題。此外，訊號的指定依據球閘陣列
封裝以及印刷電路板的繞線結果，可以很容易的完成。依據實驗結果顯示，我們
的演算法可以成功的完成100%的繞線。

並列關鍵字

BGA package ； PCB ； routing

參考文獻

[1] 2008 MOE/CAD Contest of Taiwan. [Online]. Available:

array package,” in Proceeding of Asia and South pacific Design Automaiton Conference,

1999, pp. 133–136.

[4] C.-C. Tsai, C.-M. Wang, and S.-J. Chen, “News: a net-even-wiring system for the

of Integrated Circuits and Systems, vol. 17, no. 2, pp. 182–189, 1998.