臺灣博碩士論文加值系統

在三維積體電路架構的設計流程當中，電路分割是很重要的一個課題，在晶片設計的過程當中，各個邏輯閘擺放分層的位置，將會影響矽穿孔(Through Silicon Via, TSV)數量、電路成本、良率及散熱問題，尤其當輸入功率越來越高的時候，散熱會變的更加困難，而且也會需要更多傳導功率用的功率矽穿孔(Power TSV)。因此如何找到一個分割結果，能使得晶片在power density限制之下，最小化矽穿孔之總數及Area Overhead就成為一個很重要的課題，本篇論文提出一個在功率限制下可最小化功率矽穿孔之三維積體電路分割的方法。
在本篇論文中，我們會先分析並計算電路的功率，得到每個邏輯閘各別的功率後，則可以由各層所有邏輯閘的總功率來計算出需要多少的功率矽穿孔，並且在除以各層之總面積之後可以得到各層的功率密度。我們會以multilevel的架構來對電路進行連續地coarsening，藉此降低電路的複雜度。然後在不違反功率密度限制的前提下對電路進行初始分割，接著對初始分割後的電路交錯執行uncoarsening和K-layer-Two-way FM partitioning來降低矽穿孔之總數並最佳化其結果。
在實驗結果中，我們使用了2011年IC/CAD競賽所提供的Benchmarks[1]，並比較了在各種不同的功率輸入下，使用不同cost function之分割後的結果。最後可以得知，分割時有加入功率矽穿孔之考量的分割結果，其矽穿孔之總數皆少於未考量功率矽穿孔之分割的結果。

In 3D IC Design, partition is an important step problem in physical design. The partition results of netlist will affect the number of Through Silicon Via (TSV), circuit cost, yield and thermal dissipation. Especially when the input frequency is higher, thermal dissipation will be difficult too. And that means more number of power TSV will be needed. Therefore, to find a partition result that can minimize TSV and total area overhead under power density constraint becomes an import issue. In this paper we propose a power TSV aware three dimensional integrated circuits partitioning under power constraints algorithm.
First of all, we analyze the power of a circuit. Then we can calculate the power of every logic gate. After that, we can calculate how many power TSV will be needed in each layer by the total power of logic gate on each layer. And power density of each layer equals total cell power divided by the total area of each layer. We use a multilevel framework to coarsen the netlist successively to reduce the complexity of the netlist. Then we get an initial partition result that satisfies power density constraint. Based on this initial partition result, we use Uncoarsening and K-layer-Two-way FM partitioning algorithm to refine our partition result.
As shown in the experimental, we show the result of different cost function under several different input frequency. And the number of total TSV when partitioning with power TSV consideration is less than partitioning without power TSV consideration.

中文摘要 I
Abstract II
致謝 III
目錄 IV
圖目錄 V
表目錄 VI
第一章、前言 1
第二章、相關研究與問題描述 3
2.1 相關研究 3
2.1.1 3D IC 與3D Aware Partitioning演算法之相關研究 3
2.1.2 Coarsening演算法之相關研究 5
2.2 問題描述 8
第三章、演算法與程式流程 10
3.1 程式流程 10
3.2 演算法 11
3.2.1 Construct Data Structure 12
3.2.2 Power Analysis 13
3.2.3 Multilevel Coarsening Phase 15
3.2.4 Initial Partitioning Phase 18
3.2.5 Uncoarsen and Two-Way Partition Phase 20
3.2.6 Area Overhead Refinement Phase 21
第四章、實驗結果 22
4.1 執行平台與程式語言 22
4.2 實驗結果 22
4.2.1 分割時使用不同cost function的TSV實驗結果 24
4.2.1 Initial Partition的TSV數量 28
4.2.3 在兩種不同cost function之下的各層功率分佈 34
4.2.4 在兩種不同cost function之下的Area Overhead 37
第五章、結論與未來方向 40
5.1 結論 40
5.2 未來方向 40
參考文獻 41
作者簡介 43


圖目錄
圖1-1 package層次、電路晶片層次及晶圓層次 1
圖1-2 (a) Face-to-Face, (b) Back-to-Back, (c) Face-to-Back 2
圖2-1 平面與3D IC架構下之分割擺置比較 4
圖2-2 Edge Coarsening示意圖 5
圖2-3 Hyperedge Coarsening示意圖 6
圖2-4 Modified Hyperedge Coarsening示意圖 6
圖2-5 First Choice Coarsening：Hypergraph轉換Model Weighted Graph示意圖 7
圖3-1 程式流程圖 10
圖3-2 Multilevel Hypergraph Partitioning 11
圖3-3 字典演算法之資料結構 12
圖3-4 邏輯閘頻率選擇示意圖 15
圖3-5 原始電路 (1) 16
圖3-6 原始電路 (2) 16
圖3-7 EIA table (1) 16
圖3-8 EIA table (2) 16
圖3-9 EIA table (3) 17
圖3-10 EIA table (4) 17
圖3-11 原始電路 (3) 17
圖3-12 coarsening完成後之新電路 17
圖3-13 將所有module置於第一層 18
圖3-14 將部份module搬至第二層 18
圖3-15 對一、二層進行FM 19
圖3-16 將部份module搬至第三層 19
圖3-17對二、三層進行FM 19
圖4-1 case 4於不同階段之TSV數量比較 29
圖4-2 case 3於不同階段之TSV數量比較 30
圖4-3 case 7於不同階段之TSV數量比較 31



表目錄
表3-1: Symbol definition 13
表4-1︰2011年工研院提供的Benchmark Information 23
表4-2︰各case的Power Density Constrain 23
表4-3︰case1於分割時未加入邏輯閘功率考量之TSV結果 24
表4-4︰case1於分割時加入邏輯閘功率考量之TSV結果 24
表4-5︰case2於分割時未加入邏輯閘功率考量之TSV結果 24
表4-6︰case2於分割時加入邏輯閘功率考量之TSV結果 24
表4-7︰case3於分割時未加入邏輯閘功率考量之TSV結果 25
表4-8︰case3於分割時加入邏輯閘功率考量之TSV結果 25
表4-9︰case4於分割時未加入邏輯閘功率考量之TSV結果 25
表4-10︰case4於分割時加入邏輯閘功率考量之TSV結果 25
表4-11︰case5於分割時未加入邏輯閘功率考量之TSV結果 26
表4-12︰case5於分割時加入邏輯閘功率考量之TSV結果 26
表4-13︰case6於分割時未加入邏輯閘功率考量之TSV結果 26
表4-14︰case6於分割時加入邏輯閘功率考量之TSV結果 26
表4-15︰case7於分割時未加入邏輯閘功率考量之TSV結果 27
表4-16︰case7於分割時加入邏輯閘功率考量之TSV結果 27
表4-17︰各case於分割時加入功率考量與否之total TSV數目正規化比較 28
表4-18︰case1於初始分割後之TSV結果 32
表4-19︰case2於初始分割後之TSV結果 32
表4-20︰case3於初始分割後之TSV結果 33
表4-21︰case4於初始分割後之TSV結果 33
表4-22︰case5於初始分割後之TSV結果 33
表4-23︰case6於初始分割後之TSV結果 33
表4-24︰case7於初始分割後之TSV結果 33
表4-25︰case7於分割時加入功率考量與否之功率密度結果比較 34
表4-26︰case1於分割時加入功率考量與否之功率密度結果比較 35
表4-27︰case2於分割時加入功率考量與否之功率密度結果比較 35
表4-28︰case3於分割時加入功率考量與否之功率密度結果比較 35
表4-29︰case4於分割時加入功率考量與否之功率密度結果比較 36
表4-30︰case5於分割時加入功率考量與否之功率密度結果比較 36
表4-31︰case6於分割時加入功率考量與否之功率密度結果比較 36
表4-32︰case1之Area Overhead結果比較 37
表4-33︰case2之Area Overhead結果比較 37
表4-34︰case3之Area Overhead結果比較 38
表4-35︰case4之Area Overhead結果比較 38
表4-36︰case5之Area Overhead結果比較 38
表4-37︰case6之Area Overhead結果比較 38
表4-38︰case7之Area Overhead結果比較 38
表4-39︰case1之Area Overhead正規化結果比較 38
表4-40︰case2之Area Overhead正規化結果比較 39
表4-41︰case3之Area Overhead正規化結果比較 39
表4-42︰case4之Area Overhead正規化結果比較 39
表4-43︰case5之Area Overhead正規化結果比較 39
表4-44︰case6之Area Overhead正規化結果比較 39
表4-45︰case7之Area Overhead正規化結果比較 39

[1]2011 CAD Contest Website: http://cad_contest.cs.nctu.edu.tw/cad11/index.htm
[2]D. Kung, R. Puri, "CAD Challenges for 3D ICs," in Proc. Asia and South Pacific Design Automation Conference, 2009.
[3]T. Vucurevich, Cadence Design Systems, Inc, "3-D Semiconductor’s: More from Moore," in Proc. ACM/IEEE Design Automation Conf., pp. 664, June 2008.
[4]G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar “Multilevel Hypergraph Partitioning: Application in VLSI Domain”, in Proc. ACM/IEEE Design Automation Conference, pp.526-529, 1997.
[5]G. Karypis, V. Kumar, “Multilevel k-way Hypergraph Partitioning*”, in Proc. ACM/IEEE Design Automation Conference, pp.343-348, 1999.
[6]G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar “Multilevel Hypergraph Partitioning:Applications in VLSI Domain”, IEEE Trans. VLSI Syst., vol. 7, no. 1, pp.69-79, Mar. 1999.
[7]W. R. Davis, J. Wilson, S. Mick, J. Xu, H. Hua, C. Mineo, A. M. Sule, M. Steer, and P. D. Franzon, “Demystifying 3D ICs: The Pros and Cons of Going Vertical”, IEEE Design &; Test Computer, pp.498-510, Nov.-Dec., 2005.
[8]W.-L. Hung, G. Link, Yuan Xie, N. Vijaykrishnan, and M. J. Irwin, "Interconnect and Thermal-aware Floorplanning for 3D Microprocessors", International Symposium on Quality Electronic Design, pp.99-104, Mar. 2006.
[9]C. Ferri, S. Reda, and R. I. Bahar, “Parametric Yield Management for 3D ICs: Models and Strategies for Improvement”, ACM Journal on Emerging Technologies in Computing Systems, pp.19:1-19:22, 2008.
[10]Emrah Acar, IBM Research, 3D IC Workshop, National Tsing Hua University, Hsinchu, Taiwan, 2008.
[11]I. H. Jiang, “Generic Integer Linear Programming Formulation for 3D IC Partitioning”, IEEE International SOC Conference, pp.321-324, 2009.
[12]C. M. Fiduccia and R. M. Mattheyses, “A Linear Time Heuristic for Improving Network Partitions”, in Proc. of the ACM/IEEE Design Automation Conf, pp.175-181,1982.
[13]Iris H. R. Jiang, “Generic Integer Linear Programming Formulation for 3D IC Partition”, SOCCON, pp.321-324, 2009.
[14]H. S. Ye, M. C. Chi, S. H. Huang, “A Design Partitioning Algorithm for Three Dimensional Integrated Circuits”, 3CA, pp.229-232, 2010.
[15]Y. C. Hu, Y. L. Chung and Mely Chen Chi, “A Multilevel Multilayer Partitioning Algorithm for Three Dimensional Integrated Circuit”, ISQED, p.483-487, 2011.
[16]T. Y. Hsueh, H. H. Yang, W. C. Wu and M. C. Chi, “A Layer Prediction Method for Minimum Cost Three Dimensional Integrated Circuits” , ISQED pp.359-363, 2011.
[17]C. C. Chan, Y. T. Yu, Iris H. R. Jiang, “3DICE: 3D IC Cost Evaluation Based on Fast Tier Number Estimation”, ISQED, pp.50-55, 2011.
[18]T. Y. Hsueh, H. C. Lai, H. L. Chang, M. C. Chi, “An Effective Power-Aware Partitioning Algorithm for 3D IC Designs” , 22th VLSI Design/CAD Symposium, 2011.
[19]H. L. Chang, H. C. Lai, T. Y. Hsueh, W. K. Cheng, M. C. Chi, “A 3D IC Designs Partitioning Algorithm with Power Consideration” , ISQED pp.137-142, 2012.
[20]吳偉傑, “考量功率限制之三維積體電路分割演算法” , 中原大學資訊工程研究所碩士論文 , 2011.
[21]薛祖雲, “電路分割方法相關研究與應用於電路擺置之電路分割演算法” , 中原大學資訊工程研究所碩士論文 , 2011.