Cellular Automata for Efficient Parallel Logic and Fault Simulation

Yih Lang Li, Cheng Wen Wu

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish
Pages (from-to)740-749
Number of pages10
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number6
StatePublished - 1 Jun 1995

Fingerprint Dive into the research topics of 'Cellular Automata for Efficient Parallel Logic and Fault Simulation'. Together they form a unique fingerprint.

Cite this