臺灣博碩士論文加值系統

串音現象在深次微米電路設計中是一個影響電路效能的一個重要因素，在所有可能的串音干擾中，時脈是最重要的干擾源，也是最容易受到干擾的訊號。串音現象會增加時脈的抖動並進而降低系統的效應，而且在大部份的電路設計中總是會有一個以上的時脈訊號，有時甚至有數十個，所以建立時脈的樹狀結構並有效的預防串音現象是一個很重要的課題。這篇論文中我們將討論時脈與時脈之間的串音現象並提出有效的演算法來解決這個問題，論文中將包括如何建立時脈的樹狀結構，如何執行繞線，以及如何調整緩衝器的大小來降低時脈的耦合抖動現象。實驗的結果顯示應用我們所提出演算法比一般傳統的演算法能大幅的降低由於串音所造成的耦合抖動。

Crosstalk noise is a crucial factor affecting chip performance in deep submicron technologies. Among all possible crosstalk noise sources, clock is the most common aggressor as well as victim. Crosstalk on clock nets can increase coupling jitter, which may degrade significantly the system performance. Besides, in modern chip designs, there is usually more than one clock net, and sometimes even tens of them. It is therefore imperative to design clock topologies to prevent possible coupling jitter among them. In this Dissertation, we address the coupling jitter problem. We propose algorithms to design clock topology, perform routing minimizing effective coupling length, and size buffers to minimize jitter effect. The experimental results show a significant reduction of coupling jitter compared to the conventional clock tree synthesis which does not take into account the inter-clock coupling jitter effects.

第一章 簡介與背景……………………………………………………7
第二章 問題定義………………………………………………………9.
第三章 時脈樹的分割與連接線的配置………………………………11
第四章 最小耦合的兩點網路繞線器…………………………………13
第五章 實用的緩衝器大小調整技術…………………………………15
第六章 結論與後續工作………………………………………………17

C.J. Alpert, A. Devgan, and S.T. Quay, “Buffer Insertion for Noise and Delay Optimization,” IEEE Trans. Computer-Aided Design, Vol. 18, No.11, Nov. 1999, pp. 1633-45.
C.J. Alpert, A. Devgan, and S.T. Quay, “Buffer Insertion for Noise and Delay Optimization,” Proc. ACM/IEEE Design Automation Conference, pp.362-367, 1998.
K.D. Boese and A.B. Kahng, “Zero-Skew Clock Routing Trees with Minimum Wirelength,” Proc. ASIC Conference, pp.17-21, 1992.
T.H. Chao, Y.C. Hsu, and J.M. Ho, “Zero-Skew Clock Net Routing,” Proc. ACM/IEEE Design Automation Conference, pp.518-523, 1992.
T.H. Chao, Y.C. Hsu, J.M. Ho, K.D. Boese, and A.B. Khang, “Zero Skew Clock Routing With Minimal Wirelength,” IEEE Trans. Circuits and Systems, Vol.39, No.11, Nov. 1992, pp.799-814.
L.H Chen and M. Marek-Sadowska, “Aggressor Alignment for Worst-Case Crosstalk Noise,” IEEE Trans. Computer-Aided Design, Vol.20, No.5, May 2001, pp.612-621.
L.H. Chen, “Signal Integrity Issues in Deep Submicron Technology,” P.h.D Dissertation, University of California, Santa Barbara, 2001.
J. Cong, A.B. Kahng, and G. Robins, “Matching-based methods for high-performance clock routing,” IEEE Trans. Computer-Aided Design, Vol.12, No.8, Aug. 1993, pp.1157-1169.
J. Cong and K.K. Cheng, “Minimum-Cost Bounded-Skew Clock Routing,” Proc. IEEE International Symposium on Circuits and Systems, pp.215-218, 1995.
J. Cong, A.B. Kahng, K.K. Cheng, and C.W.A Tsao, “Bounded Skew Clock and Steiner Routing Under Elmore Delay,” Proc. International Conference on Computer Aided Design, pp.66-71, 1995.
W. Cook and A. Rohe, “Computing minimum-weight perfect matching,” INFORMS J. on Computing, Vol. 11, 1999, pp. 138-148.
O. Coudert, “Gate Sizing for Constrained Delay/Power/Area Optimization,” IEEE Trans. Very Large Scale Integration System, Vol.5, No.4, Dec 1997, pp.465-472.
F. Dartu and L.T. Pileggi, “Calculating Worst-Case Gate Delays Due to Dominant Capacitance Coupling,” Proc. ACM/IEEE Design Automation Conference, pp.46-51, 1997.
S. Dhar, M.A. Franklin, and D.F. Wann, “Reduction of Clock Delays in VLSI Structures,” Proc. IEEE International Conference on Computer Design, pp.778-783, 1984.
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, Jan.1948.
T. Gao and C.L. Liu, “Minimum Crosstalk Switchbox Routing,” Proc. IEEE International Conference on Computer-Aided Design, pp.610-615, 1994.
T.Gao and C.L. Liu, “Minimum Crosstalk Channel Routing,” IEEE Trans. Computer-Aided Design, vol.15, May 1996, pp.465-474,.
K. Holwerda,“http://www.xs4all.nl/~kholwerd/bool.html”.
M.F. Hsiao, M. Marek-Sadowska, and S.J Chen, “Crosstalk Minimization for Multiple Clock Tree Routing,” Proc. IEEE Midwest Symposium on Circuits and Systems, pp.152-155, Aug 2002.
M.F. Hsiao, M. Marek-Sadowska, and S.J. Chen, “A Crosstalk Aware Two-Pin Net Router,” Proc. IEEE International Symposium on Circuits and Systems, pp.485-488, May 2003.
M.F. Hsiao, M. Marek-Sadowska, and S.J. Chen, “Minimizing Inter-Clock Coupling Jitter,” Proc.International Symposium on Quality Electronic Design, pp.333-338, Mar 2003.
M.F. Hsiao, M. Marek-Sadowska, and S.J. Chen, “Minimizing Coupling Jitter By Buffer Resizing for Multiple Coupled Clock Networks,” Proc. IEEE International Symposium on Circuits and Systems, pp.509-512, May 2003.
K.C. Hsu, Y.C. Lin, P.X. Chiu, and T.M. Hsieh, “Minimum Crosstalk Channel Routing with Dogleg,” Proc. IEEE International Symposium on Circuit and System, pp.73-76, May 2000.
D. J.-H. Huang, A. B. Kahng, and C.-W. A. Tsao, “On the Bounded-Skew Clock and Steiner Routing Problems,” Proc. ACM/IEEE Design Automation Conference, pp.508-513, June 1995.
M.A.B Jackson, A. Srinnivasan, and E.S. Kuh, “Clock routing for high performance IC,” Proc. ACM/IEEE Design Automation Conference, pp.573-579, 1990.
A.B. Kahng, J. Cong, and G. Robins, “High-Performance Clock Routing Based on Recursive Geometric Matching,” Proc. ACM/IEEE Design Automation Conference, pp.573-579, 1991.
A.B. Kahng, J. Cong, and G. Robins, “Matching-based methods for high-performance clock routing,” Proc. ACM/IEEE Design Automation Conference, pp.322-327, 1991.
A.B. Kahng, and C.W.A Tsao, “More Practical Bounded Skew Clock Routing,” Proc. ACM/IEEE Design Automation Conference, pp.594-599, 1997.
R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh, “An Exact Algorithm for Coupling-Free Routing,” Proc. International Symposium on Physical Design, pp.10-15, 2001.
R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh, “Coupling Aware Routing,” Proc. IEEE ASIC/SOC Conference, pp.392-396, 2000S. Kirkpatrick, C. Gelatt, Jr., and M. Vecchi, “Optimization by Simulated Annealing,” Science, Vol.220, May 1983, pp.671-680.
B. Krauter, and D. Widiger, “Variable Frequency Crosstalk Noise Analysis: A Methodology to Guarantee Functionality from dc to fmax,” Proc. ACM/IEEE Design Automation Conference, pp.665-668, 2002.
K.W. Lee, and C. Sechen, “A New Global Router for Row-Based Layout,” Proc. International Conference on Computer-Aided Design, pp.180-183, 1988.
J. Rubinstein, P. Penfield, and M.A. Horowitz, “Signal Delay in RC tree Networks,” IEEE Trans. Computer-Aided Design, July, 1983, pp.202-211.
S.S. Sapatnekar, “A Timing Model Incorporating the Effect of Crosstalk on Delay and its Application to Optimal Channel Routing,” IEEE Trans. Computer-Aided Design, Vol.19, No.5, May 2000, pp.550-559.
R.S. Tsay, “Exact Zero Skew,” Proc. International Conference on Computer-Aided Design, pp.336-339, 1991.
R.S. Tsay, “An exact zero-skew clock routing algorithm,” IEEE Trans. Computer-Aided Design, Vol.12, No.2, Feb. 1993, pp.242-249.
H.P. Tseng, L. Scheffer, and C. Sechen, “Timing and Crosstalk-Driven Area Routing,” IEEE Trans. Computer-Aided Design, Vol.20, No.4, Apr. 2001, pp.528-544.
A. Vittal, L.H. Chen, M. Marek-Sadowska, K.P. Wang, and S. Yang, “Crosstalk in VLSI Interconnections,” IEEE Trans. Computer-Aided Design, Vol.18, No.12, Dec. 1999, pp.1817-1824.
D.F. Wann and M.A. Franklin, “Asynchronous and Clocked Control Structures for VLSI Based Interconnection Networks,” IEEE Trans. Computers, vol.21, Mar 1983, pp.284-293..
T. Xiao and M. Marek-Sadowska, “Efficient Delay Calculation in Presence of Crosstalk,” Proc. International Symposium on Quality Electronic Design, pp.491-497, 2000.
T. Xiao and M. Marek-Sadowska, “Gate Sizing to Eliminate Crosstalk Induced Timing Violation,” International Conference on Computer Design, pp.186-191, 2001.
T. Xiao and M. Marek-Sadowska, “Crosstalk Reduction by Transistor Sizing,” Proc. Asia and South Pacific Design Automation Conference, pp.137-140, 1999.
T. Xue, E.S. Kuh, and D. Wang, “Post Global Routing Crosstalk Risk Estimation and Reduction,” Proc. IEEE/ACM International Conference on Computer-Aided Design, pp.310-315, 1996.
T. Xue, E.S. Kuh, and D. Wang, “Post Global Routing Crosstalk Synthesis,” IEEE Trans. Computer-Aided Design, Vol.16, No.12, Dec. 1997, pp.1418-1430.
H. Zhou and D.F. Wong, “Global Routing with Crosstalk Constraints,” Proc. ACM/IEEE Design Automation Conference, pp.374-377, 1998.
H. Zhou and D.F. Wong, “Global Routing with Crosstalk Constraints,” IEEE Trans. Computer-Aided Design, Vol.18, No.11, Nov. 1999, pp.1683-1688.
H. Zhou and D.F. Wong, “An Optimal Algorithm for River Routing with Crosstalk Constraints,” Proc. IEEE/ACM International Conference on Computer-Aided Design, pp.310-315, 1996.