隨著對於系統整合的需求愈來愈多，在如今的半導體產業封裝基板(substrate)已經成為其中一個最重要的載具。細間距球狀陣列(fine ball pitch grid array)封裝是廣泛被應用的技術，由於它的成本相較於其他高階封裝技術低。在細間距球狀陣列繞線中，因為機械製程的關係，有鑽孔(via)大小與導線寬度不匹配的問題。在資源緊縮的基板設計中，這種鑽孔與導線寬度不匹配的問題會增加設計的複雜度，由於不同的設計需求與鑽孔與導線大小不匹配的問題，大部分的基板繞線仍然是由有經驗的工程師客製化而成。然而手動基板繞線是相當耗時且容易出錯的工作。在此篇論文中，我們提出一個三階段的架構對於基於整數線性規劃的球柵陣列基板繞線器，我們提出的框架包含鑽孔預測階段、全域最佳化階段、拔掉重繞階段。在6個工業界封裝設計的實驗結果顯示，我們提出的框架可以得到幾乎一樣的繞線品質而且平均加速295倍。

As the rapidly growing demand for system-level integration, package substrates has become one of the most important carriers in semiconductor industry.
Fine pitch ball grid array (FBGA) packaging is a widely used technology thanks to its relative cost-effectiveness compared to other advanced packaging technologies. In the FBGA substrate routing, there is a mismatched via dimension problem owing to the mechanical processes. Such mismatched issue increases the design complexity in a tightly resource-constrained substrate design. Due to various design requirements and the mismatched via dimension in FBGA substrate designs, most substrate interconnects are still customized by experienced layout engineers. However, manual substrate routing is a time consuming and error-prone task. In this thesis, we present a three-stage framework for an integer linear programming (ILP) based substrate router. The proposed framework includes the via prediction stage, the global optimization stage, and the rip-up and reroute stage. Experimental results reveal that the proposed framework achieves almost the same routing quality with average 295X speedup on 6 industrial designs.

[1] Recommended Design Rules and Strategies for BGA Devices, https://www.xilinx.com/.
[2] T. Yan and M. D. F. Wong, "Recent research development in PCB layout", In
Proceeding of International Conference on Computer-Aided Design, pp.398-403,
2010.
[3] R. J. Lee, H. W. Hsu, and H. M. Chen, "Board- and chip-aware package wire
planning", IEEE Transaction on Very Large Scale Integration, pp.1377-1387,
vol.21, i.8, 2013.
[4] "A Network-Flow-Based RDL Routing Algorithmz for Flip-Chip Design", IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems,
pp.1417-1429, vol.26, i.8, 2007.
[5] "Layer Minimization of Escape Routing in Area Array Packaging", In Proceed-
ing of International Conference on Computer-Aided Design, pp.815-819, 2006.
[6] "Single-Layer Fanout Routing and Rout ability Analysis for Ball Grid", In
Proceeding of International Conference on Computer-Aided Design, pp.581-586,
1995.
[7] Y. Kubo and A. Takahashi, "Global routing by iterative improvements for two-
layer ball grid array packages", IEEE Transactions on Computer-Aided Design
of Integrated Circuits and Systems, pp.725-733, vol.25, i.4, 2006
[8] J. W. Fang, C. H. Hsu and Y. W. Chang, "An integer linear programming based
routing algorithm for flip-chip design", IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems, pp.98-110, vol.28, i.1, 2009.
[9] Chi-An Pan, "Integer Linear Programming Based Substrate Routing Frame-
work for Fine Pitch Ball Grid Array Package", M. S. thesis, National Taiwan
University of Science and Technology, Taipei, Taiwan, 2019.
[10] Gurobi Optimizer 8.1, http://www.gurobi.com/.
[11] LEDA 6.5, http://www.algorithmic-solutions.com.
[12] Cadence Allegro Package Designer 16.6, https://www.cadence.com/.