Microprogramming


A control unit is the most complex part in a processor.  It sends control signals to activate the data path of a processor.  Let's see an example data path and inspects how it fetches an instruction and executes it.

A control unit can be implemented in either hardwired or microprogram. A hardwired control unit is a large FSM (finite state machine) sending control signals to data path.  A microprogrammed control unit is a complex programmable unit that outputs control signals to data path according to its "microprogram".  A microprogrammed control unit can be regarded as a simple computer.  In this view, a processor has another simple processor inside it which is its control unit.  Controlling a data path is described by its microprogram.

data path

specification

32-bit ALU
32-bit bus width
32 registers

components

register bank: 1 write port, 2 read ports
ALU : add
T register (temp reg)
32-bit bus
PC (program counter) with +1 op.
memory interface
  MAR (mem address reg)
  MBR (mem buffer reg)
IR (instruction reg)

memory: CS (code segment) contains program

program: machine code

format of a 32-bit instruction

op:5 r1:5 r2:5 r3:5 x:12  (x -- don't care)

op specifies operation of instruction
   ADD  00001
r1,r2,r3  specifies register number, 32 reg. requires 5 bits

example
 
add r1 r2 r3    
means  R[r2]+R[r3] -> R[r1]
  00001 00001 00010 00011 x...x
or written in hex as
  08443X..X

The behaviour of data path can be described in register transfer level (RTL).  The level that specifies how data is flowed between components in the data path.  Let's call this description, microsteps.

notation
label:
source->destination

microsteps

fetch:
  PC -> MAR
  Mread -> MBR
  MBR -> IR
  PC + 1
  decode (goto add:)

execute
add:
  R[r2] + R[r3] -> T
  T -> R[r1]  
  goto fetch:

each step takes one clock.  some step can be overlapped if they are independent, for example, PC + 1 can be activated concurrently of any step in fetch.

Now we want to explore in more details how to realist this behaviour (the microstep).  Let's image each connection to have an ON/OFF gate (valve) associate with it.  The data flow can occur when the gate is ON.  To transfer data from a source through bus to a destination, two gates are opened, one is the gate from source to bus, another one is the gate from bus to destination, for example, to do
PC -> MAR
two gates are:  PC>BUS, BUS>MAR

Here is the list of all gates in the example:

notation
gate number, gate name

1 PC>BUS
2 BUS>MAR
3 MBR>BUS
4 BUS>MBR
5 Mread
6 BUS>IR
7 PC+1
8 Rread
9 ALU:add
10 ALU>T
11 T>BUS
12 Rwrite
13 Mwrite
14 BUS>PC
15 ?

Each microstep can be written as the state of these gates.  We use the convention that when a gate's name is written it is activated (or ON) otherwise it is idles (or OFF).

fetch:
  PC>BUS, BUS>MAR
  Mread
  MBR>BUS, BUS>IR
  PC+1

add:
  Rread, ALU:add, ALU>T
  T>BUS, Rwrite

these events can be written using gate numbers:

fetch:
  1,2
  5
  3,6
  7
add:
  8,9,10
  11,12

A finite state machine is used to realise the control unit.  A FSM for this control unit is:

notation:  state {activation; next state}

A {1,2; B}
B {5; C}
C {3,6; D}
D {7; decode}

E {8,9,10; F}
F {11,12; A}

decode is a state that is multi-way branch to other states according to opcode-field on an instruction in IR (the first 5-bit).
    
This FSM can be implemented using various technology.  The design and implementation of a FSM is greatly simplified by the use of CAD tools.

How complicate is a control unit?

A control unit is implemented as a sequential synchronous machine.  It can be described as

O = f(I)

O output is a function of I input, f is a Boolean function which is purely combinational.  To have state feedback, a part of output is stored in a memory to be fed back to input.  This memory is synchronised with a clock so that changes at its output (the state) happen at the edge of clock.  Between edge of a clock, its output does not change.

Oc = f(Ic,Is)
Is(t+1) = Os(t)

where Oc is the output, Os is the state output, Ic is the input, Is is the state input, t is time.

The size of a combination circuit with I input and O output is   big-oh(O2^I).  This is the size requires to store the output as a function of inputs.

The control unit is the example has
15 outputs
5 inputs from opcode-field of IR
6 states (fetch+add)

Os must be 3 bits to contain 6 states.
Oc is 15
Ic is 5
Is is 3

so its size is (15+3)2^(5+3), approx. 5000 bits (4608)

The table contains f and the state feedback can be viewed as a kind of program.

O = f(I)

address   O = f(I)   state
I       00110101.... 001
...     10001010.... 010
...     ...

the height of this table is 2^I, 256 in our example.  the width of each row in this table is 15+3 bits.  The content of this table is regarded as a program.  We can write it down as the event of activation of gates

fetch {1,2; B}
B {5; C}
C {3,6; D}
D {7; decode}
add {8,9,10; F}
F {11,12; fetch}

This is microprogram, voila!

Advantage and disadvantage of microprogramming.

Advantage

Making change to a hardwired control unit implies global change, that is, the circuit will be almost totally changed.  Hence, it is constly and time consuming although the present CAD tools do reduce most of the burden in this area.  In contrary, for a microprogrammed control unit, making change to it is just changing the microprogram, the bit pattern in the micromemory.  There is tools to generate these bit content from a human-readable microprogram, hence making change to microprogram is similar to edit-compile a program.  The circuit for control unit does not change.  This enables adding new instructions, modifies addressing mode, etc. or updating the version of control behavior easy to do.

Disadvantage

Microprogram relies on fast micromemory.  It requires high speed memory.  In fact, the architect of early microprogrammed machine, IBM S360 family, depended on this crucial technology, which was still in the development at that time.  The breakthrough in memory technology came, and S360 became the most successful family of computers.  Hardwired control unit is much faster.  Microprogramming is inherently very low level, making it hard to be absolutely correct.  Microprogramming is by nature concurrent, many events occur at the same time, so it is difficult to develop and debug. (for a good reading that shows this process, read Tracy Kidder's "Soul of a new machine").

16 July 2004
P. Chongstitvatana