三維晶片(Three-dimensional Integrated Circuit, 3D IC)已被視為能延續甚至超越摩爾定律(Moore’s law)的有效辦法之一，它是由數層晶片層(die)沿垂直方向堆疊而成，並利用矽穿孔(Through Silicon Vias, TSVs)做為不同晶片層間訊號傳輸的通道，此架構不僅能提升晶片整體的效能，亦能實現異質整合(heterogeneous integration)與提升頻帶寬度(bandwidth)、高密度元件整合與較短的線長。然而，由於矽穿孔的尺寸較標準元件(standard cell)大上許多，過多的矽穿孔會佔據擺置(placement)與繞線(routing)的資源外，其對於製造成本、額外的繞線長、消耗功率與良率等多方面的影響。三維晶片存在不同的堆疊方式，大部分的方式是將每相鄰兩層晶片依據面對背(F2B)的方式堆疊，然而，如果我們能夠使最上面兩層晶片使用面對面(F2F)的堆疊方式，即可以有效的減少矽穿孔使用率，並且進一步提升三維晶片的優勢。因此本研究利用數學分析法的架構，在滿足固定框架下的限制條件下，提出了能夠考慮混合堆疊模式的三維平面規劃器。在這篇論文中，我們針對不同的晶片堆疊模式使用不同的方法來實現模組分層的演算法，除此之外，在數學分析法中我們也提出了一個新的模型用來計算每個區域的模組使用率。實驗結果顯示，新模型能在二維平面規劃中得到較短的線長，且相較於[6]的三維平面散布方法與SAINT[17]，我們的三維平面規劃能獲得更好的結果。

Three-dimension integrated circuits (3D ICs) are considered to be one of the most effective ways to extend or even exceed Moore’s Law. Chips in a TSV-based 3D IC are stacked in the vertical direction and use through silicon vias (TSVs) to deliver signals between modules in different tiers. 3D ICs have a lot of advantages such as better performance of the chip, heterogeneous integration, wider bandwidth of device frequency, high density components and shorter wirelength. But TSVs will occupy more routing resource and increase manufacture cost. There exist different bonding styles for three-dimension chips, and most contiguous tiers in 3D ICs are bonded by the face-to-back (F2B) bonding style. However, if the top two tiers are bonded by the face-to-face (F2F) style, the utilizations of TSVs can be reduced and the performance in 3D ICs will be improved. Therefore, this thesis proposes a methodology to handle floorplanning in 3D ICs with hybrid bonding style under the fixed-outline constraint. In this thesis, we use different methods to implement layer assignment algorithm for different bonding style. In addition, we also propose a new density potential function to calculate the module usage of each region in the analytical approach. The experimental results show that the new density potential function can obtain shorter wirelength in two-dimension integrated circuits. Moreover, our approach get better results than [6] and [17] on F2B bonding style and hybrid bonding style in three-dimension integrated circuits, respectively.

[1] E. Beyne, “The 3-D Interconnect Technology Landscape,” IEEE MDAT pp. 8-20, 2016.
[2] J. Cong, J. Wei, and Y. Zhang, “A Thermal-driven Floorplanning Algorithm for 3D ICs,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 306-313, 2004.
[3] J. Cong, and G. Luo, “A Multilevel Analytical Placement for 3D ICs,” in Proceedings of ASP-DAC, pp. 361-366, 2009.
[4] T.-C. Chen , Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, " NTUplace3: An Analytical Placer for Large-Scale Mixed-Size Designs With Preplaced Blocks and Density Constraints," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems ,vol. 27, no. 7, pp.1228-1240, 2008.
[5] S. Chen, and T. Yoshimura, “Multi-layer Floorplanning for Stacked ICs: Configuration Number and Fixed-outline Constraints,” Integration, the VLSI Journal, vol. 43, no. 4, pp. 378-388, 2010.
[6] M.-K. Hsu, V. Balabanov, and Y.-W. Chang, “TSV-Aware Analytical Placement for 3-D IC Designs Based on a Novel Weighted-Average Wirelength Model,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 32, no. 4, pp. 497-509, 2013.
[7] C.M. Fiduccia, and R.M. Mattheyses, “A Linear-Time Heuristic for Improving Network Partitions,” in Proceedings of DAC, pp. 175-181, 1982.
[8] M.-K. Hsu, Y.-F. Chen, C.-C. Huang, S. Chou, T.-H. Lin, T.-C. Chen, and Y.-W. Chang, “NTUplace4h: A Novel Routability-Driven Placement Algorithm for Hierarchical Mixed-Size Circuit Designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, no. 12, pp. 1914-1927, 2014.
[9] L. Jin, D. Kim, L. Mu, D.-S. Kim, and S.-M. Hu, “A Sweepline Algorithm for Euclidean Voronoi Diagram of Circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 38, no. 3, pp. 260-272, 2006.
[10] 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 Proceedings of DAC, pp. 1-6, 2014.
[11] M. Kuwano, and Y. Takashima, “Stable-LSE Based Analytical Placement with Overlap Removable Length,” in Proceedings of Synthesis And System Integration of Mixed Information Technologies, pp. 115-120, 2010.
[12] S. Kirkpatrick, C. D. Gelatt, and M. Vecchi, ”Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp.671-680, May 1983.
[13] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, ”Multilevel hypergraph partitioning: Application in VLSI domain, ” in Proceedings of DAC, pp. 526–529, 1997.
[14] Z. Li, X. Hong, Q. Zhou, Y. Cai, J. Bian, H. H. Yang, V. Pitchumani, and C.-K. Cheng, “Hierarchical 3-D Floorplanning Algorithm for Wirelength Optimization,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 53, no. 12, pp. 2637-2646, 2006.
[15] C.-R. Li, W.-K. Mak, and T.-C. Wang, “Fast Fixed-Outline 3-D IC Floorplanning with TSV Co-Placement,” IEEE Transactions on Very Large Scale Integration Systems, vol. 21, no. 3, pp. 523-532, 2013.
[16] J.-M. Lin, and J.-H. Wu, “F-FM: Fixed-outline Floorplanning Methodology for Mixed-size Modules Considering Voltage-island Constraint,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, no. 11, pp. 1681-1692, 2014.
[17] J.-M. Lin, P.-Y. Chiu, and Y.-F. Chang, “SAINT: Handling Module Folding and Alignment in Fixed-outline Floorplans for 3D ICs,” in Proceedings of ICCAD, pp. 1-7, 2016.
[18] J.-M. Lin, and J.-A. Yang, “Routability-driven TSV-aware Floorplanning Methodology for Fixed-outline 3D ICs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 99, no. PP, pp. 1-1, 2017.
[19] Y. Ma, X. Hong, S. Dong, and C. K. Cheng, “3D CBL: An Efficient Algorithm for General 3D Packing Problems,” in Proceedings of Midwest Symposium on Circuits and Systems, pp. 1079-1082, 2005.
[20] W. C. 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 6 301 693, 2001.
[21] S. Panth, K. Samadi, Y. Du, and S. K. Lim, “Placement-Driven Partitioning for Congestion Mitigation in Monolithic 3D IC Designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 34, no. 4, pp. 540-553, 2015.
[22] T. Song, S. Panth, and Y.-J. Chae, “Three-tier 3D ICs for more power reduction: Strategies in CAD, design, and bonding selection,” in Proceedings of ICCCAD, pp. 752-757, 2015.
[23] H. Tamazaki, K. Sakanushi, 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, no. 1, pp. 639-645, 2000.
[24] L. Xiao, S. Sinha, J. Xu, and E. F. Y. Young, “Fixed-outline Thermal-aware 3D Floorplanning,” in Proceedings of Asia and South Pacific Design Automation Conference, pp. 561-567, 2010.
[25] P.-H. Yuh, C.-L. Yang, Y.-W. Chang, and H.-L. Chen, “Temporal Floorplanning Using 3D-subTCG,” in Proceedings of Asia and South Pacific Design Automation Conference, pp. 725-730, 2004.
[26] J. Z. Yan, and C. Chu, “DeFer: Deferred Decision Making Enabled Fixed-Outline Floorplanning Algorithm,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 3, pp. 367-381, 2010.
[27] 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 Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 590-597, 2007.