Chapter 6
How is a circuit described?

The chapters so far have built circuits by writing one gate function that calls another: a full adder calls half adders, which call XOR and AND. That is fine for a handful of gates. The processor of Chapter 5 already has hundreds, and a real one has billions of transistors. Nobody wires those by hand. Instead a circuit is written down as data, a list of which gate drives which wire, and a program reads that list and simulates the circuit. The list is what a hardware description language like Verilog is, and the simulator is how a chip is tested long before it is built in silicon.

6.1 A circuit is a netlist

Strip a circuit to its essentials and it is a graph: gates are nodes, and the wires between them are edges. Writing that graph down gives a netlist: one record per gate, naming the wire it drives, its kind, and the wires it reads. Figure 6.2 draws the netlist for the XOR circuit Chapter 2 built from four NAND gates.

The data is a direct transcription of the drawing.

Example 6-1. The XOR circuit, written as data

# XOR, described as the four-NAND circuit Chapter 2 built by hand.
XOR_FROM_NAND = [
    Gate("shared", "nand", ("a", "b")),1
    Gate("left", "nand", ("a", "shared")),
    Gate("right", "nand", ("b", "shared")),
    Gate("out", "nand", ("left", "right")),
]

• one record is one gate: the wire it drives (shared), its kind (nand), and the two wires it reads (a and b)

6.2 Simulating the description

To find what the circuit computes, the simulator works outward from the inputs. A gate can fire only once every wire it reads is known; firing it makes its output wire known, which may let other gates fire. The value spreads in waves until every wire is settled. Because a gate waits on its data, not on its place in the list, the order the gates are written in does not matter.

Example 6-2. Evaluating a netlist

def simulate(netlist: list, inputs: dict) -> dict:
    """Evaluate a combinational netlist. `inputs` gives the input wires' values;
    the result holds every wire's value. A gate fires once all the wires it reads
    are known, so the listing order does not matter."""
    values = dict(inputs)
    pending = list(netlist)
    while pending:
        ready = [g for g in pending if all(w in values for w in g.ins)]1
        if not ready:
            raise ValueError("netlist has an undriven wire or a feedback loop")2
        for gate in ready:
            values[gate.out] = _GATES[gate.kind](*[values[w] for w in gate.ins])3
        pending = [g for g in pending if g not in ready]
    return values

• a gate is ready when every wire it reads already has a value; each round fires all the ready gates at once
• if some gates remain but none are ready, the netlist is not a valid combinational circuit: a wire is undriven, or gates feed back into a loop
• firing a gate computes its wire by calling the very function its kind names, built in the chapters so far

Figure 6.3 shows the waves for the XOR netlist: from the inputs, shared fires, then left and right, then out.

The interactive version needs the in-browser runtime.

The next chapter makes the processor faster, not by redrawing its circuit but by overlapping the instructions that run through it.

Exercises

• Describe NOR as a netlist of NAND gates, and confirm the simulator agrees with the NOR gate.
• Build a netlist whose output feeds back into its own input, and watch the simulator refuse to run it.