Microprogrammed control unit

Why it exists

A hardwired control unit is a tangle of gates built for one particular instruction set. In the 1950s Maurice Wilkes proposed a tidier idea: treat each control step as a small word in a memory, and let the control unit do nothing but read words from that memory and send their bits to the datapath. The word is a microinstruction; the memory is the control store; the sequence of microinstructions for one machine instruction is a microroutine; and all microroutines together are the microprogram. Designing a control unit becomes writing a program, and changing the instruction set means changing the contents of a memory. GATE asks for the size of the control word, the size of the control store, how the next microinstruction address is chosen, and the comparison with hardwired control.

Prerequisites

You need the datapath and its control signals from the datapath.

Precise definitions

Microinstruction (control word). The set of control signals asserted in one control step, stored as a row of bits. In the simplest (horizontal) format there is one bit per control signal: the bit is 1 if the signal is asserted. Besides the signal bits a microinstruction may have a next-address field and a condition-select field for branching.

Control store (control memory). A ROM (or writable memory) holding all microinstructions. Its address input is the micro-program counter. Its size is (number of microinstructions) $\times$ (control word width).

Micro-program counter ($\mu$PC, also the control address register). Holds the address of the microinstruction to execute. Its next value is chosen by the sequencing logic:

1. Sequential: $\mu\text{PC} \leftarrow \mu\text{PC} + 1$ (the common case).
2. Starting a microroutine: after the instruction has been fetched into IR, the mapping logic converts the opcode into the starting address of its microroutine. In the example, ADD maps to 10 and LOAD to 20.
3. End of the microroutine: the End bit sets $\mu\text{PC}$ to 0, the start of the fetch routine.
4. Branching: an address field in the microinstruction, selected by a condition (a flag or a test of the instruction fields), replaces $\mu\text{PC}$. Some designs also have microprogram subroutines (a return address register) so that common sequences are shared.

Execution of one microinstruction. Read the control word at $\mu\text{PC}$ into the microinstruction register; its signal bits drive the datapath for one control step; compute the next $\mu\text{PC}$. One microinstruction therefore corresponds to one control step of the datapath. A machine instruction takes as many microinstructions as it has control steps (6 for ADD and LOAD in the earlier examples).

Horizontal and vertical formats.

• Horizontal: one bit per signal. Very wide (tens to hundreds of bits), allows many signals in parallel (high speed), needs no decoding.
• Vertical: signals are grouped into mutually exclusive groups (signals that are never asserted in the same step, for instance the registers that can drive the bus) and each group is encoded in a field. A group of $k$ exclusive signals plus "none" needs $\lceil \log_2 (k + 1) \rceil$ bits. The word is much narrower, but a decoder per field is needed (extra delay) and fewer things can happen in parallel.
• Real designs use a mix, encoding only the groups that are naturally exclusive.

Control word width. Horizontal: $\#\text{signals}$ (+ next-address bits). Vertical: $\sum_{\text{groups}} \lceil \log_2(k_g + 1) \rceil$ (+ next-address bits).

Control store size. $\text{rows} \times \text{width}$. The number of address bits of the store is $\lceil \log_2 \text{rows} \rceil$ and sets the width of the next-address field.

Nanoprogramming. When many microinstructions repeat, a two-level control can store each distinct microinstruction once in a small nanostore and keep in the main control store only short pointers to them: less memory, but one more memory access per step.

Properties. Compared with hardwired control: easier to design (it is a program), easier to modify (rewrite the store; a writable control store even allows the instruction set to be changed or another machine to be emulated), handles complex instruction sets systematically, and is cheaper for them; but it is slower (a control store access in every step) and needs the memory.

How it works

The animation executes the fetch and ADD R1,R2. Each micro-instruction takes two animation steps: first the control word is read from the control store (CW <- CS[uPC]), then its bits drive the datapath and the next address is computed. Watch the micro-program counter: 0, 1, 2 (the fetch), then 10, 11, 12 (the ADD routine), then 0 again. After the third microinstruction loads IR, the mapping logic turns the opcode ADD into the address 10.

The memory column on the right is the control store: each row is an 18-bit control word (bit order PCout, PCin, MARin, MDRout, IRin, Yin, Zin, Zout, R1out, R1in, R2out, R3in, Read, WMFC, Select4, SelectY, Add, End), shown in groups of six bits next to the names of the signals that are 1.

Worked examples

#include <stdio.h>
 
enum { PCout, PCin, MARin, MDRout, IRin, Yin, Zin, Zout, R1out, R1in, R2out, R3in, Read, WMFC, Select4, SelectY, Add, End, NSIG };
#define B(x) (1u << (x))
 
/* the control store: one 18-bit control word (one bit per signal) per row */
static unsigned store[32];
 
static int bits_needed(int exclusive_signals) {        /* k mutually exclusive signals plus "none" need ceil(log2(k + 1)) bits */
    int b = 0;
    while ((1 << b) < exclusive_signals + 1) b++;
    return b;
}
 
int main(void) {
    store[0] = B(PCout) | B(MARin) | B(Read) | B(Select4) | B(Add) | B(Zin);
    store[1] = B(Zout) | B(PCin) | B(Yin) | B(WMFC);
    store[2] = B(MDRout) | B(IRin);
    store[10] = B(R1out) | B(Yin);                     /* ADD R1,R2 */
    store[11] = B(R2out) | B(SelectY) | B(Add) | B(Zin);
    store[12] = B(Zout) | B(R1in) | B(End);
    store[20] = B(R2out) | B(MARin) | B(Read);         /* LOAD R3,(R2) */
    store[21] = B(WMFC);
    store[22] = B(MDRout) | B(R3in) | B(End);
    int start[2] = { 10, 20 };                         /* mapping: opcode ADD -> 10, LOAD -> 20 */
    int upc = 0, count = 0;
    printf("micro-program counter:");
    for (int instr = 0; instr < 2; instr++) {
        do {
            printf(" %d", upc);
            unsigned cw = store[upc];
            count++;
            if (cw & B(End)) upc = 0;                  /* End: back to the fetch routine */
            else if (cw & B(IRin)) upc = start[instr]; /* after IR is loaded, map the opcode to its routine */
            else upc++;
        } while (upc != 0);
    }
    printf(" %d\n%d microinstructions executed for the two instructions\n", upc, count);
    int width = NSIG;
    printf("horizontal control word: %d bits (one per signal), the 9 rows above need %d bits of control store\n", width, 9 * width);
    /* vertical encoding: 5 mutually exclusive bus drivers need 3 bits instead of 5 */
    printf("encoding the 5 bus-driver signals in %d bits instead of 5 gives a %d-bit word\n", bits_needed(5), width - 5 + bits_needed(5));
    int groups[5] = { 3, 7, 15, 4, 1 }, h = 0, v = 0;
    for (int g = 0; g < 5; g++) { h += groups[g]; v += bits_needed(groups[g]); }
    printf("30 signals in groups of 3, 7, 15, 4, 1: horizontal %d bits, vertical %d bits; 500 microinstructions need %d against %d bits\n", h, v, 500 * h, 500 * v);
    return 0;
}

micro-program counter: 0 1 2 10 11 12 0 1 2 20 21 22 0
12 microinstructions executed for the two instructions
horizontal control word: 18 bits (one per signal), the 9 rows above need 162 bits of control store
encoding the 5 bus-driver signals in 3 bits instead of 5 gives a 16-bit word
30 signals in groups of 3, 7, 15, 4, 1: horizontal 30 bits, vertical 13 bits; 500 microinstructions need 15000 against 6500 bits

Cheat box

Traps and GATE patterns

Connections

The control signals are those of the datapath, and the alternative implementation by gates is the hardwired control unit. The control store is a ROM, the same kind of structure as in ROM and PLA, and the vertical format uses decoders and multiplexers to expand the encoded fields. The choice between the two control styles is one of the differences between CISC and RISC.

PYQs

Consider a CPU where all the instructions require
7 clock cycles to complete execution. There are 140
instructions in the instruction set. It is found that
125 control signals are needed to be generated by
the control unit. While designing the horizontal
micro-programmed control unit, single address
field format is used for branch control logic. What
is the minimum size of the control word and control
address register?

An instruction set of a processor has 125 signals
which can be divided into 5 groups of mutually
exclusive signals as follows:

Group 1: 20 signals,
Group 2: 70 signals,
Group 3: 2 signals,
Group 4: 10 signals,
Group 5: 23 signals.

How many bits of the control words can be saved
by using vertical microprogramming over
horizontal microprogramming?

Self-check

Revision card

References