Cellular Automata for Efficient Parallel Logic and Fault Simulation

We present a unilateral 2-D cellular automata (CA) model and pipelining technique to parallelize logic and fault simulation. We show that given an acyclic digraph describing the Boolean function of a combinational circuit at the gate level, whose nodes are the logic gates of the circuit and whose directed edges stand for the propagating directions of signals, we can map this digraph onto a 2-D CA to simulate the signal propagation of the circuit on the CA. This mapping preserves not only the electrical connectivity of the circuit but also the massive parallelism inherited from the CA. Experimental results on ISCAS-85 benchmark circuits are obtained. Compared with previous fault simulation results, the time required for simulating one test pattern on an average is shorter by three to four orders of magnitude. As to pure logic simulation, our CA performs up to 9.24 billion gate evaluations per second using a 20 MHz clock and 8-b words. Scalability and extension to sequential circuits are discussed.