Chapter 19 of 39

Microprogrammed Control Unit

An old player piano does not need a pianist. A paper roll with punched holes passes over a reader; every row of holes says which keys to press at that moment. To play a different song you do not rebuild the piano, you just insert a different roll.

A microprogrammed control unit works the same way. In Hardwired Control Unit we produced each control signal with logic gates. Here, instead, we write down the set of control signals for each step as a row of bits (a "row of holes"), store all the rows in a small memory inside the CPU, and read them out one by one. The idea was proposed by Maurice Wilkes in 1951, and it powered most complex instruction set computers for decades, from the IBM System/360 to today's x86 microcode.

A microprogrammed control unit stores the control signals for each step of each instruction as microinstructions in a control memory. A microprogram sequencer reads them one at a time; the bits of the current microinstruction directly (or after decoding) become the control signals for that clock cycle.

We will build a small microprogram for the single-bus datapath of ALU & Datapath (and check it by simulating the sequencer), study next-address generation and mapping, compare horizontal and vertical formats, and solve the classic control-memory sizing problems.


Vocabulary

Term

Meaning

Control word (CW)

A string of bits, one pattern of control signals for one step.

Microinstruction

A control word plus sequencing information (how to find the next microinstruction).

Microprogram (microroutine)

The sequence of microinstructions that carries out one machine instruction (or the fetch).

Control memory (CM)

The memory holding all microprograms; usually a ROM inside the CPU (writable control store if it is RAM).

CAR (control address register), also μPC

Holds the address of the next microinstruction to read.

CDR / μIR (control data register)

Holds the microinstruction just read from control memory (optional; used for pipelining the control).

Microprogram sequencer

The logic that computes the next value of CAR.

Mapping logic

Converts the opcode of the machine instruction into the starting address of its microroutine.

Firmware

Microcode is called firmware because it sits between hardware and software.

Do not confuse two "programs". The machine program (ADD, LOAD, BR ...) is in main memory and is fetched by PC. The microprogram is in control memory and is stepped through by CAR. One machine instruction runs a whole microroutine.


Block Diagram

              IR (opcode)    status flags (N, Z, ...)    external (MFC, ...)
                  |                  |                          |
           +------v-----+            |                          |
           |  mapping   |            v                          |
           |   logic    |--->+-----------------+<---------------+
           +------------+    |  microprogram   |
                             |   sequencer     |<----- next-address and
                             +--------+--------+       branch fields
                                      | next address          ^
                               +------v------+                |
                               |     CAR     |  (+1 incrementer inside sequencer)
                               +------+------+                |
                                      |                       |
                               +------v------+                |
                               |   control   |                |
                               |   memory    |                |
                               +------+------+                |
                                      |                       |
                               +------v------+                |
                               | μIR / CDR   |----------------+
                               +------+------+
                                      | control field (decoded if encoded)
                                      v
                       control signals to the datapath

Each clock cycle:

  1. The microinstruction at address CAR is read from control memory.

  2. Its control field drives the datapath for this cycle.

  3. The sequencer uses the microinstruction's sequencing fields, the flags and possibly the opcode to load the next value into CAR.


A Small Microprogram

Let us turn the control sequences of the single-bus datapath into microcode. Each microinstruction has three parts:

+-------------------------------------+------+------+------+
|  control field: one bit per signal  |  BR  | COND |  AD  |
|  (PCout, MARin, Read, Add, Zin, ...)|  2   |  2   |  4   |
+-------------------------------------+------+------+------+
  • BR (branch type): NEXT (CAR ← CAR + 1), JUMP (CAR ← AD if COND is true, else CAR + 1), MAP (CAR ← start address of the current opcode's routine), FETCH (CAR ← 0, which plays the role of End).

  • COND: U (always true), N, NOT N, Z.

  • AD: a branch address (4 bits are enough for this 16-word control memory).

The mapping logic is a tiny lookup table: ADD R1, R2 → 4; ADD R1, (R3) → 8; BRN → 12.

Address

Control signals (bits that are 1)

BR

COND

AD

0

PCout, MARin, Read, Select4, Add, Zin

NEXT

U

-

1

Zout, PCin, Yin, WMFC

NEXT

U

-

2

MDRout, IRin

MAP

U

-

4

R1out, Yin

NEXT

U

-

5

R2out, SelectY, Add, Zin

NEXT

U

-

6

Zout, R1in

FETCH

U

-

8

R3out, MARin, Read

NEXT

U

-

9

R1out, Yin, WMFC

NEXT

U

-

10

MDRout, SelectY, Add, Zin

NEXT

U

-

11

Zout, R1in

FETCH

U

-

12

Offsetout, SelectY, Add, Zin

JUMP

NOT N

0

13

Zout, PCin

FETCH

U

-

Words 0 to 2 are the fetch routine, shared by all instructions. The MAP at word 2 is the microcode equivalent of "decode": it jumps to the routine for whatever opcode is now in IR.

Tracing It

We simulated this control memory with a small sequencer model. The addresses visited are:

Machine instruction

CAR sequence

Microinstructions

ADD R1, (R3)

0, 1, 2, 8, 9, 10, 11

7

ADD R1, R2

0, 1, 2, 4, 5, 6

6

BRN with N = 0 (not taken)

0, 1, 2, 12 → back to 0

4

BRN with N = 1 (taken)

0, 1, 2, 12, 13

5

The control signals produced in each step are exactly the same as the hardwired control sequences. The difference is where they come from: a ROM word instead of an AND-OR network. Fixing a bug in ADD now means changing words 8 to 11, not rewiring gates.

Notice the conditional branch at word 12: when N = 0, COND "NOT N" is true and CAR jumps to 0 (fetch), ending the instruction early, just like the term T4·BRN·N' in the hardwired End equation.


Next-Address Generation

The sequencer must be able to choose the next CAR value from several sources:

Source

Used for

CAR + 1

Normal sequential execution within a routine

Address field of the microinstruction

Unconditional or conditional branch (taken when the selected flag is true)

Mapping of the opcode

Jumping from the fetch routine to the instruction's routine

Subroutine register (SBR)

Return from a micro-subroutine (e.g. a shared routine that computes an effective address)

Fixed address (e.g. 0)

Going back to fetch at the end of an instruction, or to an interrupt routine

In hardware this is a multiplexer in front of CAR, plus a condition-select multiplexer that picks one status bit to test. The BR and COND fields drive their select inputs.

Two Ways to Specify the Next Address

  • Explicit next address in every microinstruction: no incrementer needed, any word can follow any word, but every microinstruction carries a full address field.

  • Implicit sequencing (CAR + 1 by default) with an address field used only for branches: shorter words, but routines must be laid out in consecutive addresses.

Mapping by Bit Placement

A mapping ROM is the most flexible, but a popular cheap trick is to place the opcode bits directly into CAR. In Mano's textbook computer, the 4-bit opcode is placed into a 7-bit CAR as 0 xxxx 00:

Opcode

CAR (0 xxxx 00)

Routine starts at

0000

0 0000 00

0

0001

0 0001 00

4

0101

0 0101 00

20

1011

0 1011 00

44

1111

0 1111 00

60

The two zeros at the end give each instruction a block of 4 consecutive words; a longer routine jumps elsewhere. The leading 0 keeps addresses 0 to 63 for instruction routines, and the fetch routine lives at address 64 and above.

Mano's Microinstruction Format

For reference, Mano's basic computer uses a 128-word control memory with 20-bit microinstructions:

+-----+-----+-----+----+----+---------+
| F1  | F2  | F3  | CD | BR |   AD    |
|  3  |  3  |  3  |  2 |  2 |    7    |   = 20 bits
+-----+-----+-----+----+----+---------+
F1, F2, F3 : three encoded micro-operation fields (up to 3 micro-ops per word)
CD         : condition  (U = always 1, I = indirect bit, S = sign of AC, Z = AC is zero)
BR         : branch type (JMP, CALL, RET, MAP)
AD         : 7-bit address field (2^7 = 128 words)

Its fetch routine is three microinstructions at address 64: AR ← PC; then read memory and increment PC; then load the address part into AR and MAP to the opcode's routine.


Horizontal vs Vertical Microinstructions

How should the control field be encoded? There are two extremes.

Horizontal (Unencoded)

One bit per control signal. With 30 control signals, the control field is 30 bits wide. Any combination of signals can be active at once, so maximum parallelism, and no decoder delay. The price is very wide control memory.

Vertical (Encoded)

Signals are encoded so the field is short, and a decoder expands it. The usual approach is to put signals that are mutually exclusive (never needed in the same step) into the same group, and encode each group with ⌈log2(k + 1)⌉ bits, where the extra code means "none of this group". For example, only one register can drive a single bus at a time, so all the "Rout" signals form one group.

Worked Example: Encoding 30 Signals

A CPU has 30 control signals that split into four mutually exclusive groups of 3, 7, 8 and 12 signals.

Group size k

Bits with a "none" code: ⌈log2(k + 1)⌉

Bits if one signal is always active: ⌈log2 k⌉

3

2

2

7

3

3

8

4

3

12

4

4

Total

13

12

Horizontal encoding would need 30 bits; field encoding reduces it to 13 (or 12). The group of 8 shows why the convention matters: 8 signals plus "none" are 9 codes, which do not fit in 3 bits. Many exam questions simply use ⌈log2 k⌉ per group; if the question does not mention a "no operation" code, state which convention you use.

An extremely vertical format encodes the whole control field as one number, allowing only one signal (or one micro-operation) per microinstruction: 30 signals would need just ⌈log2 31⌉ = 5 bits, but then many more microinstructions are needed per machine instruction.

Feature

Horizontal

Vertical

Control field

One bit per signal

Encoded fields

Word width

Wide

Narrow

Parallelism

High: many signals per word

Limited by the encoding

Decoders needed

No

Yes (extra delay)

Microinstructions per routine

Fewer

More

Speed

Faster

Slower

Control memory size

Larger (wide words)

Usually smaller


Nanoprogramming

Often a large microprogram uses only a few distinct control words, repeated many times. Nanoprogramming exploits this with two levels of memory:

  • The nano memory stores each distinct wide control word once.

  • The micro memory stores, for each microinstruction, only a short pointer into the nano memory.

Worked Example

A microprogram has 512 microinstructions, each 120 bits wide, but only 100 of them are distinct.

  • One-level control memory: 512 × 120 = 61,440 bits.

  • Two-level: a pointer needs ⌈log2 100⌉ = 7 bits. Micro memory = 512 × 7 = 3,584 bits; nano memory = 100 × 120 = 12,000 bits. Total = 15,584 bits.

That is about 3.9 times smaller. The cost is speed: every step needs two memory reads (micro, then nano). The Motorola 68000 is the best-known processor that used this scheme.


Hardwired vs Microprogrammed Control

Aspect

Hardwired

Microprogrammed

How signals are produced

Combinational logic from step counter, opcode and flags

Read from control memory, one microinstruction per step

Speed

Faster (gate delays only)

Slower (a control-memory read each step)

Flexibility

Changes need a circuit redesign

Change the microcode (even after shipping, with writable control store or microcode updates)

Design effort for large ISAs

Very high, irregular logic

Systematic, like writing a program

Handling complex instructions

Difficult

Easy: just a longer microroutine

Chip area

Grows quickly with ISA complexity

Control memory plus a simple sequencer

Typical use

RISC (MIPS, ARM, RISC-V), pipelined cores

CISC (IBM System/360, VAX, x86 complex instructions)

Modern x86 processors mix both: the common instructions are decoded by hardwired logic, and the complex ones are handled by a microcode ROM. Intel and AMD also ship microcode updates (loaded by the BIOS or OS at boot) to fix errata, which is only possible because part of the control is microprogrammed.


Solved Problems

Problem 1: Control Memory Size

A horizontal microprogrammed CPU has 40 control signals. The condition-select field chooses one of 12 status flags for conditional branches, and the next-address field addresses a control memory of 2048 words. Find the microinstruction width and the control memory size.

Solution.

  • Control field: 40 bits (one per signal).

  • Condition select: ⌈log2 12⌉ = 4 bits.

  • Next address: log2 2048 = 11 bits.

  • Width = 40 + 4 + 11 = 55 bits. Size = 2048 × 55 = 112,640 bits (14,080 bytes).

Problem 2: Microinstructions for a Machine Instruction

Using the control memory in this chapter, how many microinstructions are executed for the sequence ADD R1, (R3); BRN (with N = 0); ADD R1, R2?

Solution. 7 + 4 + 6 = 17. If each microinstruction takes one clock cycle (ignoring memory waits), the three instructions take 17 cycles.

Problem 3: Mapping

In the 0 xxxx 00 mapping scheme, at which control memory address does the routine for opcode 0110 start, and how many words does it have before it must jump?

Solution. 0 0110 00 = 00110002 = 24. The block is addresses 24 to 27, i.e. 4 words.

Problem 4: Field Encoding

A microinstruction controls 64 signals. A designer finds that they form 5 mutually exclusive groups of 4, 10, 14, 16 and 20 signals. With one "none" code per group, how wide is the encoded control field?

Solution. ⌈log2 5⌉ + ⌈log2 11⌉ + ⌈log2 15⌉ + ⌈log2 17⌉ + ⌈log2 21⌉ = 3 + 4 + 4 + 5 + 5 = 21 bits, compared with 64 bits horizontal.

Problem 5: Nanoprogram

A control unit needs 2048 microinstructions of 64 bits, of which 256 are distinct. Compare one-level and two-level storage.

Solution. One-level: 2048 × 64 = 131,072 bits. Two-level: pointer = log2 256 = 8 bits; 2048 × 8 + 256 × 64 = 16,384 + 16,384 = 32,768 bits, one quarter of the one-level size.


Common Mistakes

  • Confusing CAR with PC. PC points into main memory (machine instructions); CAR points into control memory (microinstructions).

  • Forgetting the "none" code when encoding a group. A group of 8 signals plus "none" needs 4 bits, not 3.

  • Thinking vertical is always better because it is narrower. It needs decoders and more microinstructions, so it is slower.

  • Forgetting the address field when sizing control memory. Width = control field + condition select + branch type + next address.

  • Assuming microprogrammed means slow in every case. For complex instructions, a microcoded routine may be the only practical implementation; modern CPUs keep hardwired paths for the common cases.


Interview Questions

What is a microinstruction?

A word in control memory that specifies the control signals for one step, plus information for selecting the next microinstruction (branch type, condition, address).

What does the mapping logic do?

It converts the opcode of the fetched machine instruction into the address of the first microinstruction of that instruction's routine, e.g. with a mapping ROM or by placing opcode bits into CAR (0 xxxx 00).

Compare horizontal and vertical microprogramming.

Horizontal uses one bit per signal: wide, fast, highly parallel. Vertical encodes signals into fields: narrow, needs decoders, fewer signals per word and more microinstructions, so slower.

What is nanoprogramming?

A two-level control store: a nano memory holds each distinct control word once, and the micro memory holds short pointers into it, saving space when many microinstructions repeat.

Why are microcode updates possible on modern x86 CPUs?

Part of their control is microprogrammed, and the processor can load a patch into a small writable area that overrides parts of the microcode ROM, so some bugs can be fixed without new hardware.

Why did RISC designs move away from microprogramming?

Their simple, fixed-format instructions can be controlled by small, fast hardwired logic, which suits pipelining; microcode adds a memory access per step and is mainly useful for complex instructions.


Summary

  • A microprogrammed control unit stores control words in control memory and reads one microinstruction per step, addressed by the CAR.

  • The sequencer chooses the next address from CAR + 1, a branch address (conditional on a flag), the opcode mapping, a subroutine return, or the fetch address.

  • Our sample microcode for the single-bus datapath runs ADD R1, (R3) in 7 microinstructions and BRN in 4 or 5, exactly matching the hardwired sequences.

  • Horizontal: one bit per signal, wide and fast. Vertical: encoded fields (⌈log2(k + 1)⌉ bits per group of k), narrow and slower.

  • Nanoprogramming stores distinct control words once and saves memory at the cost of a second lookup.

  • Hardwired is faster and suits RISC; microprogrammed is flexible and suits CISC. Next, we look at arithmetic algorithms that these control units sequence, starting with Booth's Multiplication Algorithm.