Master thesis 20p

The Counting Algorithm for simulation of million-gate designs

Klas Arvidsson


A key part in development and verification of digital systems is 
simulation. But hardware simulators are expensive, and software 
simulation is not fast enough for designs with a large number of gates. 
As today’s digital designs constantly grow in size (number of gates), 
and that trend shows no signs to end, faster simulators handling 
millions of gates are needed.

We investigate how to create a software gate-level simulator able to 
simulate a high number of gates fast. This involves a trade-off between 
memory requirement and speed. A compact netlist representation can 
utilize cache more efficient but requires more work to interpret, while 
high memory requirements can limit the performance to the speed of main 

We have selected the Counting Algorithm to implement the experimental 
simulator MICA. The main reasons for this choice is are the compact way 
in which gates can be stored, but still be evaluated in a simple and 
standard way.

The report describes the issues and solutions encountered and evaluate 
the resulting simulator. MICA simulates a SPARC architecture processor 
called Leon. Larger netlists are achieved by simulating several 
instances of this processor. Simulation of 128 instances is done at a 
speed of 9 million gates per second using only 3.5MB memory. In MICA 
this design correspond to 2.5 million gates.

Juha Takkinen, <>