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.