隨著人工智慧、5G通訊和電動車等應用蓬勃發展，新一代電子產品的功能越來越強大，這使得電路設計必需整合的元件越來越多元，其中還可能同時包含了類比元件，數位元件與被動元件，這使得系統單晶片(system on chip, SoC)的整合困難度越來越高，除此之外，由於設計和製造成本也會大幅提昇，導致其不符合經濟效益，因此有越來越多的公司轉向系統封裝層級來整合電路。
本研究提出一個系統級封裝(system in package, SiP)的元件擺置規劃器，同時還可以滿足固定框架的限制。為了提升效率，我們方法主體是利用一個數學解析式的擺置模型來找出元件的相對關係。方法主要可分成三大階段。首先是分群階段，將連線關係緊密的元件分為同一群；接著為多階層全域散佈階段，利用數學解析式的模型，將每一階層的群集分散元件在擺置區域內，同時最小化整體的繞線長度；最後合法化階段，為了能夠維持住全域階段的結果，首先根據全域階段元件之間的相對位置建立限制圖，接著利用整數線性規劃，在固定的框架內獲得合法的擺置結果，同時還能滿足元件與元件之間的最小間距限制。我們會利用實際的封裝設計作為測資，實驗結果證明我們的方法可以更有效率的得到擺置結果，同時具有較短的線長。

As the boom in the applications such as artificial intelligence, electric　vehicles, and 5G communication, the next-generation electronic products become more powerful. We have to integrate several components into a single design, which may include analog components, digital components, and even many passive components. This makes the classic integration by the system on chip (SoC) more challenging. Besides, it is not cost-effective due to higher design and manufacturing cost. More and more companies are looking for the opportunity to integrate such components in the system level. Hence, in the first year of this research project, we propose a fixed-outline placer which is able to place many components into a fixed-outline package for a 2.5D IC. To improve efficiency of our program, we adopt the analytical placement model with the multilevel framework to reduce solution space. Our methodology has three stages: grouping stage, global distribution stage, and legalization stage. We first group closely connected components into the same group in the grouping stage. Then, the global distribution stage spreads components over a placement region while minimizing total wirelength under the fixed-outline constraint. In order to maintain the global distribution result, the legalization stage first constructs constraint graphs according to the relative positions of components and form a set of linear constraints. Then, we apply the integer linear programming (ILP) to get a legal placement result which can meet the fixed-outline constraint and the spacing constraints at the same time. We use real package designs as benchmarks to test our program. Experimental results have shown the promising of our methodology.

[1] Y.-K. Ho and Y.-W. Chang, “Multiple chip planning for chip-interposer codesign,” in Proc. DAC, pp.27:1–27:6, July 2013.
[2] D. Seemuth, A. Davoodi and K. Morrow, “Automatic die placement and flexible I/O assignment in 2.5D IC design,” in Proc. ISQED, pp.524–527, Apr. 2015.
[3] W.-H. Liu, M.-S. Chang and T.-C. Wang, “Floorplanning and signal assignment for silicon interposer-based 3D ICs,” in Proc. DAC, pp.5:1–5:6, Aug. 2014.
[4] H. Onodera, Y. Taniguchi and K. Tamaru, “Branch-and-bound placement for building block layout,” in Proc. DAC, pp.433-439, Aug. 1991.
[5] S. Osmolovskyi, J. Knechtel, I.-L. Markov and J. Lienig, “Optimal die placement for interposer-based 3d ICs,” in Proc. ASP-DAC, pp.513–520, Feb. 2018.
[6] M.-K. Hsu and Y.-W. Chang, “Unified analytical global placement for large scale mixed-size circuit designs,” in Proc. ICCAD, pp.657-662, Dec. 2010.
[7] J.-M. Lin and Z.-H. Hung, “UFO: unified convex optimization algorithm for fixed-outline floorplanning considering pre-placed modules,” IEEE Trans. On CAD, vol. 30, no. 7, pp.1034-1044, Jul. 2011.
[8] L. Jin, D. Kim, L. Mu, D.-S. Kim, and S.-M. Hu, “A sweepline algorithm for Euclidean Voronoi diagram of circules,” IEEE Trans. On CAD, vol. 38, no. 3, pp.260-272, Mar. 2006.
[9] K.-C, Chan, J.-M. Lin, C.-J. Hsu, “A flexible fixed-outline floorplanning methodology for mixed-size modules,” in Proc. ASP-DAC, pp.435-440, Jan. 2013.
[10] T.-C. Chen, Y.-W. Chang and S.-C. Lin, “IMF: interconnect-driven multilevel floorplanning for large-scale building-module designs’’ in Proc. ICCAD, pp. 159-164, 2005.
[11] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, “NTU-place3: an analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints,” IEEE Trans. on CAD, vol.27, pp. 1228-1240, Jul. 2008.
[12] J.-M. Lin and Z.-X. Hung, “SKB-Tree: A fixed-outline driven representation for modern floorplanning problems,” in IEEE Trans. on VLSI, Vol. 20, No. 3, pp. 473-484, Mar. 2012.
[13] W. Naylor, R.Donelly, and L. Sha, “Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer,” US patent 6301693, 2001.
[14] M. Kuwano and Y. Takashima, “Stable-LSE based analytical placement with overlap removable length,” in Proc. SASIMI, pp. 115-120, 2010
[15] [Online] Available: https://www.ibm.com/analytics/cplex-optimizer/