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.

Microprogram

A general sequential circuit.  The Combinational circuit can be directly implemented as a truth table, although it is not efficient in terms of size. A read-only-memory (ROM) stored the truth table.  This ROM can be regarded as storing a "program".

sequential circuit

The ROM can output a fixed sequence of control signals simply by cycling the address of the ROM.  The content of this ROM is a microprogram.  It is comparable to a straight line program (no transfer of control).  Each entry in the ROM is called a microword. A microprogram counter is used to cycling the sequence of control.

sequencing a rom

Conditionals are the bits used to determine the flow of microprogram.  The next address determines the next microword to be executed.
A microprogram is executed as follows.
  1. A microword at the location specified by the microprogram counter is read out; control bits are latched at an output buffer which is connected to the data path.
  2. If the conditional field is specified and the test for conditional is true, the next address of microprogram will come from the next address field otherwise the microprogram counter will be incremented (execute the next microword).
microprogram control unit
What that has been described is called horizontal microprogram.  The microword can have other formats.  There are several possibilities:
  1. Single format, one address as just described above.
  2. Single format, two addresses, contain two next addresses field, one for result of test true, and the other for result of test false.
  3. Multiple formats, such as, one format for the control bits without the next address field and another format for jump on condition with the address field.  The advantage is that the microword can be shorter than the single format.  The disadvantage is that to “jump” will take one extra cycle.
Horizontal microprogram allows each control bit to be independent from other therefore enables maximum simultaneous events and also offers great flexibility. It is also waste a lot bit. For each field of a microword, there may be a group of bits that are not active at the same time therefore they can be encoded to use a fewer bit.  A decoder is required to decode these bits and to connect them to the data path.  This approach is called vertical microprogram.  There are many possibilities to compact the micro memory to be as small as possible, sometimes trading off speed for space, for example, a two-level microprogram.  The first level is vertical i.e. maximally encoded; the microword of the level one is pointed to the horizontal word of the second level.  This is rather like the first level is composed entirely from subroutine call and the second level is the subroutine.

The control unit just described has the output of control unit directly mapped to control signals.  It is possible to have more than one output format that map the output of the control unit to the actual control signals, for example using the first bit to choose the format, 1 to mean the control bit, 0 to mean the test and jump to other microprogram address.  This is called two-format microprogram.  It is the effort to reduce the size of microprogram because control and test can be mutually exclusive.

 

control bits

next address

a)       one-address format

 

control bits

true next

false next

b)       two-address format

 

0

control bits

 

1

next address

c)       multiple format

data path

example 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").

  8 July 2007
P. Chongstitvatana