Motivation

Digital circuits are often modeled as directed acyclic graphs. Given a boolean circuit and a vector of input values, the task is to compute the output values of every gate. A straightforward evaluation method is a topological traversal. This note presents structural techniques that can accelerate such computations in specific scenarios, including linear circuits and circuits with bounded skew.

Topological Ordering and Simulation

Given a circuit described as a netlist, each gate is associated with a boolean funcsion. A topological ordering ensures that before evaluating a gate, all its fanin signals are already known. The standard evaluation proceeds gate by gate in this order. Let gates be an array of structures representing the circuit, where each entry stores the gate type, fanin indices, and a pointer to its output. The following C++ code snippet performs a simple simulation using two-value logic (0 and 1).

#include <vector>
#include <cstdint>

struct GateInfo {
    enum Type { AND, OR, XOR, NOT } kind;
    uint32_t in1, in2;
    uint32_t out;
    bool is_inverted = false;
};

void simulate(std::vector<GateInfo>& netlist,
              std::vector<uint32_t>& signals) {
    std::vector<uint32_t> sorted = topological_order(netlist);
    for (auto idx : sorted) {
        const auto& g = netlist[idx];
        uint32_t lhs = signals[g.in1];
        uint32_t rhs = (g.kind != GateInfo::NOT) ? signals[g.in2] : 0;
        uint32_t res = 0;
        if (g.kind == GateInfo::AND) res = lhs & rhs;
        else if (g.kind == GateInfo::OR)  res = lhs | rhs;
        else if (g.kind == GateInfo::XOR) res = lhs ^ rhs;
        else res = ~lhs & 1;
        signals[g.out] = g.is_inverted ? ~res & 1 : res;
    }
}

In many practical circuits, the topological order is computed once and reused across multiple simulation vectors.

XOR-Dominant Circuits and Linear Algebra

Circuits that consist mainly of XOR and NOT gates can be evaluated using Gaussian elimination over GF(2). Each signal is represented as a linear combination of primary inputs. The state of the circuit is stored as a coefficient matrix A where each row corresponds to a signal and each column to a primary input. NOT gates simply add a constant term (the parity vector b).

Building the Linear Model

#include <bitset>
#include <cstdint>

constexpr size_t MAX_INPUTS = 256;
using Row = std::bitset<MAX_INPUTS>;

struct LinearSignal {
    Row coeff;
    bool constant;
};

void build_linear(LinearSignal* sigs, size_t num_sigs,
                  const std::vector<GateInfo>& gates) {
    for (const auto& g : gates) {
        LinearSignal& target = sigs[g.out];
        const LinearSignal& a = sigs[g.in1];
        if (g.kind == GateInfo::NOT) {
            target.coeff = a.coeff;
            target.constant = !a.constant;
        } else {
            const LinearSignal& b = sigs[g.in2];
            target.coeff = a.coeff ^ b.coeff;
            target.constant = a.constant ^ b.constant;
        }
    }
}

Once the linear model is constructed, evaluating the circuit for many input patterns reduces to computing (A * input) ^ b efficiently. The matrix A is usually very sparse (e.g., arising from LFSRs or CRC generators), which can be exploited with sparse matrix multiplication or dedicated hardware.

Skewed Circuit Evaluation

A circuit has bounded skew if the difference between the maximum and minimum logic depths from any enput to any output is bounded by a small constant (k). For such circuits, we can sometimes pipeline evaluation without a full topological queue, using a sliding window buffer over wire delays. While this method is circuit‑specific, it demonstrates how structural properties beyond topological ordering influence evaluation strategies.

Reducing Redundant Computations

In circuits containing repeated sub‑structures (e.g., repeated multiplier blocks in a systolic array), memoization can avoid recomputation. A hash map indexed by the tuple (gate_type, fanin1_signal, fanin2_signal) reduces duplicate evaluation. The gain is noticeable in circuits with many replicated components.

#include <unordered_map>
#include <functional>

struct MemoKey {
    uint32_t type;
    uint32_t lhs;
    uint32_t rhs;
    bool operator==(const MemoKey& o) const {
        return type == o.type && lhs == o.lhs && rhs == o.rhs;
    }
};

struct MemoHash {
    size_t operator()(const MemoKey& k) const {
        return ((k.type * 31 + k.lhs) * 31) + k.rhs;
    }
};

void simulate_memo(std::vector<GateInfo>& netlist,
                   std::vector<uint32_t>& signals) {
    std::unordered_map<MemoKey, uint32_t, MemoHash> cache;
    std::vector<uint32_t> order = topological_order(netlist);
    for (auto idx : order) {
        const auto& g = netlist[idx];
        MemoKey key{g.kind, signals[g.in1], signals[g.in2]};
        auto it = cache.find(key);
        if (it != cache.end()) {
            signals[g.out] = it->second;
            continue;
        }
        uint32_t v = 0;
        // ... same evaluation as before ...
        cache[key] = v;
        signals[g.out] = v;
    }
}

Cache invalidation is not needed because the underlying signal are updated monotonically during the pass.

These techniques illustrate how understanding the underlying structure of a circuit can lead to evaluation routines that are more performant than a naïve topological traversal. The choice among them depends on the circuit topology, the required number of evaluations, and the available memory.