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