CMP3F: a high speed fault simulator for the Connection Machine

The authors present a high-speed fault simulator, called CMP3F, that performs parallel-pattern, parallel-fault simulation, implemented on the Connection Machine (CM). Unlike conventional parallel pattern or parallel fault simulators, CMP3F can dynamically choose the fault set size as well as the number of vectors being simulated in parallel. Hence, the fault simulation process is split into several phases. The first phase primarily uses fault-list partitioning because, initially, the fault-list size dominates the fault simulation time. If fault dropping is allowed, CMP3F goes through a number of subsequent phases as the fault list becomes smaller, simulating an increasing number of distinct sets of vectors in parallel. Thus, CMP3F avoids useless computations when a small number of faults are present and maintains nearly linear speedup with an increasing number of processors. Experimental data obtained using ISCAS85 benchmark circuits suggest that CMP3F implemented on a fully configured 64 K-node CM, will perform fault simulation one to two orders of magnitude faster than most existing fault simulators