封裝基板是作為積體電路與印刷電路板之間訊號傳輸的重要載具。在基板的設計中，基板繞線的品質對於訊號傳輸效率以及傳遞結果的正確性具有關鍵的影響。然而現有的自動化基板繞線器大多針對二針腳連線的部分進行處理，對於多針腳金屬線仍須倚賴工程師手動完成，此舉不僅效率低落且容易出錯，嚴重更是影響產品上市的時間。因此本篇論文提出一個三階段的架構得以實現多針腳連線的封裝基板繞線器，同時將基板接點與錫球之間、基板接點之間以及錫球之間的連線納入考慮。基於六個實際工業設計的實驗結果顯示我們提出的架構可以完成多針腳金屬線的繞線並得到更好的繞線品質。

Package substrate is an important carrier for integrated circuit (IC) and printed circuit board (PCB).The quality of substrate routing is a critical factor for the efficiency and the accuracy of signal connection in the substrate.
However, many substrate routing research works only focus on two-pin nets, substrate engineers still need to manually complete the routing for multi-pin nets.
Manual routing is inefficient, time-consuming, and error-prone, especially for the large number of pins in net.
In this thesis, we proposed a three-stage framework for multi-pin net routing on fine pitch ball grid array package, including pin grouping, minimum spanning tree topology generation and group topology connection.
Our framework accomplishes not only the connection from finger to bump ball but also the connection between neighboring bump balls and neighboring bonding fingers.
Experimental results of six real industrial designs demonstrate that our framework can complete multi-pin net routing under better routing result.

[1] Santosh Nimbal, IC Packaging, https://fdocuments.in/reader/full/ic-packaging.
[2] IC packaging and testing, https://www.macsayssd.com/ic-packaging-and-
testing.
[3] BGA, PGA and LGA - What is behind the di_erent grid arrays,
https://www.spo-comm.de/en/blog/know-how/bga-pga-and-lga-what-is-behind-
the-di_erent-grid-arrays.
[4] FBGA - Fine-Pitch ball Grid Array, https://eesemi.com/fbga.htm.
[5] Kubo, Yukiko and Takahashi, Atsushi, \A Global Routing Method for 2-Layer
Ball Grid Array Packages", Proceedings of the 2005 International Symposium
on Physical Design, pp.36-43, 2005.
[6] Kubo, Yukiko and Takahashi, Atsushi, \Global Routing by iterative improve-
ments for two layer ball grid array packages", IEEE Transactions on computer-
aided design of integrated circuits and system, vol. 25, no. 4, pp. 725-733, April
2006.
[7] Yoichi Tomioka and Atsushi Takahashi, \Routability driven modi_cation
method of monotonic via assignment for 2-layer Ball Grid Array packages",
2008 Asia and South Paci_c Design Automation Conference pp. 238-243, 2008.
[8] Chen Shuenn-Shi, Chen Jong-Jang, Lee Trong-Yen, T. Chia-Chun, and Chen
Sao-Jie, \A New Approach to the Ball Grid Array Package Routing", IEICE
Transactions on Fundamentals of Electronics, Communications and Computer
Sciences vol. 82, pp.2599-2608, 1999.
[9] Fengxian Jiao and Sheqin Dong, \Ordered Escape routing for grid pin array
based on Min-cost Multi-commodity Flow", 2016 21st Asia and South Paci_c
Design Automation Conference, pp.384-389, 2016.
[10] Han, Kwangsoo and Kahng, Andrew B. and Lee, Hyein, \Evaluation of BEOL
design rule impacts using an optimal ILP-based detailed router", 2015 52nd
ACM/EDAC/IEEE Design Automation Conference pp.1-6, 2015.
[11] Jia-Wei Fang, I-Jye Lin, Ping-Hung Yuh, Yao-Wen Chang and Jyh-Herng
Wang, \A routing algorithm for ip-chip design", ICCAD-2005. IEEE/ACM
International Conference on Computer-Aided Design, 2005 pp. 753-758. 2005.
[12] Jia, Xiaotao and Cai, Yici and Zhou, Qiang and Yu, Bei, \A Multicommodity
Flow-Based Detailed Router With E_cient Acceleration Techniques", IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems,
vol. 37, no. 1, pp. 217-230, Jan. 2018.
[13] 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.
[14] Jun-Sheng Wu, \Optimization strategies for integer linear programming based
ball grid array substrate router", M. S. thesis, National Taiwan University of
Science and Technology, Taipei, Taiwan, 2019.
[15] Gurobi Optimizer 8.1, http://www.gurobi.com/.
[16] Joseph O'Rourke, \Computational Geometry in C (2nd ed.)", Cambridge Uni-
versity Press, 1998.
[17] Cadence Allegro Package Designer 16.6, https://www.cadence.com/.