研究生: |
吳峻陞 Jun-Sheng Wu |
---|---|
論文名稱: |
基於整數線性規劃之球柵陣列基板繞線器最佳化策略 Optimization Strategies for Integer Linear Programming Based Ball Grid Array Substrate Router |
指導教授: |
劉一宇
Yi-Yu Liu |
口試委員: |
吳坤熹
Quincy Wu 方劭云 Shao-Yun Fang 謝仁偉 Jen-Wei Hsieh 陳勇志 Yung-Chih Chen |
學位類別: |
碩士 Master |
系所名稱: |
電資學院 - 資訊工程系 Department of Computer Science and Information Engineering |
論文出版年: | 2019 |
畢業學年度: | 107 |
語文別: | 英文 |
論文頁數: | 39 |
中文關鍵詞: | 整數線性規劃 、封裝基板繞線 |
外文關鍵詞: | integer linear programming, package substrate routing |
相關次數: | 點閱:493 下載:1 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
隨著對於系統整合的需求愈來愈多,在如今的半導體產業封裝基板(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/.