隨著科技不斷進步，覆晶技術中的凸塊數量持續在增加，分布狀況也變得複雜且不規則，有時一個封裝設計中甚至存在一種以上的凸塊陣列形狀。然而，先前的研究主要專注於只含有一種凸塊陣列形狀的封裝設計，並且假設凸塊分布地非常均勻，這些研究的方法並不適用於現今產業界的設計。因此，本篇論文提出了一個基於機率分析模型的多層逃脫繞線演算法，其適用於混和型的凸塊陣列封裝設計。我們會先解析並區分不同形狀的凸塊陣列，然後使用一個基於繞線機率的方法來做每個訊號凸塊的逃脫繞線層分配。演算法也可以找到每層繞線層中每個凸塊陣列所適合的逃脫邊界，逃脫邊界是決定每個凸塊陣列在當層中可逃脫訊號的最大數量以及逃脫繞線方向的關鍵。除此之外，我們也提出了兩個新的網絡流模型來處理差分信號，還調整了一個先前著作的模型，以讓其可適用於新型的凸塊陣列結構。實驗結果顯示我們的演算法能適用並處理現今不斷變化的產業界封裝設計中的逃脫繞線問題。

As the technology advances, the bump number of a flip-chip keeps increasing. The distribution of bumps becomes more complex and irregular, sometimes there even exists more than one shape of bump array in a package. Previous researches focus on single shaped bump array and assume the distribution of bumps is quite uniform, it is not suitable for modern industrial designs. This paper proposes a probability-based multilayer escape routing algorithm for hybrid bump arrays package. We first distinguish different shapes of bump array, then use a routing probability-based method to do the layer assignment for every signal bump. The proposed algorithm will also find the suitable escape boundary for every bump array in each layer, which is the critical part that decide the maximum escape signal number and the routing direction of every bump array. We also proposed two network flow models to handle the differential pair signals and adjusted the model in [4] in order to suit the new shape of bump array. The experimental results show that our approach can handle the ever-changing industrial designs today.

[1]. IBM ILOG CPLEX Optimizer [Online]. Available: http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
[2]. T. Yan and M. D.-F. Wong, “A correct network flow model for escape routing,” In Proc. of DAC., pp. 332–335, July 2009.
[3]. T. Yan and M. D. F. Wong, “Correctly Modeling the Diagonal Capacity in Escape Routing,” IEEE TCAD, vol. 31, no. 2, pp. 285 - 293, Feb. 2012.
[4]. S.-I. Lei and W.-K. Mak, “Optimizing Pin Assignment and Escape Routing for Blind-via-Based PCBs,” IEEE TCAD, vol. 35, no. 2, pp. 246-259, Feb. 2016
[5]. P.-C. Wu and M. D. F. Wong, “Network flow modeling for escape routing on staggered pin arrays,” in Proc. of ASP-DAC, pp. 193-198, Jan. 2013.
[6]. R. Shi and C.-K. Chenq, “Efficient escape routing for hexagonal array of high density I/Os,” in Proc. of DAC, pp. 1003-1008, July 2006.
[7]. T. Yan and M. D.-F. Wong, “Recent research development in PCB layout,” In Proc. of ICCAD, pp. 398–403, Nov. 2010.
[8]. Y.-K. Ho, H.-C. Lee, and Y.-W. Chang, “Escape Routing for Staggered-Pin-Array PCBs,” In Proc. of ICCAD, pp. 306–309, Nov. 2011
[9]. Y.-K. Ho, X.-W. Shih, Y.-W. Chang, and C.-K. Cheng, “Layer minimization in escape routing for staggered-pin-array PCBs,” in Proc. of ASP-DAC, pp. 187-192, Jan. 2013.
[10]. J. Lou, S. Thakur, S. Krishnamoorthy and H. S. Sheng, "Estimating routing congestion using probabilistic analysis," IEEE TCAD, vol.2, no. 1, pp. 32 - 41, Jan. 2002.
[11]. W. Li, J. Kim, and J.-W. Chong, “A novel congestion estimation model and congestion aware floorplan for 3D ICs,” in Proc. of ICIMTR, pp. 199–204, May 2012.
[12]. J.-W. Fang, K.-H. Ho, and Y.-W. Chang, “Routing for chip-package-board co-design considering differential pairs,” In Proc. of ICCAD, pp. 512–517, Nov. 2008.
[13]. 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 TCAD, vol. 26, no. 8, pp. 1417–1429, Aug. 2007.
[14]. X. Liu, Y. Zhang, G. K. Yeap, C. Chu, J. Sun, and X. Zeng, “Global routing and track assignment for flip-chip designs,” In Proc. of DAC, pp. 90–93, June 2010.
[15]. R. Wang, R. Shi, and C.-K. Cheng, “Layer minimization of escape routing in area array packaging,” In Proc. of ICCAD, pp. 815–819, Nov. 2006.
[16]. T. Yan, P. C. Wu, Q. Ma, and M. D. F. Wong, “On the escape routing of differential pairs,” in Proc. of ICCAD, pp. 614–620, Nov. 2010.
[17]. K. Wang, H. Wang, and S. Dong, “Escape routing of mixed-pattern signals based on staggered-pin-array PCBs,” in Proc. of ISPD, pp. 93–100, Mar. 2013.
[18]. J.-W. Fang and Y.-W. Chang, “Area-I/O flip-chip routing for chippackage co-design considering signal skews,” IEEE TCAD, vol. 29, no. 5, pp. 711–721, May 2010.
[19]. M.-F. Yu, J. Darnauer, and W. W.-M. Dai, “Interchangeable pin routing with application to package layout,” in Proc. of ICCAD, pp. 668–673, Nov. 1996.
[20]. M. M. Ozdal and M. D. F. Wong, “Algorithms for simultaneous escape routing and layer assignment of dense PCBs,” IEEE TCAD, vol. 25, no. 8, pp. 1510–1522, Aug. 2006.
[21]. M. M. Ozdal, M. D. F. Wong, and P. S. Honsinger, “Simultaneous escape-routing algorithms for via minimization of high-speed boards,” IEEE TCAD, vol. 27, no. 1, pp. 84–95, Jan. 2008.
[22]. L. Luo and M. D. F. Wong, “Ordered escape routing based on Boolean satisfiability,” in Proc. of ASP-DAC, pp. 244–249, Mar. 2008.