THE FOLD / GRIND / THE GRINDSTONE / THE SYSTOLIC ARRAY
THE SYSTOLIC ARRAY
stop fetching operands and start pumping them
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Kung and Leiserson’s 1978 idea: stop fetching operands and start pumping them. Data enters at the edge of a mesh and every cell it passes through uses it once more. The arithmetic does not get cheaper. The memory does.
LIT verified live. a 16×16 output-stationary array multiplying two 16×16 matrices reproduces all 256 of 256 entries of the naive triple loop, and performs 4,096 multiply-accumulates — exactly the same count as the naive loop. What changes is the edge: 8,192 operand reads become 512, a factor of 16, which is N. The wavefront finishes in 46 cycles, matching
LIT verified live. a 16×16 output-stationary array multiplying two 16×16 matrices reproduces all 256 of 256 entries of the naive triple loop, and performs 4,096 multiply-accumulates — exactly the same count as the naive loop. What changes is the edge: 8,192 operand reads become 512, a factor of 16, which is N. The wavefront finishes in 46 cycles, matching
3N−2 exactly.2 HOW IT WAS WEAVED · AI + HUMAN
H. T. Kung and Charles Leiserson published systolic arrays in 1978; the reuse factor N and the
AVAN (AI) ran the array rather than quoting it, and instrumented both sides. The number worth having is 4,096 = 4,096: the systolic array does not do less arithmetic. Every claim of the form ‘the accelerator is 16× faster’ here is a claim about reads, and the check that proves it is the one showing the MAC counts are identical.
3N−2 wavefront latency are the standard results, and Google’s TPU is the best-known modern instance.AVAN (AI) ran the array rather than quoting it, and instrumented both sides. The number worth having is 4,096 = 4,096: the systolic array does not do less arithmetic. Every claim of the form ‘the accelerator is 16× faster’ here is a claim about reads, and the check that proves it is the one showing the MAC counts are identical.
3 ONE DIMENSION
Same arithmetic. One sixteenth of the memory traffic.
4 TWO DIMENSIONS · INTERACTIVE
Step the wavefront through the mesh.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that perfect reuse makes the array fast. The inverse is that the reuse and the rigidity are the same property. Data flows in lockstep because the wiring is the schedule; there is no instruction stream to say otherwise. So the array that hits 100% utilisation on a 16×16 matmul drops to 9.8% — 25 cells of 256 — on a 5×5 one, and the idle cells cannot be told to do anything else. Read backwards, a systolic array is not a fast processor; it is a fast shape, and the arithmetic must be bent to fit it.
LIT a 16x16 output-stationary array reproduces all 256 of 256 entries of the naive triple loop and performs 4,096 multiply-accumulates - exactly the same count as the naive loop; what changes is the edge, where 8,192 operand reads become 512, a factor of 16 which is N, and the wavefront finishes in 46 cycles, matching 3N-2 exactly
FIG H. T. Kung and Charles Leiserson published systolic arrays in 1978; the reuse factor N and the 3N-2 wavefront latency are the standard results, and Google's TPU is the best-known modern instance. AVAN ran the array and instrumented both sides. The number worth having is 4,096 = 4,096: the array does not do less arithmetic. Every '16x faster' claim here is a claim about reads, and the check that proves it is the one showing the MAC counts are identical.
FIG H. T. Kung and Charles Leiserson published systolic arrays in 1978; the reuse factor N and the 3N-2 wavefront latency are the standard results, and Google's TPU is the best-known modern instance. AVAN ran the array and instrumented both sides. The number worth having is 4,096 = 4,096: the array does not do less arithmetic. Every '16x faster' claim here is a claim about reads, and the check that proves it is the one showing the MAC counts are identical.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GRINDSTONE · David Lee Wise (ROOT0), with AVAN