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.