在高效能的VLSI同步電路上，時脈誤差會導致電路工作錯誤，建立一個零時脈誤差的時脈繞線是很重要的議題。DME(Deferred Merge Embedding)是最常見的時脈繞線建立法，它可有效的縮短總線段長。而不同的繞線結構亦可縮短總線段長，因此λ-幾何繞線提供了多種不同的繞線方向，如Manhattan-結構、Y-結構、X-結構及歐幾里得幾何。
本研究整合時脈繞線之設計流程，利用有效的叢集方式分群後，並以DME建立零時脈誤差的時脈繞線，最後用Suboptimize演算法來找出潛在的改進事件，調整中繼點，以此程序可建出總線段長較短的零時脈誤差的時脈繞線總且具有較小的連線延遲。經標準時脈Benchmark實驗後，數據顯示與同為X-architecture的繞線演算法比較，總線段長平均減少了14%；在功率消耗上平均減少了11.07%；在延遲時間上平均減少了28.79%。

In the high performance VLSI synchronous systems, clock skew might cause circuit work fault. To construct zero-skew clock routing is an important issue. The DME (Deferred Merge Embedding) algorithm is a popular method for zero-skew clock routing construction to shorten wirelength efficiently. There are various routing architectures for providing more available directions to reduce wirelength. λ-geometry routing allows new routing orientations, such as Manhattan-architecture, the Y-architecture, the X-architecture, and the Euclidean-geometry.
In this thesis we integrate the design flow of clock routing by utilizing efficient clustering algorithm, applying DME to construct zero-skew clock routing, and using our Suboptimize algorithm to improve the DME placement. The suboptimality can reduce wirelength and delay. The experimental results show that the Suboptimize algorithm achieves 14% reduction of wirelength, 11.07% reduction of power and 28.79% reduction of delay, compared with related X-architecture clock routing algorithms.

[1] A. I. Abou-Seido, B. Nowak, and C. Chu Fitted Elmore Delay: A Simple and Accurate Interconnect Delay Model, IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol.12, pp.691-696, 2007.
[2] H. B. Bakoglu, J. T. Walker, and J. D. Meindl, A symmetric clock distribution tree and optimized high-speed interconnections for reduced clock skew in VLSI and WEI circuits, Proc. IEEE Int. Conf. Computer Design: VLSI in Computer, vol. 19, pp. 118-122, 1986.
[3] H. B. Bakoglu, and Circuits, Interconnections, and Packaging for VLSI, Addison-Wesley, 1990.
[4] J. Burkis, Clock Tree Synthesis for High Performance ASICs, Proc. Of the 4th ASIC Conference and Exhibit, pp. p9-8.1-p9-8.3, 1991.
[5] H. Chen, C. K. Cheng, A. B. Kahng, I. Mandoiu, Q. Wang, and B. Yao, Estimation of Wirelength Reduction for λ-Geometry vs. Manhattan Placement and Routing, Proc. of the 2003 international workshop on System-level interconnect prediction, pp.71-76, 2003.
[6] H. Chen, C. K. Cheng, A. B. Kahng, I. Mandoiu, Q. Wang, and B. Yao, The Y-Architecture for On-Chip Interconnect: Analysis and Methodology, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol.24, pp.588-599, 2005.
[7] T. H. Chao, Y. C. Hsu, J. M. Ho, K. D. Boese, and A. B. Kahng, Zero-Skew Clock Routing with Minimum Wirelength, IEEE Trans. Circuits and Systems II: Analog and Digital Signal Processing, vol. 39, pp. 799-814, 1992.
[8] Nan-Chi Chou and Chung-Kuan Cheng, On General Zero-Skew Clock Net Construction, IEEE Trnas. on Very Large Scale Integration (VLSI) Systems, vol. 3, p.141-146.
[9] M. Edahiro, A Clustering-Based Optimization Algorithm in Zero-Skew Routings, Proc. ACM/IEEE Design Automation Conference, pp. 612-616, 1993.
[10] W. C. Elmore, The transient response of damped linear networks with particular regard to wide-band amplifiers, Journal Applied Physics, vol. 19, pp. 55-63, 1948.
[11] E. G. Friedman, Clock distribution networks in VLSI circuits and systems, A selected reprint volume, IEEE Press, 1995.
[12] M. A. B. Jackson, A Srinivasan, and E. S. Kuh, Clock Routing for High Performance ICs, Proc. ACM/IEEE Design Automation Conference, pp. 573-579, 1990.
[13] A. B. Kahng, J. Cong, and G. Robins, High-Performance Clock Routing Based on Recursive Geometric Matching, Proc. of the 28th ACM/IEEE Design Automation Conference, pp. 322-327, 1991.
[14] T. Mitsuhashi, T. Aoki, M. Murakata, and K. Yoshida, Physical Design CAD in Deep Sub-micron Era, Proc. of European on Design Automation Conference and Exhibition, pp. 350-355, 1996.
[15] J. Oh, and M. Pedram, Gated Clock Routing for Low-Power Mircoprocessor Design, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, pp.715-722, 2001.
[16] F. P. Preparata, and M. I. Shamos, Computational Geometry: An Introduction, Spring-Verlag, New York, 1985.
[17] W. Shen, Y. Cai, J. Hu, X. Hong, and B. Lu, High Performance Clock Routing in X-architecture, IEEE International Symposium on Circuits and Systems, pp.2081-2084, 2006
[18] W. Shen, Y. Cai, X. Hong, J. Hu, and B. Lu, Zero Skew Clock Routing in X-architecture Based on An Improved Greedy Matching Algorithm, Integration, the VLSI Journal, vol.41, pp.426-438, 2007
[19] N. Sherwani, Algorithms for VLSI Physical Design Automation, 2nd Ed., Kluwer Academic Publishers, 1995.
[20] A. Takahashi and Y. Kajitani, Performance and Reliability Driven Clock Scheduling of Sequential Logic Circuits, Proc. of the ASP-DAC '97. Asia and South Pacific, pp. 37-42, 1997.
[21] R. S. Tsay, An Exact Zero-Skew Clock Routing Algorithm, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 242-249, vol. 12, 1993.
[22] C. H. Wang, and W. K. Mak, λ-Geometry Clock Tree Construction with Wirelength and Via Minimization. International Symposium on VLSI Design Automation and Test, pp.1-4, 2007.
[23] http://www.xinitiative.org/