Model 1 · All models · Model specification · Instruction sets
Bill Dally (On the Model of Computation, CACM 2022) proposed pricing algorithms by their data movement. Memory is a 2D grid around the core; an access to address a costs its Manhattan distance ⌈√a⌉. Writes are free, and arithmetic instructions pay for their source reads. Below, matrix multiply runs one access per clock so the bill accumulates in the open — start with 2×2, then compare the naive 4×4 against the tiled one.
The cell at linear index a sits at Manhattan distance ⌈√a⌉ from the core, so ring k holds 2k−1 cells. The naive schedules place the arrays contiguously; the tiled schedule reserves the cheapest cells for its scratchpad and pushes the bulk arrays out.
Two thirds of the naive 4×4 bill is scratch traffic: each of the 48 accumulate steps reads C[i,j] at distance 6–7 and tmp at distance 7, so tmp alone (336) costs more than every access to A (200).
Tiling barely helps at this size — 1,296 against 1,316. The 2×2 scratchpad does keep the inner loop in the cheapest thirteen cells, but paying to copy tiles in and out, and pushing the bulk arrays from addresses 1–48 out to 14–61, eats almost all of the saving. The same schedule at 16×16 wins properly, 133,783 against 340,704, because each copied tile is reused across a whole block row instead of twice.