The Same Add, Eight Numbers at a Time, If You Can Convince the Compiler It Is Safe
Last timeWhich Limit You Are Against
A single instruction can add eight pairs of numbers at once. The hardware has had this for decades and the reason your loop is not using it is almost always one you can remove.
Several values in one register
A processor register normally holds one number. A wide register holds several
side by side, typically four, eight or sixteen depending on the hardware and
the size of the numbers, and the instruction set has versions of the ordinary
operations that act on all of them at once.
One instruction, eight additions. The cost is roughly the cost of a single
addition, because the hardware has eight adders sitting next to each other and
they all work at the same time.
| step | what happens | narrow version | wide version | elements done | what happened |
|---|---|---|---|---|---|
| 1 | load | one number from a, one from b | eight from a, eight from b | 1 and 8 | The wide load takes about the same time as the narrow one, because both fetch from the same cache line and the line was going to arrive whole regardless. |
| 2 | add | one addition | one instruction, eight additions | 1 and 8 | This is the whole trick. The eight lanes do not interact at all, so there is no coordination to pay for and the instruction costs about what one addition costs. |
| 3 | store | one number to c | eight numbers to c | 1 and 8 | Again one instruction either way. The store writes a full line, which is also what the hardware prefers. |
| 4 | loop | advance by 1, repeat n times | advance by 8, repeat n over 8 times | n and n | The same total work, with the loop running an eighth as many times, which also removes seven eighths of the loop condition and the index arithmetic. |
The constraint implied by the picture is that the lanes do not interact. Eight
independent additions is the natural shape. Anything where element three needs
the result from element two does not fit, which is the same dependency problem
from the second lesson wearing different clothes.
- iterations the widened loop performs
- elements to process
- values the wide register holds, the lane count
What it has to prove
Compilers perform this transformation automatically and have done for decades.
They do it only when they can prove it is safe, and the proof has four parts.
The iterations must be independent, so that performing eight at once gives the
same answer as performing them one after another. The memory regions involved
must not overlap, since writing eight results at once is wrong if some of those
locations are also inputs to the same group. The number of iterations must be
known, or at least checkable at run time, so the leftover can be handled. And
every iteration must do the same work, because eight lanes perform the same
instruction and cannot each take a different path.
Each of those is a real requirement rather than a conservatism. A loop that
violates any of them produces a different answer when widened.
The lesson stops here
2 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