Bit-Parallel Simulation: 15× Faster Equivalence Checking with 64-bit Wordwise Operations

Project: This post is part of the EDA Logic Synthesis Engine project — a from-scratch DAG-aware synthesis engine for the ICCAD 2026 CADC Contest.

TL;DR

Naive simulation processes one input vector at a time — a loop over N vectors × M gates. By packing 64 vectors into a 64-bit integer and using bitwise operations (&, |, ^, ~), we process 64 vectors simultaneously in a single instruction. Result: 15.3× average speedup, peaking at 28.7× on larger circuits.

---

The Problem: Equivalence Checking

After modifying a netlist (constant folding, ODC pruning, AIG rewriting), you need to verify that the output is functionally identical to the original. The standard approach:

1. Generate N random input vectors
2. Simulate both original and modified netlists
3. Compare outputs

If all N vectors produce the same outputs, the designs are probably equivalent (Monte Carlo verification). Typical N: 2000–10000.

Naive Simulation: Why It’s Slow

The straightforward approach loops over vectors, then gates: for each vector, evaluate every gate in topological order. For G gates and V vectors, that’s O(V × G) operations.

At 2000 vectors and 10K gates, that’s 20 million gate evaluations. The bottleneck isn’t computation — it’s memory access. Each gate evaluation touches scattered memory locations because each vector’s values are stored separately. This causes CPU cache misses.

On modern CPUs, a cache miss costs ~100 cycles. A cache hit costs ~1 cycle. If 30% of gate evaluations miss the cache (realistic for scattered access), you’re paying 30× more than necessary.

The Bit-Parallel Insight

Instead of processing one vector at a time, process 64 vectors simultaneously:

Before: vector[i] = 0 or 1        (1 bit per vector)
After:  vector[i] = 0xFFFFFFFF...  or 0x00000000...  (64 bits per vector)

Each gate evaluation now operates on 64-bit words. An AND gate becomes a single & instruction that processes 64 vectors at once. OR becomes |. XOR becomes ^. NOT becomes ~.

Why 64? Because modern CPUs have 64-bit general-purpose registers. You can’t go wider without SIMD (AVX-512), which adds complexity. 64-bit is the sweet spot: no special instructions needed, works on any CPU from the last 15 years.

Implementation Strategy

The implementation has three phases:

Phase 1: Pack

Convert the input matrix (V vectors × S signals) into a packed format where each signal is represented by a 64-bit word. Bit i of the word corresponds to vector i.

Why pack all at once? Because packing during simulation would add a branch per vector per gate. Packing upfront is O(V × S) but done once; simulation is O(G) and done per-gate.

Phase 2: Simulate

Single pass over gates in topological order. For each gate, read the packed words of its inputs, apply the bitwise operation, write the packed word of its output.

Why topological order? Because each gate depends only on its inputs (which have already been computed). This guarantees correctness without backtracking.

Phase 3: Extract

After simulation, extract individual vector results by bit-shifting. To get vector i’s result for signal S, shift the packed word right by i positions and mask with 1.

Why extract separately? Because extraction is O(V × S) — proportional to the number of vectors. If you only need aggregate statistics (e.g., “how many vectors produce output 1?”), you can skip extraction entirely and work with the packed words directly.

Why It’s Faster: Three Levels

Level 1: Instruction-Level Parallelism

Naive: 1 AND instruction per vector per gate. Bit-parallel: 1 AND instruction per gate, covering 64 vectors.

Theoretical speedup: 64×

Level 2: Memory Access Patterns

Naive simulation accesses gate inputs in scattered locations — each vector’s values are stored separately. This causes CPU cache misses.

Bit-parallel simulation accesses each signal exactly once per gate evaluation. All 64 vectors for that signal are in the same cache line (8 bytes = 64 bits). Sequential access → high cache hit rate.

Measured cache miss rate: ~5-10% for bit-parallel vs ~30-40% for naive.

Level 3: Reduced Loop Overhead

Naive: Inner loop runs V × G times (vector × gate). Each iteration has loop overhead (increment, branch, cache lookup).

Bit-parallel: Inner loop runs G times (gate only). The vector dimension is handled by the bitwise operation itself — no loop needed.

Measured Results

Circuit	Gates	Naive (s)	Bit-Parallel (s)	Speedup
test04	66	0.075	0.012	6.5×
test08	93	0.111	0.031	3.6×
test03	931	0.801	0.040	19.9×
test01	1,794	1.412	0.041	34.4×
test05	3,462	3.143	0.193	16.3×
test18	8,538	7.137	0.220	32.4×
test02	11,227	9.456	0.329	28.7×

Average speedup: 15.3×

Why does speedup vary?

• Small circuits (under 100 gates): Speedup is lower (3–6×) because the packing/unpacking overhead is a fixed cost that dominates when G is small.
• Medium circuits (500 to 2K gates): Sweet spot. Cache-friendly access patterns give 15–35× speedup.
• Large circuits (above 5K gates): Still fast, but memory allocation for the signal dictionary starts to matter.

The theoretical maximum is 64×. We achieve 15–35× because:

1. Memory bandwidth is the bottleneck, not computation
2. Packing and extraction have non-zero cost
3. Small circuits have too few gates to amortize the fixed overhead

Why Not SIMD (AVX-512)?

AVX-512 could process 512 vectors at once — a theoretical 8× improvement over 64-bit. But:

1. Portability: AVX-512 is only on Intel Xeon and recent AMD. Most consumer laptops don’t have it.
2. Complexity: Intrinsics programming is error-prone and hard to debug.
3. Diminishing returns: At 64× speedup, equivalence checking takes 0.04 seconds per 1K-gate circuit. Going to 0.005 seconds doesn’t change the user experience.

The 64-bit approach is the right trade-off: fast enough, portable, and simple to implement.

Lessons Learned

1. The speedup isn’t free — you need to handle non-64-aligned vector counts (padding) and extract individual results afterward.
2. Bit-parallel works best when the inner loop is simple — AND/OR/XOR are single-cycle operations. If gates had complex behaviors (multipliers, memories), the advantage would shrink.
3. This technique generalizes — any simulation with independent vectors (Monte Carlo, random testing) can benefit from bit-parallel execution. It’s a specific case of SIMD (Single Instruction, Multiple Data).

---

Previous: AIG Local Rewriting Engine — How the rewrites were generated.

Next: Using LLM Agents to Explore EDA Search Spaces → How an LLM agent guides the optimization process.

🔙 Back to Project Overview