三維晶片(Three-dimensional Integrated Circuit, 3D IC)已被視為能延續甚至超越摩爾定律(Moore’s law)的有效辦法之一，其是由數層晶粒(die)沿垂直方向堆疊而成，並利用矽穿孔(Through Silicon Vias, TSVs)作為不同晶粒間訊號傳輸的通道，此架構不僅能提升晶片整體效能，亦可實現異質整合(heterogeneous integration)。然而，由於矽穿孔的尺寸較標準元件(standard cell)大上數倍，且會佔據擺置(placement)或繞線(routing)資源，另其位置對於效能、功率消耗、溫度與良率(yield)等諸多方面影響甚鉅，故須於平面規劃(floorplanning)時將其納入考量，以避免削弱三維晶片的優勢。雖然過去已有許多文獻針對三維平面規劃進行研究與探討，但多半不是忽略矽穿孔的存在，就是未考慮固定框架限制(fixed-outline constraint)，此外，肇因於模組(module)與矽穿孔之間過大的尺寸差距，三維平面規劃若同時擺置模組與矽穿孔將更不易獲得符合固定框架的結果。鑒於上述原因，本論文提出一個可處理矽穿孔擺置並滿足固定框架限制的三維平面規劃方法，其可略分為可略分為三個階段，首先於全域分布階段，透過數學分析法最佳化不同目標，將模組與矽穿孔同步散置於各層晶粒中，藉此獲得具全域觀點的初始分布狀態；接著於合法化擺置階段，以不過度影響該分布狀態為前提下，逐層得出不違反固定框架限制的平面規劃結果；最後於矽穿孔指派階段，決定各個矽穿孔確切的位置，並進一步優化繞線長度(wirelength)。由實驗結果顯示，在相同的測試電路下，本論文所提出的方法相較於Co-place可獲得更佳的結果。

A three-dimensional integrated circuit (3D IC) which uses through silicon vias (TSVs) as inter-die connections is one of the promising 3D integration technologies to break through bottlenecks faced by a 2D IC. However, TSVs are like double-edged swords. Despite shorter wirelength brought by TSVs, abusing or misplacing TSVs may degrade a 3D IC significantly. Moreover, a TSV is much larger than a standard cell and will block the placement or routing resources. Hence, floorplanning in 3D IC should not ignore the existence of TSVs. Although many studies have been presented to cope with different problems during 3D floorplanning, most of them either neglect the TSV planning or overlook the fixed-outline constraint. As a result, this thesis proposes a TSV-aware methodology to handle fixed-outline floorplanning for 3D ICs. Our approach can obtain better results than others because all modules and TSVs in all tiers of a 3D IC are optimized simultaneously in the global distribution stage. Further, after better initial solutions are gained, our legalization stage still can maintain them and get feasible solutions while considering TSVs under the fixed-outline constraint. Experimental results show that our results respectively achieve 10% and 13% shorter wirelength than Co-place in average in benchmarks with hard modules and soft modules.

[1] K. Athikulwongse, A. Chakraborty, J.-S. Yang, D. Z. Pan, and S. K. Lim, “Stress-driven 3D-IC Placement with TSV Keep-out Zone and Regularity Study,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 669-674, 2010.
[2] 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.
[3] T.-C. Chen, Y.-W. Chang, and S.-C. Lin, “IMF: Interconnect-driven Multilevel Floorplanning for Large-scale Building-module Designs,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 159-164, 2005.
[4] 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.
[5] V. Gerousis, “Physical Design Implementation for 3D IC: Methodology and Tools,” in Proceedings of International Symposium on Physical Design, pp. 57-57, 2010.
[6] G. Karypis, R. Aggarwal, V. Kumar, and S. Shashi, “Multilevel Hypergraph Partitioning: Applications in VLSI Domain,” IEEE Transactions on Very Large Scale Integration Systems, vol. 7, no. 1, pp. 69-79, 1999.
[7] D. H. Kim, R. O. Topaloglu, and S. K. Lim, “Block-level 3D IC Design with Through-silicon-via Planning,” in Proceedings of Asia and South Pacific Design Automation Conference, pp. 335-340, 2012.
[8] 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.
[9] 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.
[10] 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.
[11] C.-T. Lin, D.-M. Kwai, Y.-F. Chou, T.-S. Chen, and W.-C. Wu, “CAD Reference Flow for 3D Via-last Integrated Circuits,” in Proceedings of Asia and South Pacific Design Automation Conference, pp. 187-192, 2010.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
[16] M.-C. Tsai, T.-C. Wang, and T. Hwang, “Through-silicon Via Planning in 3-D Floorplanning,” IEEE Transactions on Very Large Scale Integration Systems, vol. 19, no. 8, pp. 1448-1457, 2011.
[17] 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.
[18] 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.
[19] 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.
[20] W. Zhong, S. Chen, and T. Yoshimura, “Whitespace Insertion for Through-silicon Via Planning on 3-D SoCs,” in Proceedings of IEEE International Symposium on Circuits and Systems pp. 913-916, 2010.
[21] 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.