臺灣博碩士論文加值系統

在本論文中，我們提出了一個多階層的電路分割演算法應用於三維積體電路的架構中。演算法是以multilevel的架構來對netlist進行連續地coarsen。在un-coarsening的過程中執行K階層電路分割的程序。目的為最小化矽穿孔(Through Silicon Via, TSV)的總數目同時也遵守各層面積的限制。各層面積為電路面積的總和加上矽穿孔(Through Silicon Via, TSV)所使用面積的總和再除以層數。將電路分割演算法應用於三維積體電路的架構。我們使用一個類似FM的資料結構並且應用critical net的分佈，因此在一個cell搬動完後對gain值的更新非常有效率。實驗數據顯示我們提出的演算法對於工業用的測試電路可以有效率地最小化TSV所使用的數目及得到比較小的area overhead。

In this paper, we propose a multilevel K-layer partitioning algorithm for 3D ICs application. The algorithm is based on the multilevel framework to coarsen the netlist successively. A K-layer partitioning procedure is applied on each level of partition during the un-coarsening process. The objective is to minimize the total number of Through Silicon Vias (TSV) while observing the area constraint for each layer. The area of each layer is the summation of circuit area and TSV area then divided by the number of layer. The partitioning algorithm is customized for the structure of 3D ICs. We utilize a FM-like data structure and identify some critical net distributions such that after a cell move, the program may update gains very effectively. The experiments show that with the proposed algorithm can effectively produce good results with minimization the number of TSV and small total area overhead for the tested industrial cases.

目錄
中文摘要………………………………………………………………Ⅰ
英文摘要………………………………………………………………II
致謝……………………………………………………………………III
圖目錄…………………………………………………………………VI
表目錄………………………………………………………………VIII
第一章、 前言………………………………………………………1
第二章、 相關研究及背景介紹……………………………………4
2.1 Modified Hyperedge Coarsening (MHEC)演算法之簡介……4
2.2 FM演算法之簡介………………………………………………………6
第三章、 問題描述及定義…………………………………………………7
3.1 基本定義………………………………………………………………7
3.2 問題描述………………………………………………………………10
第四章、 演算法與程式流程………………………………………………12
4.1 程式流程………………………………………………………………12
4.2 演算法…………………………………………………………………13
4.2.1 Multilevel Coarsening Phase…………………………………15
4.2.2 Initial K-layer Partitioning Phase………………………15
4.2.3 K-layer Partitioning Phase…………………………………16
4.2.4 Multilevel Uncoarsening and refinement Phases………22
第五章、 實驗結果…………………………………………………………………………23
5.1 執行平台與程式語言…………………………………………………………………23
5.2 實驗結果………………………………………………………………………………23
第六章、結論與未來方向…………………………………………………………………42
6.1 結論……………………………………………………………………………………42
6.2 未來方向………………………………………………………………………………42
參考文獻……………………………………………………………………………………43

圖目錄

圖1-1: package層次、電路晶片層次及晶圓層次…………………………2
圖1-2 (a): Face-to-Face…………………………………………………2
圖1-2 (b): Back-to-Back…………………………………………………2
圖1-2 (c): Face-to-Back…………………………………………………2
圖2-1: Hyperedge Coarsening (HEC)………………………5
圖2-2: Modified Hyperdege Coarsening (MHEC)…………5
圖3-1: 3D ICs架構…………………………………………………8
圖4-1:程式流程圖……………………………………………………12
圖4-2:示意圖…………………………………………………………14
圖4-3:Multilevel K-layer partitioning pseudo code……14
圖4-4(a):F(Ni)大於1………..…………………………………………17
圖4-5-1(a):F(Ni)等於1且cell A 往上搬………………………………18
圖4-5-2(a):F(Ni)等於1且cell A 往上搬………………………………18
圖4-6-1(a):F(Ni)等於1且cell A 往下搬………………………………18
圖4-6-2(a):F(Ni)等於1且cell A 往下搬………………………………18
圖4-7-1(a):F(Ni)等於1且cell A 往上搬………………………………19
圖4-7-2(a):F(Ni)等於1且cell A 往下搬………………………………19
圖4-8:K-layer partitioning pseudo code…………………………21
圖4-9:Multiledel Uncoarsening pseudo code……………………22



表目錄
表5-1:測試電路資訊........…………………...…………………………23
表5-2(a):Circuit_1 multilevel coarsening 之結果.…………………...…24
表5-2(b):Circuit_2 multilevel coarsening 之結果…………………...…24
表5-2(c):Circuit_3 multilevel coarsening 之結果.…………………...…25
表5-2(d):Circuit_4 multilevel coarsening 之結果…………………...…25
表5-3:Number of Normalized Module at each Coarsen Level...……….26
表5-4(a):Circuit_1 : Cell distribution by number of pin……………..…26
表5-4(b):Circuit_1 : Net distribution by number of pin.....……………..27
表5-5(a):Circuit_2 : Cell distribution by number of pin……………..…27
表5-5(b):Circuit_2 : Net distribution by number of pin.....……………..28
表5-6(a):Circuit_3 : Cell distribution by number of pin…..……………28
表5-6(b):Circuit_3 : Net distribution by number of pin.…..……………29
表5-7(a):Circuit_4 : Cell distribution by number of pin……..…………29
表5-7(b):Circuit_4 : Net distribution by number of pin…..……………30
表5-8(a):Circuit_1 : Initial K-layer Partitioning 之結果....……………..31
表5-8(b):Circuit_2 : Initial K-layer Partitioning 之結果...……………..31
表5-8(c):Circuit_3 : Initial K-layer Partitioning 之結果....……………..31
表5-8(d):Circuit_4 : Initial K-layer Partitioning 之結果...……………..31
表5-9(a):Circuit_1 : K-layer Partitioning 之結果..……....……………..32
表5-9(b):Circuit_2 : K-layer Partitioning 之結果..……....……………..32
表5-9(c):Circuit_3 : K-layer Partitioning 之結果..……....……………..33
表5-9(d):Circuit_4 : K-layer Partitioning 之結果..……....……………..33
表5-10(a):Circuit_1 : K-layer Partitioning(rlo=0.9,rup=1.1)之結果...…..34
表5-10(b):Circuit_2 : K-layer Partitioning(rlo=0.9,rup=1.1)之結果...…..34
表5-10(c):Circuit_3 : K-layer Partitioning(rlo=0.9,rup=1.1)之結果...…..34
表5-10(d):Circuit_4 : K-layer Partitioning(rlo=0.9,rup=1.1)之結果...…..34
表5-11(a):Circuit_1 : K-layer Partitioning(rlo=0.85,rup=1.05)之結果.....35
表5-11(b):Circuit_2 : K-layer Partitioning(rlo=0.85,rup=1.05)之結果.....35
表5-11(c):Circuit_3 : K-layer Partitioning(rlo=0.85,rup=1.05)之結果.…35
表5-11(d):Circuit_4 : K-layer Partitioning(rlo=0.85,rup=1.05)之結果.…35
表5-12: 不同rlo、rup 在Circuit_4 中的結果.....……………………….35
表5-13(a):Circuit_1 :Initial K-layer Partitioning 之結果………………37
表5-13(b):Circuit_2 :Initial K-layer Partitioning 之結果………………37
表5-13(c):Circuit_3 :Initial K-layer Partitioning 之結果.………………37
表5-13(d):Circuit_4 :Initial K-layer Partitioning 之結果………………37
表5-14(a):Circuit_1 :K-layer Partitioning 之結果……...………………38
表5-14(b):Circuit_2 :K-layer Partitioning 之結果……...………………38
表5-14(c):Circuit_3 :K-layer Partitioning 之結果……...………………38
表5-14(d):Circuit_4 :K-layer Partitioning 之結果……...………………38
表5-15(a): rlo為0.95、rup為1.05 之結果(With Coarsening)……………39
表5-15(b): rlo為0.9、rup為1.1 之結果(With Coarsening)………………39
表5-15(c): rlo為0.85、rup為1.15 之結果(With Coarsening)……………39
表5-16(a): rlo 為0.95、rup 為1.05 之結果(Without Coarsening)………40
表5-16(b): rlo 為0.9、rup 為1.1 之結果(Without Coarsening)…………40
表5-16(c): rlo 為0.85、rup 為1.15 之結果(Without Coarsening)………40
表5-17(a): K -layer partitioning (with coarsen)之run time 及memory
usage.……………………………………………………………………41
表5-17(b): K -layer partitioning (without coarsen)之run time 及memory
usage.……………………………………………………………………41

[1] “The International Technology Roadmap for Semiconductors,” Semicond. Inc.
ASSOC., 1999 ed, http://www.itrs.net/
[2] Emrah Acar, IBM Research, 3D IC Workshop, National Tsing Hua University,
Hsinchu, Taiwan, 2008.
[3] 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.
[4] G.Karypis, V. Kumar, “Multilevel k-way Hypergraph Partitioning*,” in
Proc.ACM / IEEE Automation Conf, pp.343-348, 1999.
[5] D. G. Schweikert and B. W. Kernighan, “A proper model for the partitioning
of electrical circuits,” in Proc. ACM/IEEE Design Automation Conf., 1972,
pp. 57~62.
[6] B. W. Kernighan and S. Lin, “An efficient heuristic procedure for
partitioning graphs,” Bell Syst. Tech. J., vol. 49, no. 2, pp.
291~307,1970.
[7] C. M. Fiduccia and R. M. Mattheyses, “A linear time heuristic for
improving network partitions,” in Proc. 19th IEEE Design Automation Conf.,
1982, pp. 175~181.
[8] Emrah Acar, IBM Research, 3D IC Workshop, National Tsing Hua University,
Hsinchu, Taiwan, 2008.
[9] 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), May 2008, pp. 550~555.
[10] P.Agrawal, B.Narendran, N.Shivakumar; ”Multi-Way Partitioning of VLSI
Circuits ,” in Proc. VLSI Design, pp. 393-399.
[11] Provided by Industrail Technology Research Institute (ITRI), Hsinchu,
Taiwan, 2009.
[12] ITRS (International Technology Roadmap for Semi-conductors). (2007)
Assembly and Packaging 2007. [Online]. Available:
http://www.itrs.net/links/
2007Winter/2007_Winter_Presentations/12_Assembly_ 2007_JP.pdf
[13] N. Mokhoff, “IITC reports on interconnect progress,” EE Times, May. 16
2008.[Online]. Available:http://www.eetimes.com/showArticle.jhtml;
jsessionid = OXME0TIHUPX2MQSNDLOSKH0CJUNN2JVN?articleID=207601527
[14] Ted Vucurevich, Cadence Design Systems, Inc, “ 3-D Semiconductor’s: More
from Moore,” in Proc. ACM/IEEE Design Automation Conf., June 2008 ,pp.
664.
[15] 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., June 2008 ,pp. 668~673.
[16] K. Puttaswamy, G. H Loh, “Scalability of 3D-Integrated Arithmetic Units
in High-Performance Microprocessors,” in Proc. ACM/IEEE Design Automation
Conf., June 2007 ,pp. 622~625.
[17] D. Kung, R. Puri, “CAD Challenges for 3D ICs,” in Proc. Asia and South
Pacific Design Automation Conference, 2009.
[18] S. S. Sapatnekar, “Addressing Thermal and Power Delivery Bottlenecks in
3D Circuits,” in Proc. Asia and South Pacific Design Automation
Conference, 2009.
[19] C. Chiang, S. Sinha, ”The Road to 3D EDA Tool Readiness,” in Proc. Asia
and South Pacific Design Automation Conference, 2009.
[20] 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.
[21] M. Mondal, A. J. Ricketts, S. Kirolos, T. Ragheb, G. Link, N.
Vijaykrishnan, Y. Massoud, “Thermally Robust Clocking Schemes for 3D
Integrated,” in Proc Design, Automation and Test in Europe Conference,
2007.