Datapath and controller design: ASM charts

Lessons 2 and 3 gave you combinational logic and state machines. Real digital systems combine the two in a fixed pattern: a datapath of registers, arithmetic units and multiplexers that does the work, and a controller, a state machine, that tells the datapath what to do in each cycle. This lesson teaches a disciplined way to get from an algorithm to that structure, using algorithmic state machine (ASM) charts, and shows the trade-offs between doing an algorithm in one cycle, in many cycles on shared hardware, or in a pipeline.

The NS-5 classifier needs the root-mean-square (RMS) amplitude of each channel in every frame, to normalize the radar returns before classification. The front end already computes the mean of the squared samples for each frame; the remaining step is a square root of a 32-bit number. A square root has no single-cycle hardware primitive, and Maren Holt would rather not have firmware compute four of them every 2 ms. Jonah's task is a small square-root unit, and it is a perfect example of datapath and controller design.

From algorithm to register transfers

The first step is to write the algorithm in a form that hardware can follow, with explicit registers and a fixed number of steps. The binary digit-by-digit square root, the same method as long division, produces one result bit per step using only shifts, an addition, a comparison and a subtraction. For a 32-bit input it takes 16 steps. Written as register transfers, with op holding the remainder, res the partial result and one a single moving bit:

Each row is something hardware can do in a clock cycle, provided the right functional units exist. The arrow ← means the register takes the new value at the next clock edge, which is the same meaning as a non-blocking assignment. All the right-hand sides in one step use the values of the registers at the start of that step.

ASM charts

An ASM chart is a flowchart with clock-cycle semantics. It has three kinds of box. A state box, a rectangle, represents one state and therefore one clock cycle; it lists the Moore outputs asserted in that state and the register transfers performed at the end of it. A decision box, a diamond, tests an input or a status signal and branches. A conditional output box, a rectangle with rounded ends, lists Mealy outputs or register transfers that happen only on that branch. A state box together with the decision and conditional boxes that follow it, up to the next state boxes, forms an ASM block, and everything in one ASM block happens in the same clock cycle. Charts that include register transfers are sometimes called ASMD charts, for ASM with datapath.

Reading the chart carefully exposes the timing that a software flowchart hides. In ITER, the decision op ≥ res + one tests the values at the start of the cycle, and the transfers in both conditional boxes take effect at the end of it. The test one = 1 also uses the old value of one, so it is true in the sixteenth iteration, the one that uses the last result bit; the chart therefore leaves for DONE after exactly 16 cycles in ITER. A designer who wrote the test as one = 0, thinking of the value after the shift, would get a 17th iteration and a wrong answer. ASM charts make such off-by-one decisions visible before any code is written.

Deriving the datapath

The datapath follows mechanically from the register transfers. Every variable assigned in a state box becomes a register. Every operation becomes a functional unit, or several operations share one unit if they never occur in the same cycle. Every register with more than one source gets a multiplexer, whose select lines are control signals from the controller. Every test in a decision box becomes a status signal from the datapath to the controller.

The functional units are one 32-bit adder computing t = res + one, one 32-bit subtractor computing op − t, and a comparator for op ≥ t. The comparator is free: it is the borrow out of the subtractor, so the status signal ge is just the inverted carry of op − t. The shifts are wiring. One subtle simplification is that (res >> 1) + one never produces a carry, because one is always a single bit in a position that res >> 1 has clear, so the addition can be an OR. Synthesis would not discover that by itself, because it is a property of the algorithm rather than of the code, but the designer can write it explicitly and save an adder.

Simulating the ASM chart

Before writing RTL, Jonah checks the ASM chart with an executable model that has exactly the chart's semantics: in each cycle, every condition and right-hand side is computed from the current register values, and then all registers update together. The model also checks the result against Python's exact integer square root for many random inputs and for the worst-case values.

import math, random

def sqrt_unit(x, trace=False):
    """cycle-accurate model of the ASM chart; returns (result, cycles)"""
    R = {"state": "IDLE", "op": 0, "res": 0, "one": 0, "result": 0}
    start, cycles = True, 0
    while True:
        cycles += 1
        s, n = R, dict(R)                       # n holds next-state values
        if s["state"] == "IDLE":
            if start:
                n.update(op=x, res=0, one=1 << 30, state="ITER")
        elif s["state"] == "ITER":
            t = s["res"] + s["one"]
            ge = s["op"] >= t                   # status signal (borrow of op - t)
            if ge:
                n["op"] = s["op"] - t
                n["res"] = (s["res"] >> 1) | s["one"]   # OR is enough: no carry
            else:
                n["res"] = s["res"] >> 1
            n["one"] = s["one"] >> 2
            if s["one"] == 1:                   # tests the old value
                n["state"] = "DONE"
            if trace and cycles <= 6:
                print(f"  cycle {cycles:2d} ITER  op={s['op']:>10d}  res={s['res']:>10d}"
                      f"  one=2^{s['one'].bit_length() - 1:<2d} ge={int(ge)}")
        elif s["state"] == "DONE":
            n.update(result=s["res"] & 0xFFFF, state="IDLE")
            return n["result"], cycles
        R = n

r, c = sqrt_unit(1_000_000, trace=True)
print(f"sqrt(1,000,000) = {r} in {c} cycles")

random.seed(5)
tests = [0, 1, 2, 3, 4, 2**32 - 1, 2**31, 65535**2, 65535**2 - 1] + \
        [random.randrange(2**32) for _ in range(20000)]
bad = [x for x in tests if sqrt_unit(x)[0] != math.isqrt(x)]
print(f"{len(tests)} inputs checked against math.isqrt, mismatches: {len(bad)}")
print(f"cycles per result: {sqrt_unit(12345)[1]}, so {sqrt_unit(12345)[1] * 10} ns at 100 MHz")

  cycle  2 ITER  op=   1000000  res=         0  one=2^30 ge=0
  cycle  3 ITER  op=   1000000  res=         0  one=2^28 ge=0
  cycle  4 ITER  op=   1000000  res=         0  one=2^26 ge=0
  cycle  5 ITER  op=   1000000  res=         0  one=2^24 ge=0
  cycle  6 ITER  op=   1000000  res=         0  one=2^22 ge=0
sqrt(1,000,000) = 1000 in 18 cycles
20009 inputs checked against math.isqrt, mismatches: 0
cycles per result: 18, so 180 ns at 100 MHz

The trace shows the first iterations for an input of 1,000,000: while one is larger than the remainder, ge is 0 and only res and one shift. The model returns 1,000 after 18 cycles, and over 20,009 inputs, including 0, 2^32 − 1 and the largest perfect square, it agrees with the exact square root every time. The model is now the reference for the RTL testbench, in exactly the pattern of lesson 4.

Writing the controller and datapath

The RTL can be written as one module with the datapath and controller together, often called a finite state machine with datapath (FSMD), or as two modules joined by explicit control and status signals. The separated form is longer, but it makes the datapath reusable, makes the control signals visible in waveforms, and matches the ASM chart line for line. The combined form below is common for a unit this small.

module isqrt32 (
    input  logic        clk, rst_n,
    input  logic        start,          // pulse with x valid
    input  logic [31:0] x,
    output logic        ready,          // can accept start
    output logic        valid,          // result valid for one cycle
    output logic [15:0] result
);
    typedef enum logic [1:0] {IDLE, ITER, DONE} state_t;
    state_t state;
    logic [31:0] op, res, one;
    logic [32:0] diff;                  // op - (res + one), with borrow bit
    logic        ge;

    assign diff  = {1'b0, op} - {1'b0, res + one};
    assign ge    = ~diff[32];           // no borrow means op >= res + one
    assign ready = (state == IDLE);

    always_ff @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            state <= IDLE;  valid <= 1'b0;
        end else begin
            valid <= 1'b0;
            unique case (state)
                IDLE: if (start) begin
                          op <= x;  res <= '0;  one <= 32'h4000_0000;
                          state <= ITER;
                      end
                ITER: begin
                          if (ge) begin
                              op  <= diff[31:0];
                              res <= (res >> 1) | one;
                          end else
                              res <= res >> 1;
                          one <= one >> 2;
                          if (one == 32'd1) state <= DONE;
                      end
                DONE: begin
                          result <= res[15:0];  valid <= 1'b1;
                          state  <= IDLE;
                      end
                default: state <= IDLE;
            endcase
        end
    end
endmodule

The code follows the reset advice of lesson 3: state and valid are reset, while op, res, one and result are not, because they are always loaded before they are used. The ready and valid signals give the unit a simple handshake. A caller waits for ready, pulses start with x, and later sees valid for one cycle with the result; lesson 10 generalizes this to streaming interfaces with backpressure.

Scheduling, binding and the space of designs

Designing the square root as 16 iterations on one adder is a choice. The same algorithm could unroll two iterations per cycle, using two adders and subtractors in series, for 8 iterations and a longer critical path. It could unroll all 16 into a combinational array, about 16 times the logic, producing a result every cycle but with a path far too long for 100 MHz. Or the unrolled array could be cut by registers into a 16-stage pipeline that accepts a new input every cycle with a latency of 16 cycles. Designers describe this space with three terms that high-level synthesis tools also use, as lesson 11 explains. Scheduling assigns each operation to a clock cycle. Allocation decides how many functional units of each type exist. Binding assigns each operation to a specific unit and each value to a specific register.

The right choice follows from the throughput requirement. The NS-5 needs four square roots per 2.048 ms frame, one every 512 µs, so the iterative unit is busy for 0.04 % of the time and could even be shared with other functions. A design processing a square root per sample at 100 MHz would need the pipeline. The general method is the one used throughout this course: compute the required operations per second, divide by the clock rate to find how many operations must happen per cycle, and allocate just enough hardware to do them, with a margin.

Control and status interfaces

The separation between datapath and controller extends naturally to the boundary with software. The square-root unit's x, start, ready, valid and result signals will become fields in a memory-mapped register block that firmware reads and writes, or, more likely, will be driven by the front end's own frame logic, which calls the unit once per channel at the end of each frame. Either way, the unit has a defined protocol: what the caller must do, in what order, and what the unit promises in return. Writing that protocol down, and checking it with assertions like those of lesson 4, is part of the design rather than an afterthought.