Skip to content

Chapter 2: Buses, Memory, Datapath and Control

Chapter 1 gave us registers and the microoperations that move data between them. This chapter shows how many registers share their wires, how a whole memory fits into the same notation, and how every RTL design splits into a part that holds data (the datapath) and a part that decides what happens to it (the control unit). It closes with a complete worked design, a machine that computes the greatest common divisor, and with the first look at how an RTL description turns into a hardware description language.

2.1 Buses

If every register could talk to every other register through its own private wires, a machine with \(n\) registers would need \(n(n-1)\) one-way paths. Four 8-bit registers would need 12 paths of 8 wires each, 96 wires in all, and a sixteen-register machine would need 240 paths. Real machines share wiring through a bus: one common set of wires that, at any moment, carries the value of exactly one chosen register, and from which any register may load. Four 8-bit registers on one bus need only 8 wires, plus a few control lines to choose the source.

There are two classic ways of building a bus.

The multiplexer bus

A bank of multiplexers, one per bit, selects which register drives the bus. With four registers, a 4-to-1 multiplexer on each bit chooses among R0 to R3, using two select lines S1 S0. Any register whose load signal is 1 copies the bus at the next clock edge (Figure 2.1). This form is purely combinational, it can never short-circuit, and it is what synthesis tools actually build from an HDL description.

A bus built from a multiplexer. The select lines S1 S0 choose which register drives the bus; every register whose load signal is 1 copies the bus at the next edge.
Figure 2.1. A bus built from a multiplexer. The select lines S1 S0 choose which register drives the bus; every register whose load signal is 1 copies the bus at the next edge.

The tri-state bus

In the second form each register reaches the bus through a three-state buffer. When enabled, the buffer passes its register's value; when disabled, its output is in the high-impedance state, written Z, which is electrically a disconnection. This saves logic on a long physical bus, but the control must guarantee that exactly one buffer is enabled at a time. Two drivers fighting, one pushing a 1 and the other a 0, is a short circuit. Inside a chip, tools build the multiplexer form; tri-state buses belong to board-level wiring and chip pins.

A bus transfer is written like any other transfer, naming the bus when it matters:

BUS <- R1,  R2 <- BUS        put R1 on the bus, load it into R2
R2 <- R1                     shorthand for the same thing, when the bus is implied

2.2 Memory

Memory is treated as one large array of registers, addressed through an address register AR. Mano's notation writes M[AR] for "the memory word that AR selects". A read copies the addressed word into a data register, and a write overwrites it:

Read:   DR <- M[AR]       load the data register from the addressed word
Write:  M[AR] <- R1       store R1 into the addressed word

Both take one clock pulse, and both are microoperations like any other.

Example 2.1: which address does a read use?

In one clock pulse the transfers DR ← M[AR], AR ← AR + 1 are performed. Which word is read?

  1. Every right-hand side is sampled before any register is written.
  2. So M[AR] is evaluated with AR as it was when the pulse began, the old address.
  3. The increment lands at the same edge, leaving AR pointing at the next word, ready for the next read.

This is exactly how a processor steps through consecutive words of memory, and it is why AR and DR can safely be changed in the same pulse as the read.

2.3 Datapath and control

An RTL system divides cleanly into two cooperating parts (Figure 2.2).

  • The datapath is where data lives and is transformed: the registers, the ALU, shifters, buses and multiplexers. It answers what can be computed.
  • The control unit is a finite state machine, a circuit that is always in one of a few named states and moves between them on clock edges. It watches status flags coming back from the datapath (for example, "the result was zero"), an instruction's opcode or a counter, and on every cycle asserts the control signals that make the datapath perform the right microoperation. It answers in what order.
Every RTL design has a datapath, which holds and transforms data, and a control unit, which sends control signals to it and reads status back.
Figure 2.2. Every RTL design has a datapath, which holds and transforms data, and a control unit, which sends control signals to it and reads status back.

Return to the conditional transfer P: R2 ← R1. The P is a control signal. Somewhere in the datapath it enables the load line of R2 and steers the multiplexers so that R1 is on the bus. The control unit's whole job is to produce a correctly timed sequence of such signals. The datapath is the orchestra and the control unit is the conductor; neither makes music alone.

Control as a schedule of signals

Take a tiny machine that adds the word at memory address 20 to the accumulator. Each row of the following table is one clock cycle, and the control unit asserts the signals on that row.

Cycle Microoperation Signals the control unit raises
T0 AR ← 20 select the constant 20 onto the bus; load AR
T1 DR ← M[AR] memory read; load DR
T2 ACC ← ACC + DR ALU operation = add; load ACC
T3 (done) return to waiting

Almost every hardware bug turns out to be this: the right signal, on the wrong cycle.

Two ways to build a control unit

Hardwired control Microprogrammed control
How signals are generated Gates and a state register compute every control signal directly A small ROM stores one word per step; the bits of the word are the control signals
Speed Fast Slower: an extra memory read at each step
Changing it Redesign the logic Rewrite the ROM
Typical home Simple, fast processors with a small and regular instruction set Older processors with large and complicated instruction sets

When you write a state machine in Verilog or VHDL, you are writing hardwired control.

2.4 From RTL to a hardware description language

Here the notation pays off, because a single register transfer maps almost mechanically onto both Verilog and VHDL. Consider an accumulator that adds a data register into itself when the control signal load is 1. Mano would write load: ACC ← ACC + DR. The same microoperation in three notations:

load: ACC <- ACC + DR
module accumulator (
    input        clk,
    input        load,
    input  [7:0] DR,
    output reg [7:0] ACC
);
    always @(posedge clk) begin
        if (load)
            ACC <= ACC + DR;     // load: ACC <- ACC + DR
    end
endmodule
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity accumulator is
    port ( clk  : in  std_logic;
           load : in  std_logic;
           DR   : in  unsigned(7 downto 0);
           ACC  : out unsigned(7 downto 0) );
end accumulator;

architecture rtl of accumulator is
    signal acc_r : unsigned(7 downto 0) := (others => '0');
begin
    process (clk)
    begin
        if rising_edge(clk) then
            if load = '1' then
                acc_r <= acc_r + DR;     -- load: ACC <- ACC + DR
            end if;
        end if;
    end process;
    ACC <= acc_r;
end rtl;

Read the three side by side and the correspondence is complete:

In RTL In Verilog In VHDL
"at the next clock edge" always @(posedge clk) if rising_edge(clk)
the control function load: if (load) if load = '1' then
the arrow ← <= <=

Learning a second language is therefore mostly learning a new spelling of three ideas you already have: the clock edge, the condition and the transfer. The arrow becomes the non-blocking assignment <= in Verilog and the signal assignment <= in VHDL, both of which defer the write to the end of the time step, so that all right-hand sides are read first. That is precisely the "read everything, then write everything" rule of the previous chapter.

Why not the blocking assignment?

A blocking assignment = in Verilog takes effect immediately, like a statement in a program. In the swap R1 ← R2, R2 ← R1 it would copy R2 into R1 first and then copy the new R1 back, leaving both registers equal. Chapters 3 and 4 treat the two kinds of assignment in detail.

2.5 A worked design: a greatest-common-divisor machine

The three levels of Chapter 1 described a machine that finds the greatest common divisor of \(A\) and \(B\) by repeated subtraction. We now design it properly, as a datapath and a control unit.

Algorithm. While \(A \ne B\): if \(A > B\) replace \(A\) by \(A - B\), otherwise replace \(B\) by \(B - A\). When \(A = B\), that common value is the greatest common divisor. (The algorithm assumes both inputs are positive. If either were zero the subtraction would never make progress.)

Datapath. Two registers A and B, a comparator that reports whether \(A = B\) or \(A > B\), and a subtractor in front of each register. The status signals returned to the control unit are A == B and A > B.

Control. One state to wait for a start request, one to load the inputs, one to compare, one to subtract each way, and one to announce that the result is ready (Figure 2.3).

The control states of the GCD machine. SUBA and SUBB both return to CMP; DONE returns to IDLE.
Figure 2.3. The control states of the GCD machine. SUBA and SUBB both return to CMP; DONE returns to IDLE.

The microoperations belonging to each state, in Mano's notation, are:

State Control function Microoperation Next state
IDLE — none LOAD if start, else IDLE
LOAD S_LOAD A ← x, B ← y CMP
CMP — none DONE if \(A = B\); SUBA if \(A > B\); otherwise SUBB
SUBA S_SUBA A ← A − B CMP
SUBB S_SUBB B ← B − A CMP
DONE — none (done = 1) IDLE once start is low

The table converts directly into code, using the three-block structure that Chapter 4 explains: a state register, next-state logic, and the datapath registers with their outputs.

module gcd #(parameter W = 8) (
    input  wire         clk,
    input  wire         rst_n,
    input  wire         start,
    input  wire [W-1:0] x,
    input  wire [W-1:0] y,
    output wire [W-1:0] result,
    output wire         done
);
    localparam [2:0] S_IDLE = 3'd0, S_LOAD = 3'd1, S_CMP  = 3'd2,
                     S_SUBA = 3'd3, S_SUBB = 3'd4, S_DONE = 3'd5;

    reg [2:0]   state, next;
    reg [W-1:0] A, B;

    // control: state register
    always @(posedge clk or negedge rst_n)
        if (!rst_n) state <= S_IDLE;
        else        state <= next;

    // control: next-state logic
    always @(*) begin
        next = state;
        case (state)
            S_IDLE: if (start) next = S_LOAD;
            S_LOAD: next = S_CMP;
            S_CMP:  if (A == B)     next = S_DONE;
                    else if (A > B) next = S_SUBA;
                    else            next = S_SUBB;
            S_SUBA: next = S_CMP;
            S_SUBB: next = S_CMP;
            S_DONE: if (!start) next = S_IDLE;
            default: next = S_IDLE;
        endcase
    end

    // datapath: the registers and their microoperations
    always @(posedge clk) begin
        case (state)
            S_LOAD: begin A <= x; B <= y; end
            S_SUBA: A <= A - B;
            S_SUBB: B <= B - A;
            default: ;
        endcase
    end

    assign result = A;
    assign done   = (state == S_DONE);
endmodule

Example 2.2: tracing gcd(12, 18)

Let x = 12, y = 18 and start = 1. Each row is one clock cycle: the state the machine is in during the cycle, the microoperation of that state, and the register contents after the edge that ends the cycle.

Cycle State Microoperation \(A\) after \(B\) after Decision for the next state
0 IDLE none ? ? start = 1, go to LOAD
1 LOAD A ← 12, B ← 18 12 18 go to CMP
2 CMP none 12 18 \(A < B\), go to SUBB
3 SUBB B ← 18 − 12 12 6 go to CMP
4 CMP none 12 6 \(A > B\), go to SUBA
5 SUBA A ← 12 − 6 6 6 go to CMP
6 CMP none 6 6 \(A = B\), go to DONE
7 DONE none 6 6 done = 1, result = 6

The machine announces its answer, \(6\), seven clock cycles after it left IDLE. Notice that the datapath registers change only in the three states that name a microoperation, and that the decisions in CMP read the status of the registers as they stand at the start of the cycle.

The design shows the division of labour clearly. The always @(*) block is purely the schedule: it never touches A or B. The clocked block with the case is purely the datapath: it never decides what comes next. Almost every controller in a real chip, from a UART to a memory controller, has this shape.

2.6 Summary

  • A bus is one set of shared wires carrying one register at a time. A multiplexer bus is purely combinational and is what synthesis builds; a tri-state bus needs control that guarantees one driver.
  • Memory is a large array of registers addressed through AR; M[AR] names the addressed word, and a read or a write is an ordinary microoperation. A read in a pulse uses the address as it was at the start of the pulse.
  • Every design divides into a datapath (what can be computed) and a control unit (in what order), the control unit being a finite state machine that may be hardwired or microprogrammed.
  • A conditional transfer maps almost mechanically onto HDL: the edge, the condition and the arrow each acquire a spelling.
  • A small machine such as the GCD unit is designed by listing the registers, the status signals, the states with their microoperations and the next-state decisions, and then writing the three parts of the code.

2.7 Exercises

Exercise 2.1. Eight 16-bit registers must be able to exchange data. How many wires does direct wiring of every pair need, and how many data wires does a multiplexer bus need? How many select lines does the bus multiplexer need?

Answer

Direct wiring needs \(n(n-1) = 8 \times 7 = 56\) one-way paths of 16 wires, which is \(896\) wires. A bus needs only 16 data wires. To choose among 8 sources the multiplexer needs \(\lceil \log_2 8 \rceil = 3\) select lines.

Exercise 2.2. Write the control schedule (cycle, microoperation, signals raised) for the instruction "add the contents of the memory word whose address is in AR to ACC, then increment AR". Can the increment share a cycle with another step?

Answer

One possible schedule uses three cycles. T0: DR ← M[AR] (memory read, load DR). T1: ACC ← ACC + DR (ALU add, load ACC). T2: AR ← AR + 1 (increment, load AR). The increment can share a cycle with the read, because the read samples AR at the start of the pulse: DR ← M[AR], AR ← AR + 1 in T0 is legal (Example 2.1), which shortens the schedule to two cycles.

Exercise 2.3. A word in memory is to be incremented in place: M[AR] ← M[AR] + 1. Memory has a single port, so only one access is possible per cycle. Give a sequence of microoperations that does it.

Answer

Memory cannot be read and written in the same cycle, so the update is split into three steps. T0: DR ← M[AR] (read). T1: DR ← DR + 1 (use the ALU). T2: M[AR] ← DR (write back). AR does not change during the sequence.

Exercise 2.4. Trace the GCD machine of Section 2.5 for x = 9, y = 6, giving the contents of A and B after each LOAD, SUBA and SUBB cycle and the final result.

Answer

After LOAD: \(A = 9\), \(B = 6\). In CMP, \(A > B\), so SUBA: \(A = 9 - 6 = 3\). In CMP, \(A < B\) (\(3 < 6\)), so SUBB: \(B = 6 - 3 = 3\). In CMP, \(A = B\), so the machine goes to DONE with result = 3, and \(\gcd(9, 6) = 3\).

Exercise 2.5. What does the GCD machine do if x = 0 and y = 5? Suggest a change that makes the design safe, and say where in the design it belongs.

Answer

After LOAD, \(A = 0\) and \(B = 5\). In every CMP cycle \(A < B\), so the machine enters SUBB and computes \(B \leftarrow 5 - 0 = 5\), again and again, and never reaches DONE. The fix belongs in the control: in LOAD (or in CMP) test whether either register is zero and, if so, go to DONE at once, with a convention such as returning the other operand, since \(\gcd(0, n) = n\). This adds one status signal (A == 0, B == 0) from the datapath and one extra branch in the next-state logic.

Exercise 2.6. A designer proposes to implement the control unit of a simple, fast processor as a microprogram stored in a ROM, "because it can be changed later". Give one argument for and one against.

Answer

For: a ROM-based control unit can be corrected or extended by rewriting the control memory, with no redesign of logic, which suits machines with large and complicated instruction sets. Against: each step costs an extra memory read, so the machine is slower, and a simple, regular instruction set (as in RISC designs) needs little control, which hardwired logic generates directly and quickly.