臺灣博碩士論文加值系統

在三維積體電路(3D ICs)設計中，電路分割一直是很重要的一個課題，在晶片設計之中，如何決定各個邏輯閘擺放分層的位置，影響著電路成本、良率及散熱問題，因此如何找到一個分割結果，能使得晶片在power density限制之下，最小化矽穿孔(Through Silicon Via, TSV)及Total area overhead為一個很重要的課題，本篇論文提出一個考量功率限制之三維積體電路分割的方法。
在本篇論文中，我們先對電路平均功率做分析，依照邏輯閘啟動的頻率、電功率、電容，算出每個邏輯閘平均的電功率，將各層的邏輯閘平均電功率除上各層的總面積，即可算出各層的電功率密度。

本論文以multilevel的架構來對netlist進行連續地coarsening，使用FM-Like的演算法，分出一個符合power density限制的partition初始結果，再以這個初始partition結果，使用uncoarsening、2-way FM及k-way FM演算法最佳化其解。

本篇論文使用9個工業用的測試電路，實驗結果顯示出，我們與TSV driven做比較，signal TSV個數會些微的上昇，但是卻可以使用較少的power TSV，整體總TSV使用數目平均改進6%，本論文與2011年IC/CAD競賽隊伍做比較，其結果可以顯示出本程式有相當不錯的結果。此外我們將TSV driven partition與先前的論文做比較，程式執行時間是研究[17]的49.83倍快，是研究[18]的9.50倍快。

In 3D IC Design, partition is always an important step problem in physical design. The partition results of netlist will affect circuit cost, yield and thermal dissipation. Therefore, to find a partition result that can minimize Through Silicon Via (TSV) and total area overhead under power density constraint becomes an import issue. In this paper we propose a three dimensional integrated circuits partitioning with power consideration algorithm.

First of all, we analyze the power of a circuit. We can calculate the average power by active frequency, power and capacitance of logic gate. Power density of each layer equals total cell power divided by the total area of each layer. The algorithm is based on a multilevel framework to coarsen the netlist successively to reduce the problem size. We used FM-like algorithm to get an initial partition result that satisfies power density constraint. Based on this initial partition result, we use uncoarsening, 2-way FM and k-way FM algorithm to refine our partition result.

In this paper, we used 9 industrial integrated circuits. The experimental results show that compared to TSV driven, the number of signal TSV increases slightly, but we use less power TSV. In average, this program reduces 6% in the total number of TSVs. Comparing to IC/CAD 2011 contest, the results show that this paper has very good results. Comparing to previous research works, the runtime of TSV driven partition algorithm is 49.83 times faster than [17] and 9.50 times faster than [18].

目錄

中文摘要 I
Abstract III
誌謝 V
目錄 VI
圖目錄 VII
表目錄 VIII
第一章、前言 1
第二章、相關研究 5
2.1 Coarsening 5
2.2 FM演算法之簡介 6
2.3 Thermal model 相關研究 6
2.4.1 邏輯閘input pin的operating frequency計算 9
2.4.2 邏輯閘平均功率計算公式 11
第三章 問題描述及定義 13
3.1 問題描述 15
第四章 演算法與程式流程 17
4.1程式流程 17
4.2演算法(Algorithm) 18
4.2.1 Construct Data Structure 19
4.2.2 Power Analysis 20
4.2.3 Multilevel Coarsening Phase 22
4.2.4 Initial Partitioning Phase 25
4.2.5 2-way FM 29
4.2.6 Multilevel Uncoarsening and Refinement Phases 33
4.2.7 K-way FM 34
第五章 實驗數據 36
5.1 執行平台與程式語言 36
5.2 實驗結果 36
5.2.1 Power driven與TSV driven實驗結果比較 38
5.2.2 Power driven與2011 IC/CAD競賽比較結果 41
5.2.2 TSV driven實驗結果與相關論文比較 42
第六章 結論與未來方向 44
6.1結論 44
6.2未來方向 44
參考文獻 45
作者簡介 47

圖目錄

圖1-1 package層次、電路晶片層次及晶圓層次 2
圖1-2 (a) Face-to-Face, (b) Back-to-Back, (c) Face-to-Back 2
圖1-3 The structure of the TSVs 3
圖2-1 coarsening & uncoarsening 5
圖2-2 Compact Resistive Thermal Model 7
圖2-3 Finite element analysis 8
圖2-4 output pin的頻率取決於邏輯閘input pin中最大的頻率 10
圖2-5 output頻率取決於clock pin的頻率 10
圖2-6 電路圖決定各邏輯閘頻率的示意圖 11
圖3-1 Microprocessor Transistor Counts 1971-2011 & Moore's Law 14
圖4-1 程式流程圖 17
圖4-2 演算法示意圖 18
圖4-3 Algorithm pseudo code 19
圖4-4 字典演算法資料結構 20
圖4-5 Power TSV & Power PAD 22
圖4-6 HEC示意圖 23
圖4-7 MHEC示意圖 24
圖4-8 Initial Partitioning示意圖 27
圖4-9 Netcut計算 27
圖4-10 gain值計算 28
圖4-11 2-way FM 層與層之間搬動的順序 29
圖4-12 2-way FM示意圖 29
圖4-13 gain bucket資料結構 30
圖4-14 cell搬動後lock 31
圖4-15 K-way FM示意圖 34


表目錄

表2-1 公式(1)(2)(3)(4)的Symbol definition 12
表5-1 2011年工研院所提供的 Benchmark Circuits Information 37
表5-2 各Benchmark的Power Density Constraint 37
表5-3 2009年工研院所提供的 Benchmark Circuits Information 38
表5-4 Power Density Distribution 38
表5-5 Comparison of the Results Between TSV Driven and Power Driven 40
表5-6 The Result are Normalized to that of TSV Driven 41
表5-7 測試電路與2011 IC/CAD競賽結果比較 42
表5-8 The Result are Normalized to that of Ours Team 42
表5-9 TSV driven與論文[16][17][18]做比較 43

[1].D. Kung, R. Puri, "CAD Challenges for 3D ICs," in Proc. Asia and South Pacific Design Automation Conference, 2009.
[2].E. Acar, IBM Research, 3D IC Workshop, National Tsing Hua University, Hsinchu, Taiwan, 2008.
[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].P. D. Franzon, W. R. Davis, M.B. Steer, S. Lipa, Eun Chu Oh, T. Thorolfsson, T. Doxsee, S. Berkeley, B. Shani, K. Obermiller, "Design and CAD for 3D Integrated Circuits," in Proc. ACM/IEEE Design Automation Conf., pp. 668-673, June 2008.
[5].K. Puttaswamy, G. H Loh, "Scalability of 3D-Integrated Arithmetic Units in High-Performance Microprocessors," in Proc. ACM/IEEE Design Automation Conf., pp. 622-625, June 2007.
[6].S. S. Sapatnekar, "Addressing Thermal and Power Delivery Bottlenecks in 3D Circuits," in Proc. Asia and South Pacific Design Automation Conference, 2009.
[7].ITRS (International Technology Roadmap for Semi-conductors). (2007) Assembly and Packaging 2007.
[8].N. Mokhoff, “IITC reports on interconnect progress,” EE Times, May. 16 2008.
[9].Y. J. Lee, Y. J. Kim, G. Huang, M. Bakir, Y. Joshi, A. Fedorov, S. K. Lim, "Co-Design of Signal, Power, and Thermal Distribution," in Proc Design, Automation and Test in Europe Conference, 2009.
[10].G. Karypis, R. Aggarwal, V. Kumar, S. Shekhar "Multilevel Hypergraph Partitioning: Applications in VLSI Domain," IEEE Trans. VLSI Syst. Vol.7, pp.69-79, 1999.
[11].G. Karypis, V. Kumar, "Multilevel k-way Hypergraph Partitioning*," in Proc. ACM / IEEE Automation Conf, pp.343-348, 1999.
[12].C. M. Fiduccia and R. M. Mattheyses, "A linear time heuristic for improving network partitions," in Proc. 19th IEEE Design Automation Conf., pp. 175-181, 1982.
[13].2011年CAD contest http://cad_contest.cs.nctu.edu.tw/cad11/index.htm
[14].E. Acar, IBM Research, 3D IC Workshop, National Tsing Hua University, Hsinchu, Taiwan, 2008.
[15].2009年CAD contest http://cad_contest.ee.ntu.edu.tw/cad09/Problems.htm
[16].H. S. Ye, M. C. Chi, S. H. Huang, “A Design Partitioning Algorithm for Three Dimensional Integrated Circuits”, in Proc. Computer Communication Control and Automation (3CA), pp. 229-232, May. 2010.
[17].Y. C. Hu, Y. L. Chung, M. C. Chi, “A Multilevel Multilayer Partitioning Algorithm for Three Dimensional Integrated Circuits”, in Proc. International Symposium on Quality Electronic Design, pp. 483-487, Mar. 2010.
[18].T. Y. Hsueh, H. H. Yang, W. C. Wu, M. C. Chi, “A Layer Prediction Method for Minimum Cost Three Dimensional Integrated Circuits”, IEEE 12th International Symposium on Quality Electronic Design, pp.359-363, 2011.
[19].鍾易霖, ”應用於三維積體電路之多階層電路分割演算法, 中原大學資訊工程研究所碩士論文, 2009.
[20].胡宇成, ”應用於三維積體電路之熱導向多階層電路分割演算法, 中原大學資訊工程研究所碩士論文, 2010.
[21].K. Navas, V. Rao, L. Samule, S.W.Ho, V. Lee, X.W.Zhang, R. Yang, and E. Liao, “Development of 3D Silicon Module with TSV for System in Packaging,” in 2008 58th Electronic Components and Technology Conference (ECTC2008), pp. 550~555, May 2008.
[22].P. Wilkerson, M. Furmanczyk, and M. Turowski, “Compact Thermal Modeling Analysis for 3D Integrated Circuits,” in Proc. MIXDES, 11th International Conference Mixed Design of Integrated Circuits and Systems, Szczecin, Poland, Jun. 2004.
[23].B. Goplen , S. Sapatnekar, “Efficient Thermal Placement of Standard Cells in 3D ICs using a Force Directed Approach,” Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.86, November 2003.