A Hundred Additions in the Time of Four, Unless Each One Waits for the Last
Last timeWhy Counting Operations Fails
A processor works on many instructions at once, so independent operations are nearly free. The one thing it cannot overlap is a step that needs the answer from the step before.
Working on many at once
The previous lesson said memory was the reason two identical-looking loops can
differ enormously. This lesson is the second reason, and it is the one that
survives even when all the data is in the nearest cache and memory is not
involved at all.
A processor does not finish one instruction and then begin the next. It begins
a new instruction most cycles regardless of whether earlier ones have finished,
and at any moment it has dozens of instructions in various states of
completion. The program still reads as a sequence and the machine still
produces the answers the sequence demands. It simply does not perform them one
at a time.
The consequence is immediate: the time a program takes is not the sum of the
times of its instructions. It is closer to the time of the longest thing that
could not be overlapped with something else.
| step | cycle | independent version | dependent version | answers ready | what happened |
|---|---|---|---|---|---|
| 1 | 1 | starts add 1, add 2, add 3, add 4 | starts add 1 only | 0 and 0 | The independent version can start all four immediately, because none of them needs any of the others. The dependent version has nothing else it is allowed to begin: add 2 needs the answer from add 1, which does not exist yet. |
| 2 | 2 | all four still in progress | still waiting on add 1 | 0 and 0 | An addition takes about four cycles from start to answer on a typical processor, so neither version has a result yet. |
| 3 | 4 | all four answers arrive | add 1 answers, add 2 starts | 4 and 1 | The independent version is finished. The dependent version has completed a quarter of its work and may now begin the second step. |
| 4 | 16 | finished twelve cycles ago | add 4 finally answers | 4 and 4 | Four times the time for exactly the same four additions. The only difference is whether each one needed the answer from the last. |
Two different costs
The reason the independent version finishes in four cycles rather than one is
that an operation has two separate costs and they are commonly confused.
Latency is how long one operation takes from the moment it starts to the moment
its answer is available. Throughput is how often a new one can be started. For
an addition the first might be four cycles and the second one cycle, meaning
the hardware can begin a new addition every cycle while each takes four to
complete, so four are in flight at any time.
| latency, cycles | one can start every, cyc | how many fit in flight | |
|---|---|---|---|
| floating point add | 4 | 1 | 4 |
| floating point multiply | 4 | 1 | 4 |
| floating point divide | 14 | 4 | 4 |
| integer divide | 20 | 15 | 2 |
| load from the nearest ca | 5 | 1 | 5 |
| integer add | 1 | 1 | 1 |
Which number you pay depends entirely on whether your work is independent. A
loop doing a thousand unrelated additions pays the throughput number and takes
about a thousand cycles. A loop doing a thousand additions where each needs the
previous answer pays the latency number and takes about four thousand.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents