Control Unit

Types of instructions

An instruction tells the CPU one operation. By their job, instructions fall into these groups.

• Data transfer: move data between registers and memory, for example LOAD, STORE, MOV, PUSH, POP.
• Arithmetic: ADD, SUB, MUL, DIV, INC, DEC.
• Logical and shift: AND, OR, XOR, NOT, shifts and rotates.
• Program control: JMP, conditional branches such as JZ, CALL and RET. They change the value of PC.
• Input and output: IN and OUT, which move data to and from devices.

Instruction formats

An instruction word has an opcode, which tells the operation, and operand fields, which tell where the data is. It may also have a mode field for the addressing mode. The number of address fields decides the format.

Take the statement $X = (A + B) \times (C + D)$ to see each format.

Three-address format. Each instruction has two sources and one destination.

ADD R1, A, B      ; R1 = A + B
ADD R2, C, D      ; R2 = C + D
MUL X, R1, R2     ; X = R1 * R2

The program is short, but the instructions are long.

Two-address format. The first operand is also the destination.

MOV R1, A
ADD R1, B
MOV R2, C
ADD R2, D
MUL R1, R2
MOV X, R1

This is the common format in x86 processors.

One-address format. The accumulator AC is the second operand and the destination.

LOAD A
ADD B
STORE T
LOAD C
ADD D
MUL T
STORE X

Zero-address format. Operands are taken from the top of a stack, so the instruction names no address. Only PUSH and POP name a memory address.

PUSH A
PUSH B
ADD
PUSH C
PUSH D
ADD
MUL
POP X

The programs use 3, 6, 7 and 8 instructions. More address fields mean fewer instructions, but longer ones. A zero-address instruction is the shortest, but it needs more of them.

Choosing a format. The three-address format is used in RISC machines such as MIPS, where registers hold the operands, so the fields are short. The two-address format is common in CISC machines such as x86. The one-address format was used in early machines with a single accumulator. The zero-address format is used in stack machines, for example in the evaluation of expressions and in the Java virtual machine. The choice is a balance between program length, instruction length and speed.

Instruction length. For example, if the opcode is 8 bits and each register field is 5 bits, a three-register instruction needs $8 + 3 \times 5 = 23$ bits, and it fits in a 32 bit word with room for a mode field.

An instruction cycle has these phases:

• Fetch: the instruction is read from the memory address held in PC, and PC is incremented.
• Decode: the control unit finds out the operation from the opcode.
• Operand fetch: the effective address is found, and the operand is read from memory or a register.
• Execute: the ALU or another unit does the operation.
• Write back (store): the result is saved in a register or memory.

After this, the CPU may check for an interrupt, and then repeat the cycle for the next instruction.

An instruction passes through a few cycles, called sub cycles, before it is finished. The CPU repeats them for each instruction.

Fetch cycle. The address in PC goes to the address register, and the instruction is read from memory into IR. Then PC is incremented.

$$AR \leftarrow PC$$

$$IR \leftarrow M[AR],; PC \leftarrow PC + 1$$

Decode cycle. The control unit decodes the opcode in IR. It also finds out the addressing mode from the mode bit. This tells how the operand is to be found.

Indirect cycle. If the address is indirect, the effective address is read from memory:

$$AR \leftarrow M[AR]$$

For direct addressing this cycle is skipped.

Execute cycle. The operation named by the opcode is carried out. A memory-reference instruction reads the operand and uses it. A register-reference instruction works on registers only. An input-output instruction moves data to or from a device. A branch instruction loads a new value in PC.

Interrupt cycle. After execution, the CPU checks if an interrupt is waiting. If so, it saves PC, and jumps to the interrupt service routine. If not, the cycle goes back to fetch.

The diagram shows these cycles in order and the way that execution goes back to fetch for the next instruction. The sequence counter times each cycle with the pulses T0, T1, T2 and so on. This is how every instruction of a program is run, one after another.

For example, in ADD 500, fetch brings the instruction in, decode finds the ADD, the indirect cycle is skipped, execute reads the word at 500 and adds it to AC, and the interrupt check follows.

Notes on the sub cycles. The fetch cycle is the same for all instructions, but the execute cycle is different for each. A register-reference instruction needs no memory read and finishes quickly, while a memory-reference instruction needs at least one memory access. Because of this, the number of clock pulses is not the same for each instruction. The control unit uses the sequence counter to track the pulse, and clears it at the end of the instruction.

The instruction cycle has these steps, repeated for every instruction:

1. Fetch: the instruction is read from the memory location given by PC into the instruction register, and PC is increased.
2. Decode: the control unit finds out the operation from the opcode.
3. Read the effective address: if the address is indirect, the operand address is read from memory.
4. Execute: the operation is done, for example an ALU operation, a data transfer or a branch.
5. Store the result: the result goes to a register or to memory.
6. Interrupt check: the CPU checks for a pending interrupt, then starts the next cycle.

The instruction cycle is the complete set of steps the CPU takes to process one instruction. It begins with fetching the instruction from memory, and goes on with decoding it, reading the operands, executing the operation, and storing the result. The CPU then repeats the cycle for the next instruction, whose address is in the program counter. A computer keeps running instruction cycles as long as it is working a program.

The statement is

$$P = \frac{(X - Y + Z) \times (A ^ B)}{(C ^ D \times E)}$$

Here the caret is taken as a binary operator, written POW. So $A ^ B$ is the instruction POW. The same order of evaluation is used in all three programs: first $(X - Y + Z)$, then $A ^ B$, then the product of both. Then $C ^ D$, then multiply by $E$, and last the division.

(i) Two-address instructions. The first operand is both a source and the destination.

(ii) One-address instructions. Every instruction uses the accumulator AC as the other operand, and T1 and T2 are temporary memory locations.

(iii) Zero-address instructions. These use a stack. PUSH puts a value on the stack. An operation takes the top two values, applies the operation, and pushes the result. For SUB and DIV, the lower element is the left operand. The expression in reverse Polish form is $X,Y - Z + A,B ^ \times C,D ^ E \times /$, and the program is:

The three programs use 11, 15 and 16 instructions. As the number of address fields drops, the program becomes longer, but each instruction becomes shorter.

The instruction format depends on the number of address fields. The types are:

• Three-address: ADD R1, R2, R3. Two sources and one destination.
• Two-address: ADD R1, R2. The result replaces the first operand.
• One-address: ADD X. The other operand and the result are in the accumulator.
• Zero-address: ADD. Operands are on the stack, as in a stack machine.

Each format holds an opcode and zero to three operand fields. More addresses make the program short, but each instruction long.

The instruction cycle is the set of steps the CPU repeats to run each instruction of a program. It starts when the machine is powered on and stops only when a halt instruction is run or power is lost.

Flowchart

        +------------------+
        |  START (PC set)  |
        +--------+---------+
                 v
        +------------------+
        | FETCH: AR <- PC  |
        | IR <- M[AR]      |
        | PC <- PC + 1     |
        +--------+---------+
                 v
        +------------------+
        | DECODE opcode,   |
        | read mode bit I  |
        +--------+---------+
                 v
          < indirect? >--yes--> AR <- M[AR]
                 | no                 |
                 +<-------------------+
                 v
        +------------------+
        |     EXECUTE      |
        +--------+---------+
                 v
          < interrupt? >--yes--> save PC, go to ISR
                 | no
                 +---------> back to FETCH

Explanation

The cycle has four main phases.

Fetch. The address in the program counter (PC) goes to the address register (AR). The memory word at that address is read into the instruction register (IR). Then PC is increased by one so that it points to the next instruction. This is written as follows.

$$AR \leftarrow PC$$

$$IR \leftarrow M[AR],; PC \leftarrow PC + 1$$

Decode. The control unit looks at the opcode bits of IR and finds which operation is needed. A decoder turns the three opcode bits into one of eight lines. The mode bit I tells whether the operand address is direct or indirect.

Read the effective address. If the instruction is indirect, the address field only points to a memory word that holds the real operand address. So the CPU reads that word:

$$AR \leftarrow M[AR]$$

For a direct instruction, nothing more is needed here.

Execute. The operation is carried out. A memory-reference instruction such as ADD reads the operand into the data register DR and adds it to the accumulator AC. A register-reference instruction such as CLA clears AC. A branch instruction loads a new address into PC. An input-output instruction moves data to or from a device.

Interrupt check. After the execute phase, the CPU checks if an interrupt request has come. If yes, it saves the contents of PC (the return address), and starts the interrupt service routine. When the routine finishes, the return address is restored, and the program goes on. If no interrupt is pending, control goes back to the fetch phase for the next instruction.

All these steps are timed by the sequence counter, which generates the pulses T0, T1, T2 and so on. At the end of each instruction the counter is cleared, so the next fetch starts again at T0.

A worked example. Suppose PC holds 300 and the word at address 300 is the instruction ADD 500, with the mode bit I equal to 0. In the fetch phase, AR gets 300, IR gets the word from location 300, and PC becomes 301. In the decode phase, the decoder finds that it is an ADD, and the address field gives 500. As the instruction is direct, there is no indirect read. In the execute phase, the word at address 500 is read into DR, and AC is replaced by $AC + DR$. The sequence counter is cleared, and the next instruction at 301 is fetched.

Why the cycle matters. Every program, however large, runs only by repeating this loop. The speed of a computer in a large part depends on how fast the loop runs. Pipelining overlaps the loops of different instructions to make it faster.

(i) Timing diagram of the instruction cycle

The CPU repeats the instruction cycle for every instruction. It has a fetch phase, a decode phase, an execute phase, and an interrupt check when needed. A timing diagram shows which register transfer happens at which clock pulse.

The fetch part takes three clock pulses (T0 to T2). The decode part takes one more (T3). The execute part follows. The register transfers are given below.

$$T_0:; AR \leftarrow PC$$

$$T_1:; IR \leftarrow M[AR],; PC \leftarrow PC + 1$$

$$T_2:; D_0,\dots,D_7 \leftarrow \text{decode } IR(12\text{-}14),; AR \leftarrow IR(0\text{-}11),; I \leftarrow IR(15)$$

At T0 the address of the next instruction goes from the program counter (PC) to the address register (AR). At T1 the instruction is read from memory into the instruction register (IR), and PC moves on to the next address. At T2 the opcode is decoded and the address field is saved in AR. The mode bit I tells if the address is direct or indirect.

In the next clock pulse, if the instruction is indirect, the effective address is read as $AR \leftarrow M[AR]$ at T3. Then the execute phase starts with the timing signals T4, T5, T6 and so on. For example, for an ADD instruction the steps are:

$$T_4:; DR \leftarrow M[AR]$$

$$T_5:; AC \leftarrow AC + DR,; SC \leftarrow 0$$

Setting the sequence counter SC to zero at the end starts the next fetch at T0. The sequence counter (SC) is the small counter that produces the timing signals T0, T1, T2 and so on.

(ii) Subroutine

A subroutine is a group of instructions that does one job and can be used many times from different places in a program. It saves memory because the code is written once. The main program uses a CALL instruction to run it. The CALL stores the return address, which is the address of the next instruction, usually on the stack. Then it loads the subroutine address into PC. At the end, a RETURN instruction pops the saved address back into PC. The main program then continues from where it left off.

$$SP \leftarrow SP - 1,; M[SP] \leftarrow PC,; PC \leftarrow \text{subroutine address}$$

Because the return address is on a stack, subroutines can call other subroutines, and even themselves (recursion).

Interrupt and sub cycles. Before each fetch, the CPU also checks if an interrupt is pending. If the interrupt flip-flop is set, the CPU saves the return address, usually in memory location 0, and jumps to the interrupt service routine. So the full cycle is fetch, decode, read the effective address if indirect, execute, and then the interrupt check. Each of these is a sub cycle, and each is driven by the timing signals from the sequence counter.

Why the timing diagram matters. It shows exactly in which clock pulse each register is loaded. The control unit uses these timing signals together with the decoded opcode to produce the control signals. Memory reads and writes also fit inside these pulses, so the whole machine stays in step with one clock.

RISC architecture

RISC means Reduced Instruction Set Computer. Its idea is that most programs use a few simple instructions most of the time. So the processor is built to run these very fast, and complex jobs are made from many simple instructions.

Features

• A small set of simple instructions, of fixed length, such as 32 bits.
• Each instruction takes one clock cycle, in most cases.
• Only LOAD and STORE instructions access memory. All other instructions work on registers. This is the load-store architecture.
• A large set of registers, often with overlapping register windows, which makes the procedure calls fast.
• Few and simple addressing modes.
• A hardwired control unit, with no microcode.
• A pipeline that is easy to build and keep full, as all the instructions are alike.

Advantages

• Higher speed, because of one-cycle instructions and good pipelining.
• A simple control unit, so a smaller chip, lower design time and lower cost.
• Less power use, which is the reason ARM is used in phones.
• Easier for compilers to optimize, as the instructions are regular.

Disadvantages. The programs are longer, as more instructions are needed, and they need more memory for code.

Comparison of RISC and CISC

In short, RISC moves the complexity from the hardware to the software, and CISC does the reverse.

Instruction pipelining

Instruction pipelining splits the execution of an instruction into stages, such as fetch, decode, execute, memory access and write back. Each stage has its own hardware. While one instruction is in a later stage, the next instruction is already in an earlier stage. So many instructions are in progress at the same time, and one instruction can finish in every clock cycle once the pipeline is full.

For $k$ stages, $n$ instructions and a stage time $t_p$, the times are:

$$T_{non\text{-}pipelined} = n,k,t_p$$

$$T_{pipelined} = (k + n - 1),t_p$$

$$\text{Speedup} = \frac{T_{non\text{-}pipelined}}{T_{pipelined}}$$

Numerical

Here the number of stages is $k = 5$, the stage time is $t_p = 20$ ns, and the number of instructions is $n = 10$.

(i) Without pipelining. Each instruction passes through all 5 stages one after the other, and the next one starts only after it ends. So one instruction takes $5 \times 20 = 100$ ns.

$$T_{non\text{-}pipelined} = 10 \times 5 \times 20 = 1000 \text{ ns}$$

(ii) With pipelining. The first instruction needs 5 cycles to come out. After that, each of the remaining 9 instructions finishes in one more cycle. So the total is $5 + 9 = 14$ cycles.

$$T_{pipelined} = (5 + 10 - 1) \times 20 = 14 \times 20 = 280 \text{ ns}$$

(iii) Speedup.

$$\text{Speedup} = \frac{1000}{280} \approx 3.57$$

Therefore the pipeline needs 280 ns for 10 instructions instead of 1000 ns, and the speedup is about 3.57. It is less than the ideal value 5, because the pipeline takes time to fill. If more instructions are run, the speedup comes closer to 5. For 1000 instructions, it would be $5000/1004 \approx 4.98$.

Remark. The result shows why pipelining is used. The total time falls from 1000 ns to 280 ns, though one instruction still takes 100 ns from start to end. The gain is in the throughput, which is the number of instructions finished per unit time. Hazards such as data dependencies would add stall cycles and lower the speedup further.

Processor organization

A processor has a datapath and a control unit. The datapath holds the registers, the ALU and the buses. The control unit gives the signals. The main registers are the program counter (PC), instruction register (IR), address register (AR), data register (DR), accumulator (AC) and general registers.

Instruction fetch, decode and execute

The CPU repeats a basic cycle for every instruction.

• Fetch: the address in PC goes to AR. The instruction is read into IR, and PC is incremented.
• Decode: the control unit decodes the opcode and finds the addressing mode.
• Execute: the ALU or other unit does the operation. The operands are read from registers or memory, and the result is stored.

$$AR \leftarrow PC,\quad IR \leftarrow M[AR],\quad PC \leftarrow PC + 1$$

The control unit times these steps with a sequence counter, and it may check for interrupts at the end.

Pipelining

Pipelining overlaps the cycles of different instructions. The work is split into stages such as fetch, decode, execute, memory and write back. While one instruction is executed, the next is decoded, and a third is fetched. After the pipeline fills, one instruction finishes in every clock cycle. For $k$ stages and $n$ instructions:

$$S = \frac{nk}{k + n - 1}$$

Hazards (structural, data and control) can slow it, and they are cured by stalls, forwarding and branch prediction.

Parallel processing techniques

Parallel processing means doing many operations at the same time to increase speed. It can be done at several levels:

• Instruction-level: pipelining and superscalar processors that issue many instructions in a cycle.
• Data-level: vector and array processors, and GPUs, apply one instruction to many data items.
• Thread and processor-level: multicore and multiprocessor systems run different tasks or threads together.

In Flynn's classification there are four types: SISD, SIMD, MISD and MIMD. A normal single core CPU is SISD, a vector unit is SIMD, and a multicore machine is MIMD.

Control

Control can be hardwired for speed or microprogrammed for flexibility. In all cases the control unit decides what happens in each clock pulse, and the processor organization decides how fast the work is done.

Pipelining is a technique to overlap the execution of many instructions. The work of one instruction is divided into stages, with separate hardware for each stage. When one instruction moves to the next stage, a new one enters the first stage. It is like an assembly line in a factory, where every worker does one small job, and all work at the same time.

Stages of an instruction pipeline

A common pipeline has five stages.

1. Instruction fetch (IF): the instruction is read from memory using the address in the program counter.
2. Instruction decode (ID): the opcode is decoded, and the source registers are read.
3. Execute (EX): the ALU does the operation, or calculates the address of a memory operand.
4. Memory access (MEM): a load reads data from memory, and a store writes data to memory.
5. Write back (WB): the result is written in the destination register.

In the timing diagram, each row is an instruction and each column is a clock cycle. Instruction 2 starts one cycle after instruction 1. After the pipeline fills in cycle 5, one instruction completes in every clock cycle.

Performance

For $k$ stages, $n$ instructions and a stage time $t_p$:

$$T_{pipelined} = (k + n - 1),t_p$$

$$T_{non\text{-}pipelined} = n,k,t_p$$

The speedup is then:

$$S = \frac{nk}{k + n - 1}$$

For large $n$ the speedup is close to $k$. For example, 100 instructions in a 5-stage pipeline give $500/104 \approx 4.81$.

Hazards. The pipeline cannot always run at full speed.

• A structural hazard happens when two instructions need the same hardware in the same cycle, such as one memory port for both fetch and data.
• A data hazard happens when an instruction needs a result that an earlier instruction has not yet written. It is reduced by forwarding the result directly and by stalling.
• A control hazard happens at a branch, when the next instruction is not known. It is reduced by branch prediction and by delayed branches.

Advantages and limits. Pipelining gives higher throughput and better use of the hardware. It does not reduce the time of a single instruction, and hazards and unequal stage times reduce the gain. RISC designs have simple, equal-length instructions, so they pipeline very well.

RISC uses a small set of simple, fixed-length instructions, each done in about one clock cycle. CISC uses a large set of complex, variable-length instructions that may take many cycles.

Pipelining is a technique in which the work of an instruction is broken into stages, and many instructions are processed at the same time, each in a different stage. Think of a laundry with a washer, a dryer and an iron. While one load is in the dryer, the next load is already in the washer. In the same way, a new instruction enters the pipeline in every clock cycle.

The space-time diagram shows the stages (space) on one axis and the clock cycles (time) on the other. After the first few cycles, the pipeline is full, and one instruction finishes in every cycle.

Speedup. For $k$ stages, $n$ tasks and a clock time $t_p$:

$$T_{pipelined} = (k + n - 1),t_p$$

$$T_{non\text{-}pipelined} = n,k,t_p$$

$$S = \frac{nk}{k + n - 1}$$

For a very large $n$, the speedup comes close to $k$. For example, for $k = 4$ and $n = 100$, the speedup is $400/103 \approx 3.88$.

Types of pipelining

• Arithmetic pipeline: the stages of an arithmetic operation are overlapped. For floating point addition, the stages are compare exponents, align mantissas, add mantissas and normalize the result. It is used in vector processors and in floating point units.
• Instruction pipeline: the instruction cycle is split into stages like fetch, decode, operand fetch, execute and write back. A new instruction is fetched while the earlier ones are in later stages.
• Processor pipeline: a stream of data passes through a series of processors, each doing a part of the job. This is less common.
• Linear and non-linear pipelines: in a linear pipeline, data flows from the first stage to the last in one direction. A non-linear pipeline has feedback or feed-forward paths, so a stage may be used more than once.
• Static and dynamic pipelines: a static pipeline does one type of function at a time. A dynamic one can do different functions at different times.
• Unifunction and multifunction pipelines: the first does a fixed function, the second can be set to do several.

Hazards. A pipeline may stall because of three kinds of hazards. A structural hazard is when two stages need the same resource. A data hazard is when an instruction needs a result that is not ready. A control hazard comes from branches. They are solved by stalling, forwarding data and predicting branches.

Advantage. Pipelining raises the throughput without making any single instruction faster. The cost is extra registers between the stages and more complex control.

Example of an instruction pipeline. With four stages (fetch, decode, execute, write back), the first instruction finishes after 4 cycles. After that, one instruction finishes in each cycle. So 10 instructions need $4 + 10 - 1 = 13$ cycles, while without pipelining they need $10 \times 4 = 40$ cycles.

RISC means Reduced Instruction Set Computer. It is a design in which the CPU uses a small set of simple instructions, and each one is executed in a single clock cycle.

Main features:

• Fixed-length instructions and a few addressing modes.
• Only LOAD and STORE instructions touch memory. All other work is done on registers.
• A large register file, often with register windows.
• A hardwired control unit, which is fast.
• Pipelining works well, since the instructions are simple.

RISC needs more instructions for a job, but each is quick. Examples are ARM, MIPS and SPARC.

RISC (Reduced Instruction Set Computer) uses a small set of simple instructions. CISC (Complex Instruction Set Computer) uses many powerful, complex instructions.

Parallelism

Parallelism means doing more than one job at the same time. It is used to make a computer faster. It can be at the instruction level (pipelining), at the processor level (many CPUs), or at the data level (vector and array processors). A simple example is a kitchen where one person chops, one cooks and one serves at the same time.

Pipelining

Pipelining is a method where the work of one instruction is split into stages, and many instructions are in different stages at the same time. Each stage has its own hardware. Like a car assembly line, a new instruction enters the pipeline in every clock cycle, while older ones move forward.

A simple instruction pipeline has these stages:

• IF: instruction fetch.
• ID: instruction decode and register read.
• EX: execute in the ALU.
• MEM: memory access.
• WB: write back the result.

The diagram shows that in clock cycle 5 five different instructions are being worked on, one in each stage. Without pipelining, the next instruction would have to wait until the whole of the earlier one finishes.

Speedup. Let $k$ be the number of stages, $n$ the number of instructions and $t_p$ the clock time of one stage. Then:

$$T_{pipelined} = (k + n - 1),t_p$$

$$T_{non\text{-}pipelined} = n,k,t_p$$

$$S = \frac{n,k,t_p}{(k + n - 1),t_p} = \frac{nk}{k + n - 1}$$

When $n$ is very large, the speedup tends to $k$. So a five-stage pipeline can be at most about five times faster.

Problems. Pipelines lose speed because of hazards:

• Structural hazard: two stages need the same hardware at once.
• Data hazard: an instruction needs a result that an earlier one has not produced yet.
• Control hazard: a branch changes the flow, so the fetched instructions may be wrong.

These are handled by stalls, forwarding (bypassing) and branch prediction.

Difference. Parallelism is the wider idea of many things happening together. Pipelining is one way to get it, using overlapped stages inside one processor. Pipelining does not shorten the time of one instruction, but it raises the throughput, that is, the number of instructions finished per second.

Example. Take a five-stage pipeline and 100 instructions, with the same clock time for every stage. Then the speedup is:

$$S = \frac{nk}{k + n - 1} = \frac{100 \times 5}{5 + 100 - 1} = \frac{500}{104} \approx 4.81$$

This is close to the ideal value of 5.

Types of parallelism in short. Instruction-level parallelism overlaps instructions inside one CPU, for example pipelining and superscalar issue. Thread-level parallelism runs different threads on different cores. Data-level parallelism applies one operation on many data items together, as in vector processors and GPUs. A real computer today often uses all three.

Where pipelining is used. Besides the instruction pipeline, there are arithmetic pipelines, for example for floating point addition, which split the work into stages such as exponent compare, align, add and normalize.

Hardwired control unit

A hardwired control unit makes the control signals with a fixed network of logic gates, decoders and flip-flops. There is no control memory. The signals depend on the opcode, the timing pulse and the status flags.

Design

 IR (opcode) -> [Instruction decoder] -> D0 ... D7 --+
                                                     v
 Clock -> [Sequence counter] -> [Timing decoder] --> [Control logic] -> control signals
              ^   T0 ... T15                          ^   (AND, OR gates)
              |                                       |
         clear (end of instruction)           Flags, mode bit I, interrupt R

The parts are:

• Instruction register and decoder. The opcode bits go to a decoder, for example 3 to 8. It makes one line $D_0$ to $D_7$ high for the current instruction.
• Sequence counter and timing decoder. The counter counts clock pulses. A 4 to 16 decoder makes the timing signals $T_0$ to $T_{15}$. Each signal gives one time slot for a micro operation.
• Control logic network. AND and OR gates combine the decoder lines, the timing signals and the flags. There is a Boolean equation for each control signal. For example, the signal to load AR is

$$AR\text{ load} = R'T_0 + R'T_2,D_7,I'$$

• Flags and condition bits. The zero flag, the carry flag and the mode bit I affect some of the signals.

Working

At $T_0$, $T_1$ and $T_2$ the same fetch signals appear for every instruction. After decoding, the line $D_i$ of the instruction and the later timing signals $T_3$, $T_4$, ... create the signals for the execute part. At the end, a signal clears the sequence counter, and the next instruction is fetched.

Advantages

• Very fast, since the signals come straight from gates.
• Good for RISC and pipelined designs.
• No control memory is needed.

Disadvantages

• The design is complex for a large instruction set, as every signal needs its own equation.
• It is hard to change. A new instruction means a new circuit.
• Error fixing is difficult and costly.
• Less regular, and it takes a long design time.

Use. Hardwired control is chosen in RISC processors, where the instructions are few and simple, so the equations are small and the speed matters more than flexibility.

In a microprogrammed control unit, each microinstruction holds the control signals for one step. The way these signals are put into the microinstruction gives two styles, horizontal and vertical.

Horizontal microprogramming

In this style, each control signal of the machine has its own bit in the microinstruction. If the bit is 1, the signal is active. So the signals go to the hardware straight, with no decoder in between. Many signals can be active together, so many micro operations can be done in parallel in a single step. The word is very wide, often over 100 bits.

• Advantages: fast, high parallelism, little decoding, simple control.
• Disadvantages: large control memory, long words, and many bits are zero in most words, so space is wasted. The programmer needs to know the hardware in detail.

Vertical microprogramming

Here the control signals are put in groups, and each group is coded in a small field. For example, 3 bits can select one of 8 signals. A decoder for each field turns the code into the signal lines. Only one signal per field can be active at a time, so less parallelism is possible. The word is short.

• Advantages: small control memory, short words, easier to write and understand, like a machine language.
• Disadvantages: slower, because of decoding time, and less parallel.

Example. Let there be 16 control signals. A horizontal microinstruction needs 16 bits for them. A vertical one that groups them in two fields of 8 signals needs two 3 bit fields, which is 6 bits. So the memory is smaller, but a decoder is needed for each field and only one signal in a field can be on.

Many designs use a mix, called a nanoprogramming or mixed scheme, to get a balance between speed and size.

In a microprogrammed control unit, each microinstruction holds the control signals for one step. The way these signals are put into the microinstruction gives two styles, horizontal and vertical.

Horizontal microprogramming

In this style, each control signal of the machine has its own bit in the microinstruction. If the bit is 1, the signal is active. So the signals go to the hardware straight, with no decoder in between. Many signals can be active together, so many micro operations can be done in parallel in a single step. The word is very wide, often over 100 bits.

• Advantages: fast, high parallelism, little decoding, simple control.
• Disadvantages: large control memory, long words, and many bits are zero in most words, so space is wasted. The programmer needs to know the hardware in detail.

Vertical microprogramming

Here the control signals are put in groups, and each group is coded in a small field. For example, 3 bits can select one of 8 signals. A decoder for each field turns the code into the signal lines. Only one signal per field can be active at a time, so less parallelism is possible. The word is short.

• Advantages: small control memory, short words, easier to write and understand, like a machine language.
• Disadvantages: slower, because of decoding time, and less parallel.

Example. Let there be 16 control signals. A horizontal microinstruction needs 16 bits for them. A vertical one that groups them in two fields of 8 signals needs two 3 bit fields, which is 6 bits. So the memory is smaller, but a decoder is needed for each field and only one signal in a field can be on.

Real designs often take a middle path between the two, to balance speed and memory size.

Microprogram sequencing means choosing the order in which microinstructions are read from the control memory. Each machine instruction is carried out by a small program of microinstructions, called a microroutine. The sequencer must start the right routine, move through it, and then go back to fetch the next instruction.

Structure

The control address register (CAR) holds the address of the microinstruction to be read. A multiplexer feeds CAR from different sources. A branch logic unit tests a status bit. An incrementer gives CAR plus one. A mapping logic converts an opcode into a starting address. A subroutine register (SBR) keeps the return address.

How the next address is found

1. Sequential flow: CAR is incremented to give the next microinstruction.
2. Branch: if the condition in the microinstruction is true, its address field is loaded in CAR, else CAR is incremented.
3. Mapping: at the end of the fetch routine, the opcode in IR is mapped to the first address of the routine for that instruction.
4. Call and return: a micro-subroutine call saves CAR plus one in SBR and jumps. A return loads SBR back in CAR.

How a complex instruction executes

Take a complex instruction such as multiply. First, the fetch microroutine reads the instruction into IR. Then the mapping logic turns the opcode into the starting address of the multiply routine. The first microinstruction is read, and its bits are sent as control signals. The next address is chosen by the sequencer. The routine may contain a loop, which repeats shift and add micro operations, with a branch microinstruction to test a counter. When the loop ends, the last microinstruction jumps back to the fetch routine.

So the complex instruction is built from many simple micro-steps: load registers, add, shift, test, and branch. No special hardware is needed for it. Only the sequence of microinstructions in the control memory is written for it.

Importance. With a good sequencer, complex instructions can be added or changed by changing only the microprogram. Common steps, such as the operand address calculation, are written once as a micro-subroutine, and shared. That is why microprogram sequencing makes execution of complex instructions possible in a clean way.

The control unit is the part of the CPU that directs all other parts. It does not process data itself.

It first fetches the instruction from memory using the address in the program counter, and places it in the instruction register. It then decodes the opcode to learn what is to be done. Using the decoded instruction and the clock timing signals, it produces control signals. These open the right data paths, select the ALU function, and give read or write commands to memory and I/O. It also watches status flags and interrupt requests. It may be hardwired (logic gates) or microprogrammed (control memory).

Hardwired versus microprogrammed control unit

Components of the hardwired control unit

A hardwired unit produces the control signals with a fixed circuit. Its parts are as follows.

• Instruction register (IR): it holds the instruction. The opcode part is sent to the decoder.
• Instruction decoder: a decoder, for example 3 to 8, converts the opcode to one of the lines $D_0$ to $D_7$. Each line stands for one instruction type.
• Sequence counter (SC) and timing decoder: SC counts the clock pulses, and a 4 to 16 decoder produces the timing signals $T_0$ to $T_{15}$. Each signal marks one step of the instruction. At the end, SC is cleared.
• Flip-flops and flags: the mode bit I, the interrupt flip-flop R, and the status flags like zero and carry also affect the signals.
• Control logic gates: a network of AND, OR and NOT gates combines the decoder outputs, the timing signals and the flags. For example, a load signal for AR is given by

$$AR\text{ load} = R'T_0 + R'T_2,D_7,I'$$

• Control outputs: these go to the registers, the ALU, the bus selectors and memory, and they decide what is done in each clock pulse.

 IR -> [Decoder] -> D0..D7 --+
 Clock -> [SC] -> [T0..T15] -+-> [Control logic] -> signals
 Flags ----------------------+

The unit works at gate speed, but a change in the instruction set means a new circuit.

Explanation of the difference. In the hardwired unit, the signals are made by gates, so the speed is high but the circuit is fixed. In the microprogrammed unit, the signals are read from memory as microinstructions, so it is slow but easy to change. The first suits RISC, and the second suits CISC. A hardwired design needs a full redesign when a new instruction is added. A microprogrammed design needs only a new microroutine.

The control unit makes the signals that tell the other parts of the CPU what to do in each clock cycle. It can be built in two ways.

Explanation. In the hardwired unit, the opcode is decoded and combined with the timing signals by logic gates. The gates give the control signals straight away, so it is very fast. But a change in even one instruction means a new circuit. Its design needs state tables and Boolean equations, so a big instruction set makes the design long and error-prone.

In the microprogrammed unit, each machine instruction has a small program of microinstructions in the control memory. The control address register selects the microinstruction, and its bits go out as control signals. The next address is found by the sequencer. To add or fix an instruction, one just writes or changes its microprogram. The price is the memory access in each step, which makes it slower.

Which is better. Neither is best everywhere. When speed matters most and the instruction set is small, as in RISC, the hardwired design is chosen. When the instruction set is large and flexibility matters, as in CISC, microprogrammed control is chosen. Some modern CPUs use a mix, with hardwired control for common simple instructions and microcode for rare complex ones.

Short example. Suppose the CPU must run an ADD. In the hardwired unit, the ADD line from the decoder and the timing pulse $T_4$ meet at an AND gate, and its output starts the add. In the microprogrammed unit, the opcode is mapped to the address of the ADD routine, the first microinstruction is read, and its bits start the same add. Both give the same result. The first does it with gates, and the second does it by reading words from memory.

Effect on the instruction set. Because microcode is cheap to change, early computers added many complex instructions, which led to the CISC style. When designers saw that simple instructions are used most, they moved to hardwired control with RISC.

In horizontal microprogramming each control signal has its own bit in the microinstruction. In vertical microprogramming the signals are grouped into fields and coded, and a decoder gives the signals.

In a microprogrammed control unit, the control memory holds the microinstructions. The control address register (CAR) gives the address to read. The address selection circuit, also called the sequencer, decides what goes into CAR next, so that the microinstructions run in the right order.

Parts of the circuit

• Multiplexer (MUX): it selects one of four possible next addresses.
• Incrementer: gives CAR plus one.
• Branch logic: tests the status bits chosen by the microinstruction and decides whether a branch is taken.
• Mapping logic: converts the opcode from the instruction register into a starting address.
• Subroutine register (SBR): stores the return address of a micro-subroutine.
• Control memory: a ROM that holds the microinstructions. It is read at the address in CAR.

How the next address is selected

The select lines of the multiplexer come from the branch logic. It gives four ways to choose the address.

1. Increment: CAR becomes $CAR + 1$. This is the normal flow, when the condition is false or no branch is wanted.
2. Branch: the address field of the microinstruction is loaded into CAR when the tested status bit is true. It is either a conditional or an unconditional jump.
3. External mapping: after the fetch routine, the opcode bits of the instruction are mapped to the first address of the routine that executes it. This is the way a machine instruction starts its microprogram.
4. Subroutine call and return: on a call, the return address is saved in SBR and the branch address is loaded in CAR. On a return, SBR is copied back into CAR.

Mapping example. Let the opcode be 4 bits and let each routine be allowed 4 microinstructions. Then the address is formed as 0, then the opcode, then 00. For opcode 1010 the address is 0101000, that is 40. If the opcode changes by one, the starting address changes by four, so the routines do not overlap. A 7 bit CAR can address $2^7 = 128$ words.

Working in sequence. The microinstruction read from the control memory has a condition field, a branch field and an address field. The condition field selects one status bit. The branch field tells the MUX what to choose when that bit is true. If the bit is false, the incrementer path is taken. At the next clock pulse the chosen address is stored in CAR, and the next microinstruction is read.

This arrangement lets the microprogram do loops, tests and calls, so complex instructions can be built from simple micro-steps without extra hardware for each.

Why this design is used. The same small circuit supports straight-line flow, loops, tests and shared micro-subroutines. For example, the routine that finds an indirect operand address is written once, and many instruction routines call it. This saves control memory. The cost is only a few extra gates and one register, so address selection stays cheap and fast.

Hardwired versus microprogrammed control

Control steps for R1 <- R2 * (R3) on a single bus

The instruction means: take the number stored in memory at the address held in R3, multiply it by R2, and put the product in R1. On a single bus architecture, only one register can put data on the bus at a time. So the ALU keeps one input in the temporary register Y, takes the other from the bus, and stores the result in register Z. The control steps are as follows.

1. $PC_{out}$, $MAR_{in}$, Read, Select 4, Add, $Z_{in}$. This starts the fetch. The address of the instruction goes to the memory address register, and PC plus 4 goes into Z.
2. $Z_{out}$, $PC_{in}$, $Y_{in}$, WMFC. PC is updated, and the CPU waits for the memory function to complete.
3. $MDR_{out}$, $IR_{in}$. The fetched instruction is moved from the memory data register to the instruction register. Now the instruction is decoded.
4. $R3_{out}$, $MAR_{in}$, Read. The address of the operand, held in R3, goes to MAR and a memory read is started.
5. $R2_{out}$, $Y_{in}$, WMFC. R2 is placed in Y, and the CPU waits until the operand arrives in MDR.
6. $MDR_{out}$, Select Y, Multiply, $Z_{in}$. The ALU multiplies Y with the operand from the bus, and the product is saved in Z.
7. $Z_{out}$, $R1_{in}$, End. The product is moved into R1, and the instruction is complete.

Steps 1 to 3 are the fetch part, which is the same for every instruction. Steps 4 to 7 are the execute part. In a hardwired unit, these signals are produced by gates driven by the step counter, while in a microprogrammed unit each step is one microinstruction.

Using the sequence. Seven control steps mean seven clock cycles for this one instruction. If the memory is slow, the two WMFC steps (wait for memory function complete) make the CPU stall until the data is ready. On a multi-bus architecture, some of these steps could be joined, so fewer cycles are needed. That is why single bus designs are simple and cheap but slower.

Short note on the choice. The table shows that hardwired control suits fast and simple machines, while microprogrammed control suits machines with many complex instructions. Many processors use both.

A microprogram sequencer is the circuit that decides the address of the next microinstruction to be read from the control memory. A microprogram control unit needs it because the microinstructions are not always run in a straight line. They may branch, call a micro-subroutine, or jump to the routine of a new machine instruction.

Block diagram parts

• Multiplexer (MUX): picks one of the possible sources for the next address.
• Branch logic (condition select): tests a status bit, for example zero or carry, chosen by the microinstruction. It decides if the branch is taken.
• Incrementer: adds one to the present address, for straight-line flow.
• Subroutine register (SBR): stores the return address for a micro-subroutine call.
• Control address register (CAR): holds the address that goes to the control memory.
• Control memory: holds the microinstructions. Its output goes to the pipeline register.
• Mapping logic: converts the opcode of the machine instruction into the starting address of its microroutine.

Working

The control memory reads the microinstruction at the address in CAR. This microinstruction has a micro-operation field, a condition select field, a branch control field and a branch address field. The micro-operation field goes out as control signals. The other fields go into the sequencer.

The sequencer then chooses the next address from one of these sources.

1. Next in sequence: if no branch is needed, the incrementer gives CAR plus one.
2. Branch address: if the tested condition is true, the address field of the microinstruction is loaded into CAR. If it is false, CAR is incremented.
3. Mapped address: at the end of the fetch routine, the mapping logic turns the opcode into the starting address of the right routine.
4. Subroutine call and return: for a call, the return address (CAR plus one) is saved in SBR and the branch address is loaded. For a return, SBR is loaded back into CAR.

The multiplexer selects among these by the select lines that come from the branch control field. Then CAR is loaded with the chosen address at the next clock pulse, and the cycle repeats.

Example. If the control memory has 128 words, CAR is 7 bits wide, since $2^7 = 128$. The branch address field is also 7 bits. A common micro-subroutine, for example the one that finds an indirect operand address, is written once and called by many routines, which saves control memory.

The sequencer keeps the control unit flexible, since the order of microinstructions can be changed without any change in the hardware.

Summary of the sequencer. In one line, the sequencer is the "next address" box of the control unit. It lets the microprogram do loops, tests and calls, in the same way that a branch instruction does it in a machine program.

Difference between hardwired and microprogrammed control

Components of the hardwired control unit

In a hardwired unit, a fixed circuit takes the instruction and the clock and produces the control signals.

• Instruction register (IR): holds the instruction being run. Its opcode bits go to the decoder.
• Instruction decoder: a decoder, for example 3 to 8, turns the opcode into one active line $D_0$ to $D_7$. Each line means one instruction.
• Timing unit: it has a clock, a sequence counter (SC) and a 4 to 16 decoder. It gives timing signals $T_0, T_1, T_2$ and so on, one per clock pulse, so each step gets its own time slot.
• Flag and condition inputs: the status flags such as zero, carry and overflow also go into the circuit, because some signals depend on them.
• Control logic gates (combinational circuit): AND, OR and NOT gates combine the decoder lines, the timing signals and the flags. The output is the set of control signals that go to the ALU, registers, buses and memory.
• Control signal outputs: these signals open the paths and tell the units what to do in that clock pulse.

For example, the signal to load AR from PC happens in the fetch step at $T_0$ of every instruction:

$$AR\text{ load} = R'T_0 + R'T_2 , D_7 I'$$

This kind of Boolean equation is written for each signal and then built with gates.

 IR --> [Decoder] --D0..D7--+
                            v
 Clock -> [SC] -> [T0..T15]-> [Control logic ] --> control signals
                            ^   [ gates       ]
 Flags ---------------------+

Because the signals come straight from gates, the unit works at the speed of the hardware. But the design must be done again if an instruction is added.

Which one to choose. A hardwired unit gives the highest speed, so it is the choice for RISC machines with a small and fixed set of instructions. A microprogrammed unit costs less to design and modify, so it suits CISC machines with hundreds of complex instructions. Many real processors use a mix: simple instructions are hardwired and rare, complex ones are microcoded.

Note on the sequence counter. When an instruction finishes, the sequence counter is cleared by a control signal. This makes the timing signals start again at $T_0$ for the next instruction. Without this reset the timing would run on into the wrong time slots.

A microinstruction is one word stored in the control memory. It holds the control signals for one step. There are two main types.

• Horizontal microinstruction: each control signal has its own bit. The word is long, but many signals can be active together, so it is fast.
• Vertical microinstruction: the bits are encoded into small fields. A decoder gives the signals. The word is short, but decoding makes it slower.

Some books also mention a third type, the nanoinstruction, used in a two-level control store.

In a microprogrammed control unit the control signals are not made by logic gates. They are stored as words, called microinstructions, in a special memory. A set of microinstructions that carries out one machine instruction is a microprogram or routine.

Main components

• Control memory: a fast ROM that holds all the microprograms. One word is one microinstruction.
• Control address register (CAR): holds the address of the next microinstruction to read.
• Control data register (CDR) or pipeline register: holds the microinstruction just read, so the next address can be prepared while this one is used.
• Next address generator (sequencer): works out the next value for CAR. It can increment CAR, load a branch address, load an address from the opcode, or return from a subroutine.
• Decoders and control outputs: the fields of the microinstruction go out as control signals to the ALU, registers and memory.

Format of a microinstruction. It usually has three parts. The first is the micro-operation field, which gives the control signals. The second is the condition field, which selects a status bit to test. The third is the branch address field, which gives the next address when the condition is true.

Working

First, the opcode of the machine instruction in IR is mapped to the starting address of its microprogram. This address is loaded in CAR. Then the microinstruction at that address is read from the control memory into CDR. Its micro-operation field is sent out as control signals, so the hardware does that step. At the same time the sequencer finds the next address. If there is no branch, CAR is increased by one. If the condition is true, the branch address is loaded. This repeats until the last microinstruction, which sends the control back to the fetch routine for the next instruction.

Control memory sizes. For example, if the control memory has 128 words, CAR needs 7 bits, because $2^7 = 128$.

Advantages. The design is regular and easy to change. New instructions can be added by writing new microprograms, so it is flexible.

Disadvantage. It is slower than a hardwired unit, because each step needs a memory read.

Address sequencing. The sequencer has to choose the next address in four common ways. It can increment CAR for straight-line code. It can branch to an address given in the microinstruction, conditionally or not. It can map the opcode bits to a starting address, which happens at the end of the fetch routine. And it can call and return from a micro-subroutine, using a small register to save the return address. A multiplexer in the sequencer picks one of these sources.

Mapping example. If the opcode is 4 bits and each routine can have up to 4 microinstructions, the starting address can be formed as 0, opcode, 00. So opcode 0011 maps to address 0001100, which is 12. This keeps the mapping hardware very simple.

Horizontal and vertical forms. The micro-operation field may be coded one bit per signal (horizontal) or in encoded groups (vertical). This choice trades speed for control memory size.

A micro operation is a basic operation on the data stored in registers, done in one clock pulse. A machine instruction is carried out as a sequence of micro operations. They fall into four types.

1. Register transfer micro operations. They copy data from one register to another. For example, $R2 \leftarrow R1$ copies R1 into R2, and $AR \leftarrow PC$ moves the program counter to the address register. Memory transfers are written as $DR \leftarrow M[AR]$ (read) and $M[AR] \leftarrow DR$ (write). A transfer may happen only under a condition, such as $P: R2 \leftarrow R1$.

2. Arithmetic micro operations. They do arithmetic on the numbers in registers.

3. Logic micro operations. They work on each bit of the registers separately. Examples are AND, OR, XOR and NOT. For instance, $R1 \leftarrow R1 \wedge R2$ is used to clear selected bits (masking). XOR can be used to find the bits that differ, and OR can set bits.

4. Shift micro operations. They move the bits of a register to the left or right. A logical shift puts in a zero. A circular shift (rotate) puts the bit that goes out back at the other end. An arithmetic shift keeps the sign bit. A left arithmetic shift multiplies by 2, and a right arithmetic shift divides by 2. For example, shifting 0110 (6) to the left by one gives 1100, and logical right shift of 0110 gives 0011 (3).

Use in the control unit. The control unit makes the control signals that run the micro operations in the right order. For example, the fetch cycle is the sequence of micro operations $AR \leftarrow PC$, then $IR \leftarrow M[AR]$ and $PC \leftarrow PC + 1$. In a microprogrammed unit, each microinstruction names one or more micro operations. So all work of a computer finally reduces to these four types.

A micro operation is a simple operation done on data in registers during one clock pulse. Instructions are carried out as a series of micro operations. There are four types.

• Register transfer: copy data from one register to another, for example $R1 \leftarrow R2$.
• Arithmetic: add, subtract, increment or decrement, for example $R3 \leftarrow R1 + R2$.
• Logic: bit-wise AND, OR, XOR and complement.
• Shift: move bits left or right in a register.

A micro operation is a small, basic operation done on data stored in registers in one clock pulse. Examples are shifting a register, adding two registers, or loading one register from another, written as $R1 \leftarrow R2 + R3$.

Microcode is the set of microinstructions stored in the control memory of a microprogrammed control unit. Each microinstruction holds the control signals for some micro operations. A group of microinstructions makes a microprogram, which carries out one machine instruction. Microcode sits between the hardware and the machine language.