隨著現今半導體產品的金屬腳位越來越多，半導體封裝已成為半導體設計中不可或缺的一環。而在封裝設計中，基板扮演著一個重要的角色並為晶片提供連接和散熱功能。由於基板繞線須遵守許多複雜的設計規則，大多基板設計仍須依賴工程師手動完成繞線。然而，手動繞線非常耗時且容易出錯。隨著封裝設計的複雜度提升，基板繞線自動化需求變的至關重要。雖然先前已有基板繞線問題的相關研究，但由於設計規則複雜和繞線資源緊湊，導致業界現今仍沒有可完全自動化的繞線器。本篇論文以先前基於網格的整數線性規劃封裝繞線器，針對網格繞線和拔起且重繞階段提出最佳化策略。實驗結果以六個工業界封裝實體設計的結果顯示，我們提出的最佳化策略可以避免繞線資源浪費並獲得較佳的繞線品質，進一步消除設計規則的違反。

With more and more I/O pins in highly integrated semiconductor products, semiconductor packaging has become an essential part of IC design nowadays.
The substrate plays an important role in semiconductor packaging, and provides the chip with electrical connection and heat dissipation.
Since there are many complex design rules in substrate routing, most substrate designs are manually crafted by experienced engineers.
However, manual substrate layout design is time-consuming and error-prone.
With the increasing complexity of modern package designs, substrate routing design automation has become an imperative demand.
Although several previous works address the substrate routing problem, there is still no fully automated industrial substrate router owing to the complex design rules and relatively limited routing resource.
In this thesis, based on a previously developed ILP package substrate router, we propose several optimization heuristics in grid-based routing graph and in the rip-up and reroute stage.
Experimental results show that our proposed optimization heuristics are capable of avoiding routing resource wastage, achieving better routing quality, and eliminating design-rule violations.

[1] M. F. Yu, W. Wei-Ming Dai, \Single-Layer Fanout Routing and Routability
Analysis for Ball Grid\ In Proceeding of International Conference on Computer-
Aided Design, pp.581-586, 1995.
[2] Y. Kubo and A. Takahashi, \A Global Routing Method for 2-Layer Ball Grid
Array Packages", in Proc. ISPD, pp.36-43, 2005.
[3] 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.
[4] Y. Tomioka and A. Takahashi, \Routability driven via assignment method for 2-
layer ball grid array packages," IEICE Transactions on Fundamentals, pp.1433-
1441, vol.E92-A, i.6, 2009.
[5] Y. Tomioka, Y. Kurata, Y. Kohira, A. Takahashi, \MILP-Based Ecient Rout-
ing Method with Restricted Route Structure for 2-Layer Ball Grid Array Pack-
ages" IEICE Transactions on Fundamentals of Electronics Communications
and Computer Sciences, pp.2998-3006, 2009.
[6] J. W. Fang, C. H. Hsu and Y. W. Chang, \An integer linear programming based
routing algorithm for
ip-chip design" IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems, pp.98-110, vol.28, i.1, 2009.
[7] H. W. Hsu, M. L. Chen, and H. M. Chen, "Routability-driven bump assign-
ment for chip-package co-design" in Proc. of Asia and South Pacic Design
Automation Conference, pp.519-524 2014.
[8] J.R Jiang, Y.C Kuo, Y.H Chen, and H. M. Chen, "On pre-assignment route
prototyping for irregular bumps on BGA packages", Design Automation and
Test in Europe, pp.1311{1314 2020.
[9] T. C. Lin, D. Merrill, Y.Y. Wu, "A Unied Printed Circuit Board Routing
Algorithm With Complicated Constraints and Dierential Pairs", in Proc. of
Asia and South Pacic Design Automation Conference, pp.170-175 2021.
[10] C. A. Pan, \Integer Linear Programming Based Substrate Routing Framework
for Fine Pitch Ball Grid Array Package", M. S. thesis, National Taiwan Uni-
versity of Science and Technology, Taipei, Taiwan, 2019.
[11] J. S. 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.
[12] Cadence Allegro Package Designer 16.6, https://www.cadence.com/.
[13] Gurobi Optimizer 8.1, http://www.gurobi.com/.
[14] Design Guidelines for Cypress Ball Grid Array (BGA) Packaged Devices,
https://www.cypress.com/.
[15] L. T. Wang, Y. W. Chang, K. T. Cheng, "Electronic Design Automation"
Morgan Kaufmann, February, 2009.