臺灣博碩士論文加值系統

由於近代積體電路的製造技術有快速的進步，而且設計的複雜度增加得非常快，導致在晶片上的黏著墊(Bond pad)數量大幅增加。為了讓焊錫球點網狀陣列(Ball Grid Array)上數量眾多的連接到晶片(IC)的邊界，在逃脫繞線上使用多層板是必要的趨勢。由於印刷電路板上的繞線層數對於成本與產出會有很大的影響，發展高速且有效的方法以減低繞線層數變得非常重要。然而，大多數工業設計仍是由工程師手動繞線，這導致完成設計所需花費的時間會花得很長，而且往往需要花費更多的繞線層數。 因此，我們提出了一個針對極大規模的焊錫球點網狀陣列的多層繞線方法。
由於BGA球點(Balls)的繞線序列會影響到需要的繞線層數，我們提出了十字切割法以增加每一個繞線層可以逃脫繞線的球點數量。此外，我們提出了一個高效的多方向搜尋方法對每一個球點尋找逃脫路徑，同時在繞線可以避免產生銳角。實驗結果顯示我們提出的多方向搜尋方法是非常快速且在繞線不會產生銳角。藉由提出的多方向搜尋方法以及十字切割法，我們的方法可以在相同的層數下，比最先進的方法還要迅速。

The complexity of modern IC design is increasing in a dramatic speed, which makes the number of pads in a chip grow exponentially. To enable a large amount of pads to connect to the boundaries of the pad matrix, the trend of using multiple layers to complete escape routing becomes necessary. Since cost and yields of a PCB are greatly impacted by layer number, developing an efficient and effective methodology to minimize routing layers becomes very important. However, most of designs in industry are still routed manually. It not only increases time-to-market but also consumes more routing layers. Therefore, we propose a new methodology to complete multi-layer escape routing for a large scale pad matrix. Since routing sequence of pads has a lot to do with required layer number, a novel cross patten is proposed to divide a pad matrix such that boundary channels in each layer can be increased. Besides, we propose an efficient and effective multi-direction search method to route each pad, which can avoid generating angle wires. The experimental results show that EDSM algorithm can be faster and no acute angle wires. With EDSM algorithm and cross pad division pattern, our routing methodology can achieve the same routing layers compared to Wang et. al. [18] in a very fast runtime. A 80 * 80 pad matrix can be routed by our algorithm in 4.84 sec.

摘 要 i
ABSTRACT ii
誌 謝 iv
List of Tables vii
List of Figures viii
Chapter 1. Introduction 1
1.1 Motivation 1
1.2 Package Technique 3
1.2.1 Dual Inline Package (DIP) 4
1.2.2 Quad Flat Package (QFP) 4
1.2.3 Ball Grid Array (BGA) 5
1.3 Related Work 7
1.3.1 Ring Based Escape Routing 7
1.3.2 Net-work Based Escape Routing 9
1.4 Our Contribution 10
1.5 Thesis Organization 12
Chapter 2. Problem Formulation 14
2.1 Via Type 14
2.2 Trace Bends 15
2.3 Problem Formulation 16
2.4 Construction of a Routing Map 18
Chapter 3. Eight Direction Search Method (EDSM) 21
3.1 Preview of Lee’s Algorithm 21
3.2 Eight Direction Search Method (EDSM) 23
3.3 Time Complexity 26
3.4 The Sacrifice of Optimization 27
Chapter 4. Multi-layer Escape Routing Algorithm 29
4.1 Related Work 29
4.2 Estimation of a Pad Matrix Routed in Top Layer 32
4.3 Assignment of Pads Routed in Bottom Layer 34
4.4 The Remaining Routing Source 37
4.5 Assignment of Pads Routed in Internal Layers 38
4.6 Full Chip Routing Method 41
Chapter 5. Experimental Results 44
Chapter 6. Conclusions and Future Work 51
6.1 Conclusion 51
6.2 Future Work 51
Bibliography 53

[1]S.S. Chen, J.J. Chen, C.C Tsai, S.J. Chen, “An even wiring approach to the ball grid array package routing, in Proc. of ICCD, pp. 303-303, 1999.
[2]W.T. Chan, F.Y.L. Chin, H.F. Ting, “Escaping a grid by edge-disjoint paths, in Proc. of ACMSIAM, pp. 726-734, 2000.
[3]C.F. Coombs, Jr., Printed Circuits Handbook, 6th ed. McGraw-Hill, pp. 3.10-3.11,2007.
[4]J.W. Fang, I.J. Lin, Y.W. Chang, and J.H. Wang, “A network-flow based RDL routing algorithm for flip-chip design, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 26, no. 8, pp. 1417-1429, 2007.
[5]J.W. Fang, M.D.F. Wong, Y.W. Chang, “Flip-chip routing with unified area-I/O pad assignments for package-board co-design, in Proc. of DAC, pp. 336-339, 2008
[6]N.M. Gasparini, “A method of designing a group of bumps for C4 packages to maximize the number of bumps and minimize the number of package layers, in Proc.of ECTC, pp. 695-696, 1994.
[7]M. Horiuchi, E. Yoda, Y. Takeuchi, “Escape routing design to reduce the number of layers in area array packaging, IEEE Trans. On Advanced Packaging, vol.23, no.4, pp. 686-691, Nov. 2000.
[8]Y.K Ho, H.C Lee, Y.W Chang, “Escape routing for staggered-pin-array PCBs, in Proc. of ICCAD, pp. 306-309, 2011.
[9]L. Luo, T. Yan, Q. Ma, M.D.F. Wong, T. Shibuya, “B-escape: a simultaneous escape routing algorithm based on boundary routing, in Proc. of ISPD, pp. 19-25,2010.
[10]H. Kong, T. Yan, M.D.F. Wong, “Optimal simultaneous pin assignment and escape routing for dense PCBs, in Proc. of ASPDAC, pp. 275-280, 2010.
[11]Q. Ma, T. Yan, M.D.F. Wong, “A Negotiated Congestion based router for simutaneous Escape Routing, in Proc. of ISQED, pp. 606-610, 2010.
[12]Charles Pfeil, BGA Breakouts and Routing: Effective Design Methods for Very Large BGAs, 2nd ed. Mentor Graphics, pp. 6-7, 84-85, 2010.
[13]S. B. Sathe, V. V. Calmidi, and R. J. Stutzman, “Parameters affecting package thermal performance—A low end system level example, Electronics Cooling, vol. 7, no. 2, 2001. [Online]. Available: http://electronics-cooling.com/html/2001_may_a3.html.
[14]R. Shi, C.K Cheng, “Efficient escape routing for hexagonal array of high density I/Os, in Proc. of DAC, pp. 1003-1008,2006.
[15]R. Shi, H. Chen, C.K. Cheng, D. Beckman, D. Huang, “Layer count reduction for area array escape routing, Int. Conf. ＆ Exhibition on Device Packaging, Scottsdale, 2005
[16]E. Winkler, “Escape routing from chip scale packages, in Proc.of IEMT, pp. 393-401, 1996.
[17]J. Wilson, B. Guenin, “Cooling Solution in The Past Decade, Electonics Cooling, vol. 11, no. 4, pp. 6-20, 2006.
[18]R. Wang, R. Shi, C.K. Cheng, “Layer minimization of escape routing in area array packaging, in Proc. of ICCAD, pp. 815-819, 2006.
[19]L.T. Wang, Y.W. Chang, K.T. Cheng, Electronic Design Automation: Synthesis, Verification, and Test (Systems on Silicon), 1st ed. Morgan Kaufmann, pp. 692-697, 2009.
[20]M. F. Yu, W. M. Dai, “Pin assignment and routing on a single-layer pin grid array, in Proc. of ASPDAC, pp. 203-208, 1995.
[21]M. F. Yu, W. M. Dai, “Single-layer fanout routing and routability analysis for ball grid arrays, in Proc. of ICCAD, pp. 581-586, 1995.
[22]T. Yan, M.D.F. Wong, “A correct network flow model for escape routing, in Proc. of DAC, pp. 332-335, 2009.T. Yan, M.D.F. Wong, “Recent Research Development in PCB Layout, in Proc. of ICCAD, pp. 398-403, 2011.