打線接合是一種傳統封裝技術，晶片和基板之間是透過打線傳輸信號。由於打線接點擺放牽涉大量設計規則，手動設計需要耗費大量時間和精力。本論文專注於自動化擺放打線接點的設計。我們將擺放問題分成三個主要階段。首先，我們利用整數線性規劃決定接點所在的接點列。接著，我們採用混合整數二次規劃來擺放接點，並確保符合打線交叉限制。最後，我們調整接點位，同時考慮接點方向角度和最小間距限制。我們的方法在總線長和繞線完成優於手動設計結果。我們整合的打線接點擺放和基板繞線框架的最終佈局成果可供佈局工程師開始新封裝設計專案的參考設計。

Wire bonding is a traditional packaging technique that enables chip pins to
transmit signals to bonding fingers on the substrate through bonding wires. Due to numerous wire-bonding design constraints, manual substrate design requires much time and engineering effort. In this thesis, we address finger placement design automation. We divide the finger placement into three stages. First, we employ integer linear programming to allocate each net finger row. After that, we utilize mixed-integer quadratic programming to place the bonding fingers and ensure compliance with bonding wire crossing constraints. Finally, we refine the bonding finger locations, taking both the bonding finger orientation angle and the minimum distance constraints into account. The final layouts generated by our integrated finger placement and substrate routing framework outperform manual designs in terms of total wire length and routing completion rate. These layouts can be taken as reference designs for layout engineers to start with new package design projects.

[1] Yao-Wen Chang, “EDA for More-Moore and More-than-Moore Designs: Challenges and Opportunities,” IEEE/ACM International Conference On Computer Aided Design, 2020. Keynote.
[2] Farhang Yazdani, “Foundations of Heterogeneous Integration: An IndustryBased, 2.5D/3D Pathfinding and Co-Design Approach,” Springer, 2018.
[3] Chao-Hung Lu, Hung-Ming Chen, Chien-Nan Jimmy Liu, Wen-Yu Shih, “Package routability- and IR-drop-aware finger/pad assignment in chip-package co-design,” Design, Automation & Test in Europe Conference & Exhibition, pp.845-850, 2009.
[4] Wai-Kei Mak, Yu-Chen Lin, Chris Chu, Ting-Chi Wang, “Pad Assignment
for Die-Stacking System-in-Package Design,” IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, pp.1711-1722, vol.31, i.11, 2012.
[5] Yu-En Lin, Che-Hsu Lin, Yi-Yu Liu, “Wire-bond package finger placement
with minimal distance,” In Proceedings of Workshop on Synthesis And System Integration of Mixed Information Technologies, pp.186-191, 2021.
[6] Peter Spindler, Ulf Schlichtmann, Frank M. Johannes, “Abacus: fast legalization of standard cell circuits with minimal movement,” Proceedings of International Symposium on Physical Design, pp.47-53, 2008.
[7] Jun-Sheng Wu, Chi-An Pan, and Yi-Yu Liu, “ILP-based Substrate Routing
with Mismatched Via Dimension Consideration for Wire-bonding FBGA Package Design,” ACM Transactions on Design Automation of Electronic Systems, pp.1-26, vol.28, i.5, 2023.
[8] Wan-Wei Chen, “Routing Friendly Via Assignment for Fine Pitch Ball Grid
Array Package Design,” M.S. thesis, National Taiwan University of Science
and Technology, Taipei, Taiwan, 2020.
[9] Ming-Yen Chuang, “Clustered-based Multi-pin Fine Pitch Ball Grid Array Substrate Routing Optimization,” M.S. thesis, National Taiwan University of Science and Technology, Taipei, Taiwan, 2021.
[10] Chen-Yu Hsieh, “Optimization Heuristics for Grid-based Integer Linear Programming Package Substrate Router,” M.S. thesis, National Taiwan University of Science and Technology, Taipei, Taiwan, 2021.
[11] Chung-Wei Lin, Po-Wei Lee, Yao-Wen Chang, Chin-Fang Shen, Wei-Chih
Tseng, “An Efficient Pre-assignment Routing Algorithm for Flip-Chip Designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits
and Systems, pp. 878-889, vol.31, i.6, 2012.
[12] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
“Introduction to Algorithms, Third Edition,” The MIT Press, 2009.
[13] Yun-Chih Chang, Yao-Wen Chang, Guang-Ming Wu, Shu-Wei Wu, “B*-Trees: A New Representation for Non-Slicing Floorplans,” Proceedings 37th Design Automation Conference, pp. 458-463, 2000.
[14] Gurobi Optimizer 10.0.1. http://www.gurobi.com/.
[15] Chris Chu, “FLUTE: fast lookup table based wirelength estimation technique,” IEEE/ACM International Conference on Computer Aided Design, pp. 696-701, 2004.
[16] Cairo 2D Graphics Library 1.18.0. https://www.cairographics.org/.
[17] Cadence Allegro Package Designer 17.4. https://www.cadence.com/.