SIMD
The slogan is one instruction, n lanes, n times faster, and it is true exactly once: when every element takes the same path and the count divides by the width. Two things break it and both are countable. A count that does not divide leaves the last iteration issuing for lanes with nothing to do. And a conditional the data disagrees on cannot be skipped for the lanes that do not take it, so the group runs both sides with the wrong lanes masked off each time, and the work becomes the sum of the two paths rather than the larger of them. Flynn's 1966 paper, the one the name comes from, names the second of these on page 1907. This page counts them both, and the last panel holds the elements fixed and changes only their order.
New to doing one thing to many values at once? Start here
Ordinary code works on one value at a time: add these two numbers, then the next two. A machine with lanes holds several values side by side and applies one instruction to all of them at once. Eight lanes, one add, eight sums. The instruction stream is single and the data stream is not, which is the classification this machine is named after.
The lanes are not independent processors, and that is the whole subject. They execute the same instruction in the same cycle, so a lane with nothing to do still occupies its slot, and a lane whose data wants the other side of a branch cannot simply take it. Everything this page counts follows from that: instructions issued, against elements actually processed.
Numbers in a fixed-size box
A number on paper can be as long as it needs to be. A number in a computer gets a fixed number of digits and no more, so there is always a largest one it can hold and always a smallest difference it can tell apart.
Almost everything surprising about computer arithmetic follows from that. What happens when you count past the largest value depends on which kind of number it is: a fixed-width integer wraps round to the smallest, and a floating-point number goes to infinity instead. A value too fine for the gap is not rejected, it is rounded to the nearest one that fits, and then the rounding is added to the next rounding. These are not faults in the machines here. They are the edges of the box, and the machines are what people built to live inside it.
The machine for this idea on its own is Two's Complement, if you would rather press it than read about it.
One instruction, many lanes, and then the data disagrees
1 One instruction across the lanes on data that all takes the same path, where the speedup is the lane count exactly
One instruction, many lanes. When every element takes the same path and the count divides by the width, the speedup is the lane count and the slogan is exactly right. This panel is that case, and it is the only one on the page where the number comes out whole.
| quantity | value | where it comes from |
|---|
2 A count that does not divide by the lane width, and the lanes the last iteration issues for anyway
A count that does not divide by the width leaves the last iteration short. The instruction issues anyway, for every lane, and the ones with nothing to do are masked off: they occupy a lane slot and produce nothing. Move the count above and watch the speedup drop the moment it stops dividing, then climb back as the next full group fills.
| iteration | lanes with an element | bodies issued | lane slots doing nothing |
|---|
3 The same elements in a different order, where only the arrangement changed and the speedup did not survive it
Now give the elements a conditional. A lane whose element takes the other path cannot be skipped: the group runs both sides, one after the other, with the wrong lanes masked off each time. So the cost depends on how the two kinds are ARRANGED, and not only on how many there are. The three arrangements below hold the same elements in every case.
| arrangement | instructions issued | iterations that ran both sides | lane slots used | speedup |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| with no divergence and a count that divides, the speedup is the lane count exactly | yes | 64 elements over 8 lanes is 8 issues, a speedup of 8 and not one idle lane slot |
| one more element costs a whole extra issue, and seven lanes sit idle for it | yes | 65 elements is 9 issues against 8, a speedup of 7.222 rather than 8 |
| and the simulated speedup matches the closed form for the tail | yes | 7.222222 against 7.222222 |
| the same elements in a different order give a speedup of 8.00 or 4.00, and nothing about the data changed | yes | both do 64 useful lane operations; one issues 8 instructions and the other 16 |
| when every group is split, every iteration runs both sides and half the lane slots do nothing | yes | 8 of 8 iterations diverged, and utilisation is 50.0 per cent |
| no arrangement anywhere in the sweep beats the lane count | yes | checked every width to 16, every count to 40 and three arrangements |
What is real here, and what is not
Nothing here is timed, and the speedup is a count
Every figure on this page is instructions issued against elements processed. There is no clock, no memory system, no cache and no pipeline, so nothing here is a prediction of how fast any real machine would run this loop. A real one has all of those and they can dominate. What the counting argument does establish is an upper bound the hardware cannot beat, and the two ways the data alone pushes you under it.
One conditional, two bodies, and both are the same size
The model has exactly two paths and charges one instruction issue for each body a group needs. Real divergence nests, so a chain of conditionals can leave a single lane active through several bodies, and real bodies are not the same length, so the expensive side dominates. Both make the picture worse than this page draws it. Nothing here makes it better.
The arrangements are chosen, not measured, and they are deterministic
Blocked, striped and clustered are three layouts this page defines, not distributions taken from any workload. They are here because they hold the same elements and produce different answers, which is the point: the speedup depends on the order and not only on the counts. Real data is not usually any of the three. The same settings give the same layout every time, so what the page prints can be checked rather than sampled.
Flynn's paper is the name, and the degradation is named in it too
The 1966 paper is a classification and not a machine: it defines Single Instruction Stream-Multiple Data Stream as one of four organizations. On page 1907, discussing branches, Flynn writes that multiple stream organizations may exhibit branch induced degradation from an analog spatial inefficiency in which only one path activates or determines the outcome of a dependency. That is lane divergence, in the paper that named SIMD. It is described here rather than quoted, because the scan is two columns and its OCR interleaves them line by line, so no quotation of that passage is contiguous in the archived text.
The ILLIAC IV is the worked example and not the date
The roster dates this to Flynn's paper of December 1966 rather than to a machine. The ILLIAC IV, designed from 1966 and running in 1975, is the machine most people picture, and Flynn's own example in the paper is SOLOMON. Dating the entry to the machine would put it at least nine years later and would date the idea to one implementation of it, which is the same choice Compare and Swap made when it took the manual over the folklore.