Ultra Fast Parallel Fault Analysis on Structurally Synthesized BDDs

An efficient method of parallel fault simulation for combinational circuits is proposed. The method is based on structurally synthesized BDDs (SSBDD) which represent gate-level circuits at higher, macro level where macros represent subnetworks of gates. Converting gate-level circuits to the macro-level is accompanied with fault collapsing. A parallel fault analysis algorithm for SSBDDs was developed. For the faults at fanout stems a new full Boolean differential based parallel fault analysis method is proposed. The algorithm is equivalent to exact critical path tracing. Because of the parallelism and higher abstraction level modeling the speed of analysis is considerably increased. Experimental data show that by the new method speed-up measured in several times has been achieved compared to the current state-of-the-art commercial tools and other exact critical path tracing methods.