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 datapathEach clock cycle:
The microinstruction at address CAR is read from control memory.
Its control field drives the datapath for this cycle.
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.