平面規劃在實體設計之中是個非常重要的步驟，隨著半導體製程的演進，為了降低晶片面積、提高元件密度、減少電路的總連線長度，晶片開始往三維的方向去做堆疊，三維晶片成為未來發展的趨勢。如果將模組切割後再擺置，可以降低線長與功率消耗，而這些切割後的子區塊會在不同晶片層中對齊，可視為一個立體的堆疊式模組(stacked module)。其中堆疊式記憶體(stacked memory)為現今三维堆疊領域中主要的應用之一，不但能降低其功耗，還能提升存取速度，因此如何在三維平面規劃中去擺置各種堆疊式模組就變得非常重要。
本研究中提出了一個可考慮堆疊式模組的三維平面規劃器，它能滿足固定框架的限制條件。我們採用兩階段式的平面規劃方法，在全域階段使用數學最佳化的分析，將模組均勻的分散在各晶片層並同時最小化線長，接著在合法化階段利用限制圖(constraint graph)結合整數線性規劃(integer linear programming, ILP)的方法，建立模組之間的相對關係並維持住全域階段優良的線長，其中我們還將彈性模組(soft module)的面積限制轉換成線性表示式，使得求解的過程更有效率。由實驗的結果證明，我們的總繞線長度不但優於Co-place，還可以在三維晶片中擺置堆疊式模組，而且執行速度也較使用凸面最佳化(convex optimization)的方法更為快速。

Floorplanning is a crucial stage in the physical design flow. As semiconductor industry advances, the design of integrated circuits (ICs) is moving toward three-dimensional integrated circuits (3D ICs). Compared to traditional 2D ICs, 3D ICs are able to provide higher device density, smaller chip area, shorter wirelength, etc. It is believed that power consumption can be further reduced if some modules are partitioned and are placed in adjacent dies. The sub-blocks partitioned from a module must be placed at the same coordinate in different dies, and they can be regarded as a stacked module. Stacked memory is one of the important applications in the 3D stacking field, which not only can save power but also can increase its access speed. Hence, it is indeed to have a 3D floorplanner to consider stacked modules under the fixed-outline constraint. This thesis proposes a two-stage methodology to handle this problem. In the first stage, we use an analytical approach to spread modules in the fixed-outline region with the consideration of wirelength. In the second stage, we use the integer linear programming (ILP) to determine the exact locations and shapes of modules to remove overlaps. Moreover, the area constraint of a soft module is transformed to a polyline. This speeds up the process of solving the ILP problem. Experimental results show that our approach not only can obtain better wirelength than Co-place without stacked modules but also can place all stacked modules at identical coordinates under the fixed-outline constraint in 3D ICs. Also, our runtime is faster than applying convex optimization.

[1] S. N. Adya and I. L. Markov, “Fixed-outline Floorplanning: Enabling Hierarchical Design,” IEEE Trans. on VLSI Systems, vol 11(6), pp. 1120-1135, Dec. 2003.
[2] 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.
[3] 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.
[4] 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(7), pp. 1228-1240, Jul. 2008
[5] L. Cheng, L. Deng, and M.D.F. Wong, “Floorplanning for 3-D VLSI design,” in Proc. ASP-DAC, pages 405–411, 2005.
[6] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, “B*-Trees: A New Representation for Non-slicing Floorplans,” in Proc. DAC, pp. 458-463, 2000.
[7] J. Cong, J. Wei, and Y. Zhang, “A Thermal-driven Floorplanning Algorithm for 3D ICs,” in Proc. ICCAD, 2004, pp. 306-313.
[8] L. Hagen and A. B. Kahng, “New Spectral Methods for Ratio Cut Partitioning and Clustering,” IEEE Trans. on CAD, vol. 11, no. 9, pp. 1074–1085, Sep. 1992.
[9] O. He, S. Dong, J. Bian, S. Goto, and C.-K. Cheng, “A Novel Fixed-outline Floorplanner with Zero Deadspace for Hierarchical Design,” in Proc. ICCAD, pp. 16-23, 2008.
[10] 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.
[11] M. Jung, T. Song, Y. Wan, Y. Peng, and S.-K. Lim, “On Enhancing Power Benefits in 3D ICs: Block Folding and Bonding Styles Perspective,” in Proc. DAC, pages 1-6, 2014.
[12] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel Hypergraph Partitioning: Applications in VLSI domain,” IEEE Trans. on VLSI Systems, vol. 7, no. 1, pp. 69-79, Mar. 1999.
[13] M. Kuwano and Y. Takashima, “Stable-LSE Based Analytical Placement with Overlap Removable Length”, in Proc. SASIMI, pp. 115-120, 2010.
[14] C.-R. Li, W.-K. Mak, and T.-C. Wang, “Fast Fixed-Outline 3-D IC Floorplanning with TSV Co-Placement,” IEEE Trans. on VLSI systems, vol. 21, no. 3, pp. 523-532, 2013.
[15] J.-M. Lin, and Y.-W. Chang, “TCG: A Transitive Closure Graph-based Representation for Non-slicing Floorplans,” in Proc. DAC, pp.764-769, 2001.
[16] J.-M. Lin, Z.-X. 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.
[17] J.-M. Lin and Z.-X. Hung, “SKB-tree: A Fixed-outline Driven Representation for Modern Floorplanning Problems.” IEEE Trans. on VLSI Systems, vol. 20, no.3, pp. 473-484, Mar. 2012.
[18] M. S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret, “Applications of Second Order Cone Programming,” Linear Algebra and its Applications, vol. 284, pp. 193-228, Nov. 1998.
[19] C. Luo, M. Anjos, A. Vannelli, “Large-scale Fixed-outline Floorplanning Design Using Convex Optimization Techniques,” in Proc. ASP-DAC, pp 198-203, 2008.
[20] Y. Ma, X. Hong, S. Dong, and C.-K. Cheng, “3D CBL: An Efficient Algorithm for General 3D Packing Problems,” in Proc. MWSCAS, vol. 2, pp.1079-1082, 2005.
[21] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “Rectangle-packing Based Module Placement,” in Proc. ICCAD, pp. 472-479, 1995.
[22] 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,” U.S. Patent 6301693, 2001.
[23] H. Y. Nonmember, S. On, S. Nakatake, and Y. Kajitani, “The 3D-Pack by Meta Data Structure and Pack Heuristics,” IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, vol. E83-A, pp. 639-645, 2000.
[24] R. H. J. M. Otten, “Automatic Floorplan Design,” in Proc. DAC, pp. 261-267, 1982.
[25] D. F. Wong and P. S. Sakhamuri, “Efficient Floorplan Area Optimization”, in Proc. DAC, pp. 586-589, 1989.
[26] L. Xiao, S. Sinha, J. Xu, and E. F. Y. Young, “Fixed-outline Thermal-aware 3D Floorplanning,” in Proc. ASP-DAC, pp. 561-567, 2010.
[27] J.-Z. Yan and C. Chu, “DeFer: Deferred Decision Making Enabled Fixed-outline Floorplanning Algorithm,” IEEE Trans. on CAD, vol. 29, no. 3, pp.119-130, 2010.
[28] P.-H. Yuh, C.-L. Yang, Y.-W. Chang, and H.-L. Chen, “Temporal Floorplanning Using 3D-subTCG,” in Proc. ASP-DAC, 2004, pp. 725-730.
[29] P. Zhou, Y. Ma, Z. Li, R. P. Dick, L. Shang, H. Zhou, X. Hong, and Q. Zhou, “3D-STAF: Scalable Temperature and Leakage Aware Floorplanning for Three-dimensional Integrated Circuits,” in Proc. ICCAD, pp. 590-597, 2007.