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".
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.
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.
- 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.
- 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).
What that has been described is called horizontal microprogram. The
microword can have other formats. There are several possibilities:
- Single format, one address as just described above.
- Single format, two addresses, contain two next addresses field,
one for result of test true, and the other for result of test false.
- 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
c)
multiple
format
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
