An Exact and Linear-Time Critical Path Tracing Algorithm Critical path tracing has been proposed as an alternative to fault simulation because it is faster and requires less memory than conventional fault simulation. It is also very useful in fault and design error diagnosis because the fault behavior may not exactly match a particular fault model so that fast observability calculations are important. The original implementation, CRIPT, was reported to be an approximate method due to self-masking and multiple path sensitization [1]. In addition, CRIPT had O(G2) time complexity where G is the number of gates in the circuit. More recently, CRIPT was made exact with the introduction of stem analysis by forward propagation [2][3]. However, the extended CRIPT was slow. A one pass critical path tracing algorithm was proposed by Navabi et al [4], which runs in linear time. However, it has several problems. First, the stem analysis only consider two-input AND, NAND, OR and NOR gates. Second, the rules used to determine stem criticality do not cover all reconvergence cases. Third, it does not consider unknown values, Thus, this method cannot be applied on real circuits. In this poster, we present an exact and linear-time critical path tracing algorithm. The performance of critical path tracing is determined primarily by the efficiency of stem analysis. The proposed strategy can determine stem criticality in one pass based on six rules. The algorithm uses a three-valued algebra so that it can handle unknown value. Experiments on ISCAS85 and ISCAS89 benchmarks show that the computation time is nearly linear in the number of nets. [1] M. Abramovici, P. R. Menon, and D. Miller, “Critical Path Tracing: An Alternative to Fault Simulation,” IEEE Design & Test of Computers, vol. 1, Feb. 1984, pp. 83-93. [2] P. Menon, Y. Levendel, and M. Abramovici, “Critical Path Tracing in Sequential Circuits,” IEEE Int. Conf. Computer Aided Design, Nov. 1988, pp. 162-165. [3] M. Favalli, P. Olivo, M. Damiani, and B. Ricco, “Fault Simulation of Unconventional Faults in CMOS circuits,” IEEE Trans. on Computer Aided Design, vol. 10, no. 5, May. 1991, pp. 667-682. [4] M. Shadfar, A. Peymandoust, Z. Navabi, “Using VHDL Critical Path Tracing Models for Pseudo Random Test Generation,” VHDL International User’s Forum, Santa Clara, CA, Apr. 1995, pp. 41-45.