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