混合架構時鐘樹合成考慮障礙避免之整體電容最小化｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	何俊瑋 Chun-Wei Ho
論文名稱：	混合架構時鐘樹合成考慮障礙避免之整體電容最小化 Total Capacitance Minimization Clock Synthesis with Blockage-Avoiding Hybrid-Structure Network
指導教授：	方劭云 Shao-Yun Fang
口試委員:	李毅郎 Yih-Lang Li 劉一宇 Yi-Yu Liu 王乃堅 Nai-Jian Wang
學位類別：	碩士 Master
系所名稱：	電資學院 - 電機工程系 Department of Electrical Engineering
論文出版年：	2017
畢業學年度：	105
語文別：	英文
論文頁數：	64
中文關鍵詞：	實體設計、時鐘樹合成、混和架構時鐘樹、樹狀結構時鐘樹、網狀結構時鐘樹、避障礙物繞線
外文關鍵詞：	Physical Design, Clock Tree Synthesis, Hybrid-structure Clock Synthesis, Tree-based Clock Synthesis, Mesh-based Clock Synthesis, Obstacle-avoiding Routing
相關次數：	點閱：337 下載：6
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

電路時序延遲逐漸成為決定電路效能的重要因素，時鐘樹的設計也日益重要。樹狀結構時鐘樹(tree-based clock network)由於擁有容易實現與分析的優勢，因此特別適合用於規模較小之晶片實作。然而，進入奈米世代，電路製程變異對電路時序有極大的影響，樹狀結構時鐘樹便不敷使用。網狀結構時鐘樹(mesh-based clock network)因其擁有相較於樹狀結構時鐘樹較多的共有通道(sharing path)，使得網狀結構擁有較佳的抗製程變異之能力。但是過多的共有通道使得網狀結構時鐘樹會消耗過多的能源，進而降低晶片效能。本論文提出使用混和架構時鐘樹(hybrid-structured clock network)結合樹狀結構及網狀結構時鐘樹之優點，設計時鐘樹電路。給定一電路元件佈局，我們首先針對底層(leaf-level)之網狀結構製造。針對網狀結構進行優化以及電路元件之分配，達到負載平衡以維持緩衝器(buffer)之驅動能力。接著針對上層架構(top-level)，我們考慮障礙物避免之繞線(obstacle-avoiding routing)。針對障礙物避免之繞線，首先建立生成圖(spanning graph)，接著利用Dijkstra演算法搜尋最短路徑，建立繞線路徑。為符合電路設計限制，緩衝器擺置於上層樹狀電路，增加電路可靠度。實驗結果顯示，混和架構能有效降低整體電容量，進而降低電路功率消耗。

Circuit delay has become a crucial concern in high performance VLSI system, and is increasingly affected by process variation at nano-node technologies. Additionally, power dissipation of clock tree should be minimized in order to meet the system power requirement. Clock distribution networks share a huge portion of power among all chip elements. The power consumption of the clock distribution network can account for up to 40\% of the entire chip power budget. The tradeoff between the circuit delay and power consumption is hard to be dealt with. In addition, as the technology node scale below 65nm, the on-chip-variation (OCV) has become a serious concern, especially for the skew of clock network. Since the higher skew has the negative influence on the maximum clock frequency, reducing the skew variation can improve timing yield. Among the different methods suggested for process, voltage and temperature (PVT) variations reduction, clock mesh provides high robustness to variations due to the redundant path. However, clock meshes suffer from several drawbacks such as high power dissipation, difficulty in analyzing and automating because of multiple paths and many mesh nodes. By contrast, conventional clock tree structure is commonly used due to low power consumption, less routing resource usage. Nevertheless, a tree-based network is highly sensitive to PVT variations.
In this thesis, we propose to use the hybrid structure that combines tree-based and mesh-based structures for power and skew trade-off methodology. First, the mesh pitch is determined initially that is based on the local skew distance provided by the ISPD 2010 contest. Next, the sink loading contained in each lattice is evaluated. If the maximum sink loading within each mesh lattice is too large to be driven by the biggest size buffer, the pitch size will be re-compute in order to shrink until the sink loading is drivable. Then, we propose a mesh loading balance algorithm to minimize the difference of sink loading in each lattice.
While the construction of the mesh is settle down, the local tree in each lattice will be constructed and the local tree root will simply connect to the nearest mesh stub as the tapping point. We will treat the tapping points as the top-level tree sinks for building the top-level tree, and then we adopt extended-DME algorithm to handle the obstacle routing. Experimental results suggest that hybrid-structured clock network can minimize the total capacitance under skew constrains.

Acknowledgements                                                                   iv
Abstract (Chinese)                                                                  v
Abstract                                                                          vii
List of Tables                                                                     xi
List of Figures                                                                   xii
Chapter 1. Introduction                                                             1
1 Introduction to clock routing . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Clock Tree Synthesis  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Tree-base Clock Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Mesh-based Clock Synthesis . . . . . . . . . . . . . . . . . . . . . . . . .  5
3 Related Work  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1 Pathlength-based Clock Tree Synthesis . . . . . . . . . . . . . . . . . . . . 7
3.2 RC-delay Based Clock Tree Synthesis  . . . . . . . . . . . . . . . . . . . . 11
4 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Chapter 2. Preliminaries                                                           18
1 Deferred Merge Embedding . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 Non-linear Delay Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Local Clock Skew . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4 Problem Formulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Chapter 3. Total capacitance minimization clock synthesis with blockage-avoiding
hybrid-structure network                                                           23
1 Algorithm Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 Mesh Size Determination  . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Loading Balance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 Mesh Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 Local Tree Construction  . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.1 Balance Bipartition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.2 Bottom-Up Phase: The Tree of Merging Segments. . . . . . . . . . . . . . . . 32
5.3 Top-Down Phase: Embedding of Nodes . . . . . . . . . . . . . . . . . . . . . 32
6 Top-Level Tree Construction  . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.1 Merging segment Shortening . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.2 Obstacle-Avoiding Routing  . . . . . . . . . . . . . . . . . . . . . . . . . 38
7 Buffer Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Chapter 4. Experimental Results                                                    41
1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2 Hybrid-Structure Clock Network Results . . . . . . . . . . . . . . . . . . . . 41
3 Loading Balance  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Chapter 5. Conclusions and Future Work                                             46
Bibliography                                                                       48
                                

[1] Y. Cheon, P.H. Ho, A.B. Kahang, S. Reda, and Q. Wang “Power-Aware Placement,”
in Proceedings of ACM/EDAC/IEEE Design Automation Conference
(DAC) , pp. 795-880, 2005.
[2] M. Donno, E. Macci, and L. Mazzoni “Power-Aware Clock Tree Planning,” in
Proceedings of ISPD, pp. 138-147, 2004.
[3] A. Vittal, M. Marek-Sadowska “Low-Power buffered block tree design,” in
Proceedings of 2016 IEEE/ACM International Conference on Computer-Aided
Design (ICCAD) , pp. 965-975, 1997.
[4] S. Dhar, M. Franklin, and D. Wann “Reduction of clock delay in VLSI
structure,” in Proceedings of 2016 IEEE/ACM International Conference on
Computer-Aided Design (ICCAD) , pp. 778-783, 1984.
[5] M.A.B. Jackson, A. Srinivasan, and E.S. Kuh “Clock routing for highperformance
ICs,” in Proceedings of the 27th ACM/IEEE Design Automation
Conference (DAC) , pp. 573-579, 1990.
[6] A. Kahng, J. Cong, and G. Robins “High-performance clock routing based on
recursive geometric matching,” in Proceedings of the 28th ACM/IEEE Design
Automation Conference , pp. 322-327, 1991.
[7] J. Cong, A. Kahng and G. Robins “Matching based model for high performance
clock routing,” in Proceedings of IEEE Transactions on Computer-Aided Design
of Integrated Circuits and Systems , pp. 1157-1169, 1993.
[8] R.S. Tsay “Exact zero skew,” in Proceedings of IEEE International Conference
on Computer-Aided Design , pp. 336-339, 1991.
[9] 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 Proceedings
of IEEE/ACM International Conference on Computer-Aided Design ,
pp. 452-457, 2010.
[10] H. Xin, H. Xu and L. Yujing “Implementation of clock network based on clock
mesh,” in Proceedings of International Conference on Information Technology
and Management Innovation , pp. 739-744, 2015.
[11] T.H. Chao, Y.C. Hsu and J.M. Ho et al. “Zero skew clock routing with minimum
wirelength,” in Proceedings of IEEE Transctions on Circuit and System , pp.
799-813, 1992.
[12] W.C. Elmore “The Transient Response of Damped Linear Networks with Particular
Regard to Wideband Amplifiers,” in Proceedings of Journal of Applied
Physics , pp. 55-63, 1948.
[13] R. Gupta, B. Tutuianu and L.T. Pileggi “The Elmore delay as a bound for RC
trees with generalized input signals,” in Proceedings of IEEE Transactions on
the Computer-Aided Design of Integrated Circuits and Systems , Volume: 16,
Issue: 1, pp. 95-104, 1997.
[14] P. Restle, T. McNamara, D. Webber, et al. “A clock distribution network for
microprocessors,” in Proceedings of IEEE Journal of Solid-State Circuit , vol.
36, no. 5, pp. 792-799, 2001.
[15] D.F. Wong and C.L. Liu “A new algorithm for floorplan design,” in Proceedings
of IEEE/ACM Design Automation Conference , pp. 101-107, 1986.
[16] L. Xiao, Z. Xiao and Z. Qian “Local clock skew minimization using blockageaware
mixed tree-mesh clock network,” in Proceedings of IEEE/ACM International
Conference on Computer-Aided Design (ICCAD) , pp. 458-462, 2010.
[17] H. Huang, W.S. Luk, W. Zhao and X. Zeng “DME-based clock routing in the
presence of obstacles,” in Proceedings of 2007 7th International Conference on
ASIC , pp. 1225-1228, 2007.
[18] ISPD 2010 high performance clock network synthesis contest.
ACM SIGDA and Intel Corporation. Available:
http://www.sigda.org/ispd/contests/10/ispd10cns.html

簡易檢索 / 詳目顯示

相關論文