Single-bus datapath and register transfer

Why it exists

The instruction cycle describes what has to happen; the datapath is the hardware that makes it happen. It consists of registers, an ALU, the buses that connect them, and the control signals that open and close the connections. Each control signal is a switch: put this register on the bus, load that register from the bus, make the ALU add, start a memory read. A control step is one clock period during which a set of such switches is closed. An instruction is a sequence of control steps, and the control unit's only job is to produce the right signals in the right order. GATE asks for the control sequence of an instruction on a given datapath, the number of steps it takes, why certain registers exist, and how timing translates to clock rate.

Prerequisites

You need registers and their load control from registers and shift registers, and the ALU from ALU design.

Precise definitions

Single-bus datapath. All registers, the ALU's input and the memory interface are connected to one shared bus. The components:

• PC, MAR, MDR, IR as in the instruction cycle; general registers $R_0 \ldots R_n$.
• Y: a temporary register that holds one ALU operand. Z: a temporary register that holds the ALU result. They exist because the bus can carry only one value at a time, while the ALU needs two operands: one comes from Y and the other from the bus, and the result is held in Z until the bus is free to move it to its destination.
• ALU: its first input is Y or the constant 4 (a multiplexer selects it with SelectY or Select4), its second input is the bus.
• Memory interface: the memory address is taken from MAR and the data goes through MDR. The Read signal starts a read; WMFC ("wait for memory function completed") stalls the control until the memory has delivered the word into MDR.

Control signals. For each register $R$: $R_{in}$ loads it from the bus at the end of the control step; $R_{out}$ puts its contents on the bus during the step. Rules:

1. At most one $R_{out}$ signal may be active in a step (otherwise two registers fight over the bus).
2. Any number of $R_{in}$ signals may be active (several registers can load the same bus value).
3. A register loaded in a step is not available on the bus until the next step (values are latched at the end of the step).

Control sequences (this page's datapath; $+4$ because instructions are 4 bytes). The fetch, common to all instructions:

Execution of ADD R1,R2 (R1 $\leftarrow$ R1 + R2):

Execution of LOAD R3,(R2) (R3 $\leftarrow$ M[R2]):

So both instructions take 6 control steps in this design. An instruction with a memory operand such as ADD R1,(R2) takes 7 (fetch 3, then R2out/MARin/Read; R1out/Yin/WMFC; MDRout/SelectY/Add/Zin; Zout/R1in/End), because the memory read adds a step.

Clocks per instruction. With a fast memory every control step is one clock. A slow memory makes the step with WMFC last as many clocks as the memory needs: with a 3-clock read the fetch takes $1 + 3 + 1 = 5$ clocks, ADD R1,R2 takes $5 + 3 = 8$, and LOAD R3,(R2) takes $5 + 1 + 3 + 1 = 10$.

Clock period. It must be at least the delay of the slowest control step: the time for a register to drive the bus, the bus to settle, the ALU to compute (when used) and the destination register's setup time. Steps that use the ALU are the longest, which is why the ALU delay sets the clock.

Multiple-bus organisations. With two or three buses (for example one for the source registers and one for the destination) the ALU's two operands and its result can move at the same time, so Y and Z are not needed and instructions take fewer steps (the textbook three-bus design executes the same ADD in four control steps instead of six), at the cost of more wiring and gates.

How it works

Step through the two instructions. The rtl line is the set of control signals active in that control step. In each step only one register drives the bus, and every register loaded in the step shows its new value in the next table row.

Worked examples

#include <stdio.h>
 
enum {
    PCout = 1 << 0, PCin = 1 << 1, MARin = 1 << 2, MDRout = 1 << 3, IRin = 1 << 4, Yin = 1 << 5, Zin = 1 << 6, Zout = 1 << 7,
    R1out = 1 << 8, R1in = 1 << 9, R2out = 1 << 10, R3in = 1 << 11, Read = 1 << 12, WMFC = 1 << 13, Select4 = 1 << 14,
    SelectY = 1 << 15, Add = 1 << 16, End = 1 << 17
};
#define OUTS (PCout | MDRout | Zout | R1out | R2out)
 
static const int fetch[3] = { PCout | MARin | Read | Select4 | Add | Zin, Zout | PCin | Yin | WMFC, MDRout | IRin };
static const int add_seq[3] = { R1out | Yin, R2out | SelectY | Add | Zin, Zout | R1in | End };
static const int load_seq[3] = { R2out | MARin | Read, WMFC, MDRout | R3in | End };
 
static int pc = 100, mar, mdr, ir, y, z, r1 = 5, r2 = 8, r3;
static int mem[64];                                   /* word index = byte address / 4: 1 = ADD R1,R2   2 = LOAD R3,(R2) */
static int pending;
 
/* one control step: at most one register may drive the bus; everything loaded is latched at the end of the step */
static int step(int s) {
    int drivers = s & OUTS;
    if (drivers & (drivers - 1)) return -1;           /* two drivers on the bus */
    int bus = 0;
    if (s & PCout) bus = pc;
    if (s & MDRout) bus = mdr;
    if (s & Zout) bus = z;
    if (s & R1out) bus = r1;
    if (s & R2out) bus = r2;
    int alu = ((s & Select4) ? 4 : y) + bus;
    int npc = pc, nmar = mar, nmdr = mdr, nir = ir, ny = y, nz = z, nr1 = r1, nr3 = r3;
    if (s & PCin) npc = bus;
    if (s & MARin) nmar = bus;
    if (s & IRin) nir = bus;                          /* the bus carries MDR during the IRin step */
    if (s & Yin) ny = bus;
    if ((s & Zin) && (s & Add)) nz = alu;
    if (s & R1in) nr1 = bus;
    if (s & R3in) nr3 = bus;
    if (s & Read) pending = 1;
    if (s & WMFC) { nmdr = mem[mar / 4]; pending = 0; }
    pc = npc; mar = nmar; mdr = nmdr; ir = nir; y = ny; z = nz; r1 = nr1; r3 = nr3;
    return 0;
}
 
int main(void) {
    mem[100 / 4] = 1;
    mem[104 / 4] = 2;
    mem[8 / 4] = 42;
    int steps = 0;
    for (int instr = 0; instr < 2; instr++) {
        for (int i = 0; i < 3; i++) { step(fetch[i]); steps++; }
        const int *seq = ir == 1 ? add_seq : load_seq;
        for (int i = 0; i < 3; i++) { step(seq[i]); steps++; }
        printf("after %s: PC = %d, R1 = %d, R3 = %d, %d control steps so far\n", ir == 1 ? "ADD R1,R2" : "LOAD R3,(R2)", pc, r1, r3, steps);
    }
    printf("two drivers on the bus (R1out + R2out) rejected: %s\n", step(R1out | R2out) < 0 ? "yes" : "no");
    return 0;
}

after ADD R1,R2: PC = 104, R1 = 13, R3 = 0, 6 control steps so far
after LOAD R3,(R2): PC = 108, R1 = 13, R3 = 42, 12 control steps so far
two drivers on the bus (R1out + R2out) rejected: yes

Cheat box

Traps and GATE patterns

Connections

The sequence of micro-operations here is the register-transfer description of the instruction cycle. The signals are produced either by a hardwired control unit or by a microprogrammed one. The registers are the registers of the digital logic part, and the ALU is ALU design. Pipelining replaces one long multi-step execution by overlapping the steps of several instructions.

PYQs

A partial data path of a processor is given in the
figure, where RA, RB, and RZ are 32-bit registers.
Which option(s) is/are CORRECT related to
arithmetic operations using the data path as shown?

Consider the following data path diagram

Consider an instruction: R0 ← R1 + R2. The
following steps are used to execute it over the given
data path. Assume that the PC is incremented
appropriately. The subscripts r and w indicate read
and write operations, respectively.
1. R2r TEMP1r, ALUadd, TEMP2w
2. R1r TEMP1w,
3. PCr, MARw, MEMr
4. TEMP2r, R0w
5. MDRr, IRw
Which one of the following is the correct order of
execution of the above steps?

The following data path of a CPU

The ALU, the bus and all the registers in the data
path are of identical size. All operations including
incrementation of the PC and the GPRs are to be
carried out in the ALU. Two clock cycles are
needed for memory read operation—the first one
for loading addresses in the MAR and the next one
for loading data from the memory bus into the
MDR.
The instruction "add R0, R1" has the register
transfer interpretation
R0 ← R0 + R1.
The minimum number of cycles needed for
execution cycle of this instruction is

Consider the following data path of a CPU.

The ALU, the bus and all the registers in the data
path are of identical size. All operations including
incrementation of the PC and the GPRs are to be
carried out in the ALU. Two clock cycles are
needed for memory read operation - the first one
for loading address in the MAR and the next one
for loading data from the memory bus into the
MDR.
The instruction "call Rn, sub" is a two word
instruction. Assuming that PC is incremented
during the fetch cycle of the first word of the
instruction, its register transfer interpretation is
Rn ← PC + 1
PC ← M[PC]
The minimum number of CPU clock cycles needed
during the execution cycle of this instruction is:

Self-check

Revision card

References