在各種電路最佳化裡電路時間分析扮演相當重要的角色，找出同時滿足功能需求與時間需求的輸入向量稱為時間自動測試向量產生器，一個時間自動測試向量產生器的演算法將會找出在模擬之後同時滿足功能需求與時間需求的輸入向量，先前許多與時間分析的相關研究都使用時間自動測試向量產生器當作解決問題核心的技術，像有串音干擾(crosstalk)、最大瞬間電流，但盡管時間自動測試向量產生器是這麼地有用，但是傳統上的時間自動測試向量產生器速度相當慢並且不能夠處理很大的電路，這我們的論文中，我們提出很有效的方法來建構出時間自動測試向量產生器，我們的所建構出的時間自動測試向量產生器平均來說比之前所提出的研究快了六倍，在某些例子裡我們的效能甚至快了三十二倍。

Circuit timing analysis is important in various aspects of circuit optimization. The problem of finding input vectors achieving functional and temporal requirements is known as timed Automatic Test Pattern Generation (timed ATPG). A timed ATPG algorithm will return an input vector that satisfies functional and temporal requirements simultaneously when evaluated. Several previous works use timed ATPG as a core engine for solving problems related to timing analysis, such as crosstalk and maximum instantaneous current analysis. Despite the usefulness of timed ATPG, traditional timed ATPG is slow and unscalable for large circuits. In this thesis, we present a very effective way for timed ATPG. On average, our results are 6 times faster than the most recent work, and in some cases, up to 32 times faster.

List of Contents:
Abstract 1
Contents 2
List of Figures 3
List of Tables 4
Chapter 1 Introduction 5
Chapter 2 Timed Characteristic Function 10
Chapter 3 Efficient Implementation of the Timed Characteristic Function 14
3.1. Recursive Formulations of the TCF Calculus 15
3.2. Sharing Mechanism using Arrival Time Information 20
3.3. Correlation Information Extraction between TCFs 25
Chapter 4 Overall Flow 27
Chapter 5 Experimental Results 29
Chapter 6 Conclusions 38
References 39

[1]. P. Ashar, and S. Malik, “Functional Timing Analysis Using ATPG,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995.
[2]. P. Ashar, S. Malik, and S. Rothweiler, “Functional Timing Analysis using ATPG,” in Proceedings of the European Design Automation Conference, 1993.
[3]. R. I. Bahar, H. Cho, G. D. Hachtel, E. Macii, and F. Somenzi, “Timing Analysis of Combinational Circuits using ADD’s,” in Proceedings of IEEE European Design Test Conference, pp. 625-629, Feb. 1994.
[4]. H.-C. Chen, and D. Du, “Path Sensitization in Critical Path Problem,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 2, pp. 196-207, Feb. 1993.
[5]. S. Devadas, K. Keutzer, and S. Malik, “Computation of Floating Mode Delay in Combinational Circuits: Theory and Algorithms,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 12, pp. 1913-1923, Dec. 1993.
[6]. J. L. Güntzel, A. C. M. Pinto, and R. Reis “A Timed Calculus for ATG-Based Timing Analysis of Circuits with Complex Gates,” IEEE Latin American Test Workshop, Feb. 2001.
[7]. H. Kriplani, F. Najm, and I. N. Hajj, “Pattern independent maximum current estimation in power and ground buses of CMOS VLSI circuits: algorithms, signal correlations, and their resolution,” IEEE Transactions on Computer-Aided Design, pp. 998-1012, Aug. 1995.
[8]. Y.-M. Jiang, A. Krstic, and K.-T. Cheng, “Estimation for Maximum Instantaneous Current Through Supply Lines for CMOS Circuits,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 8, no. 1, pp. 61-73, Feb. 2000.
[9]. Y.-M. Jiang, K.-T. Cheng, and A. Krstic, “Estimation of Maximum Power and Instantaneous Current Using a Genetic Algorithm,” IEEE Custom Integrated Circuits Conference, 1997.
[10]. R. Kundu, and R. D. Blanton, “Timed Test Generation for Crosstalk Switch Failure in Domino CMOS Circuits,” in Proceedings of the IEEE VLSI Test Symposium, pp. 379-385, Apr. 2002.
[11]. R. Kundu, and R. D. Blanton, “ATPG for Noise-Induced Switch Failures in Domino Logic,” in Proceedings of the International Conference on Computer-Aided Design, pp. 765-768, Nov. 2003.
[12]. P. C. McGeer, A. Saldanha, P. R. Stephan, R. K. Brayton, and A. L. Sangiovanni-Vicentelli, “Timing Analysis and Delay-Fault Test Generation using Path-Recursive Functions,” in Proceedings of the International Conference on Computer Aided-Design, 1991.
[13]. A. Nadel, “Backtrack Search Algorithms for Propositional Satisfiability: Review and Innovations” Master’s Thesis, the Hebrew University of Jerusalem, 2002.
[14]. J. P. M. Silva, and K. A. Sakallah, “Efficient and Robust Test Generation-Based Timing Analysis,” in Proceedings of the International Symposium on Circuits and Systems, 1994.
[15]. J. P. M. Silva, and K. A. Sakallah, “GRASP: A New Search Algorithm for Satisfiability,” in proceedings of the International Conference on Computer-Aided Design, pp. 220-227, Nov. 1996.
[16]. L. G. Silva, J. P. M. Silva, L. M. Silveira, and K. A. Sakallah, ”Satisfiability Models and Algorithms for Circuit Delay Computation,” ACM Transactions on Design Automation of Electronic Systems, vol. 7, no. 1, pp. 137-158, Jan. 2002.
[17]. H. Yalcin, and J. P. Hayes, “Hierarchical Timing Analysis Using Conditional Delays,” in Proceedings of the International Conference on Computer-Aided Design, 1995.
H. Zhang, “SATO: An Efficient Propositional Prover”, in Proceedings of International Conference on Automated Deduction, pp. 272-275, Jul. 1997.