Thank you for the link. That article says the cpu has a 630 op reorder buffer. Does that mean it has to throw out up to 630 instructions on a mispredict? That sounds huge, so I wonder if I’m misunderstanding.
r1 = r2 * r3
r2 = r3 * r4
r3 = r4 * r5
r4 = r5 * r6
But if you rewrite the names of the registers (variables) and use a larger set of registers (variables) then you can express the same semantics without overwriting any registers. If you do so you can run the operations in parallel on different execution units within the same core.
The ability to run multiple functions at the same time is called "multiple (or wide) issue".
There are different kinds of functional units inside a cpu. For example, some can do basic arithmetic but not divide. At any given time, some functional units will be busy or free. The amount of effective parallelism present in the input stream you can effectively use is bound on whether you can successfully map your instructions into functional units that are free at that time.
Often, you while cannot run a given instruction because for example the multiplier unit is busy, the next instruction could be run because it depends on the divider functional unit, which at that time is free.
The ability to execute instructions out of order is called, well, "out of order execution". It depends on the ability to rename registers and keep track of actual data dependencies. The cpu needs some memory to keep track of that data.
It's unrelated pipelining (which I could give a try explaining too if anybody cares to hear a similar explanation)
Most operation above a certain level of complexity can be broken down in individual smaller steps that have to happen in order and each step takes some time. Once one such step is done, the next step is performed etc.
If the logic for each of those steps is implemented in hardware, once a step is done executing, the logic just sits there idle, waiting for the next operation (composed of smaller steps) to be executed.
Pipelining is a technique that allows to make use of that otherwise idle logic to start performing the first step of the next operation.
For example, let's consider this small program:
r3 = r1 + r2
r2 = r3 + r1
r1 = r3 + r4
load instruction 1
decode instruction 1
perform r1 + r2
write result in r3
load instruction 1
decode instruction 2
perform r3 + r1
write result in r2
load instruction 1
decode instruction 3
perform r3 + r4
write result in r1
load instruction 1
decode instruction 1 | load instruction 1
perform r1 + r2 | decode instruction 2 | load instruction 3
write result in r3 | perform r3 + r1 | decode instruction 3
write result in r2 | perform r3 + r4
write result in r1
This example architecture has a pipeline depth of 4.
The execution is still strictly in order. The idea is that you can start doing some work for the next instruction before the previous one is fully completed.
For example, you can decode the next instruction after you decoded the current one. Also, you can perform a computation on the next instruction as soon as you have computed the results of the previous one, even before you actually have written the results in the actual destination register, provided there is additional logic that ships the result of the current operation as an operand of the arithmetic unit for the next cycle.
The maximum duration of each step is bound by the clock period. The faster the clock, the less time you have for a single step. The deeper the pipeline, the faster the clock can tick and still produce one operation per clock tick. We'll see next some of the many things that prevents us from just riding this idea to the extreme and deepening the pipeline to ludicrous amounts and harness ludicrous clock speeds.
You may have noticed that this dummy architecture here has been carefully designed so that the next instruction can consume the result of the previous instruction if the instruction stream so requires.
Imagine a different architecture that is divided in 6 steps, where the + operation itself is pipelined in two steps.
load instruction 1
decode instruction 1
access r1, r2
start +
continue +
write result in r3
load instruction 2
decode instruction 2
access r3, r1
start +
continue +
write result in r2
load instruction 3
decode instruction 3
access r3, r4
start +
continue +
write result in r1
load instruction 1
decode instruction 1 | load instruction 1
access r1, r2 | decode instruction 2 | load instruction 3
start + | access r3, r1 | decode instruction 3
continue + | start + (HAZARD!) | access r3, r4
write result in r3 | continue + | start +
write result in r2 | continue +
write result in r1
decode instruction 1
access r1, r2 | decode instruction 2
start + | access r3, r1 | decode instruction 3
continue + | nop | nop
write result in r3 | start + | access r3, r4
continue + | start +
write result in r2 | continue +
write result in r1
So far we were looking at a linear instruction stream. Let's see what happens when you have a branch:
r3 = r1 + r2
call func1
r1 = r3 + r4
r2 = r3 + r1
return
load instruction 1
decode instruction 1 | load instruction 2
perform r1 + r2 | decode instruction 2 | load instruction 3
write result in r3 | perform pc + 1 | decode instruction 3 (HAZARD!!)
| write pc=func1, ra=pc+1 | perform r3 + r4 (^^^^^^^^)
| write result in r1 (^^^^^^^^)
As you can see, once we set the program counter and tell the CPU that the program flow continues from another place, the work the CPU has started doing in the pipeline becomes invalid.
load instruction 1
decode instruction 1 | load instruction 2
perform r1 + r2 | decode instruction 2 | load instruction 3
write result in r3 | perform pc+1, &func1 | nop
| write pc=func1, ra=pc+1 | load ins func1.1
| decode ins func1.1 | load ins func1.2
| perform r3 + r1 | decode ins func1.2
| write result in r2 | read ra
| write pc=ra
In our dummy example this adds 2 cycle latency. Not all is lost since we can still do a little bit of pipelining, but for all intents and purposes this is a pipeline flush.
Some architectures (especially the older RISCs but it's still quite common in DSPs) work around this problem by introducing one or more "branch delay slots"; these are instructions that appear physically after a call/jump/branch instruction but get executed before the branch is actually taken.
A equivalent program for such an architecture would look like:
call func1
r3 = r1 + r2
r1 = r3 + r4
return
r2 = r3 + r1
load instruction 1
decode instruction 1 | load instruction 2
perform pc+1, &func | decode instruction 2 | load ins func1.1 |
write pc=func1, ra=pc+1 | perform r1 + r2 | decode ins func1.1 | load ins func1.2
write result in r3 | read ra | decode ins func1.2
| write pc=ra | perform r3 + r1
| write r2
Stalls are ultimately caused by data dependencies. The program counter is just data, on which the instruction stream itself depends on.
(In the real world obviously things get much more complicated but you get the idea)