跳到主要內容

臺灣博碩士論文加值系統

(44.220.255.141) 您好!臺灣時間:2024/11/15 00:31
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:姜柏廷
研究生(外文):Chiang, Po-Ting
論文名稱:考慮時鐘樹之力導向後全域擺置最佳化
論文名稱(外文):Clock Tree Aware Force-Directed Post Global Placement Optimization
指導教授:李毅郎
指導教授(外文):Li, Yih-Lang
口試委員:王廷基方劭云劉文皓
口試委員(外文):Wang, Ting-ChiFang, Shao-YunLiu, Wen-Hao
口試日期:2015-06-29
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學與工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:中文
論文頁數:39
中文關鍵詞:全域擺置時鐘樹
外文關鍵詞:global placementclock tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:281
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
  功率消耗是現今積體電路設計時其中一項主要考量的改善目標。由於時鐘樹具有高負載電容及高切換頻率的特性,因此[27]提到時鐘樹的功耗可能會占據總功耗的40%。在傳統的實體設計流程中,擺置完成之後才進行時鐘樹合成,而時鐘樹合成會建立時脈來源(clock source)到所有暫存器(register)的連線,因此時鐘樹合成所得到的結果會受限於擺置完成後暫存器的位置。
  本研究實作特定應用積體電路的後全域擺置最佳化,透過結合根據分群結果來執行的三階段時鐘樹合成器到全域擺置器中,快速建立虛擬時鐘樹。此後全域擺置器根據虛擬時鐘樹的結構資訊對暫存器加入額外的時鐘樹縮減力來改善暫存器擺置的位置,擺置的結果則交由商業用軟體(SOC Encounter)來進行時鐘樹合成,改善暫存器位置的結果最後會使得時鐘樹合成完相對於未改善前能減少時鐘樹繞線長度並降低時鐘樹的切換功率。

  Power consumption is one of the primary optimization objectives for modern integrated circuit designs. Clock trees can contribute more than 40% of the total power consumption due to their high frequency of switching and high capacitance [27]. In the traditional physical design flow, placement is before clock tree synthesis. Clock tree synthesis is to construct a tree to connect the clock source with all registers. Therefore optimizes clock trees are limited by the quality of register placement.
  This study implements ASIC post global placement optimization. We integrates a fast three stage clock tree synthesis method based on modified k-means clustering into our global placer. The fast three stage clock tree synthesis constructs the structure of the virtual clock tree. Then this post global placer add multi-level clock net contractive force according to the structure of the virtual clock tree to optimize register locations. We get the clock tree synthesis result by the commercial tool SOC Encounter. Our optimized result can not only reduce clock tree wirelength but also minimize clock net switching power.

摘要 I
Abstract II
Acknowledgement III
Contents IV
List of Tables VI
List of Figures VII
Chapter1 Introduction 1
Chapter 2 Preliminaries 6
2.1 Problem Formulation 6
2.2 Evaluation Metric 7
2.3 Previous Work 7
Chapter 3 Our Clock Tree Aware Force-Directed Post Global Placement Optimization 14
3.1 Overview of Our Flow 14
3.2 Modified K-Means Clustering 16
3.3 Three Stage Clock Tree Synthesis 17
3.3.1 Overview of CTS 17
3.3.2 Graph Model 19
3.3.3 Minimum Bottleneck Maximum Matching 20
3.3.4 Tree Construction 23
3.4 Multi-Level Clock Net Contractive Force and Weight Assigning 24
3.5 Clock Tree Aware Post Global Placement Optimization Converge Criterion 26
Chapter 4 Experimental Results 27
4.1 Benchmarks 28
4.2 Industrial Case Experiments on Clock Tree Aware Global Placement Optimization 29
4.3 Modified Case Experiments on Clock Tree Aware Global Placement Optimization 31
Chapter 5 Conclusion 36
Chapter 6 Bibliography 37

[1] P. Spindler, U. Schlichtmann, and F. M. Johannes, “Kraftwerk2: A Fast Force-Directed Quadratic Placement Approach Using An Accurate Net Model,” in Proceedings of IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 27, no. 8, pages1398–1411, August 2008.
[2] J. R. Shewchuk. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. Technical Report CMU-CS-94-125, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, March 1994.
[3] M.-C. Kim, D.-J. Lee, I. L. Markov, “SimPL: An Effective Placement Algorithm,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 649–656, November 2010.
[4] J. Z. Yan, C. Chu, and W. K. Mak, “Safechoice: A Novel Approach to Hypergraph Clustering for Wirelength-Driven Placement,” in Proceedings of IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems (TCAD), vol. 30, no. 7, pages 1020–1033, July 2011.
[5] N. Viswanathan and C. C.-N. Chu, “Fastplace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 24, no. 5, pages 722–733, May 2005.
[6] X. He, T. Huang, L. Xiao, H. Tian, G. Cui, and E. Young, “Ripple: An Effective Routability-Driven Placer by Iterative Cell Movement,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 74–79, November 2011.
[7] C. Deng, Y. Cai, and Q. Zhou, “A Register Clustering Algorithm for Low Power Clock Tree Synthesis,” in Proceedings of IEEE international Symposium on Circuit and System(ISCAS), pages 389-392, June 2014
[8] Y. Wang, Q. Zhou, X. Hong, Y. Cai, “Clock-Tree Aware Placement Based on Dynamic Clock-Tree Building,” in Proceedings of IEEE International Symposium on Circuits and System(ISCAS), pages 2040-2043, May 2007
[9] D.-J. Lee, I. L. Markov, “Obstacle-Aware Clock-tree Shaping during Placement”, in Proceedings of IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD) vol.31, no. 2, pages 205-216, February 2012
[10] R. S. Tsay, “Exact Zero Skew,” in Proceeding of IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 336–339, November 1991.
[11] Y. Cheon, P.-H. Ho, A. B. Kahng†, S. Reda, Q. Wang, “Power-Aware Placement,” in Proceedings of IEEE/ACM Design Automation Conference (DAC), pages 795-800, June 2005.
[12] C. Chu. Chapter 11: Placement. In Electronic Design Automation: Synthesis, Verification, and Test, L.-T. Wang, Y.-W. Chang and K.-T. Cheng, Editors, Elsevier, 2009.
[13] C. Sechen and A. L. Sangiovanni-Vincentelli. “Timberwolf 3.2: A New Standard Cell Placement and Global Routing Package,” in Proceedings of IEEE/ACM Design Automation Conference (DAC), pages 432–439, June 1986.
[14] M. Wang, X. Yang, and M. Sarrafzadeh. “Dragon2000: Standard-Cell Placement Tool for Large Industry Circuits,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 260–263, November 2000.
[15] A. R. Agnihorti, S. Ono, C. Li, M. C. Yildiz, A. Khathate, C.-K. Koh, and P. H. Madden, “Mixed Block Placement via Fractional Cut Recursive Bisection,” in Proceedings of IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 24, no. 5, pages 748–761, May 2005.
[16] J. A. Roy, D. A. Papa, S. N. Adya, H. H. Chan, A. N. Ng, J. F. Lu, and I. L. Markov, “Capo: Robust and Scalable Open-Source Min-Cut Floorplacer,” in Proceedings of ACM International Symposium on Physical Design (ISPD), pages 224–226, April 2005.
[17] Z.-W. Jiang, B.-Y. Su, and Y.-W. Chang, “Routability-Driven Analytical Placement by Net Overlapping Removal for Large-Scale Mixed-Size Designs,” in Proceedings of IEEE/ACM Design Automation Conference (DAC), pages 167–172, June 2008.
[18] M.-K. Hsu, S. Chou, T.-H. Lin, and Y.-W. Chang, “Routability-Driven Analytical Placement for Mixed-Size Circuit Designs,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 80–84, November 2011.
[19] J. Cong, T. Chan, J. Shinnerl, K. Sze and M. Xie, “mPL6: Enhanced Multilevel Mixed-size Placement,” in Proceedings of ACM International Symposium on Physical Design (ISPD), pages 212–214, April 2006.
[20] J. Kleinhans, G. Sigl, F. Johannes, and K. Antreich, “Gordian: VLSI Placement by Quadratic Programming and Slicing Optimization,” in Proceedings of IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems (TCAD), pages 356–365, March 1991.
[21] U. Brenner and M. Struzyna, “Faster and Better Global Placement by A New Transportation Algorithm,” in Proceedings of IEEE/ACM Design Automation Conference (DAC), pages 591–596, June 2005.
[22] G.-J. Nam, S. Reda, C. J. Alpert, P. G. Villarrubia, and A. B. Kahng, “A Fast Hierarchical Quadratic Placement Algorithm,” in Proceedings of IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 25, no. 4, pages 678–691, April 2006.
[23] N. Viswanathan, G.-J. Nam, C. J. Alpert, P. Villarrubia, H. Ren, and C. Chu, “RQL: Global Placement via Relaxed Quadratic Spreading and Linearization,” in Proceedings of IEEE/ACM Design Automation Conference (DAC), pages 453–458, June 2007.
[24] X.-W. Shih, H.-C. Lee, K.-H. Ho and Y.-W. Chang, “High Variation-Tolerant Obstacle-Avoiding Clock Mesh Synthesis with Symmetrical Driving Trees,” in Proceeding of IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 452–457, November 2010.
[25] N. Viswanathan, C. Alpert, C. Sze, Z. Li, Y. Wei, “ICCAD-2012 CAD Contest in Design Hierarchy Aware Routability-Driven Placement and Benchmark Suite,” In Proc. ICCAD, pages 345-348, 2012.
[26] M. C. Kim, N. Viswanathan, Z. Li, C. Alpert, “ICCAD-2013 CAD Contest in Placement Finishing and Benchmark Suite,” In Proc. ICCAD, pp. , 2013
[27] M.Donno, E. Macci, and L. Mazzoni, “Power-Aware Clock Tree Planning,” in Proceedings of ACM International Symposium on Physical Design (ISPD), pages 138-147, April 2004.
[28] T.-H. Wu, “Design Hierarchy Aware Routability Driven Placement,” Master Thesis in NCTU, October 2012.
[29] H.-H. Chu, “Clock Tree Synthesis with Buffer Insertion/Sizing,” Master Thesis in NCTU, September 2013.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top