由於封裝設計規則之複雜，時至今日封裝的自動化繞線器仍未完善，因此基板連接的設計通常由有經驗之工程師手動完成。為了提供可量化的判斷依據並幫助工程師生成早期佈局設計，我們採用了IC設計流程中常用的早期設計分析的概念，以協助工程師進行封裝基板設計佈局的評估。本文提出了一種基於機率分佈的估計方法，包括預估計階段和重新分配階段，以避障並最大程度地減少期望值分佈的總溢出量。此外，我們提出了兩種改進策略，分別是估計引導的生成和占用項的校準，以分別提高執行時間和估計精度。實驗結果顯示我們提出來之架構可以準確並快速估計一基板設計之繞線難度。

The automated router for package substrates is not quite mature owing to complex design rules. Therefore, the designs of package substrates are usually done manually by experienced engineers. In order to produce a quantifiable basis for judgment and to assist engineers in generating the early stage layout design with minimal routing overflow, we adopt the idea of early stage design analysis, commonly used in IC design flow, to assist package substrate design evaluation for layout engineers. In this thesis, we propose an estimation method based on probability distribution. The estimation method consists of pre-estimation stage and redistribution stage to avoid routing obstacles and to minimize the accumulated routing overflow. Furthermore, two refinement strategies, estimation guide generation and occupancy term calibration, are propose to improve the execution time and estimation accuracy, respectively. The experimental results show that our proposed framework can accurately and quickly estimate the difficulty of a design for early package substrate design evaluation.

[1] Steven L. Teig, ”The X Architecture : not your father’s diagonal wiring,”
SLIP’02, April 6-7, 2002, San Diego, California, USA.
[2] Tsung-Yi Ho, Chen-Feng Chang, Yao-Wen Chang, Sao-Jie Chen, ”Multilevel
Full-Chip Routing for the X-Based Architecture,” DAC 2005, June 13–17, 2005,
Anaheim, California, USA.
[3] Yu Hu, Tong Jing, Xianlong Hong, Xiaodong Hu, and Guiying Yan, ”A Routing Paradigm with Novel Resources Estimation and Routability Models for
X-Architecture Based Physical Design,” SAMOS 2005.
[4] Zhen Cao, Tong Jing, Yu Hu, Yiyu Shi, Xianlong Hong, Xiaodong Hu, Guiying
Yan, ”DraXRouter: Global Routing in X-Architecture with Dynamic Resource
Assignment,” Asia and South Pacific Conference on Design Automation, 2006.
[5] Yaoguang Wei, Sheqin Dong, Xianlong Hong, Yuchun Ma, ”An Accurate and
Efficient Probabilistic Congestion Estimation Model in the X Architecture,”
SLIP’07, March 17-18, 2007, Austin, Texas, USA.
[6] Y. Kubo, A. Takahashi, ”A Global Routing Method for 2-Layer Ball Grid Array
Packages,” in Proc. ISPD, pp.36–43, 2005.
[7] Chi-An Pan, “Integer Linear Programming Based Substrate Routing Framework for Fine Pitch Ball Grid Array Package,” M. S. thesis, National Taiwan
University of Science and Technology, Taipei, Taiwan, 2019.
[8] 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.
[9] 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.
[10] Cadence Allegro Package Designer 16.6. https://www.cadence.com/.
[11] Xiaolin Wu ,“An efficient antialiasing technique ,“ ACM SIGGRAPH Computer
Graphics , July 1991.
[12] BRYAN D. AGKLAND, The Edge Flag Algorithm—A Fill Method for Raster
Scan Displays, IEEE TRANSACTIONS ON COMPUTERS, VOL. C-30, NO.
1, JANUARY 1981.
[13] Yen-Jung Chang, Yu-Ting Lee, Ting-Chi Wang, NTHU-Route 2.0: A Fast and
Stable Global Router, 2008 IEEE/ACM International Conference on Computer Aided Design.
[14] Jinan Lou, S. Thakur, S. Krishnamoorthy, H.S. Sheng, Estimating Routing
Congestion Using Probabilistic Analysis, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, Volume: 21, Issue: 1, Jan
2002.
[15] Design Guidelines for Cypress Ball Grid Array (BGA) Packaged Devices,
https://www.cypress.com/.
[16] J. Shibata, M. Horita, N. Izumi, T. Shikano, M. Okada, Y. Noguchi, K. Imamura, H. Fukunaga, M. Yasunaga, T. Hirai, T. Hashimoto, Y. Takemoto, “Development of Fine Pitch Ball Grid Array,” IEEE 2nd 1998 IEMT/IMC Symposium, pp.45-49, 1998.
[17] Jurjen Westra, Chris Bartels , Patrick Groeneveld, “Probabilistic Congestion
Prediction”, ISPD’04, April 18–21, 2004, Phoenix, Arizona, USA.
[18] Wen-Hao Liu, Yih-Lang Li, and Cheng-Kok Koh, “A Fast Maze-Free Routing Congestion Estimator With Hybrid Unilateral Monotonic Routing”,
IEEE/ACM International Conference on Computer-Aided Design (ICCAD)
2012, November 5-8, 2012, San Jose, California, USA.