本論文，在系統晶片中我們提出了一個採用了1) FED(Fitted Elmore Delay) 延遲模型所導出的非直線型的分接點，結合2)利用粒子群最佳化(Particle Swarm Optimization, PSO)演算法的優化特性，將時脈繞線的連線形狀由類H型變成類X型，找出四點的最佳分接點，達到在零時脈傾斜(Zero Clock Skew)下，有效的減少時脈繞線的總線段長和時脈延遲(Clock Delay)的目的。
我們提出「最佳化演算法應用於時脈繞線之實現」的方法，實驗證明顯示此方法，跟傳統λ-Geometry DME routing方法比較，在同樣的測試例子下，及在達到零時脈傾斜(Zero Clock Skew)下，有效的減少時脈繞線的總線段長19%~5%和時脈延遲(Clock Delay) 14%~-22%。證明了將H形狀轉成X形狀是可行的並且有效。

關鍵詞 : 時脈樹、零時脈傾斜、時脈延遲、粒子群最佳化演算法

In this paper in the system on chip design, we propose a method to determine a nonlinear branch connection location in the timing pulse wiring design that is 1) based on Fitted Elmore Delay model and it then combines 2) the evolution characteristics of the Particle Swarm Optimization (PSO) algorithm to change the connection topology of timing pulse wiring from H shape to X shape; it determine and finds, under the requirement of Zero Clock Skew, the best branch location in the X shape wiring. With this design it can effectively reduce the total required wire length of the timing pulse wiring and reduce the overall timing pulse delay.
  We propose the methodology of ‘Optimization Algorithm Applied to Zero Skew Clock Tree Implementation’ and from many test experiments  under the requirement of Zero Clock Skew it reveals that our proposed design algorithm, comparing with the conventional λ-Geometry DME routing method, can effectively reduce the total wiring length of the timing pulse wiring by 5% ~ 19% and clock delay by 14%~-22% ; consequently it appears that our proposed algorithm by changing the conventional H shape into X shape in the wiring design is a realizable and effective design methodology.

目錄
第一章	緒論 ..............................................1
1.1 研究動機與目的 ..........................................1
1.2 回顧時脈繞線相關背景知識...................................4
	1.2.1 時脈設計方法...................................4
	1.2.2 各種時脈繞線法.................................5
1.3 論文章節內容簡述..........................................7
第二章	延遲模型............................................9
2.1 導論...................................................9
2.2 FED延遲模型.............................................9
2.2.1 直線型的分接點........................................10
2.2.2 非直線型的分接點.......................................12
第三章	時脈繞線法.........................................15
3.1	叢集方式...........................................15
	3.1.1導論.........................................15
	3.1.2 MMM(Method of means and Medians)...........15
3.2 最佳化演算法應用於時脈繞線................................17
	3.2.1導論.........................................17
	3.2.2 PSO應用於時脈繞線之實現........................19
第四章	實驗結果...........................................22
4.1模擬參數及測試例子設定....................................22
4.2模擬與效能分析...........................................24
第五章	結論與未來展望......................................33
參考文獻..................................................36

圖目錄
圖1.1 典型的SoC結構圖與系統時脈的關係...........................2
圖1.2 SoC的時脈延遲.........................................2
圖1.3 SoC的時脈傾斜.........................................3
圖1.4 時脈週期的等效邏輯圖....................................4
圖1.5 實驗流程圖............................................8
圖2.1 以FED延遲模型表示的單一導線線段..........................10
圖2.2 以FED延遲模型表示合併兩個子樹............................11
圖2.3 FED模型加入Snaking的意示圖.............................12
圖2.4 直線型的分接點與非直線型的分接點的示意圖...................12
圖2.5 四點對角線的交點.......................................14
圖2.6 四點X型與H型的繞線的示意圖..............................14
圖3.1 MMM procedure code..................................16
圖3.2 MMM分群法實例.........................................17
圖3.3 H形狀與X形狀的示意圖...................................18
圖3.4 PSO應用於時脈繞線之實現流程圖...........................21
圖4.1 測試例子8點(MMM+DME).................................25
圖4.2 測試例子8點(Optimization Algorithm)..................26
圖4.3 測試例子16點(MMM+DME)................................27
圖4.4 測試例子16點(Optimization Algorithm).................28
圖4.5 測試例子32點(MMM+DME)................................29
圖4.6 測試例子32點(Optimization Algorithm).................30
圖4.7 測試例子64點(MMM+DME)................................31
圖4.8 測試例子64點(Optimization Algorithm).................32
圖5.1 對稱分群後示意圖......................................34
圖5.2 不對稱分群示意圖......................................34

表目錄
表4.1 Fitted Elmore Delay(FED)延遲模型模擬參數設定............22
表4.2粒子群最佳化演算法模擬參數設定.............................23
表4.3 測試例子模擬參數設定....................................23
表4.4 連線長度比較..........................................24
表4.5 延遲時間比較..........................................24

[1].	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.
[2].	Burkis, J. , "Clock tree synthesis for high performance ASICs," ASIC Conference and Exhibit, 1991. Proceedings., Fourth Annual IEEE International , vol., no., pp.P9-8/1-3, 23-27 Sep 1991
[3].	Friedman, E.G. , "Clock distribution design in VLSI circuits-An overview," Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International Symposium on , vol., no., pp.1475-1478 vol.3, 3-6 May 1993
[4].	Jackson, M.A.B., Srinivasan, A., Kuh, E.S., , "Clock routing for high-performance ICs," Design Automation Conference, 1990. Proceedings., 27th ACM/IEEE , vol., no., pp.573-579, 24-28 Jun 1990
[5].	Kahng, A., Cong, J., Robins, G., , "High-performance clock routing based on recursive geometric matching," Design Automation Conference, 1991. 28th ACM/IEEE , vol., no., pp.322-327, 1991
[6].	Ting-Hai Chao, Yu-Chin Hsu, Jan-Ming Ho, Kahng, A.B., , "Zero skew clock routing with minimum wirelength," Circuits and Systems II: Analog and Digital Signal Processing, IEEE Transactions on , vol.39, no.11, pp.799-814, Nov 1992
[7].	Edahiro, M. , "A Clustering-Based Optimization Algorithm in Zero-Skew Routings," Design Automation, 1993. 30th Conference on , vol., no., pp. 612- 616, 14-18 June 1993
[8].	Tsay, R.-S. , "Exact zero skew," Computer-Aided Design, 1991. ICCAD-91. Digest of Technical Papers., 1991 IEEE International Conference on , vol., no., pp.336-339, 11-14 Nov 1991
[9].	Elmore, W. C. , "The Transient Response of Damped Linear Networks with Particular Regard to Wideband Amplifiers," Journal of Applied Physics , vol.19, no.1, pp.55-63, Jan 1948
[10].	Abou-Seido, A.I., Nowak, B., Chu, C., , "Fitted Elmore delay: a simple and accurate interconnect delay model," Very Large Scale Integration (VLSI) Systems, IEEE Transactions on , vol.12, no.7, pp. 691- 696, July 2004
[11].	Hongyu Chen, Bo Yao, Feng Zhou, Chung-Kuan Cheng , "Physical planning of on-chip interconnect architectures," Computer Design: VLSI in Computers and Processors, 2002. Proceedings. 2002 IEEE International Conference on , vol., no., pp. 30- 35, 2002
[12].	Hongyu Chen, Chung-Kuan Cheng, Kahng, A.B., Mandoiu, I.I., Qinke Wang, Bo Yao , "The Y  architecture for on-chip interconnect: analysis and methodology," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , vol.24, no.4, pp. 588- 599, April 2005
[13].	Weixiang Shena, Yici Caia, Jiang Hu, Xianlong Honga, Bing Lu , "High performance clock routing in X-architecture," Circuits and Systems, 2006. ISCAS 2006. Proceedings. 2006 IEEE International Symposium on , vol., no., pp.4 pp.
[14].	C. C. Tsai, C. C. Kuo, T. Y. Lee, and J. O. Wu, “X-architecture clock tree construction associated with buffer insertion and sizing,” in Proc. IEEE ASQED, July, 2009, pp. 298-303.
[15].	C. C. Tsai, C. C. Kuo, J. O. Wu, T. Y. Lee, and R. S. Hsiao, “X-clock routing based on pattern matching,” in Proc. IEEE SOCC, Sept. 2008, pp. 357-360.
[16].	C. C. Tsai, C. C. Kuo, L. J. Gu, and T. Y. Lee, “Antenna violation avoidance/fixing for X-clock routing,” in Proc. IEEE ISQED, Mar., 2010, pp. 508-514.
[17].	C. C. Tsai, C. C. Kuo, L. J. Gu, and T. Y. Lee, “Double-via Insertion Enhanced XArchitecture Clock Routing for Reliability,” in Proc. IEEE ISCAS, May, 2010, pp.3413-3416.
[18].	Xu Jun, Huiyou Chang , "The Discrete Binary Version of the Improved Particle Swarm Optimization Algorithm," Management and Service Science, 2009. MASS '09. International Conference on , vol., no., pp.1-6, 20-22 Sept. 2009
[19].	Youxin Luo, Xiaoyi Che , "Chaos Immune Particle Swarm Optimization Algorithm with Hybrid Discrete Variables and its Application to Mechanical Optimization," Intelligent Information Technology Application Workshops, 2009. IITAW '09. Third International Symposium on , vol., no., pp.190-193, 21-22 Nov. 2009
[20].	Supratid, I.M. , "A Multi-Subpopulation Particle Swarm Optimization: A Hybrid Intelligent Computing for Function Optimization ," Natural Computation, 2007. ICNC 2007. Third International Conference on , vol.5, no., pp.679-684, 24-27 Aug. 2007
[21].	Lin Lu, Qi Luo, Jun-yong Liu, Chuan Long , "An improved particle swarm optimization algorithm," Granular Computing, 2008. GrC 2008. IEEE International Conference on , vol., no., pp.486-490, 26-28 Aug. 2008
[22].	Jiao Wei, Liu Guangbin, Liu Dong , "Elite Particle Swarm Optimization with mutation," System Simulation and Scientific Computing, 2008. ICSC 2008. Asia Simulation Conference - 7th International Conference on , vol., no., pp.800-803, 10-12 Oct. 2008
[23].	Hongbing Zhu, Chengdong Pu, Eguchi, K., Jinguang Gu , "Euclidean Particle Swarm Optimization," Intelligent Networks and Intelligent Systems, 2009. ICINIS '09. Second International Conference on , vol., no., pp.669-672, 1-3 Nov. 2009
[24].	Fan Chunxia, Wan Youhong , "An adaptive simple particle swarm optimization algorithm," Control and Decision Conference, 2008. CCDC 2008. Chinese , vol., no., pp.3067-3072, 2-4 July 2008
[25].	Zhixiang Hou , "Hammerstein Model Identification Based on Adaptive Particle Swarm Optimization," Intelligent Information Technology Application, Workshop on , vol., no., pp.137-140, 2-3 Dec. 2007
[26].	Zhi-Xiang Hou , "Wiener model identification based on adaptive particle swarm optimization," Machine Learning and Cybernetics, 2008 International Conference on , vol.2, no., pp.1041-1045, 12-15 July 2008
[27].	VLSI CAD Laboratory, University of California, San Diego, “Bounded-skew clock tree routing version 1.0,” May 2000,vlsicad.ucsd.edu/GSRC/bookshelf/Slots/BST/
[28].	D. J.-H. Huang, A. B. Kahng, and C.-W. A. Tsao, "On the Bounded-Skew Clock and Steiner Routing Problems", Proc. 32nd ACM/IEEE Design Automation Conf., San Francisco, June 1995, pp. 508-513.
[29].	J. Cong, A. B. Kahng, C.-K. Koh, and C.-W. A. Tsao, "Bounded-Skew Clock and Steiner Routing Under Elmore Delay", Proc. IEEE Intl. Conf. on Computer Aided Design, San Clara, November 5-9, 1995, pp. 66-71.
[30].	J. Cong, A. B. Kahng, C.-K. Koh and C.-W. A. Tsao, ``Bounded-Skew Clock and Steiner Routing', ACM Trans. on Design Automation of Electronic Systems, Vol. 4, No. 1, January, 1999.