時脈偏移最佳化已經成為晶片製造過程中一個很重要的課題。為了克服製程、電壓、溫度變異所造成的影響，自動時脈偏移同步方案可以在晶片製造出來之後動態地調整並降低時脈偏移。在自動時脈偏移同步方案中有兩個主要的元件，分別是可調變延遲緩衝器以及相差偵測器。之前的研究大部分強調可調變延遲緩衝器放置的位置。在這篇論文中，我們提出由於實際的可調變延遲緩衝器及相差偵測器設計上有其物理上的限制，相差偵測器連接正反器的拓墣也會影響最後的時脈偏移。在這篇論文中，我們首先分析給定相差偵測器架構下最糟的時脈偏移量。接著，我們提出一個能夠產生最小時脈偏移之相差偵測器架構的演算法。我們的實驗結果非常地振奮人心。

Clock skew optimization has been an important concern in circuit designs. To overcome the influence caused by PVT variations, the automatic skew synchronization scheme can dynamically adjust and reduce the clock skew after a chip is manufactured. There are two key components in a skew synchronization scheme: Adjustable Delay Buffer (ADB) and Phase Detector (PD). Most previous researchers emphasize on ADB placement issues. In this thesis, we show that how FFs are connected by PDs can also greatly influence the final clock skew due to limitations of a practical ADB and PD design. We first analyze the worst-case clock skew of PD connection structures. Then we propose an algorithm to generate an optimal PD connection structures resulting in the minimum clock skew. Our experimental results are very encouraging.

Abstract i
List of Contents: ii
List of Figures: iii
List of Tables: iv
Chapter 1 INTRODUCTION 1
Chapter 2 THE EFFECT OF THE RESOLUTION SKEW AND THE SAMPLING SKEW BETWEEN TWO CONNECTING FFS 6
2.1 Clock Skew Caused by Sampling Clock Signals 8
2.2 Clock Skew Caused by ADB Limitations 10
2.3 The Intrinsic Skew of Two Directly Connecting FFs 12
Chapter 3 THE TREE STRUCTURE TO SYNCHRONIZE ALL FLIP FLOPS 13
Chapter 4 THE LARGEST INTRINSIC SKEW OF THE WHOLE CIRCUIT 15
4.1 The Intrinsic Skew of Two Synchronized Flip Flops 15
4.2 Finding the Maximum Intrinsic Skew of a Circuit 18
Chapter 5 PROBLEM FORMULATION AND THE OPTIMAL SPANNING TREE SOLUTION 21
5.1 Problem Formulation 22
5.2 The Optimal Spanning Tree Solution 25
Chapter 6 IMPLEMENTATION CONCERNS 28
6.1 Flip Flop Partitions of the Circuit for PD Connections 29
6.2 Computing the Intrinsic Skew between FFa and FFb 31
Chapter 7 EXPERIMENTAL RESULT 33
Chapter 8 CONCLUSION 38
REFERENCES 39

[1] Bang Ye Wu, "An improved algorithm for the k-source maximum eccentricity spanning trees," Discrete Applied Mathematics, 2004.
[2] Charles E. Dike, Nasser A. Kurd, Priyadarsan Patra, and Javed Barkatullah, "A design for digital, dynamic clock deskew," Digest of technical papers of the symposium on VLSI circuits, 2003.
[3] Charles J. Alpert, Anirudh Devgan, and Stephen T. Quay, "Buffer insertion with accurate gate and interconnect delay computation," Proceedings of the 36th ACM/IEEE conference on Design automation, 1999.
[4] Eiichi Takahashi, Yuji Kasai, Masahiro Murakawa, and Tetsuya Higuchi, "A post-silicon clock timing adjustment using genetic algorithms," Digest of technical papers of the symposium on VLSI circuits, 2003.
[5] George Geannopoulos, and Ximing Dai "An Adaptive Digital Deskewing Circuit for Clock Distribution Networks, "Digest of Technical Papers of IEEE International Solid-State Circuits Conference, 1998.
[6] H.B. McMahan, A. Proskurowski, "Multi-source spanning trees: algorithms for minimizing source eccentricities," Discrete Applied Mathematics, 2004.
[7] Jan-Ming Ho, D. T. Lee, Chia-Hsiang Chang, and C. K. Wong, "Minimum Diameter Spanning Trees and Related Problems," Society for Industrial and Applied Mathematics Journal on Computing, 1991.
[8] Jason Cong, Zhigang Pan, Lei He, Cheng-Kok Koh, and Kei-Yong Khoo, "Interconnect design for deep submicron ICs," Proceedings of the IEEE/ACM international conference on Computer-aided design, 1997.
[9] Jeng-Liang Tsai, and Lizheng Zhang and Charlie Chung-Ping Chen, "Statistical timing analysis driven post-silicon-tunable clock-tree synthesis," Proceedings of the IEEE/ACM International conference on Computer-aided design, 2005.
[10] John F. Ewen, Albert X. Widmer, Mehmet Soyuer, Kevin R. Wrenner, Ben Parker, and Herschel A. Ainspan, "Single-Chip 1062Mbaud CMOS Transceiver for Serial Data Communication," Proceedings of the IEEE International Solid-State Circuits Conference, 1995.
[11] Nasser A. Kurd, Javed S. Barkatullah, Rommel O. Dizon, Thomas D. Fletcher, and Paul D. Madland, "A Multigigahertz Clocking Scheme for the Pentium 4 Microprocessor," IEEE Journal of Solid State Circuits, vol. 36, 2001.
[12] Patrick Mahoney, Eric Fetzer, Bruce Doyle, Sam Naffziger, "Clock Distribution on a Dual-Core, Multi-Threaded Itanium-Family Processor," Proceedings of the IEEE International Solid-State Circuits Conference, 2005.
[13] Simon Tam, Rahul Dilip Limaye, and Utpal Nagarji Desai, "Clock Generation and Distribution for the 130-nm ItaniumR 2 Processor with 6-MB On-Die L3 Cache," IEEE Journal of Solid State Circuits, vol. 39, 2004.
[14] Simon Tam, Stefan Rusu, Utpal Nagarji Desai, Robert Kim, Ji Zhang, and Ian Young, "Clock generation and distribution for the first IA-64 microprocessor," IEEE Journal of Solid State Circuits, vol. 35, 2000.
[15] Ting-Hai Chao, Yu-Chin Hsu, Jan-Ming Ho, Kenneth D. Boese, Student Member, ZEEE, and Andrew B. Kahng, "Zero Skew Clock Routing with Minimum Wirelength," IEEE Transaction on Circuits and Systems II: Analog and Digital Signal Processing, vol. 39, 1992.
[16] Ting-Hai Chao, Yu-Chin Hsu, and Jan-Ming Ho "Zero skew clock net routing," Proceedings of the 29th ACM/IEEE conference on Design automation, 1992.
[17] Uday Padmanabhan, Janet Meiling Wang, Senior Member, IEEE, and Jiang Hu, "Robust Clock Tree Routing in the Presence of Process Variations," IEEE Transaction on Computer-aided Design of Integrated Circuits and Systems, VOL. 27, NO. 8, 2008.
[18] Vishal Khandelwal and Ankur Srivastava, "Variability-Driven Formulation for Simultaneous Gate Sizing and Postsilicon Tunability Allocation," IEEE Transaction on Computer-aided Design of Integrated Circuits and Systems, VOL. 27, NO. 4, 2008.
[19] Yi Wang, Wai-Shing Luk, Xuan Zeng, Jun Tao, Changhao Yan, Jiarong Tong, Wei Cai, and Jia Ni, "Timing Yield Driven Clock Skew Scheduling Considering non-Gaussian Distributions of Critical Path Delays," Proceedings of the 45th ACM/IEEE conference on Design automation, 2008.