在高效能的同步設計中，時鐘樹的合成是非常重要的步驟，隨著製程科技的進步，如何建立一個能夠適應製程變異的時鐘樹變得越來越重要。在2009 ISPD競賽中，主辦單位使用CLR這個值去判定一棵時鐘樹適應製程變異的能力。因此在這篇論文中，我們根據DME演算法去發展一個有效率的演算法來建立一棵時鐘樹並且考慮CLR。不同於傳統的方法在線段合併的步驟會建立一個完全圖(complete graph)，我們根據線段的分佈情形去建立一個生成圖(spanning graph)，如此一來可以成功且有效地減少圖形的連線，因此我們的方法執行時間比使用完全圖的方法還要快。除此之外，為了得到更準確的訊號變化率，我們在插入緩衝器的方法，則是採用考慮訊號變化率限制來取代傳統只考慮負載電容的技術。此外，為了達到最小化CLR的目的，我們會廣泛的使用較窄的線和較大的緩衝器。實驗結果顯示我們的演算法在執行時間上比使用完全圖的演算法來得快。

Clock tree synthesis is a very important stage in high-performance synchronous design. As process technology advances, building a robust clock tree that can adapt process variation becomes more and more important. In ”2009 ACM ISPD Clock Network Synthesis Contest”, they propose to use clock latency range(CLR) for the judgement of robustness of a clock tree against process variation. Thus, in this thesis, we develop an efficient algorithm to build a clock tree that considers CLR based on the Deferred-Merge Embedding algorithm (DME). Unlike traditional methods which have to build a complete graph in segment merging phase, we propose to build a spanning graph according to the distribution of segments, which can significantly reduce number of edges. Thus, our algorithm can run much faster than the methods using a complete graph. Besides, for getting more accurate values of slews, we adopt slew-constrained buffering technique instead of using traditional buffering methods which can only consider capacitance loading. Moreover, in order to minimize the CLR, we widely used narrow wires and big buffers. The experimental results show that our algorithm achieves better results in terms of the CPU runtime compared the with method using a complete graph.

[1] Hai Zhou, Narendra V. Shenoy, and William Nicholls. “Efficient minimum spanning tree construction without delaunay triangulation,” In Proc. of ASP-DAC, 2001, pp. 192-197.
[2] C. N. Sze, P. Restle, G. J. Nam, and C. Alpert, “ISPD2009 clock network synthesis contest,” In Proc. of ISPD, 2009, pp. 149-150.
[3] Dhar, Franklin, and Wang, “Reduction of clock delays in VLSI structure” In Proc. Of ICCD, 1984, pp. 778-783.
[4] M. A. B. Jackson, A. Srinivasan, and E. S. Kuh, “Clock routing for high-performanceICs,” In Proc. of DAC, 1990, pp. 573-579.
[5] A. B. Kahng, J. Cong, and G. Robins, “High-performance clock routing based on recursive geometric matching,” In Proc. of DAC, 1991, pp. 322-327.
[6] Cong, Kahng, Robins, “Matching based models for high-performance clock routing,” In Proc. of TCAD, 1993.
[7] R. S. Tsay, “Exact zero skew,” In Proc. of ICCAD, 1991, pp. 336-339.
[8] T. H. Chao, Y. C. Hsu, J.M. Ho, K. D. Boese, and A. B. Kahng, “Zero skew clock routing with minimum wirelength,” In Proc. of ASIC, 1992, pp. 799-814.
[9] Y. P. Chen and D. F. Wong, “An algorithm for zero-skew clock tree routing with buffer insertion,” In Proc. of EDAC, 1996, pp. 230-236.
[10] A. Vittal and M.Marek-Sadowska, “Power optimal buffered clock tree design,” In Proc.of DAC, 1996, pp. 497-502.
[11] I. M. Liu, T. L. Chou, D. F. Wong, and A. Aziz, “Zero-skew clock tree construction by simultaneous routing, wire sizing and buffer insertion,” In Proc. of ISPD, 2000, pp. 33-38.
[12] M. Edahiro, “A clustering-based optimization algorithm in zero-skew routings,” In Proc. of DAC, 1993, pp. 612- 616.
[13] R. S. Shelar, “An efficient clustering algorithm for low power clock tree synthesis,” In Proc. of ISPD, 2007, pp. 181-188.
[14] S. Lin and C. K.Wong, “Process-variation-tolerant clock skew minimization,” In Proc. of ICCAD, 1994, pp. 284-288.
[15] P. J. Restle, T. G. McNamara, D. A. Webber, P. J. Camporese, K. F. Eng, K. A. Jenkins, D. H. Allen,M. J. Rohn,M. P. Quaranta, D.W. Boerstler, C. J. Alpert, C. A. Carter, R. N. Bailey, J. G. Petrovick, B. L. Krauter, and B. D. McCredie, “A clock distribution network for microprocessors,” In Proc. of SSC, 2001, pp. 792-799.
[16] A. D. Mehta, Y. P. Chen, N. Menezes, D. F. Wong, and L. T. Pileggi, “Clustering and loading balancing for buffered clock tree synthesis,” In Proc. of ICCAD, 1997, pp. 217-223.
[17] A. Rajaram, J. Hu, and R. Mahapatra, “Reducing clock skew variability via crosslinks,” In Proc. of DAC, 2004, pp.18-23.
[18] X.W. Shih, C. C. Cheng, Y. K. Ho, and Y.W. Chang, “Blockage-avoiding buffered clock tree synthesis for clock latency-range and skew minimization,” In Proc. of ASP-DAC, 2010, pp. 395-400.
[19] J. W. Lu, W. K. Chow, C. W. Sham, and F. Y. Young, “A dual-MST approach for clock network synthesis,” In Proc. of ASP-DAC, 2010, pp. 467-473.
[20] W. H. Liu, Y. L. Li, and H. C. Chen, “Minimizing clock latency range in robust clock tree synthesis,” In Proc. of ASP-DAC, 2010, pp. 389-394.
[21] D. Lee and I. L. Markov, “Contango: Integrated optimization of SoC clock network,” In Proc. of EDAC, 2010, pp. 1468- 1473.
[22] S. Hu, C. J. Alpert, J. Hu, S. K. Karandikar, Z. Li,W. Shi, and C. N. Sze, “Fast algorithms for slew-constrained minimum cost buffering,” In Proc. of TCAD, 2007, pp. 2009-2022.
[23] C. V. Kashyap, C. J. Alpert, F. Liu, and A. Devgan, “Closed form expressions for extending step delay and slew metrics to ramp inputs,” In Proc. of ISPD, 2003, pp. 24-31.
[24] H. B. Bakoglu, Circuits, Interconnects, and Packaging for VLSI. Reading, MA: Addison- Wesley, 1990.
[25] W. C. Elmore, “The transient response of damped linear networks with particular regard to wide-band amplifiers,” In Proc. of Applied Physics, 1948, pp. 55-63.
[26] C. N. Sze, P. Restle, G. J. Nam, and C. Alpert, “ISPD2009 clock network synthesis contest,” In Proc. of ISPD, 2009, pp. 149-150.
[27] S. Chou, C. S. Han, P. K. Huang, K. F. Tien, T. Y. Ho, “An Effective and Efficient Framework for Clock Latency Range Aware Clock Network Synthesis,” In Proc. of TCAD, 2011, pp. 1045-1057.
[28] X. W. Shih, H. C. Leey, K. H. Ho, and Y. W. Chang, “High Variation-Tolerant Obstacle- Avoiding Clock Mesh Synthesis with Symmetrical Driving Trees,” In Proc. of ICCAD, 2010, pp. 452-457