The order in which a CPU runs instructions

So what is inside a CPU? Three kinds of thing.

• Control unit … the commander, decoding instructions and telling each part what to do
• Arithmetic unit (ALU) … where addition, subtraction, comparison and logical operations actually happen
• Registers … the fastest and smallest storage there is, inside the CPU

Registers have separate names by purpose, and that is what the exam asks about.

• Program counter (instruction address register) … holds the address where the next instruction to execute sits
• Instruction register … holds the instruction just fetched
• General-purpose registers, accumulator … hold the data used in calculation
• Index register, base register … hold values used in computing addresses
• Status register (flag register) … holds the state of a result (came to zero, overflowed, went negative). Conditional branches look here to decide where to go

Do not swap the two with similar names. Holding an address makes it the program counter; holding an instruction makes it the instruction register.

Before it runs, a program is placed in main memory. The CPU reads from there in order and executes. That approach is the stored program method (the von Neumann type), and almost every computer today works this way.

From reading to executing, the same three beats repeat.

• Fetch … read the instruction at the address the program counter points to and put it in the instruction register
• Decode … the control unit works out what kind of instruction it is
• Execute … the arithmetic unit runs and the result is written to a register or to main memory

What is nicely arranged here is that the program counter automatically points at the next one as soon as the fetch is done. So left alone, instructions run top to bottom in the order they were written.

Only when you want to change the order does a branch instruction rewrite the program counter. That single move is how if and for are realised.

One instruction is made of two things: what to do and which value to use. The first is the operation part (opcode) and the second the address part (operand).

There are several ways of reading that address part, and those are the addressing modes. Three to start with.

• Immediate addressing … the value written in the address part is the data itself. No address is visited. The fastest
• Direct addressing … the value in the address part is an address. The data at that address is used
• Indirect addressing … the address in the address part holds another address. You follow it twice before reaching the data

The difference is how many times you follow: zero for immediate, once for direct, twice for indirect. The more times, the slower, but the more flexible in exchange.

The other three decide the address by adding a register value to the address part. The address you actually go to read or write is the effective address.

• Index addressing … address part + index register. Used to fetch the nth element of an array; add one to the register and you are at the neighbour
• Base addressing … address part + base register. Put the start address of the program in and the same instructions run wherever they sit in main memory
• Relative addressing … address part + the program counter. Pointing so many along from the current instruction

All three add, so tell them apart by what is being added: the index to step through elements, the base to change where it sits, and the relative to count from where you are.

A CPU does not run whenever it feels like it. It advances a little at a time on each beat of a steady rhythm, the clock.

The beats per second is the clock frequency, in Hz (hertz). The time for one beat is the clock cycle time, the reciprocal of the frequency.

Put numbers in. 1GHz is a billion beats a second, so one beat is 1 / a billion = one nanosecond. At 2GHz it is two billion beats and one beat is half a nanosecond. Double the frequency and the beat halves.

Two things are easily misunderstood here. First, the reciprocal of the frequency is the time of one beat, not the time of one instruction. How many beats an instruction takes is a separate matter.

Second, doubling the frequency does not double the performance of the whole system. Main memory and the buses run on their own clocks, so speeding up only the CPU leaves the waiting behind.

The clocks needed to finish one instruction is the CPI (cycles per instruction). With that, speed follows from formulas.

• Average instruction execution time = CPI x clock cycle time
• Instructions executable per second = clock frequency / CPI

Rewriting that instruction count in units of a million instructions per second gives MIPS. A hundred million instructions a second is 100 MIPS.

Try numbers. At 1GHz with a CPI of 0.8, the count is a billion / 0.8 = 1.25 billion instructions a second. Dividing is the point; multiplying gives 800 million, which is wrong.

It is asked the other way round too. At an average instruction time of 20 nanoseconds, one second / 20 nanoseconds = 50 million instructions a second. Divide by a million for 50 MIPS.

A CPI can be less than 1. With the pipelining and superscalar techniques coming later, more than one instruction can finish per beat.

In a real CPU the clocks needed differ by kind of instruction. Adding two registers is quick, while an instruction touching main memory is slow.

So the average is weighted by how often each instruction appears (its frequency of appearance). That thinking is the instruction mix.

Average CPI = the sum of (the CPI of an instruction x its frequency of appearance)

Suppose a 700MHz CPU with this breakdown.

• Register to register operation … 4 clocks, appearing 30 per cent of the time
• Memory to register operation … 8 clocks, 60 per cent
• Unconditional branch … 10 clocks, 10 per cent

The average CPI is 4 x 0.3 + 8 x 0.6 + 10 x 0.1 = 1.2 + 4.8 + 1.0 = 7 clocks. Then just put it in the earlier formula: 700MHz / 7 = 100 million instructions a second = 100 MIPS.

Do not average without using the frequencies. That is the only pitfall in this kind of question.

Doing fetch, decode and execute one instruction at a time leaves the fetch circuitry idle while execution goes on. What a waste.

So the processing of an instruction is divided finely into stages, and when the previous instruction moves to the next stage, the next instruction enters the one just vacated. Exactly like a factory production line, and that is pipelining.

What matters is that the time taken by one instruction has not got shorter. What has got faster is the number of instructions finishing per unit of time. A choice mixing that up is always present.

The textbook five stages of RISC line up like this.

• 1 instruction fetch, 2 instruction decode and register file read, 3 execute and address generation, 4 memory access, 5 write back

There is a weakness: branch instructions. Later instructions have already been fed in before it is settled which comes next, so a wrong guess means throwing away everything fed in. That disturbance is a pipeline hazard.

The countermeasures are branch prediction and speculative execution: predict "it probably branches this way" and start executing those instructions before the branch target is settled. Right, and it is pure gain; wrong, and you only throw it away.

Having got the taste for pipelining, the next direction is increasing how many are lined up. Lots of names appear, so sort them by what is being increased.

• Superscalar … several pipelines side by side. Several instructions can pass the same stage at once, so more than one instruction finishes per clock. Which arithmetic unit to use is decided dynamically at execution time
• Superpipelining … dividing the stages more finely so each stage takes less time
• VLIW … which instructions run simultaneously on which arithmetic units is allocated in advance by the compiler
• Out-of-order execution … instructions with no dependency are executed early, regardless of the order written
• Simultaneous multithreading … another thread runs in the pipeline idle time, making one core look like two
• Multicore … several arithmetic centres (cores) built into one CPU
• GPU … a processor with a great many floating point units lined up. Good at work applying the same calculation to masses of data, like 3D and image processing

Multicore has a merit and a limit worth remembering. The merit is that it raises performance while holding down power consumption, more easily than raising the clock of one core. The limit is that n times the cores is not n times the performance, because cores contend for shared resources such as main memory and waiting arises there.

Finally, two ways of thinking about CPU design itself: making instructions lavish or making them plain.

CISC goes towards doing something complicated in one instruction. There are many kinds, of varying length, taking many clocks each. Inside, an instruction is broken into fine units called microinstructions and executed, which is microprogram control.

RISC goes the other way, narrowing instructions down to simple ones. They are of uniform length and one instruction finishes in something close to one clock. Being driven directly by circuitry, it is called wired logic control.

Neither is superior, but RISC suits pipelining. With uniform instruction lengths and stage counts, staggering and feeding them through works cleanly. That is why RISC turns up in pipelining questions.