Week 7 · Lesson 1
Measuring speed: FLOPs, bytes and the roofline
Until now the grader asked one question: are the bits right? From this week it also asks how long your kernel takes. Before making anything faster, you need to know how fast it could possibly be, and what is holding it back. Two numbers answer that: how much arithmetic a kernel does, and how many bytes it has to move.
Work and time
A FLOP is one floating-point operation: an add or a multiply. A 768×768 matrix multiply does about 2 · 768³ ≈ 0.9 billion of them (one multiply and one add per term). Divide the FLOPs by the seconds the kernel takes and you get its speed in GFLOP/s, billions of FLOPs per second.
tools/bench.py does this for any program. On the machine this course was built on, the same GEMM ran at 9 GFLOP/s as plain loops and at over 200 GFLOP/s with the schedule this week teaches. Both versions compute the identical bits.
What limits a kernel
A processor can only do so many operations per second: its peak. Memory can only deliver so many bytes per second: its bandwidth. A kernel is held back by whichever runs out first.
The deciding number is the kernel's arithmetic intensity: FLOPs per byte moved between memory and the processor.
- An elementwise add of two f32 arrays reads 8 bytes and writes 4 for each single add: about 0.08 FLOPs per byte. However fast the processor, it waits on memory.
- A matrix multiply of N×N matrices reads about
3 · 4N²bytes and does2N³FLOPs: an intensity that grows with N. At N = 768 it's over 100 FLOPs per byte. Memory is no excuse: it's the arithmetic that has to get faster.
Memory can feed at most bandwidth · intensity FLOP/s, and the processor can do at most peak. So the best a kernel can reach is the smaller of the two. Draw that against intensity and you get a roof: a slanted part (memory-bound) meeting a flat part (compute-bound). It's called the roofline.
| kernel | FLOPs per byte | limited by | what helps |
|---|---|---|---|
| elementwise add | about 0.08 | memory | moving fewer bytes: fusing ops (week 4), using every byte of each cache line |
| a reduction (sum) | about 0.25 | memory | the same, plus threads (several cores pull from memory at once) |
| a large matmul | 100 or more | compute | keeping data close (caches, registers), SIMD, threads |
The roofline
Write attainable: the best GFLOP/s a kernel can reach, given the machine's peak and bandwidth and the kernel's FLOPs and bytes.
Measuring honestly
Timing is noisy. Other programs run, the processor changes its clock speed, the first run warms the caches. Three habits make numbers trustworthy:
- Time the kernel alone. Not the compiler, not loading the data. The harness reads a monotonic clock just before and just after the kernel call.
- Take the best of several runs. Noise only ever makes a run slower, so the minimum is the closest to the truth.
- Compare on the same machine, at the same time. A number from your laptop and one from a server mean nothing side by side. The speed tests run your kernel and the reference kernel alternately, three times each, and compare the bests.
How week 7 grades speed
A test with # speed: 0.5 requires your kernel to run at least half as fast as the reference compiler's kernel for the same program, built the same way, on your machine. It must also give exactly the reference's bits. Half is generous on purpose: the tests aren't measuring clever tricks, they're checking that your compiler does what the program's schedule says. Lessons 7.3 and 7.4 show a renderer that ignores the schedule landing 2 to 8 times too slow.
Nothing this week changes what a program computes. Unrolling and threads must keep every add in its original order, so a fast kernel's output is identical to a slow one's. The C is compiled with -ffp-contract=off, which stops the C compiler from fusing a multiply and an add into one instruction. That fused instruction rounds once instead of twice, so it would change the bits.
Check yourself
How many GFLOPs does a 768×768 by 768×768 matrix multiply do? (Count a multiply and an add per term.)
2 · 768³, in billions.
2 · 768³ = 905,969,664, about 0.9 GFLOP.
That GEMM takes 4 ms. About how many GFLOP/s is that?
GFLOPs divided by seconds.
0.906 / 0.004 ≈ 226 GFLOP/s.
A machine has a peak of 100 GFLOP/s and 20 GB/s of bandwidth. An elementwise add does 1 FLOP per 12 bytes. What limits it?
Memory can feed bandwidth · intensity.
20 · (1/12) ≈ 1.7 GFLOP/s, far below the peak. A faster processor wouldn't help this kernel at all.
Why does the grader take the best of three runs, not the average?
Can noise make a kernel faster than it really is?
No. Interference only slows a run down. The minimum filters it out better than an average, which a single slow run would drag up.
Your renderer uses an instruction that does a·b + c with one rounding. What happens on the tests?
The spec says mul, then add, each rounded.
A fused multiply-add skips the rounding after the multiply. The result is often more accurate, and sometimes different in the last bit, which the bit-exact tests catch. That's why the harness passes -ffp-contract=off.