Tutorial · compilers, performance, programming-languages, hardware

Write your own kernel optimiser

First published at blog.csongor.co.uk.

Csongor Kiss walks through building a kernel optimiser with Cachet, using grids and tiles to schedule loops so a program's data flow matches the hardware instead of hand-writing custom kernels.

Write your own kernel optimiser

Csongor Kiss · 5 November 2026

Optimising a program is done in one of two ways. The first is to write down a program that computes the result we want, and hope that the compiler is smart enough to make it fast. The second, when that isn’t enough, is to rewrite it by hand, so that its data flow matches the hardware. This is where abstractions break down. When the compiler gives up on something written with a nice Python library, we end up writing custom kernels, intrinsics, and inline assembly.

Both rely on transformations that preserve meaning only under conditions, such as the output not overlapping the inputs. Compiler optimisations let us keep our original program, but hide the transformations. Hand-optimised code shows the result of the transformations, but hides where we started from.

Tutorial · compilers, performance, programming-languages, hardware

Write your own kernel optimiser

First published at blog.csongor.co.uk.

Csongor Kiss walks through building a kernel optimiser with Cachet, using grids and tiles to schedule loops so a program's data flow matches the hardware instead of hand-writing custom kernels.

Write your own kernel optimiser

Csongor Kiss · 5 November 2026

Optimising a program is done in one of two ways. The first is to write down a program that computes the result we want, and hope that the compiler is smart enough to make it fast. The second, when that isn’t enough, is to rewrite it by hand, so that its data flow matches the hardware. This is where abstractions break down. When the compiler gives up on something written with a nice Python library, we end up writing custom kernels, intrinsics, and inline assembly.

Both rely on transformations that preserve meaning only under conditions, such as the output not overlapping the inputs. Compiler optimisations let us keep our original program, but hide the transformations. Hand-optimised code shows the result of the transformations, but hides where we started from.

are pattern variables: they match parts of the original program. For example, `$step` is the code in the sum, and `$a`, `$b`, `$lo` and `$hi` are the loop bounds.\n\nThe last part, `relate`, tells the checker how to compare the original program, `S`, with the replacement, `T`. The first two lines read each sum as a sequence of updates to its cell of `c`, one for each `k`. The last asks the checker to show that moving the loop over `j` inside produces identical outputs. Different values of `j` update different cells of `c`, and the inputs are only read. Swapping `j` and `k` changes when we visit each output, but each output still receives its updates in ascending order of `k`.\n\nThe checker uses an SMT solver, an automated prover, to check the equivalence for the actual program being rewritten. Importing `hoist` doesn’t exempt it from the check: if we break its definition, the schedule is refused, as the [side note on broken steps](#panel-wrong) shows.\n\nNot every step needs this much. `interchange`, which `bands` uses to reorder its packing loops, swaps two loops and asks the checker to show that no iteration reads what another writes:\n\n```\ncachetstep fn interchange (i, j) =\n from\n for i in $A do\n for j in $B do\n $body\n to\n for j in $B do\n for i in $A do\n $body\n relate\n interchange S.i\n```\n\n### When a step is wrong\n\nThe library’s `hoist` step works, which doesn’t say much for the checker. Suppose we break it. We’ll copy it into our own program under a new name, keeping its `relate` proof recipe, and use the copy in place of `hoist` in `swapped`.\n\nWe start with an off-by-one, in a copy called `sloppy`, by changing a single line of `to`:\n\n```\ncachet for k in $lo + 1 .. $hi do\n```\n\nThe schedule that calls it is refused:\n\n```\ncould not prove relation swapped'1_sloppy: the loops at S.k and T.k run the same number of times\n```\n\n`S` and `T` are the programs before and after the step, as in `hoist`’s `relate`, and `swapped'1` is the program the step starts from, after `zero`.\n\nThat one is easy to spot by hand. Here’s one that isn’t. In a copy called `backwards`, we keep the loop bounds but change its body to visit the products in reverse order. `$step[$acc][k := e]` replaces `k` with `e` in the matched sum’s body:\n\n```\ncachet store $cell = $step[$acc][k := $hi - 1 - (k - $lo)]\n```\n\nEvery product is still added exactly once, and the loop nest it writes out is a correct matrix multiplication over the reals. In floating point, the additions happen in the opposite order, so they round differently:\n\n```\ncould not prove relation swapped'1_backwards: the two runs hold the same words in parameter 3 after each iteration of the loops at S.j and T.j\n```\n\nParameter 3 is `c`: the checker couldn’t establish that its contents are identical after the rewrite. Notice that this is a failed proof, rather than a proof that the kernel is wrong: the checker reports “a model the search cannot rule out”. It’s refused all the same, because the burden of proof is on the step.\n\nThere’s also the requirement that `c` can’t overlap `a` or `b`. A call already has to prove this, without a schedule getting involved. Passing the same matrix as an input and as the output, as in `matmul a b a`, is refused at the call:\n\n```\ncould not prove the call of matmul lends parts of one whole at once, which must be apart: Disjoint (interval (allocated region) 0 (1024 * sizeof f32)) (interval (allocated region) 0 (1024 * sizeof f32))\n```\n\nThe checker has caught the missing iteration, the reversed sum and the overlapping arrays. The backwards loop is the interesting one, though. Neither order is more accurate in general, but we asked for identical results, so the rewrite is refused. Sometimes a different order is exactly what makes a kernel fast, as it is for attention near the end of the post.\n\nThese examples use library steps, whose relations are checked at each use. The [claim panel](#panel-claim) explains how this differs from built-in layout steps, and how the compiler reports any library laws or instruction templates it takes on trust.\n\n### Fusing an epilogue\n\nA layer of a neural network usually does something to the product before storing it, such as a ReLU, which replaces negative values with zero. In Cachet, that’s part of the contraction:\n\n```\ncachetcontraction layer\n (reads a: [f32; M, K])\n (reads b: [f32; K, N])\n -> out c: [f32; M, N] =\n c[i, j] = max (sum k. a[i, k] * b[k, j]) 0.0\n```\n\nWe can apply `tiled`’s two steps to this contraction too. Only the last line of the resulting kernel changes:\n\n```\ncachet t = mma x y t\n store ct_2 = max t 0.0\n```\n\nThe ReLU is applied to the accumulator tile while the SIMD groups still hold it, so the product is never written to memory and read back. We didn’t have to ask for this. A contraction’s equations describe values, not buffers, so an intermediate only gets storage of its own if a schedule asks for it. The same guarantee applies here: the kernel produces exactly the same result as `layer` evaluated using the GPU’s arithmetic.\n\n### The running summary for attention\n\n[FlashAttention](https://arxiv.org/abs/2205.14135) avoids storing the full score matrix by keeping a running summary: the largest score so far, `m`, a sum `l` of weights `e^(s - m)`, and a sum `o` of those weights times the values. When a later block raises the maximum, we rescale both totals by the same factor. Over the reals, this leaves their ratio `o / l` unchanged, so we can adjust the old summary without going back to the old scores. Then we add the new block’s contributions and carry on.\n\nThe `cachet:attention` library puts these operations in `Online`, an implementation of the `Monoid` interface. A *monoid* provides an empty value and an associative operation for combining values. For these summaries, associativity holds over the reals. To combine two summaries, we rescale both to their shared maximum and add them:\n\n```\ncachetimpl Monoid for Online where\n const Value = Weights\n fn empty () = Weights { m = -Num.infinity (), l = -0.0, o = -0.0 }\n fn combine (a: Weights) (b: Weights) =\n let m = max a.m b.m\n let x = rescale a.m m\n let y = rescale b.m m\n Weights { m, l = a.l * x + b.l * y, o = a.o * x + b.o * y }\n```\n\nThe final weighted value is `o / l`, which the library calls `normalised`. `key s v` makes the summary of a single key, with score `s` and value `v`.\n\nTo regroup this reduction, the checker needs laws for these operations. For `PlusTimes f32`, Cachet proves the [semiring laws](#panel-semiring) for the corresponding real-number operations. It doesn’t prove `Online`’s laws. The library states them with reasons, which the checker takes on trust.\n\nThe algebra behind combining summaries is that `(m, l, o)` represents the pair `(e^m l, e^m o)`, and combining summaries adds these pairs. The library also states a *block law*, which lets a schedule add a whole block of keys at once:\n\n```\ncachet law associative over reals = \"(m, l, o) stands for (e^m l, e^m o), which combine adds\"\n law block over reals = \"a block's terms, each e^(s - m2) at the block's largest score m2, add to the summary rescaled to m2 as combine adds them\"\n```\n\nThe reasons in these declarations are shortened from the library’s. They explain the algebra, but aren’t proofs checked by the compiler.\n\n### Reproducibility\n\nNote\n\nRunning the same computation with different schedules doesn’t always give identical results. GPU libraries often split a reduction across threads and combine the partial sums with atomics, which makes the order (and so the result) vary from run to run. This is why frameworks like PyTorch have a separate “deterministic algorithms” mode, which is often slower. In Cachet, a schedule that changes the order says so in its contraction, and the shadow shows exactly which order it uses.\n\n### Related work\n\n[Halide](https://halide-lang.org/) separates an image-processing algorithm from its schedule: the algorithm says what each pixel is, and the schedule chooses the order, tiling, vectorisation and parallelism. [TVM](https://arxiv.org/abs/1802.04799) brought the same idea to deep learning; its `tensorize` step matches a computation against the description of a hardware intrinsic and replaces it with that intrinsic, much like using the reference body of `simdgroup_mma8`.\n\nThe closest relative to what I’m trying to do here is [Exo](https://exo-lang.dev/): the programmer chooses the transformations, and the compiler checks them. [Exo 2](https://arxiv.org/abs/2411.07211) lets users build scheduling libraries by composing a small set of trusted primitives. Cachet’s library steps also put rewrites in user code, with a relation to check at each use.\n\nIndex notation has precedents too. [Tensor Comprehensions](https://arxiv.org/html/1802.04730v3#S3) generalises Einstein notation for tensor computations. [TACO](https://github.com/tensor-compiler/taco/blob/master/include/taco/index_notation/README.md) supports index equations and scheduling operations, including for sparse tensors. [Dex](https://arxiv.org/abs/2104.05372) makes index sets part of its type system. Matrix operations with different choices of addition and multiplication are central to [GraphBLAS](https://raw.githubusercontent.com/DrTimothyAldenDavis/GraphBLAS/stable/Doc/GraphBLAS_UserGuide.pdf), where a semiring supplies those operations.\n\nThe treatment of floating point is where the projects diverge. [Futhark’s `reduce`](https://futhark-lang.org/examples/scan-reduce.html) requires an associative operator and a neutral element, but does not verify those laws. Cachet asks for permission to regroup in the contraction, with `[reassoc]`. It then checks the kernel against the exact arithmetic order in its shadow, and relates that shadow to the original contraction using the stated laws.\n\n[Triton](https://triton-lang.org/main/programming-guide/chapter-1/introduction.html) and [ThunderKittens](https://hazyresearch.stanford.edu/blog/2024-05-12-tk) expose blocks or tiles directly to the programmer. This is roughly the level of Cachet’s grids and tiles; contractions and schedules provide a way to construct those programs from a separate definition.\n\nThat lower layer is still needed. Contractions describe matrix multiplication, convolutions written as contractions, and attention with a monoid like `Online`. But a kernel that stages inputs through shared memory with explicit barriers still needs to be written directly with grids and tiles.\n\n### The complete example\n\n[The complete example](https://blog.csongor.co.uk/code/cachet-contractions.cachet) uses the final, generic `matmul` throughout, including for `rows`, `swapped`, and `tiled`. The early `f32` examples correspond to binding `S` to `PlusTimes f32`.\n\nThe file contains the matrix-multiplication schedules compared in the overview; attention is separate. Its `main` compares `rows`, `swapped`, `tiled`, `tower` and `packed` with `matmul` on the same `f32` inputs. The larger `fast`, `bands`, `sme` and `big_tiles` schedules are defined here but aren’t called by `main`; the benchmark checks that their results match `matmul` exactly.\n\nThe file starts by naming the platform, which is where `M4Gpu` comes from:\n\n```\ncachetmodule (platform = AppleSilicon)\nimport \"../../platforms/apple-silicon.cachet\"\nimport \"cachet:monoid\"\nimport \"cachet:simd\"\nimport \"cachet:steps\"\nimport \"../../examples/lib/panel-major.cachet\"\n```\n\nCachet’s compiler isn’t public yet, so the file is here to read rather than to run. We ran it twice: once in Cachet’s interpreter, and once as a native executable on an M4 Max Mac, where its GPU grids use Metal. Both printed:\n\n```\n1.751874327659607\n0\n0\n0\n0\n0\n3.0\n```\n\nThe first line is an element of the product. The next five lines show how many output elements differ from `matmul` for `rows`, `swapped`, `tiled`, `tower` and `packed`. The comparison is bit for bit, and all five counts are zero. The next line is the shortest path from node 0 to node 2 in a ring, computed by `matmul` at `MinPlus f32`.\n\nNote\n\nThese are correctness examples. The sizes here are small; the [performance measurements](#comparing-the-results) use the same schedules at 1024 × 1024 and larger.\n\n## Footnotes\n\n1. In some cases, such as sums of floating-point numbers, the preservation does not strictly hold. In these cases, we can tell the compiler that we’re willing to treat floating-point addition as associative, which then lets us split a sum across threads. [↩](#user-content-fnref-asterisk)\n2. Billions of floating-point operations per second, counting a multiply-add as two operations. [↩](#user-content-fnref-gflops)\n3. When all you have is a hammer… [↩](#user-content-fnref-hammer)\n4. A grid without `on` runs on the host. A built executable runs its outermost loop on several threads, while Cachet’s interpreter runs the iterations in order. Since no iteration can observe another’s effects, both produce identical results. [↩](#user-content-fnref-host)\n","body_html":"\u003ch1 id=\"write-your-own-kernel-optimiser\">Write your own kernel optimiser\u003c/h1>\n\u003cp>Csongor Kiss · 5 November 2026\u003c/p>\n\u003cp>Optimising a program is done in one of two ways. The first is to write down a program that computes the result we want, and hope that the compiler is smart enough to make it fast.\nThe second, when that isn’t enough, is to rewrite it by hand, so that its data flow matches the hardware. This is where abstractions break down. When the compiler gives up on something written with a nice Python library, we end up writing custom kernels, intrinsics, and inline assembly.\u003c/p>\n\u003cp>Both rely on transformations that preserve meaning only under conditions, such as the output not overlapping the inputs.\nCompiler optimisations let us keep our original program, but hide the transformations. Hand-optimised code shows the result of the transformations, but hides where we started from.\u003c/p>\n\u003cp>In both cases, the decisions that matter are made somewhere we can’t see: for example, which block has to stay in cache, or which loops can be vectorised.\nAn optimising compiler makes these decisions based on a model of the hardware that’s hidden from the source language.\nIn hand-optimised code, we keep these in our head, or in comments in the source file.\u003c/p>\n\u003cp>When performance matters, I would rather not have a clever compiler. Instead, I want the compiler to be explicit.\nThat’s the idea behind Cachet, a language I’ve been building to help reason about performance. In Cachet, which cache a buffer stays in, how much data moves between memory levels, and which instructions the hardware provides are part of the language. We can then make informed decisions, and have the compiler check our assumptions. If an assumption stops holding as the program evolves, it becomes a compile error rather than a performance regression.\u003c/p>\n\u003cp>\u003ca href=\"#user-content-fnref-asterisk\">1\u003c/a>\u003c/p>\n\u003cp>In some cases, such as sums of floating-point numbers, the preservation does not strictly hold. In these cases, we can tell the compiler that we’re willing to treat floating-point addition as associative, which then lets us split a sum across threads.\u003c/p>\n\u003cp>This post is about the transformations themselves. In Cachet, we write down \u003cem>what\u003c/em> to compute and, separately, \u003cem>how\u003c/em> to compute it. A sequence of transformations, a \u003cem>schedule\u003c/em>, turns the computation into an optimised program. The compiler then checks that each transformation preserves the meaning of the original.\u003ca href=\"#user-content-fn-asterisk\">1\u003c/a>\u003c/p>\n\u003cp>We’ll use matrix multiplication as a running example. Starting from its one-line definition, we’ll derive cache-blocked CPU kernels, and optimised GPU kernels using matrix hardware. I’ve run these examples on my laptop (with an M4 Max), but nothing in the technique is specific to Apple’s hardware: Cachet already checks programs for NVIDIA’s H100, though it can’t build them for it yet.\u003c/p>\n\u003cp>To see how we’re doing, we’ll compare each schedule with an optimised library implementation on the same hardware: OpenBLAS for the CPU’s vector instructions, Apple’s Accelerate for its matrix units, and MLX for the GPU. The little bars along the way show how close we get to the library’s speed, with the library at 100%. Each comparison uses the same matrix size and precision.\u003c/p>\n\u003ch2 id=\"matrix-multiplication-by-hand\">Matrix multiplication by hand\u003c/h2>\n\u003cp>Matrix multiplication is very easy to do correctly, but notoriously difficult to do quickly. The definition fits on one line:\u003c/p>\n\u003cpre>\u003ccode>c[i, j] = sum k. a[i, k] * b[k, j]\u003c/code>\u003c/pre>\n\u003cp>A machine needs a little more handholding. For an M × K matrix multiplied by a K × N matrix, we can spell out the order of operations with three nested loops:\u003c/p>\n\u003cpre>\u003ccode>c// c starts out as all zeroes\nfor (int i = 0; i < M; i++)\n for (int j = 0; j < N; j++)\n for (int k = 0; k < K; k++)\n c[i][j] += a[i][k] * b[k][j];\u003c/code>\u003c/pre>\n\u003cp>\u003ca href=\"#user-content-fnref-gflops\">2\u003c/a>\u003c/p>\n\u003cp>Billions of floating-point operations per second, counting a multiply-add as two operations.\u003c/p>\n\u003cp>This loop nest reaches just 1.17 GFLOP/s\u003ca href=\"#user-content-fn-gflops\">2\u003c/a> on one core for 1024 × 1024 matrices: about 1% of OpenBLAS’s speed on the same core. There’s a lot of room to improve:\u003c/p>\n\u003cp>Naive loop nest\u003c/p>\n\u003cp>\u003cstrong>1.17 GFLOP/s\u003c/strong> · 1,843.33 ms1.1% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · one core · 1024 × 1024 · f32\u003c/p>\n\u003cp>The colours show how often each variable changes: \u003ccode>i\u003c/code> the least, \u003ccode>j\u003c/code> more often, and \u003ccode>k\u003c/code> on every multiplication. The hottest variable controls how the inner loop moves through the arrays. Here, \u003ccode>k\u003c/code> walks along a row of \u003ccode>a\u003c/code>, but down a column of \u003ccode>b\u003c/code>.\u003c/p>\n\u003cp>The arrays are stored row by row: \u003ccode>b[0][0]\u003c/code>, \u003ccode>b[0][1]\u003c/code>, and so on, followed by the next row. This is called \u003cem>row-major\u003c/em> order.\nThe processor doesn’t fetch single values. When a value isn’t in its \u003cem>cache\u003c/em> (the small, fast memory close to the core), it fetches a whole chunk of neighbouring bytes called a \u003cem>cache line\u003c/em>. Reading those neighbours can then use the cached copy, avoiding another trip to main memory.\u003c/p>\n\u003cp>Walking along a row uses those neighbours straight away. Walking down a column jumps a whole row at a time, and the cache may have replaced a line by the time we return to its other values. Here’s a small model of the two access patterns:\u003c/p>\n\u003cp>Each row of squares is a row of \u003ccode>b\u003c/code>, and each group of four is one cache line. In this model, a cached read takes 1 tick and a miss takes 8 ticks. Reads run one at a time, without prefetching.\u003c/p>\n\u003cp>Time 0\u003c/p>\n\u003cp>\u003cstrong>Along the rows\u003c/strong>inner loop \u003ccode>for j\u003c/code>\u003c/p>\n\u003cp>The next read is the next element.\u003c/p>\n\u003cp>\u003cstrong>Down the columns\u003c/strong>inner loop \u003ccode>for k\u003c/code>\u003c/p>\n\u003cp>The next read is a whole row ahead.\u003c/p>\n\u003cp>In the cacheBeing readWaiting for memory\u003c/p>\n\u003cp>This \u003ca href=\"#panel-cache\">cache model\u003c/a> holds 4 lines and evicts the least recently used line, so a column of 8 pushes out each line before the walk returns to it.\u003c/p>\n\u003cp>We can get the row-wise access pattern just by swapping the two inner loops:\u003c/p>\n\u003cpre>\u003ccode>c// c starts out as all zeroes\nfor (int i = 0; i < M; i++)\n for (int k = 0; k < K; k++)\n for (int j = 0; j < N; j++)\n c[i][j] += a[i][k] * b[k][j];\u003c/code>\u003c/pre>\n\u003cp>The hottest variable is now \u003ccode>j\u003c/code>, the last subscript of \u003ccode>b\u003c/code> and \u003ccode>c\u003c/code>, so the inner loop walks along their rows, using neighbouring values while their line is still cached. (\u003ccode>a[i][k]\u003c/code> stays the same throughout that loop.) For large matrices, this makes a big difference:\u003c/p>\n\u003cp>Swapped loops\u003c/p>\n\u003cp>\u003cstrong>33 GFLOP/s\u003c/strong> · 65.64 ms30% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · one core · 1024 × 1024 · f32\u003c/p>\n\u003cp>Swapping the loops makes the same multiplication about 28 times faster, though it’s still only 30% of OpenBLAS’s speed on one core.\u003c/p>\n\u003cp>An astute reader might notice that we still walk through all of B for every row of A. If B is too large to stay in cache, much of it has to be fetched again on each pass. Blocking, which we’ll get to \u003ca href=\"#blocking-matrix-multiplication\">shortly\u003c/a>, keeps a block of inputs in cache until we’ve done as much work with it as possible.\u003c/p>\n\u003cp>Swapping loops doesn’t preserve a program’s meaning in general, though. Here, provided \u003ccode>c\u003c/code> doesn’t overlap either input, different values of \u003ccode>j\u003c/code> update different outputs. Each output still receives the same products in ascending order of \u003ccode>k\u003c/code>; we’ve only changed how updates to different outputs are interleaved. These conditions aren’t written down, and a fast kernel has many such rewrites stacked on top of each other.\u003c/p>\n\u003cp>We’d like the compiler to check these conditions for us.\u003c/p>\n\u003ch2 id=\"say-what-not-how\">Say what (not how)\u003c/h2>\n\u003cp>\u003ca href=\"#user-content-fnref-hammer\">3\u003c/a>\u003c/p>\n\u003cp>When all you have is a hammer…\u003c/p>\n\u003cp>Loops make this harder than it needs to be. They commit us to visiting the outputs in a particular sequence, even though each output can be computed independently. Before changing that sequence, we have to establish which parts of the order matter, which is busywork for either the programmer or the compiler. Finding constructs that describe the computation itself, and still map well to the hardware, is a language design problem.\u003ca href=\"#user-content-fn-hammer\">3\u003c/a>\u003c/p>\n\u003cp>We can now write the definition as a Cachet function, starting with ordinary 32-bit floats:\u003c/p>\n\u003cpre>\u003ccode>cachetcontraction matmul\n (reads a: [f32; M, K])\n (reads b: [f32; K, N])\n -> out c: [f32; M, N] =\n c[i, j] = sum k. a[i, k] * b[k, j]\u003c/code>\u003c/pre>\n\u003cp>This is a \u003cem>contraction\u003c/em>: a function defined by an equation for each output element. The body is the formula we started with. \u003ccode>[f32; M, K]\u003c/code> is an array with \u003ccode>M\u003c/code> rows and \u003ccode>K\u003c/code> columns, and \u003ccode>reads\u003c/code> lets the function read it. \u003ccode>-> out c\u003c/code> names the result: the caller provides space for \u003ccode>c\u003c/code>, and \u003ccode>matmul\u003c/code> fills it.\u003c/p>\n\u003cp>\u003ccode>M\u003c/code>, \u003ccode>K\u003c/code>, and \u003ccode>N\u003c/code> are the dimensions. The equation tells us which outputs are independent, which inputs to add up, and which operations to use:\u003c/p>\n\u003cul>\u003cli>\u003ccode>i\u003c/code> and \u003ccode>j\u003c/code> appear on the left, so they are \u003cem>free\u003c/em>: each pair names one element of \u003ccode>c\u003c/code>, which is written exactly once. Different pairs compute independent outputs.\u003c/li>\u003cli>\u003ccode>k\u003c/code> only appears under the \u003ccode>sum\u003c/code>, so it’s \u003cem>summed\u003c/em>: for each output, we multiply the pairs of inputs it selects and add up the products.\u003c/li>\u003cli>\u003ccode>*\u003c/code> and \u003ccode>+\u003c/code> come from the element type. Here that’s \u003ccode>f32\u003c/code>, but we’ll see later that the same formula works when an element is a block (another matrix).\u003c/li>\u003c/ul>\n\u003cp>Since the free indices say nothing about order, the outputs can be computed in any order, or all at once.\u003c/p>\n\u003ch3 id=\"rewriting-the-loop-nest\">Rewriting the loop nest\u003c/h3>\n\u003cp>A contraction has a precise meaning as a loop nest. You can ask Cachet’s compiler, \u003ccode>cachetc\u003c/code>, to print it with \u003ccode>cachetc scheduled\u003c/code>.\u003c/p>\n\u003cp>A \u003cem>schedule\u003c/em> is a sequence of rewrites that turns this loop nest into another function. The compiler applies the rewrites once, when it builds the program. Calling the resulting function just runs the kernel.\u003c/p>\n\u003cp>The swap we already know comes first. The schedule is above the loop body it produces. Use Previous and Next to follow the rewrites; the current step is highlighted. \u003ccode>...\u003c/code> leaves out code that isn’t relevant to the step:\u003c/p>\n\u003cpre>\u003ccode>schedule swapped of matmul =\n zero (i, j) c\n hoist (j, k) c\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for i in 0 .. M do\n for j in 0 .. N do\n var acc'0: f32 = -0.0\n for k in 0 .. K do\n acc'0 = fma (load a[i, k]) (load b[k, j]) acc'0\n store c[i, j] = acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for zi in 0 .. M do for zj in 0 .. N do\n store c[zi, zj] = -0.0\nfor i in 0 .. M do\n for j in 0 .. N do\n for k in 0 .. K do\n let acc'0 = load c[i, j]\n store c[i, j] = fma ... acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for zi in 0 .. M do for zj in 0 .. N do\n store c[zi, zj] = -0.0\nfor i in 0 .. M do\n for k in 0 .. K do\n for j in 0 .. N do\n let acc'0 = load c[i, j]\n store c[i, j] = fma ... acc'0\u003c/code>\u003c/pre>\n\u003cp>Each output adds up its products in ascending order of k, starting from zero.\u003c/p>\n\u003cp>\u003cstrong>1.17 GFLOP/s\u003c/strong> · 1,843.33 ms1.1% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>zero\u003c/code> stores zero in every cell first, in a loop of its own. The listing shows each sum as updates to its cell, with the same products in the same order.\u003c/p>\n\u003cp>\u003cstrong>1.17 GFLOP/s\u003c/strong> · 1,836.16 ms1.1% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>hoist\u003c/code> runs the sum's steps outside the loop over j, and each cell holds its running total between visits. Each output receives the same multiply-adds in the same order.\u003c/p>\n\u003cp>\u003cstrong>33 GFLOP/s\u003c/strong> · 65.64 ms30% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>swapped: bits of matmul\u003c/code>\u003c/p>\n\u003cp>In the starting loop nest, \u003ccode>load\u003c/code> reads a value and \u003ccode>store\u003c/code> writes one. The running total, \u003ccode>acc'0\u003c/code>, starts from zero, written \u003ccode>-0.0\u003c/code> for a reason the \u003ca href=\"#panel-semiring\">semiring panel\u003c/a> explains, and is stored once at the end. Each step uses a \u003ca href=\"#panel-fma\">fused multiply-add\u003c/a>: \u003ccode>fma a b acc\u003c/code> computes \u003ccode>a * b + acc\u003c/code> with a single rounding, rather than rounding the product separately.\u003c/p>\n\u003cp>This is the behaviour a schedule must preserve: each output receives the same chain of multiply-adds, in ascending order of \u003ccode>k\u003c/code>.\u003c/p>\n\u003cp>There’s a small problem with swapping the loops as they are. Each output keeps its running total in a local variable, which is stored once at the end. After the swap, we’d leave that output to work on the next one, then return to it at the next value of \u003ccode>k\u003c/code>. Its total has to survive between visits.\u003c/p>\n\u003cp>The first step, \u003ccode>zero (i, j) c\u003c/code>, prepares for this. It writes zero to every element of \u003ccode>c\u003c/code> first, in a loop of its own, and then has each output’s sum start from what its cell holds. The listing shows this sum as updates to the cell: you can read it as load the total, add a product, store it back. Each total still starts from zero and receives the same products in the same order.\u003c/p>\n\u003cp>Now \u003ccode>hoist (j, k) c\u003c/code> moves the steps of the sum outside the loop over \u003ccode>j\u003c/code>. Each visit loads a cell’s total, adds the next product, and stores it back.\u003c/p>\n\u003cp>After both steps, the line at the bottom summarises the schedule’s \u003ca href=\"#panel-claim\">\u003cem>claim\u003c/em>\u003c/a>: what the compiler has checked. Here, \u003ccode>swapped\u003c/code> and \u003ccode>matmul\u003c/code>’s own loop nest produce identical results, bit for bit, for any inputs that satisfy the function’s requirements. The resulting function takes the same arrays as \u003ccode>matmul\u003c/code>, so we call it as \u003ccode>swapped a b c\u003c/code>.\u003c/p>\n\u003cp>The \u003ccode>hoist\u003c/code> we used for \u003ccode>matmul\u003c/code> is a \u003cem>step function\u003c/em> from the \u003ccode>cachet:steps\u003c/code> library: a rewrite with a proof recipe. Its \u003ca href=\"#panel-hoist\">definition\u003c/a> gives a piece of program to match, its replacement, and instructions for checking that the result is preserved. Every time we use the step, the checker has to establish this for the actual program we’re rewriting.\u003c/p>\n\u003cp>Most other steps are defined in \u003ccode>cachet:steps\u003c/code> in the same way. A few layout steps, such as \u003ccode>split\u003c/code> and \u003ccode>order\u003c/code>, are built into the compiler.\u003c/p>\n\u003ch2 id=\"blocking-matrix-multiplication\">Blocking matrix multiplication\u003c/h2>\n\u003cp>We now return to our astute reader’s observation: we keep fetching the same inputs for different outputs. Blocking lets us keep a block in cache while computing several outputs from it.\u003c/p>\n\u003cp>The inner kernel alone can take hundreds of lines: \u003ca href=\"https://github.com/flame/blis\" rel=\"nofollow ugc noopener\">BLIS\u003c/a>’s \u003ca href=\"https://github.com/flame/blis/blob/a8037cfc4330030c726efaec1ffeb1f93d468aa3/kernels/haswell/3/bli_gemm_haswell_asm_d6x8.c#L939-L1656\" rel=\"nofollow ugc noopener\">double-precision kernel for Haswell\u003c/a> runs to about 720. Much of that code deals with registers and instructions. The code around the kernel divides the work into blocks, hands it out to threads, and organises memory access around the cache hierarchy of one particular machine.\u003c/p>\n\u003cp>The \u003ca href=\"#panel-matmul\">structure of matrix multiplication\u003c/a> gives us several ways to divide up that work. We’ll start with the CPU: blocking, packing the inputs, and tuning the kernel. Then we’ll build GPU schedules from the same contraction.\u003c/p>\n\u003ch3 id=\"working-through-a-sum-in-chunks\">Working through a sum in chunks\u003c/h3>\n\u003cp>Each output has a sum to work through. We can cut it into consecutive pieces, provided the running total carries on from one piece to the next. Here are the first two steps of \u003ccode>tower\u003c/code>, a CPU schedule we’ll build up later:\u003c/p>\n\u003cpre>\u003ccode>First two stepsschedule tower of matmul =\n zero (i, j) c\n split k by 16 as gk ragged\u003c/code>\u003c/pre>\n\u003cp>\u003cstrong>1.5 GFLOP/s\u003c/strong> · 1,428.42 ms1.4% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>zero\u003c/code> prepares the output cells as before. \u003ccode>split\u003c/code> divides the sum over \u003ccode>k\u003c/code> into chunks of at most 16 products. It names the chunk \u003ccode>gk\u003c/code>, and \u003ccode>k\u003c/code> now counts the position within it. The part that updates one output has this shape:\u003c/p>\n\u003cpre>\u003ccode>Loop body for one outputfor gk in blocks (0 .. K) 16 do\n for k in 0 .. gk.len do\n let acc = load c[i, j]\n store c[i, j] = fma (load a[i, gk[k]]) (load b[gk[k], j]) acc\u003c/code>\u003c/pre>\n\u003cp>\u003ccode>gk.len\u003c/code> is the chunk’s length, and \u003ccode>gk[k]\u003c/code> is the corresponding index in the original sum. At \u003ccode>K = 40\u003c/code>, the chunks cover \u003ccode>k = 0\u003c/code> through \u003ccode>15\u003c/code>, then \u003ccode>16\u003c/code> through \u003ccode>31\u003c/code>, then \u003ccode>32\u003c/code> through \u003ccode>39\u003c/code>. (\u003ccode>ragged\u003c/code> means the last chunk can be shorter.) The cell isn’t reset between chunks: it carries the same running total through the same products in the same order.\u003c/p>\n\u003cp>Giving each chunk a separate total and combining those totals afterwards would be a different transformation. It would let us compute the chunks independently, but it would regroup the additions. Over the reals that makes no difference (since addition is associative), but in floating point, each addition rounds, so the answer can change. A plain \u003ccode>sum\u003c/code> doesn’t allow that. We’ll use a contraction that gives permission to regroup when we get to \u003ca href=\"#attention\">attention\u003c/a>.\u003c/p>\n\u003cp>Chunking lets us work through each output’s sum in pieces. To reuse inputs across neighbouring outputs, we need to work on several outputs together.\u003c/p>\n\u003ch3 id=\"reusing-inputs-across-outputs\">Reusing inputs across outputs\u003c/h3>\n\u003cp>Two 8 × 8 matrices make the pattern visible. Grouping their entries into 4 × 4 blocks gives us a 2 × 2 matrix of matrices. The lower multiplication follows the same pattern as the ordinary 2 × 2 multiplication above it, except that each entry is now a block.\u003c/p>\n\u003cp>Reusing inputs across a 4 × 4 output block\u003c/p>\n\u003cp>\u003cstrong>Regrouping each matrix into four blocks.\u003c/strong>\u003c/p>\n\u003cp>Each of the four entries is now a 4 × 4 matrix.\u003c/p>\n\u003cp>Loading animation…ScrubProgress\u003c/p>\n\u003cp>2 × 2 reference\u003c/p>\n\u003cp>Each block contains 4 × 4 entries\u003c/p>\n\u003cp>First contributionSecond contributionRunning sum\u003c/p>\n\u003cp>Fetch a line for the next row of A.\u003c/p>\n\u003cp>The first row has received its contributions from these blocks. The four lines of B are still in cache: each can now help compute the next row.\u003c/p>\n\u003cp>A short excerpt from the multiplication, using a small illustrative cache. Fetches from memory are slowed down; hits run faster. Only input data occupies this cache. Output colour includes work done before the excerpt.\u003c/p>\n\u003cp>For example, the upper-left output block is \u003ccode>A[0, 0] × B[0, 0] + A[0, 1] × B[1, 0]\u003c/code>, where the indices now select whole blocks. Each \u003ccode>×\u003c/code> is a matrix multiplication: every row of the A block is multiplied by every column of the B block.\u003c/p>\n\u003cp>We can follow that one output block. We keep 16 running totals, initially zero. The first pair of input blocks supplies the products for \u003ccode>k = 0, 1, 2, 3\u003c/code>. We update all 16 totals, then replace the inputs with the second pair, for \u003ccode>k = 4, 5, 6, 7\u003c/code>. The totals stay where they are. Only after both pairs have contributed do we store the finished output block.\u003c/p>\n\u003cp>To compute one output independently, we read eight values from A and eight from B. Repeating that for all 16 outputs takes 256 input loads. Working on the block, we load 16 values from A and 16 from B, keep them while updating all 16 outputs, then do the same with the next pair: 64 input loads. Each A value contributes to four output columns, and each B value contributes to four output rows.\u003c/p>\n\u003cp>Reusing the inputs this way leaves the arithmetic unchanged. Drawing block boundaries alone doesn’t achieve this: we have to \u003ca href=\"#panel-blocking\">keep the values nearby\u003c/a> while updating the outputs. These counts describe the algorithm’s loads, not transfers from main memory; caches may satisfy some of the loads in either version.\u003c/p>\n\u003cp>The figure’s \u003cstrong>Keep them in cache\u003c/strong> view follows a few products from the next row of C. With whole rows, the walk through B has evicted the lines we need again. With blocks, those lines are still there. (The cache is deliberately tiny, so we can see everything it contains.) The loop swap improved reuse within a row; blocking lets us reuse the same inputs across several rows as well.\u003c/p>\n\u003cp>The blocked multiplication is the same formula as before, applied to a 2 × 2 matrix whose elements are 4 × 4 blocks. The \u003ccode>+\u003c/code> and \u003ccode>×\u003c/code> it uses are matrix addition and multiplication. That’s the trick: tiling is matrix multiplication at a different element type. (We can do this more than once, which is convenient when the machine has more than one level of cache.)\u003c/p>\n\u003ch2 id=\"scheduling-for-the-cpu\">Scheduling for the CPU\u003c/h2>\n\u003cp>We’ll want both 32-bit and 64-bit CPU versions, but the loop swap didn’t use any property of \u003ccode>f32\u003c/code>. Instead of writing the contraction again for \u003ccode>f64\u003c/code>, we can make its element type and operations a parameter:\u003c/p>\n\u003cpre>\u003ccode>cachetcontraction matmul {S : Semiring}\n (reads a: [S.Value; M, K])\n (reads b: [S.Value; K, N])\n -> out c: [S.Value; M, N] =\n c[i, j] = sum k. a[i, k] * b[k, j]\u003c/code>\u003c/pre>\n\u003cp>\u003ccode>S\u003c/code> supplies the element type \u003ccode>S.Value\u003c/code>, the operations, and their laws. This interface is called a \u003ca href=\"#panel-semiring\">\u003cem>semiring\u003c/em>\u003c/a>. \u003ccode>PlusTimes f32\u003c/code> supplies ordinary floating-point arithmetic, with \u003ccode>fma\u003c/code> for its \u003ccode>mul_add\u003c/code>, so \u003ccode>matmul @(S = PlusTimes f32)\u003c/code> is the computation we’ve used so far. We’ll use this generic definition for the rest of the post.\u003c/p>\n\u003cp>\u003ccode>tower\u003c/code>, the CPU schedule whose first two steps split each sum into chunks, continues from there. The next two steps cut the rows and columns into blocks too, and \u003ccode>order\u003c/code> then moves the loop over chunks outside the output loops. We now take one block of the depth \u003ccode>k\u003c/code> and visit all the outputs it contributes to, giving us a chance to reuse blocks of A and B while they’re still in cache. This schedule still runs on one CPU core. The figure follows it into \u003ccode>packed\u003c/code>, which adds packing and register storage:\u003c/p>\n\u003cpre>\u003ccode>schedule tower of matmul =\n zero (i, j) c\n split k by 16 as gk ragged\n split i by 16 as gi, 4 as ui ragged\n split j by 8 as gj ragged\n order (gk, gj, gi, ui, i, j)\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>schedule packed of matmul @(S = PlusTimes f32)\n (mut packA: [f32; 16, 16] in PanelMajor 4 at DRAM)\n (mut packB: [f32; 16, 8] at DRAM) =\n ...\n order (gk, gj, gi, ui, i, j)\n pack a into packA along gi over (a0, a1)\n keep packA along gi within L2 into packA_L2\n ...\n pack b into packB along gj over (b0, b1)\n ...\n keep packB along gj within L1 into packB_L1\n ...\n registers (i, j) into c rows 4 lanes 8 through fma\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for i in 0 .. M do\n for j in 0 .. N do\n var acc'0: S.Value = S.zero ()\n for k in 0 .. K do\n acc'0 = S.mul_add ... acc'0\n store c[i, j] = acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for zi in 0 .. M do for zj in 0 .. N do\n store c[zi, zj] = S.zero ()\nfor i in 0 .. M do\n for j in 0 .. N do\n for k in 0 .. K do\n let acc'0 = load c[i, j]\n store c[i, j] = S.mul_add ... acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>... // zero C\nfor i in 0 .. M do\n for j in 0 .. N do\n for gk in blocks (0 .. K) 16 do\n for k in 0 .. gk.len do\n let acc'0 = load c[i, j]\n store c[i, j] = S.mul_add ... acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>... // zero C\nfor gi in blocks (0 .. M) 16 do\n for ui in blocks (0 .. gi.len) 4 do\n for i in 0 .. ui.len do\n for j in 0 .. N do\n for gk in blocks (0 .. K) 16 do\n for k in 0 .. gk.len do\n let acc'0 = load c[gi[ui[i]], j]\n store c[gi[ui[i]], j] = S.mul_add ... acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>... // zero C\nfor gi in blocks (0 .. M) 16 do\n for ui in blocks (0 .. gi.len) 4 do\n for i in 0 .. ui.len do\n for gj in blocks (0 .. N) 8 do\n for j in 0 .. gj.len do\n for gk in blocks (0 .. K) 16 do\n for k in 0 .. gk.len do\n let acc'0 = load c[gi[ui[i]], gj[j]]\n store c[gi[ui[i]], gj[j]] = S.mul_add ... acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>... // zero C\nfor gk in blocks (0 .. K) 16 do\n for gj in blocks (0 .. N) 8 do\n for gi in blocks (0 .. M) 16 do\n for ui in blocks (0 .. gi.len) 4 do\n for i in 0 .. ui.len do\n for j in 0 .. gj.len do\n for k in 0 .. gk.len do\n let acc'0 = load c[gi[ui[i]], gj[j]]\n store c[gi[ui[i]], gj[j]] = S.mul_add ... acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>... // zero C\nfor gk in blocks (0 .. K) 16 do\n for gj in blocks (0 .. N) 8 do\n for gi in blocks (0 .. M) 16 do\n for a0 in 0 .. gi.len do\n for a1 in 0 .. gk.len do\n store packA[a0, a1] = load a[gi[a0], gk[a1]]\n ... // update C from packA and B\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>... // zero C\nfor gk in blocks (0 .. K) 16 do\n for gj in blocks (0 .. N) 8 do\n for gi in blocks (0 .. M) 16 do\n for a0 in 0 .. gi.len do\n for a1 in 0 .. gk.len do\n store packA[a0, a1] = load a[gi[a0], gk[a1]]\n lease mut packA_L2 = packA at L2\n ... // update C from packA_L2 and B\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>... // zero C\nfor gk in blocks (0 .. K) 16 do\n for gj in blocks (0 .. N) 8 do\n for b0 in 0 .. gk.len do\n for b1 in 0 .. gj.len do\n store packB[b0, b1] = load b[gk[b0], gj[b1]]\n for gi in blocks (0 .. M) 16 do\n for a0 in 0 .. gi.len do\n for a1 in 0 .. gk.len do\n store packA[a0, a1] = load a[gi[a0], gk[a1]]\n lease mut packA_L2 = packA at L2\n ... // update C from packA_L2 and packB\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>... // zero C\nfor gk in blocks (0 .. K) 16 do\n for gj in blocks (0 .. N) 8 do\n for b0 in 0 .. gk.len do\n for b1 in 0 .. gj.len do\n store packB[b0, b1] = load b[gk[b0], gj[b1]]\n lease mut packB_L1 = packB at L1\n for gi in blocks (0 .. M) 16 do\n for a0 in 0 .. gi.len do\n for a1 in 0 .. gk.len do\n store packA[a0, a1] = load a[gi[a0], gk[a1]]\n lease mut packA_L2 = packA at L2\n ... // update C from packA_L2 and packB_L1\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>... // zero C\nfor gk in blocks (0 .. K) 16 do\n for gj in blocks (0 .. N) 8 do\n ... // pack B and keep it at L1\n for gi in blocks (0 .. M) 16 do\n ... // pack A and keep it at L2\n for ui in blocks (0 .. gi.len) 4 do\n var acc'0: [Vec f32 8; 4] = ...\n ... // load the current totals from C into acc'0\n for k in 0 .. gk.len do\n let lanes: Vec f32 8 = load packB_L1[...] ...\n for i in 0 .. ui.len do\n let row: Vec f32 8 = splat (load packA_L2[...])\n acc'0[i] = fma row lanes acc'0[i]\n ... // store acc'0 back to C\u003c/code>\u003c/pre>\n\u003cp>The generic contraction, and the loop nest it means. Each output adds up its products in ascending order of k.\u003c/p>\n\u003cp>\u003cstrong>1.17 GFLOP/s\u003c/strong> · 1,843.33 ms1.1% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>Every cell is zeroed first, and its sum then starts from what the cell holds.\u003c/p>\n\u003cp>\u003cstrong>1.17 GFLOP/s\u003c/strong> · 1,836.16 ms1.1% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>The sum runs in blocks of at most 16 steps, gk, each continuing from what the cell holds. As in the earlier chunking example, each output keeps one running total and receives the same products in the same order.\u003c/p>\n\u003cp>\u003cstrong>1.5 GFLOP/s\u003c/strong> · 1,428.42 ms1.4% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>The rows are cut into blocks of 16, gi, and each block into groups of four rows, ui. i now picks a row within those four.\u003c/p>\n\u003cp>\u003cstrong>1.49 GFLOP/s\u003c/strong> · 1,440.12 ms1.4% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>The columns are cut into blocks of 8, gj, and j picks a column within a block.\u003c/p>\n\u003cp>\u003cstrong>1.48 GFLOP/s\u003c/strong> · 1,447.36 ms1.4% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>order\u003c/code> puts the depth blocks outside the output loops. Within each depth block, it visits 16 × 8 output blocks, the blocks of columns outside the blocks of rows. Each output continues from its previous total, receiving the same products in the same order.\u003c/p>\n\u003cp>\u003cstrong>27 GFLOP/s\u003c/strong> · 79.35 ms25% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>tower: bits of matmul\u003c/code>\u003c/p>\n\u003cp>\u003ccode>pack\u003c/code> copies the block of A that the loops gi and gk pick out into a scratch buffer, packA, which becomes a parameter. The kernel reads the copy instead of a.\u003c/p>\n\u003cp>\u003cstrong>39 GFLOP/s\u003c/strong> · 55.58 ms36% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>keep\u003c/code> says that packA stays in L2 while it's used, and adds that to the function's working set.\u003c/p>\n\u003cp>\u003cstrong>39 GFLOP/s\u003c/strong> · 55.5 ms36% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>pack\u003c/code> copies the block of B into packB, which becomes another parameter of the kernel.\u003c/p>\n\u003cp>\u003cstrong>37 GFLOP/s\u003c/strong> · 58.63 ms34% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>keep\u003c/code> records that packB is to stay in L1 while it is used.\u003c/p>\n\u003cp>\u003cstrong>37 GFLOP/s\u003c/strong> · 58.55 ms34% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>registers\u003c/code> holds a 4 × 8 block of c across the depth loop: four rows of two four-lane vectors, updated with vector \u003ccode>fma\u003c/code>. This ties the schedule to \u003ccode>PlusTimes f32\u003c/code>.\u003c/p>\n\u003cp>\u003cstrong>49 GFLOP/s\u003c/strong> · 44.21 ms45% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>packed: bits of matmul_PlusTimes_f32\u003c/code>\u003c/p>\n\u003cp>Each cell’s running total still carries on from one depth block to the next, so no addition is regrouped. Each step has to prove that it preserves the result, for every size of matrix. It doesn’t need to know how \u003ccode>S\u003c/code> implements its operations: before and after the rewrite, each output applies the same operations to the same values in the same order. So \u003ccode>tower\u003c/code> works for any \u003ccode>S\u003c/code>.\u003c/p>\n\u003cp>\u003ccode>tower\u003c/code> is actually slower than \u003ccode>swapped\u003c/code>. Splitting the loops into blocks hasn’t given us a fast inner kernel yet.\u003c/p>\n\u003cp>The first \u003ccode>pack\u003c/code> step in the figure starts a new schedule, \u003ccode>packed\u003c/code>, which continues where \u003ccode>tower\u003c/code> left off. Two \u003ccode>pack\u003c/code> steps copy blocks of A and B into temporary buffers, arranging the values for the kernel to read. These buffers become parameters of \u003ccode>packed\u003c/code>, and two \u003ccode>keep\u003c/code> steps say which cache each buffer should stay in.\u003c/p>\n\u003cp>The last step, \u003ccode>registers (i, j) into c rows 4 lanes 8 through fma\u003c/code>, holds a 4 × 8 block of C in vector registers across the depth loop. A vector instruction operates on several values at once; here, its multiply-add updates four \u003ccode>f32\u003c/code> values. This ties the schedule to the machine’s vector registers, so we bind \u003ccode>S\u003c/code> to \u003ccode>PlusTimes f32\u003c/code>.\u003c/p>\n\u003cp>The figure writes out every step, but \u003ccode>tower\u003c/code> and \u003ccode>packed\u003c/code> share their first five. We can give those steps a name with \u003ccode>schedule fn\u003c/code>, and make the block sizes parameters:\u003c/p>\n\u003cpre>\u003ccode>cachetschedule fn block_product (i, j, k) c (MC, MR, NC, KC) =\n zero (i, j) c\n split k by KC as gk ragged\n split i by MC as gi, MR as ui ragged\n split j by NC as gj ragged\n order (gk, gj, gi, ui, i, j)\n\nschedule tower of matmul =\n block_product (i, j, k) c (16, 4, 8, 16)\n\nschedule packed of matmul @(S = PlusTimes f32)\n (mut packA: [f32; 16, 16] in PanelMajor 4 at DRAM)\n (mut packB: [f32; 16, 8] at DRAM) =\n block_product (i, j, k) c (16, 4, 8, 16)\n pack a into packA along gi over (a0, a1)\n keep packA along gi within L2 into packA_L2\n pack b into packB along gj over (b0, b1)\n keep packB along gj within L1 into packB_L1\n registers (i, j) into c rows 4 lanes 8 through fma\u003c/code>\u003c/pre>\n\u003cp>\u003ccode>(i, j, k) c\u003c/code> names the indices and output to rewrite, as in \u003ccode>hoist\u003c/code>. \u003ccode>MC\u003c/code> and \u003ccode>MR\u003c/code> choose the outer and inner row block sizes, \u003ccode>NC\u003c/code> the column block size, and \u003ccode>KC\u003c/code> the depth. Both schedules pass the same sizes; \u003ccode>packed\u003c/code> then adds the steps below the call.\u003c/p>\n\u003cp>The call to \u003ccode>block_product\u003c/code> expands into its steps when the compiler reads the schedule. The following steps can keep working on the loops it produces: \u003ccode>pack\u003c/code> copies their inputs, \u003ccode>keep\u003c/code> records their cache requirements, and \u003ccode>registers\u003c/code> holds their running totals in registers. There’s no function call left in the kernel.\u003c/p>\n\u003cp>Schedule functions can call other schedule functions too, so we can build up an optimisation from smaller ones. Each rewrite is checked against the program left by the preceding steps, including those from a helper. The checks compose along with the transformations: if every step preserves the result under its stated conditions, the whole sequence does too.\u003c/p>\n\u003cp>\u003ccode>PanelMajor 4\u003c/code> lays out A in groups of four rows, putting the four values from each column in consecutive memory. The inner kernel reads four values at each depth step, and this layout keeps them together. B’s buffer keeps the ordinary row-major layout, so its eight values from that step are contiguous too. We still write \u003ccode>packA[i, k]\u003c/code>; only the address it refers to changes.\u003c/p>\n\u003cp>The scratch buffers live in main memory (\u003ccode>DRAM\u003c/code>); \u003ccode>keep\u003c/code> names the cache views the kernel will read. The cache requirements appear in the generated function’s declaration:\u003c/p>\n\u003cpre>\u003ccode>cachetscratch packA, packB\nworking_set\n @L1 { keep packB = descriptor packB }\n @L2 { keep packA = descriptor packA }\u003c/code>\u003c/pre>\n\u003cp>\u003ccode>scratch\u003c/code> requires the kernel to write to each buffer location before reading it. The caller therefore doesn’t need to clear the buffers first. The \u003ccode>working_set\u003c/code> rows say which buffer stays in which cache, and a caller of \u003ccode>packed\u003c/code> has to show that they fit. The \u003ca href=\"#panel-blocking\">memory hierarchy panel\u003c/a> shows where the buffers live. The block sizes are deliberately small here.\u003c/p>\n\u003ch2 id=\"making-it-fast\">Making it fast\u003c/h2>\n\u003cp>\u003ccode>packed\u003c/code> multiplies two 1024 × 1024 matrices at 47 GFLOP/s. OpenBLAS reaches 108 on the same core with the same vector instructions.\u003c/p>\n\u003ch3 id=\"how-much-data-are-we-moving\">How much data are we moving?\u003c/h3>\n\u003cp>Copying the inputs is extra work. We expect it to pay off because the kernel can then read them repeatedly from cache, without going back to main memory. But how much copying have we actually asked for?\u003c/p>\n\u003cp>The compiler keeps an account of what each function does, and \u003ccode>cachetc account\u003c/code> prints it, one operation at a time. Here is \u003ccode>packed\u003c/code>’s, shortened:\u003c/p>\n\u003cpre>\u003ccode>packed\n operations\n loop host x 1\n writes c 4 * M * N\n loop host x ceil (K / 16) * ceil (N / 8)\n reads b 512; writes packB 512\n loop host x ceil (K / 16) * ceil (M / 16) * ceil (N / 8)\n reads a 1024; writes packA 1024\n loop host x ceil (K / 16) * ceil (M / 16) * ceil (N / 8)\n reads c 512, packA_L2 1024, packB_L1 2048; writes c 512; work fma 2048, ...\u003c/code>\u003c/pre>\n\u003cp>The number after each \u003ccode>x\u003c/code> says how many times that operation runs. The first row zeroes \u003ccode>c\u003c/code>, all \u003ccode>4 * M * N\u003c/code> bytes of it. The next two copy a 16 × 8 block of B and a 16 × 16 block of A into their buffers. \u003ccode>reads\u003c/code> and \u003ccode>writes\u003c/code> count bytes; \u003ccode>work fma\u003c/code> counts multiply-adds.\u003c/p>\n\u003cp>The last row is the computation on one block: it reads packed A from L2 and packed B from L1, then performs 2,048 multiply-adds. The repetition counts use M, N and K, so we can see how the work grows with the matrices.\u003c/p>\n\u003cp>The generated function also declares bounds on this traffic, next to the \u003ccode>working_set\u003c/code> we saw above. These rows count the cache lines moved by each pack:\u003c/p>\n\u003cpre>\u003ccode>cachetmovement\n traffic packB_pull = ceil (K / 16) * ceil (N / 8) *\n lines (span_bytes packB.span) from DRAM to L1 and back\n traffic packA_pull = ceil (K / 16) * ceil (N / 8) * ceil (M / 16) *\n lines (span_bytes packA.span) from DRAM to L2 and back\u003c/code>\u003c/pre>\n\u003cp>A caller can put a limit on this traffic too. For two 32 × 32 matrices, the loop order above packs A once for each combination of a depth block, a column block and a row block: 2 × 4 × 2 = 16 packs. If the caller allows only eight, the call is refused. We have to change the schedule or allow the extra traffic. The \u003ca href=\"#panel-traffic-budget\">full example and refusal\u003c/a> show how the caller writes this budget.\u003c/p>\n\u003cp>The account is exact within the platform file’s model of the caches, but it knows nothing about prefetchers, replacement policies, or another process sharing the cache. Whether reducing these counts makes the kernel faster still has to be measured.\u003c/p>\n\u003ch3 id=\"tuning-the-kernel\">Tuning the kernel\u003c/h3>\n\u003cp>Our blocks are small enough to read, but far smaller than the caches they’re kept in. The obvious next step is to make them larger:\u003c/p>\n\u003cpre>\u003ccode>schedule packed of matmul @(S = PlusTimes f32)\n (mut packA: [f32; 16, 16] in PanelMajor 4 at DRAM)\n (mut packB: [f32; 16, 8] at DRAM) =\n ...\n keep packB along gj within L1 into packB_L1\n registers (i, j) into c rows 4 lanes 8 through fma\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>schedule larger of matmul @(S = PlusTimes f32)\n (mut packA: [f32; 512, 256] in PanelMajor 4 at DRAM)\n (mut packB: [f32; 256, 8] at DRAM) =\n ...\n keep packB along gj within L1 into packB_L1\n registers (i, j) into c rows 4 lanes 8 through fma\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>schedule rows_first of matmul @(S = PlusTimes f32)\n (mut packA: [f32; 512, 256] in PanelMajor 4 at DRAM)\n (mut packB: [f32; 256, 8] at DRAM) =\n ...\n keep packB along gj within L1 into packB_L1\n registers (i, j) into c rows 4 lanes 8 through fma\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>schedule fast of matmul @(S = PlusTimes f32)\n (mut packA: [f32; 512, 256] in PanelMajor 4 at DRAM)\n (mut packB: [f32; 256, 16] at DRAM) =\n ...\n keep packB along gj within L1 into packB_L1\n registers (i, j) into c rows 4 lanes 16 through fma\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 16 do\n for gj in blocks (0 .. N) 8 do\n ... // pack B and keep it at L1\n for gi in blocks (0 .. M) 16 do\n ... // pack A and keep it at L2\n for ui in blocks (0 .. gi.len) 4 do\n var acc'0: [Vec f32 8; 4] = ...\n ... // load C, accumulate across k, and store C\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 256 do\n for gj in blocks (0 .. N) 8 do\n ... // pack B and keep it at L1\n for gi in blocks (0 .. M) 512 do\n ... // pack A and keep it at L2\n for ui in blocks (0 .. gi.len) 4 do\n var acc'0: [Vec f32 8; 4] = ...\n ... // load C, accumulate across k, and store C\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 256 do\n for gi in blocks (0 .. M) 512 do\n ... // pack A and keep it at L2\n for gj in blocks (0 .. N) 8 do\n ... // pack B and keep it at L1\n for ui in blocks (0 .. gi.len) 4 do\n var acc'0: [Vec f32 8; 4] = ...\n ... // load C, accumulate across k, and store C\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 256 do\n for gi in blocks (0 .. M) 512 do\n ... // pack A and keep it at L2\n for gj in blocks (0 .. N) 16 do\n ... // pack B and keep it at L1\n for ui in blocks (0 .. gi.len) 4 do\n var acc'0: [Vec f32 16; 4] = ...\n ... // load C, accumulate across k, and store C\u003c/code>\u003c/pre>\n\u003cp>\u003ccode>packed\u003c/code> as we left it: blocks of 16 rows, 8 columns and 16 steps of depth, and a 4 × 8 register tile.\u003c/p>\n\u003cp>\u003cstrong>47 GFLOP/s\u003c/strong> · 45.39 ms44% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>packed: bits of matmul_PlusTimes_f32\u003c/code>\u003c/p>\n\u003cp>A's blocks grow to 512 rows by 256 columns, half a megabyte each, kept in L2, and A is copied four rows at a time. B's grow to 256 by 8, kept in L1. The loop order is unchanged.\u003c/p>\n\u003cp>\u003cstrong>48 GFLOP/s\u003c/strong> · 44.73 ms44% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>larger: bits of matmul_PlusTimes_f32\u003c/code>\u003c/p>\n\u003cp>\u003ccode>order\u003c/code> now puts the blocks of rows, gi, outside the blocks of columns, gj, so each panel of A is packed once per depth block and then used with every panel of B.\u003c/p>\n\u003cp>\u003cstrong>66 GFLOP/s\u003c/strong> · 32.79 ms61% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>rows_first: bits of matmul_PlusTimes_f32\u003c/code>\u003c/p>\n\u003cp>The register tile is 4 × 16: four rows of four vectors, giving us sixteen independent chains. The columns are blocked by 16 to match, and so are B's panels.\u003c/p>\n\u003cp>\u003cstrong>116 GFLOP/s\u003c/strong> · 18.56 ms107% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · one core · 108 GFLOP/s\u003c/p>\n\u003cp>CPU · 1024 × 1024 · f32\u003c/p>\n\u003cp>\u003ccode>fast: bits of matmul_PlusTimes_f32\u003c/code>\u003c/p>\n\u003cp>The first step, \u003cstrong>Larger blocks\u003c/strong>, mostly changes sizes. The blocks of A are now 512 rows by 256 columns, half a megabyte, kept in L2, and the blocks of B are 256 by 8, kept in L1. These tall rectangular blocks are often called \u003cem>panels\u003c/em>. Surprisingly, it’s barely faster: 48 GFLOP/s. (The correctness proof is perfectly happy with this.)\u003c/p>\n\u003cp>The traffic account shows a lot of repeated copying. The factor \u003ccode>ceil (N / 8)\u003c/code> in A’s traffic row comes from \u003ccode>gj\u003c/code>, which is still outside \u003ccode>gi\u003c/code>: we pack each panel of A again for every panel of B. At 1024 × 1024, that’s 1,024 copies of half a megabyte for one multiplication. A \u003ca href=\"#panel-traffic-budget\">traffic contract\u003c/a> written for these sizes can refuse this order.\u003c/p>\n\u003cp>\u003cstrong>Rows first\u003c/strong> puts \u003ccode>gi\u003c/code> before \u003ccode>gj\u003c/code> in the \u003ccode>order\u003c/code>, so the rows are outside the columns, and the factor \u003ccode>ceil (N / 8)\u003c/code> moves to B’s row, whose panels are 64 times smaller. That gets us to 66 GFLOP/s.\u003c/p>\n\u003cp>That’s still only about 61% of OpenBLAS. Another problem is that we’re waiting for our own results. A vector \u003ccode>fma\u003c/code> on the M4 Max takes four cycles before its result can be used by the next \u003ccode>fma\u003c/code> in the same chain. The core can start four independent vector \u003ccode>fma\u003c/code>s per cycle, so it needs 16 independent chains to keep doing that while earlier results are on their way.\u003c/p>\n\u003cp>Each vector holds four \u003ccode>f32\u003c/code> values, so our 4 × 8 tile occupies only eight vectors. After updating those eight, we have to wait before we can update them again. Widening the tile gives the core more independent totals to work on in the meantime:\u003c/p>\n\u003cp>Keeping the vector units busy\u003c/p>\n\u003cp>Eight vectors give us two cycles of work, then two cycles waiting for the first results. Widening the tile gives us more independent totals to update in the meantime.\u003c/p>\n\u003cp>A repeating four-cycle window, slowed down. This isolates the dependency between updates; loads and other instructions are omitted.\u003c/p>\n\u003cp>The platform file gives the number of values per vector as \u003ccode>lanes\u003c/code>, the number of \u003ccode>fma\u003c/code>s it can start per cycle as \u003ccode>fma_pipes\u003c/code>, and the delay before using a result as \u003ccode>fma_latency\u003c/code>. We can use them to write a requirement next to the schedule, whose last step becomes \u003ccode>registers (i, j) into c rows MR lanes NR through fma\u003c/code>:\u003c/p>\n\u003cpre>\u003ccode>cachetconst MR : Nat = 4\nconst NR : Nat = 8\n\nproof enough_chains =\n assert MR * ceil (NR / platform.lanes @Vec @f32) >=\n platform.fma_pipes @Vec * platform.fma_latency @Vec\u003c/code>\u003c/pre>\n\u003cp>With a 4 × 8 tile, it’s refused:\u003c/p>\n\u003cpre>\u003ccode>could not prove proof enough_chains: MR * ceil (NR / platform.lanes Vec f32) >= platform.fma_pipes @Vec * platform.fma_latency @Vec\u003c/code>\u003c/pre>\n\u003cp>A reader who has been counting independent chains will already know what to try: \u003ccode>NR = 16\u003c/code>. Each of the four rows now occupies four vectors, giving us sixteen independent chains, and the proof goes through. \u003ccode>fast\u003c/code> now runs at 116 GFLOP/s, as fast as OpenBLAS:\u003c/p>\n\u003cp>What each change adds on one core\u003c/p>\n\u003cp>The wider tile brings \u003ccode>fast\u003c/code> to about OpenBLAS's speed, and about 2.4 times the speed of \u003ccode>packed\u003c/code>.\u003c/p>\n\u003cp>\u003cstrong>CPU · one core\u003c/strong>1024 × 1024 · f32 · NEON vectors\u003c/p>\n\u003cdiv class=\"table-wrap\">\u003ctable>\u003cthead>\u003ctr>\u003cth>Tuning step\u003c/th>\u003cth>Speed relative to the library0100%\u003c/th>\u003cth>GFLOP/s\u003c/th>\u003cth>Library speed\u003c/th>\u003c/tr>\u003c/thead>\u003ctbody>\u003ctr>\u003ctd>\u003ccode>packed\u003c/code>Starting schedule\u003c/td>\u003ctd>\u003c/td>\u003ctd>47\u003c/td>\u003ctd>44%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>Larger blocksUse more of the caches\u003c/td>\u003ctd>\u003c/td>\u003ctd>48\u003c/td>\u003ctd>44%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>Rows firstRepack the smaller panels\u003c/td>\u003ctd>\u003c/td>\u003ctd>66\u003c/td>\u003ctd>61%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>A wider tile4 × 16 outputs · fast\u003c/td>\u003ctd>\u003c/td>\u003ctd>116\u003c/td>\u003ctd>107%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>OpenBLASNEON kernels\u003c/td>\u003ctd>\u003c/td>\u003ctd>108\u003c/td>\u003ctd>100%\u003c/td>\u003c/tr>\u003c/tbody>\u003c/table>\u003c/div>\n\u003cp>GFLOP/s, higher is better. The dashed line marks OpenBLAS's speed in this run. Every version produces exactly the same result as \u003ccode>matmul\u003c/code>. These tuning steps were measured together, in a separate run from the overview below.\u003c/p>\n\u003cp>\u003ccode>fast\u003c/code> still produces exactly the same result as \u003ccode>matmul\u003c/code>. If someone later narrows the tile to save registers, the \u003ccode>enough_chains\u003c/code> check fails, pointing out the dependency we’d reintroduce. This check relies on the platform file’s numbers: Apple doesn’t publish the latency or throughput, so the file uses published measurements.\u003c/p>\n\u003cp>We could also have asked Cachet to find that width. With \u003ccode>MR\u003c/code> still fixed at four, we can replace \u003ccode>const NR : Nat = 16\u003c/code> with:\u003c/p>\n\u003cpre>\u003ccode>cachetsynth const NR : Nat =\n minimize n in (n): n where\n n > 0, n <= 64,\n n % platform.lanes @Vec @f32 == 0,\n MR * ceil (n / platform.lanes @Vec @f32) >=\n platform.fma_pipes @Vec * platform.fma_latency @Vec\u003c/code>\u003c/pre>\n\u003cp>This asks for the smallest width from 1 to 64 that fills whole vectors and supplies enough independent chains. For the platform above, that is 16. So the condition that refused our 4 × 8 tile can also pick the width for us. \u003ccode>synth const\u003c/code> chooses the number at compile time, and the rest of the schedule is checked with that number in place, just as if we’d written it ourselves.\u003c/p>\n\u003cp>Several parameters can be chosen together too, and the candidates ranked by a cost expression, such as the estimated load cost per multiply-add. We’d still benchmark the promising candidates: a low cost in the model needn’t mean a short running time.\u003c/p>\n\u003ch3 id=\"using-the-other-cores\">Using the other cores\u003c/h3>\n\u003cp>We now have a fast kernel for one core. To use the other cores, we can divide the output rows between them. In \u003ccode>bands\u003c/code>, \u003ccode>parallel gi\u003c/code> turns the loop over blocks of 64 rows into a \u003cem>grid\u003c/em> of independent iterations. It runs on the host, so CPU threads take the bands of rows.\u003c/p>\n\u003cp>Each iteration has a \u003cem>write window\u003c/em>: the part of the output it’s allowed to update. The compiler infers this from the rows it stores, and checks that the windows don’t overlap. Threads can read the same inputs, but can’t write each other’s outputs.\u003c/p>\n\u003cp>\u003ccode>parallel\u003c/code> is a library step too, and it’s short enough to show in full:\u003c/p>\n\u003cpre>\u003ccode>cachetstep fn parallel t =\n from\n for t in $lo .. $hi do\n $body\n to\n grid t in $lo .. $hi do\n $body\u003c/code>\u003c/pre>\n\u003cp>There’s no \u003ccode>relate\u003c/code> proof recipe this time. The grid it produces has to prove its windows don’t overlap anyway.\u003c/p>\n\u003cp>The threads share the packed inputs: A is packed once per block of depth, for every row, and B is packed in groups of 16 columns and kept in L2:\u003c/p>\n\u003cpre>\u003ccode>cachetschedule bands of matmul @(S = PlusTimes f32)\n (mut packA: [f32; M, 256] in PanelMajor 4)\n (mut packB: [f32; 256, 1024] in ColumnPanels 16 at DRAM) =\n zero (i, j) c\n\n // Block and reorder the loops.\n split k by 256 as gk ragged\n split j by 1024 as gj, 16 as uj ragged\n split i by 64 as gi, 4 as ui\n order (gk, gj, gi, ui, uj, i, j)\n\n // Give each CPU thread a band of output rows.\n parallel gi\n\n // Pack the inputs for reuse across the output bands.\n pack a into packA along gk over (a0, a1)\n strip a0 4 (pa, ra)\n interchange (ra, a1)\n parallel pa\n\n pack_lanes b into packB along gj over (b0, b1, bt) lanes 16\n keep packB along gj within L2 into packB_L2\n parallel b0\n\n // Accumulate a 4 × 16 output block in vector registers.\n registers (i, j) into c rows 4 lanes 16 through fma\u003c/code>\u003c/pre>\n\u003cp>\u003cstrong>757 GFLOP/s\u003c/strong> · 2.84 ms88% of OpenBLAS's speed\u003c/p>\n\u003cp>100% = OpenBLAS · CPU · all cores · 863 GFLOP/s\u003c/p>\n\u003cp>CPU · all cores · 1024 × 1024 · f32\u003c/p>\n\u003cp>The packing loops are parallel too. \u003ccode>strip a0 4 (pa, ra)\u003c/code> divides A’s rows into groups of four, with \u003ccode>pa\u003c/code> selecting a group and \u003ccode>ra\u003c/code> a row within it. \u003ccode>interchange (ra, a1)\u003c/code> moves the column loop outside those four rows, so the copy writes neighbouring values in \u003ccode>PanelMajor 4\u003c/code> order. \u003ccode>parallel pa\u003c/code> lets separate threads pack separate groups.\u003c/p>\n\u003cp>For B, \u003ccode>ColumnPanels 16\u003c/code> stores groups of 16 columns, with each group’s rows one after another. \u003ccode>pack_lanes\u003c/code> copies 16 values at a time into that layout, and \u003ccode>parallel b0\u003c/code> distributes the rows. On NEON, 16 \u003ccode>f32\u003c/code> values fit in four vectors.\u003c/p>\n\u003cp>On all cores, \u003ccode>bands\u003c/code> reaches 757 GFLOP/s, where OpenBLAS reaches 863. No sum is split between threads, only rows, so the result is still identical to \u003ccode>matmul\u003c/code>’s.\u003c/p>\n\u003ch3 id=\"cpu-matrix-units\">CPU matrix units\u003c/h3>\n\u003cp>\u003ccode>fast\u003c/code> and \u003ccode>bands\u003c/code> use NEON, the CPU’s vector instructions. The M4 also has a \u003ca href=\"#panel-matrix-units\">matrix unit\u003c/a>, accessed through SME, Arm’s Scalable Matrix Extension. We can use it for \u003ccode>f64\u003c/code> by choosing another multiply-add, \u003ccode>outer_fma_primitive\u003c/code>, which updates 8 × 8 blocks with \u003cem>outer products\u003c/em>. An outer product multiplies each of eight values from A by each of eight values from B, contributing one product to each of the block’s 64 totals. \u003ccode>sme\u003c/code> holds a 32 × 16 tile of C as eight such blocks, and lays out the rest of the work for the M4 Max’s two matrix units, one in each cluster of performance cores:\u003c/p>\n\u003cpre>\u003ccode>schedule sme of matmul @(S = PlusTimes f64)\n (mut packA: [f64; M, 3072] in PanelMajor 32)\n (mut packB: [f64; 3072, 256] in ColumnPanels 16 at DRAM) =\n ...\n split k by 3072 as gk ragged\n split j by 256 as gj, 16 as uj\n ...\n split i by 1536 as gi, 32 as ui\n ...\n order (gk, gj, gi, ui, uj, i, j)\n ...\n parallel gi\n ...\n pack a into packA along gk over (a0, a1)\n ...\n strip a0 32 (pa, ra)\n ...\n parallel pa\n ...\n pack b into packB along gj over (b0, b1)\n ...\n strip b1 16 (pb, rb)\n ...\n interchange (b0, pb)\n ...\n parallel pb\n ...\n registers (i, j) into c rows 32 lanes 16 through fma\n ...\n outer_products i c 8 8 outer_fma_primitive\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for i in 0 .. M do\n for j in 0 .. N do\n var acc'0: f64 = -0.0\n for k in 0 .. K do\n acc'0 = fma ... acc'0\n store c[i, j] = acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for i in 0 .. M do\n for j in 0 .. N do\n for gk in blocks (0 .. K) 3072 do\n var acc'0: f64 = if gk.lo == 0 then -0.0 else load c[i, j]\n for k in 0 .. gk.len do\n acc'0 = fma ... acc'0\n store c[i, j] = acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for i in 0 .. M do\n for gj in 0 .. N / 256 do\n for uj in blocks (0 .. 256) 16 do\n for j in 0 .. uj.len do\n for gk in blocks (0 .. K) 3072 do\n var acc'0: f64 = if gk.lo == 0 then -0.0 else load c[...]\n for k in 0 .. gk.len do\n acc'0 = fma ... acc'0\n store c[...] = acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gi in 0 .. M / 1536 do\n for ui in blocks (0 .. 1536) 32 do\n for i in 0 .. ui.len do\n for gj in 0 .. N / 256 do\n for uj in blocks (0 .. 256) 16 do\n for j in 0 .. uj.len do\n for gk in blocks (0 .. K) 3072 do\n var acc'0: f64 = if gk.lo == 0 then -0.0 else load c[...]\n for k in 0 .. gk.len do\n acc'0 = fma ... acc'0\n store c[...] = acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 3072 do\n for gj in 0 .. N / 256 do\n for gi in 0 .. M / 1536 do\n for ui in blocks (0 .. 1536) 32 do\n for uj in blocks (0 .. 256) 16 do\n for i in 0 .. ui.len do\n for j in 0 .. uj.len do\n var acc'0: f64 = if gk.lo == 0 then -0.0 else load c[...]\n for k in 0 .. gk.len do\n acc'0 = fma ... acc'0\n store c[...] = acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 3072 do\n for gj in 0 .. N / 256 do\n grid gi in 0 .. M / 1536\n writes c[...] do\n for ui in blocks (0 .. 1536) 32 do\n for uj in blocks (0 .. 256) 16 do\n for i in 0 .. ui.len do\n for j in 0 .. uj.len do\n var acc'0: f64 = if gk.lo == 0 then -0.0 else load c[...]\n for k in 0 .. gk.len do\n acc'0 = fma ... acc'0\n store c[...] = acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 3072 do\n for a0 in 0 .. M do\n for a1 in 0 .. gk.len do\n store packA[a0, a1] = load a[a0, gk[a1]]\n for gj in 0 .. N / 256 do\n grid gi in 0 .. M / 1536\n writes c[...] do\n ... // update C from packA and B\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 3072 do\n for pa in 0 .. M / 32 do\n for ra in 0 .. 32 do\n for a1 in 0 .. gk.len do\n store packA[0 + pa * 32 + ra, a1] = load a[...]\n for gj in 0 .. N / 256 do\n grid gi in 0 .. M / 1536\n writes c[...] do\n ... // update C from packA and B\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 3072 do\n grid pa in 0 .. M / 32 writes packA[...] do\n for ra in 0 .. 32 do\n for a1 in 0 .. gk.len do\n store packA[0 + pa * 32 + ra, a1] = load a[...]\n for gj in 0 .. N / 256 do\n grid gi in 0 .. M / 1536\n writes c[...] do\n ... // update C from packA and B\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 3072 do\n grid pa in 0 .. M / 32 writes packA[...] do\n ... // pack A\n for gj in 0 .. N / 256 do\n for b0 in 0 .. gk.len do\n for b1 in 0 .. 256 do\n store packB[b0, b1] = load b[gk[b0], gj * 256 + b1]\n grid gi in 0 .. M / 1536\n writes c[...] do\n ... // update C from packA and packB\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 3072 do\n grid pa in 0 .. M / 32 writes packA[...] do\n ... // pack A\n for gj in 0 .. N / 256 do\n for b0 in 0 .. gk.len do\n for pb in 0 .. 256 / 16 do\n for rb in 0 .. 16 do\n store packB[b0, 0 + pb * 16 + rb] = load b[...]\n grid gi in 0 .. M / 1536\n writes c[...] do\n ... // update C from packA and packB\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 3072 do\n grid pa in 0 .. M / 32 writes packA[...] do\n ... // pack A\n for gj in 0 .. N / 256 do\n for pb in 0 .. 16 do\n for b0 in 0 .. gk.len do\n for rb in 0 .. 16 do\n store packB[b0, 0 + pb * 16 + rb] = load b[...]\n grid gi in 0 .. M / 1536\n writes c[...] do\n ... // update C from packA and packB\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for gk in blocks (0 .. K) 3072 do\n grid pa in 0 .. M / 32 writes packA[...] do\n ... // pack A\n for gj in 0 .. N / 256 do\n grid pb in 0 .. 16 writes packB[...] do\n for b0 in 0 .. gk.len do\n for rb in 0 .. 16 do\n store packB[b0, 0 + pb * 16 + rb] = load b[...]\n grid gi in 0 .. M / 1536\n writes c[...] do\n ... // update C from packA and packB\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>... // pack inputs, and distribute the output bands\nfor ui in blocks (0 .. 1536) 32 do\n for uj in blocks (0 .. 256) 16 do\n var acc'0: [Vec f64 16; 32] = ...\n ... // the 32 × 16 output tile: −0.0 on the first block, else c's\n for k in 0 .. gk.len do\n let lanes: Vec f64 16 = ...\n for i in 0 .. ui.len do\n let row: Vec f64 16 = ...\n acc'0[i] = fma row lanes acc'0[i]\n ... // store the output tile\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>... // pack inputs, and distribute the output bands\nfor ui in blocks (0 .. 1536) 32 do\n for uj in blocks (0 .. 256) 16 do\n var blocks_2: [Vec f64 (8 * 8); 4 * 2] = ...\n ... // the same tile as eight 8 × 8 blocks: −0.0, else c's\n for k in 0 .. gk.len do\n ... // row and column masks\n let column_all: Vec f64 32 = load packA[...]\n let row_all: Vec f64 16 = load packB[...]\n for q in 0 .. ui.len / 8 * 2 do\n let column = slice_lanes column_all (floor (q / 2) * 8)\n let row = slice_lanes row_all (q % 2 * 8)\n blocks_2[q] =\n outer_fma_primitive column row blocks_2[q] rows cols\n ... // store the eight blocks\u003c/code>\u003c/pre>\n\u003cp>The same contraction as before.\u003c/p>\n\u003cp>\u003cstrong>0.83 GFLOP/s\u003c/strong> · 69,476.69 ms<0.1% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · 3072 × 3072 · f64\u003c/p>\n\u003cp>The sum is split into blocks of up to 3072 steps, gk. The first starts each running total at −0.0; later blocks continue from the value stored in c. At 3072 × 3072, one block covers the whole sum, so c is only written, never cleared or read.\u003c/p>\n\u003cp>\u003cstrong>0.93 GFLOP/s\u003c/strong> · 62,386.23 ms0.1% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · 3072 × 3072 · f64\u003c/p>\n\u003cp>The columns are cut into blocks of 256, gj, one packed block of B each, and each block into groups of 16, uj.\u003c/p>\n\u003cp>\u003cstrong>0.94 GFLOP/s\u003c/strong> · 61,876.99 ms0.1% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · 3072 × 3072 · f64\u003c/p>\n\u003cp>The rows are cut into bands of 1536, gi, each visited 32 rows at a time, ui. At 3072 × 3072 that's two bands, one for each of the M4 Max's two performance clusters, each with its own matrix unit.\u003c/p>\n\u003cp>\u003cstrong>0.92 GFLOP/s\u003c/strong> · 63,067.5 ms0.1% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · 3072 × 3072 · f64\u003c/p>\n\u003cp>\u003ccode>order\u003c/code> puts the depth blocks first, then the blocks of columns and the bands of rows. Within a band, uj runs inside ui, so we visit the tiles across the same 32 rows of c before moving down to the next 32.\u003c/p>\n\u003cp>\u003cstrong>1.19 GFLOP/s\u003c/strong> · 48,650.12 ms0.1% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · 3072 × 3072 · f64\u003c/p>\n\u003cp>The bands run as a grid on the host, one thread each.\u003c/p>\n\u003cp>\u003cstrong>2.01 GFLOP/s\u003c/strong> · 28,797.85 ms0.2% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · parallel · 3072 × 3072 · f64\u003c/p>\n\u003cp>\u003ccode>pack\u003c/code> copies each depth block of A into packA, for every row.\u003c/p>\n\u003cp>\u003cstrong>1.76 GFLOP/s\u003c/strong> · 32,895.09 ms0.2% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · parallel · 3072 × 3072 · f64\u003c/p>\n\u003cp>\u003ccode>strip\u003c/code> divides A's copying loop into panels of 32 rows.\u003c/p>\n\u003cp>\u003cstrong>1.75 GFLOP/s\u003c/strong> · 33,041.84 ms0.2% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · parallel · 3072 × 3072 · f64\u003c/p>\n\u003cp>The panels of A are copied in parallel.\u003c/p>\n\u003cp>\u003cstrong>1.71 GFLOP/s\u003c/strong> · 33,919.67 ms0.2% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · parallel · 3072 × 3072 · f64\u003c/p>\n\u003cp>\u003ccode>pack\u003c/code> copies each block of B into packB.\u003c/p>\n\u003cp>\u003cstrong>3.83 GFLOP/s\u003c/strong> · 15,138.54 ms0.4% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · parallel · 3072 × 3072 · f64\u003c/p>\n\u003cp>\u003ccode>strip\u003c/code> divides B's columns into panels of 16.\u003c/p>\n\u003cp>\u003cstrong>3.86 GFLOP/s\u003c/strong> · 15,035.36 ms0.4% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · parallel · 3072 × 3072 · f64\u003c/p>\n\u003cp>\u003ccode>interchange\u003c/code> moves the panel loop, pb, outside the row loop, b0, so the copy visits one panel at a time.\u003c/p>\n\u003cp>\u003cstrong>3.92 GFLOP/s\u003c/strong> · 14,800.12 ms0.5% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · parallel · 3072 × 3072 · f64\u003c/p>\n\u003cp>The panels of B are copied in parallel.\u003c/p>\n\u003cp>\u003cstrong>3.87 GFLOP/s\u003c/strong> · 14,984.23 ms0.4% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · parallel · 3072 × 3072 · f64\u003c/p>\n\u003cp>\u003ccode>registers\u003c/code> keeps the running totals for a 32 × 16 block of c in registers throughout the depth loop, updating them with vector \u003ccode>fma\u003c/code>.\u003c/p>\n\u003cp>\u003cstrong>42 GFLOP/s\u003c/strong> · 1,379.47 ms4.8% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · parallel · 3072 × 3072 · f64\u003c/p>\n\u003cp>\u003ccode>outer_products\u003c/code> uses the matrix unit to hold those totals as eight 8 × 8 blocks. For each step of k, it updates them with outer products from a column of A and a row of B. The LLVM backend selects the matrix instructions.\u003c/p>\n\u003cp>\u003cstrong>894 GFLOP/s\u003c/strong> · 64.82 ms103% of Accelerate's speed\u003c/p>\n\u003cp>100% = Accelerate · CPU · matrix units · 871 GFLOP/s\u003c/p>\n\u003cp>CPU · parallel · 3072 × 3072 · f64\u003c/p>\n\u003cp>\u003ccode>sme: bits of matmul_PlusTimes_f64\u003c/code>\u003c/p>\n\u003cp>Like \u003ccode>bands\u003c/code>, \u003ccode>sme\u003c/code> divides the rows into bands, but uses larger blocks. Each band of 1536 rows runs on a thread of its own, so at 3072 × 3072 each matrix unit works on one band. Packing the inputs is just copying, so that work can still run across all the cores.\u003c/p>\n\u003cp>Within a band, the \u003ccode>order\u003c/code> in step 4 visits the tiles along C’s rows. We work across the same 32 rows before moving down to the next 32, keeping the accesses to C on the same memory pages. Visiting the tiles down the columns would start every tile on 32 new rows.\u003c/p>\n\u003cp>At this matrix size, one depth block covers the whole sum: 3072 steps. Each tile’s running totals can stay in the matrix unit until the sum is finished, and we store the result once. With blocks of 768, we’d write each output tile four times, reading it back between blocks. Those extra transfers cost about a tenth of the running time.\u003c/p>\n\u003cp>There’s also no \u003ccode>zero\u003c/code> step here. The first depth block starts the running totals at \u003ccode>-0.0\u003c/code> in the matrix unit, so we don’t need to clear C and then read it back. At this size, C is only ever written. Two library steps and a few new checker rules make this possible while keeping the result identical to \u003ccode>matmul\u003c/code>’s.\u003c/p>\n\u003cp>For each step along the depth, we load a column of A and a row of B once, using SME2’s multi-vector load instructions. All eight 8 × 8 blocks then reuse those values.\u003c/p>\n\u003cp>For the checker, \u003ccode>outer_fma_primitive\u003c/code> is a scalar \u003ccode>fma\u003c/code> on each active cell of the accumulator. Here the LLVM backend selects the matrix instructions. We rely on the compiler and hardware to implement the operation correctly, without supplying a template of our own.\u003c/p>\n\u003cp>On 3072 × 3072 matrices of \u003ccode>f64\u003c/code>, \u003ccode>sme\u003c/code> reaches 894 GFLOP/s, slightly faster than Accelerate, Apple’s BLAS, at 871 on the same matrix units. Like \u003ccode>bands\u003c/code>, it splits no sums between threads, so it produces the same result as \u003ccode>matmul\u003c/code>.\u003c/p>\n\u003ch2 id=\"scheduling-for-the-gpu\">Scheduling for the GPU\u003c/h2>\n\u003cp>The GPU schedules start again from \u003ccode>matmul\u003c/code>. The examples below bind \u003ccode>S\u003c/code> to \u003ccode>PlusTimes f32\u003c/code>, and their performance bars compare with MLX on 4096 × 4096 matrices.\u003c/p>\n\u003ch3 id=\"independent-outputs\">Independent outputs\u003c/h3>\n\u003cp>We gave CPU threads separate bands of output rows. On the GPU, the unit of work is one output element.\u003c/p>\n\u003cp>A GPU runs the same small program, called a \u003cem>kernel\u003c/em>, many times. Each invocation is a \u003cem>thread\u003c/em>, and its indices tell it which piece of work to do. Thread \u003ccode>(i, j)\u003c/code> computes \u003ccode>c[i, j]\u003c/code>: it reads row \u003ccode>i\u003c/code> of A and column \u003ccode>j\u003c/code> of B and keeps one running total. The GPU assigns threads to hardware as space becomes available; they needn’t all run at once.\u003c/p>\n\u003cp>We use a grid again, this time on the GPU:\u003c/p>\n\u003cpre>\u003ccode>schedule rows of matmul @(S = PlusTimes f32) on M4Gpu =\n grid over (i, j)\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for i in 0 .. M do\n for j in 0 .. N do\n var acc'0: f32 = -0.0\n for k in 0 .. K do\n acc'0 = fma ... acc'0\n store c[i, j] = acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>grid on M4Gpu i in 0 .. M, j in 0 .. N\n writes c[i, j] as ct do\n ... // the same running total and k loop\n store ct = acc'0\u003c/code>\u003c/pre>\n\u003cp>Each output adds up its products in ascending order of k, starting from zero.\u003c/p>\n\u003cp>\u003cstrong>0.65 GFLOP/s\u003c/strong> · 211,498.49 ms<0.1% of MLX's speed\u003c/p>\n\u003cp>100% = MLX · GPU · 13,113 GFLOP/s\u003c/p>\n\u003cp>CPU · 4096 × 4096 · f32\u003c/p>\n\u003cp>Each pair (i, j) runs as one GPU thread. Its write window is one element of c; the inputs may be read by many threads. Each thread's loop over k is unchanged.\u003c/p>\n\u003cp>\u003cstrong>2,399 GFLOP/s\u003c/strong> · 57.28 ms18% of MLX's speed\u003c/p>\n\u003cp>100% = MLX · GPU · 13,113 GFLOP/s\u003c/p>\n\u003cp>GPU · 4096 × 4096 · f32\u003c/p>\n\u003cp>\u003ccode>rows: bits of matmul_PlusTimes_f32\u003c/code>\u003c/p>\n\u003cp>\u003ccode>grid over (i, j)\u003c/code> gives each pair of indices its own grid iteration. In this schedule, each iteration runs as one GPU thread. \u003ccode>on M4Gpu\u003c/code> selects the device, from the description of the target machine named at the top of the file. We call the resulting function with \u003ccode>rows a b c\u003c/code>.\u003c/p>\n\u003cp>A grid is an ordinary Cachet construct, so we could have written \u003ccode>rows\u003c/code> by hand, and it would have been checked in the same way. In particular, the grid’s header says what each iteration may write:\u003c/p>\n\u003cpre>\u003ccode>cachetgrid on M4Gpu i in 0 .. M, j in 0 .. N writes c[i, j] as ct do\u003c/code>\u003c/pre>\n\u003cp>\u003ca href=\"#user-content-fnref-host\">4\u003c/a>\u003c/p>\n\u003cp>A grid without \u003ccode>on\u003c/code> runs on the host. A built executable runs its outermost loop on several threads, while Cachet’s interpreter runs the iterations in order. Since no iteration can observe another’s effects, both produce identical results.\u003c/p>\n\u003cp>\u003ccode>writes c[i, j]\u003c/code> gives the iteration’s write window, referred to as \u003ccode>ct\u003c/code> in the grid’s body. Cachet checks that different iterations’ windows \u003ca href=\"#panel-races\">don’t overlap\u003c/a>, and that each iteration writes only within its own.\u003ca href=\"#user-content-fn-host\">4\u003c/a> For example, suppose we wrote this grid by hand for 32 × 32 matrices, but stored each result one column to the right, into \u003ccode>c[i, (j + 1) % 32]\u003c/code>. The checker would find a thread that writes outside its window:\u003c/p>\n\u003cpre>\u003ccode>could not prove a grid iteration reaches only its own window: i == i && (j + 1) % 32 == j\n counterexample: j = 0\u003c/code>\u003c/pre>\n\u003cp>\u003ccode>rows\u003c/code> performs the same multiply-adds in the same order as \u003ccode>matmul\u003c/code>, but it runs them on the GPU. A GPU may handle some floating-point values differently from the CPU. The M4 Max’s GPU, for example, flushes \u003cem>subnormals\u003c/em> (very small numbers near zero) to zero. The guarantee is therefore that \u003ccode>rows\u003c/code> produces exactly the same result as \u003ccode>matmul\u003c/code> evaluated using that GPU’s arithmetic.\u003c/p>\n\u003cp>The grid layout is currently a built-in step. Its side conditions are checked, but its rewrite law is \u003ca href=\"#panel-wrong\">part of the compiler we trust\u003c/a>.\u003c/p>\n\u003ch3 id=\"tiles\">Tiles\u003c/h3>\n\u003cp>\u003ccode>rows\u003c/code> gives each grid iteration one output number. We can give it a whole output tile instead, with several threads cooperating on it. In Cachet, that tile is an ordinary local matrix value: an accumulator, or a block loaded from an input. The grid divides the independent work; the tiles hold the values each iteration works with.\u003c/p>\n\u003cp>The illustration uses 32 × 32 matrices, with 16 × 16 output tiles, advancing eight steps along \u003ccode>k\u003c/code> at a time.\u003c/p>\n\u003cp>The M4’s GPU executes threads in groups of 32, called \u003ca href=\"#panel-simd\">\u003cem>SIMD groups\u003c/em>\u003c/a>. A group can collectively perform an 8 × 8 matrix operation. Our 16 × 16 output tile has four 8 × 8 parts, so we’ll give each part to one SIMD group. Those four groups make up a \u003cem>threadgroup\u003c/em>, which cooperates on one tile. Separate threadgroups compute the four independent output tiles:\u003c/p>\n\u003cp>A 32 × 32 output, divided among threads or threadgroups\u003c/p>\n\u003cp>1,024 threads; one output each.The outline marks C[9, 10].\u003c/p>\n\u003cp>Here’s the schedule:\u003c/p>\n\u003cpre>\u003ccode>schedule tiled of matmul @(S = PlusTimes f32) on M4Gpu =\n grid over (i, j)\n tiles (i, j, k) (16, 16) (8, 8)\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for i in 0 .. M do\n for j in 0 .. N do\n var acc'0: f32 = -0.0\n for k in 0 .. K do\n acc'0 = fma ... acc'0\n store c[i, j] = acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>grid on M4Gpu i in 0 .. M, j in 0 .. N writes c[i, j] as ct do\n var acc'0: f32 = -0.0\n for k in 0 .. K do\n acc'0 = fma ... acc'0\n store ct = acc'0\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>grid on M4Gpu gi in 0 .. M / 16, gj in 0 .. N / 16\n by tile (si, sj) parts [8, 8]\n writes c[...] as ct_2 do\n var t: [f32; 16, 16] = repeat (-0.0)\n for k in 0 .. K / 8 do\n let x: [f32; 16, 8] = load a[...]\n let y: [f32; 8, 16] = load b[...]\n t = mma x y t\n store ct_2 = t\u003c/code>\u003c/pre>\n\u003cp>Each output adds up its products in ascending order of k, starting from zero.\u003c/p>\n\u003cp>\u003cstrong>0.65 GFLOP/s\u003c/strong> · 211,498.49 ms<0.1% of MLX's speed\u003c/p>\n\u003cp>100% = MLX · GPU · 13,113 GFLOP/s\u003c/p>\n\u003cp>CPU · 4096 × 4096 · f32\u003c/p>\n\u003cp>Each pair (i, j) gets its own grid iteration, as in \u003ccode>rows\u003c/code>.\u003c/p>\n\u003cp>\u003cstrong>2,399 GFLOP/s\u003c/strong> · 57.28 ms18% of MLX's speed\u003c/p>\n\u003cp>100% = MLX · GPU · 13,113 GFLOP/s\u003c/p>\n\u003cp>GPU · 4096 × 4096 · f32\u003c/p>\n\u003cp>\u003ccode>tiles\u003c/code> groups the outputs into 16 × 16 tiles, one for each grid iteration, shared among four SIMD groups in 8 × 8 parts, and works through the sum eight steps of k at a time. t starts at zero and holds the tile's running totals across the k loop; x and y are the next pair of input blocks, and \u003ccode>mma\u003c/code> multiplies them and adds the product to t with the device's \u003ccode>simdgroup_mma8\u003c/code>. Here M and N must be multiples of 16, and K a multiple of 8.\u003c/p>\n\u003cp>\u003cstrong>5,282 GFLOP/s\u003c/strong> · 26.02 ms40% of MLX's speed\u003c/p>\n\u003cp>100% = MLX · GPU · 13,113 GFLOP/s\u003c/p>\n\u003cp>GPU · 4096 × 4096 · f32\u003c/p>\n\u003cp>\u003ccode>tiled: bits of matmul_PlusTimes_f32\u003c/code>\u003c/p>\n\u003cp>\u003ccode>grid over (i, j)\u003c/code> starts with the independent outputs, as in \u003ccode>rows\u003c/code>. The \u003ccode>tiles\u003c/code> step groups them into 16 × 16 tiles and gives each SIMD group an 8 × 8 part. These parts don’t overlap, so each output still has one owner.\u003c/p>\n\u003cp>For \u003ccode>k\u003c/code>, \u003ccode>tiles\u003c/code> keeps the same running total across chunks, just as \u003ccode>tower\u003c/code> does. The GPU matrix instruction we use is called \u003ccode>simdgroup_mma8\u003c/code>. Its reference body adds each block’s eight products in ascending order of \u003ccode>k\u003c/code>, so each output receives the same chain of multiply-adds, now eight at a time.\u003c/p>\n\u003cp>\u003ccode>t\u003c/code> holds the output tile’s running totals, starting from zero, and \u003ccode>x\u003c/code> and \u003ccode>y\u003c/code> are the next pair of input blocks. \u003ccode>mma x y t\u003c/code> is \u003cem>matrix multiply-accumulate\u003c/em>: multiply the two input blocks and add their product to \u003ccode>t\u003c/code>. The totals stay in \u003ccode>t\u003c/code> throughout the depth loop, and are stored at the end.\u003c/p>\n\u003cp>In effect, \u003ccode>tiles\u003c/code> makes each element an 8 × 8 matrix, with \u003ccode>simdgroup_mma8\u003c/code> as its multiply-add. It’s still our \u003ccode>matmul\u003c/code>, just at a different element type. Select a level to see one element of its type:\u003c/p>\n\u003cp>One element at three matrix types\u003c/p>\n\u003cp>\u003cstrong>\u003ccode>[f32; 8, 8]\u003c/code>\u003c/strong>\u003c/p>\n\u003cp>One 8 × 8 block: one SIMD group's part of the tile. Each simdgroup_mma8 adds eight steps of k to all 64 outputs at once.\u003c/p>\n\u003cp>[{"title":"One number","type":"f32","what":"One output, a single f32. Its chain adds one product per step of k."},{"title":"An 8 × 8 block","type":"[f32; 8, 8]","what":"One 8 × 8 block: one SIMD group's part of the tile. Each simdgroup_mma8 adds eight steps of k to all 64 outputs at once."},{"title":"The whole tile","type":"[[f32; 8, 8]; 2, 2]","what":"The whole 16 × 16 tile: one grid iteration, a 2 × 2 matrix of blocks shared out among four SIMD groups."}]\u003c/p>\n\u003cp>Inputs are now reused within each SIMD group. Different groups still load their inputs separately; to share those loads too, we’d need \u003cem>threadgroup memory\u003c/em>, a small memory that all the groups in a threadgroup can access. We could also give each group more outputs to work on. That would reuse each input more times, but would need room for more running totals. We’ll try larger tiles next.\u003c/p>\n\u003cp>The compiler reasons about a reference implementation of the matrix multiply-add and uses a code template to replace it with a GPU instruction. We \u003ca href=\"#panel-matrix-instruction\">test that instruction against the reference\u003c/a>, but don’t prove that they always produce identical results, so the template remains a trusted assumption.\u003c/p>\n\u003cp>\u003ccode>tiles\u003c/code> itself is a library step: its relation is checked in the same way as \u003ccode>hoist\u003c/code>’s.\u003c/p>\n\u003ch3 id=\"larger-tiles\">Larger tiles\u003c/h3>\n\u003cp>\u003ccode>tiled\u003c/code> gives each SIMD group only one 8 × 8 block of the accumulator. We can give it more outputs, so that each input is reused more times. With 64 × 32 output tiles and 32 × 16 parts, each SIMD group holds eight accumulator blocks:\u003c/p>\n\u003cpre>\u003ccode>cachetschedule big_tiles of matmul @(S = PlusTimes f32) on M4Gpu =\n grid over (i, j)\n tiles (i, j, k) (64, 32) (32, 16)\u003c/code>\u003c/pre>\n\u003cp>\u003cstrong>12,407 GFLOP/s\u003c/strong> · 11.08 ms95% of MLX's speed\u003c/p>\n\u003cp>100% = MLX · GPU · 13,113 GFLOP/s\u003c/p>\n\u003cp>GPU · 4096 × 4096 · f32\u003c/p>\n\u003cp>At 4096 × 4096, \u003ccode>big_tiles\u003c/code> reaches 12,407 GFLOP/s: about 2.3 times \u003ccode>tiled\u003c/code>’s speed, and 95% of MLX’s. The result is still identical to \u003ccode>tiled\u003c/code>’s.\u003c/p>\n\u003ch2 id=\"comparing-the-results\">Comparing the results\u003c/h2>\n\u003cp>We’ve now implemented the same \u003ccode>matmul\u003c/code> using four different multiply-add operations: scalar \u003ccode>fma\u003c/code>, vector \u003ccode>fma\u003c/code>, the CPU’s \u003ccode>outer_fma_primitive\u003c/code>, and the GPU’s \u003ccode>simdgroup_mma8\u003c/code>. In each case, the schedule chooses a block of the output to update at once, and the instruction that updates it.\u003c/p>\n\u003cp>Here are all the matrix multiplication schedules together, grouped by the hardware they use. Each group compares Cachet with a library on the same matrix size and precision:\u003c/p>\n\u003cp>How the schedules compare with the libraries\u003c/p>\n\u003cp>Apple M4 Max. Higher GFLOP/s means faster multiplication. In each group, the dashed line is the library's speed, set to 100%.\u003c/p>\n\u003cp>\u003cstrong>CPU · one core\u003c/strong>1024 × 1024 · f32 · NEON vectors\u003c/p>\n\u003cdiv class=\"table-wrap\">\u003ctable>\u003cthead>\u003ctr>\u003cth>Schedule\u003c/th>\u003cth>Speed relative to the library0100%\u003c/th>\u003cth>GFLOP/s\u003c/th>\u003cth>Library speed\u003c/th>\u003c/tr>\u003c/thead>\u003ctbody>\u003ctr>\u003ctd>\u003ccode>matmul\u003c/code>\u003c/td>\u003ctd>\u003c/td>\u003ctd>1.2\u003c/td>\u003ctd>1%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>\u003ccode>swapped\u003c/code>\u003c/td>\u003ctd>\u003c/td>\u003ctd>33\u003c/td>\u003ctd>30%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>\u003ccode>tower\u003c/code>\u003c/td>\u003ctd>\u003c/td>\u003ctd>27\u003c/td>\u003ctd>25%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>\u003ccode>packed\u003c/code>\u003c/td>\u003ctd>\u003c/td>\u003ctd>49\u003c/td>\u003ctd>45%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>\u003ccode>fast\u003c/code>\u003c/td>\u003ctd>\u003c/td>\u003ctd>116\u003c/td>\u003ctd>107%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>OpenBLAS\u003c/td>\u003ctd>\u003c/td>\u003ctd>108\u003c/td>\u003ctd>100%\u003c/td>\u003c/tr>\u003c/tbody>\u003c/table>\u003c/div>\n\u003cp>\u003cstrong>CPU · all cores\u003c/strong>1024 × 1024 · f32 · NEON vectors\u003c/p>\n\u003cdiv class=\"table-wrap\">\u003ctable>\u003cthead>\u003ctr>\u003cth>Schedule\u003c/th>\u003cth>Speed relative to the library0100%\u003c/th>\u003cth>GFLOP/s\u003c/th>\u003cth>Library speed\u003c/th>\u003c/tr>\u003c/thead>\u003ctbody>\u003ctr>\u003ctd>\u003ccode>bands\u003c/code>\u003c/td>\u003ctd>\u003c/td>\u003ctd>757\u003c/td>\u003ctd>88%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>OpenBLAS\u003c/td>\u003ctd>\u003c/td>\u003ctd>863\u003c/td>\u003ctd>100%\u003c/td>\u003c/tr>\u003c/tbody>\u003c/table>\u003c/div>\n\u003cp>\u003cstrong>CPU · matrix units\u003c/strong>3072 × 3072 · f64 · SME matrix instructions\u003c/p>\n\u003cdiv class=\"table-wrap\">\u003ctable>\u003cthead>\u003ctr>\u003cth>Schedule\u003c/th>\u003cth>Speed relative to the library0100%\u003c/th>\u003cth>GFLOP/s\u003c/th>\u003cth>Library speed\u003c/th>\u003c/tr>\u003c/thead>\u003ctbody>\u003ctr>\u003ctd>\u003ccode>sme\u003c/code>\u003c/td>\u003ctd>\u003c/td>\u003ctd>894\u003c/td>\u003ctd>103%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>Accelerate\u003c/td>\u003ctd>\u003c/td>\u003ctd>871\u003c/td>\u003ctd>100%\u003c/td>\u003c/tr>\u003c/tbody>\u003c/table>\u003c/div>\n\u003cp>\u003cstrong>GPU\u003c/strong>4096 × 4096 · f32 · Metal\u003c/p>\n\u003cdiv class=\"table-wrap\">\u003ctable>\u003cthead>\u003ctr>\u003cth>Schedule\u003c/th>\u003cth>Speed relative to the library0100%\u003c/th>\u003cth>GFLOP/s\u003c/th>\u003cth>Library speed\u003c/th>\u003c/tr>\u003c/thead>\u003ctbody>\u003ctr>\u003ctd>\u003ccode>rows\u003c/code>\u003c/td>\u003ctd>\u003c/td>\u003ctd>2,399\u003c/td>\u003ctd>18%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>\u003ccode>tiled\u003c/code>\u003c/td>\u003ctd>\u003c/td>\u003ctd>5,282\u003c/td>\u003ctd>40%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>\u003ccode>big_tiles\u003c/code>\u003c/td>\u003ctd>\u003c/td>\u003ctd>12,407\u003c/td>\u003ctd>95%\u003c/td>\u003c/tr>\u003ctr>\u003ctd>MLX\u003c/td>\u003ctd>\u003c/td>\u003ctd>13,113\u003c/td>\u003ctd>100%\u003c/td>\u003c/tr>\u003c/tbody>\u003c/table>\u003c/div>\n\u003cp>Bar lengths compare each schedule with its own library baseline, not with the other hardware groups. Matrix size and precision differ between groups; within each group, they are the same for Cachet and the library.\u003c/p>\n\u003cp>For these sizes, \u003ccode>fast\u003c/code> is about level with OpenBLAS on one core, and \u003ccode>sme\u003c/code> is slightly faster than Accelerate. \u003ccode>bands\u003c/code> reaches 88% of OpenBLAS’s speed across all cores, and \u003ccode>big_tiles\u003c/code> reaches 95% of MLX’s on the GPU. Each kernel must produce exactly the same result as \u003ccode>matmul\u003c/code> using its target device’s arithmetic. The libraries don’t promise this; we checked each kernel against its reference before timing it.\u003c/p>\n\u003ch2 id=\"attention\">Attention\u003c/h2>\n\u003cp>So far, every schedule has kept the original order of additions. Attention gives us a reason to relax that requirement.\u003c/p>\n\u003cp>Attention lets each position in a sequence mix information from other positions, giving more weight to the ones relevant to it. Each position has a \u003cem>query\u003c/em> to compare with the others’ \u003cem>keys\u003c/em>; the resulting weights say how much of each \u003cem>value\u003c/em> to include. The Transformer in \u003ca href=\"https://arxiv.org/html/1706.03762v7#S3.SS2.SSS1\" rel=\"nofollow ugc noopener\">Attention Is All You Need\u003c/a> writes this as:\u003c/p>\n\u003cp>Attention(*Q*, *K*, *V\u003cem>) = softmax(\u003c/em>QK\u003cem>T / √\u003c/em>d\u003cem>k)\u003c/em>V*\u003c/p>\n\u003cp>There are two matrix multiplications, with a softmax between them. The first computes scores; softmax turns each row into weights that add up to one; the second mixes the values. We divide the scores by the square root of the query width, *d*k. We’ll leave that scale factor out of the example below.\u003c/p>\n\u003cp>Here it is as a contraction. \u003ccode>q\u003c/code> holds the queries, \u003ccode>kt\u003c/code> the transposed keys, and \u003ccode>v\u003c/code> the values. \u003ccode>Online\u003c/code> is a library implementation of the weighted sum, which we’ll unpack in a moment:\u003c/p>\n\u003cpre>\u003ccode>cachetcontraction attend\n (reads q: [f32; 64, 16])\n (reads kt: [f32; 16, 32])\n (reads v: [f32; 32, 16])\n -> out y: [f32; 64, 16] =\n s[i, j] = sum c. q[i, c] * kt[c, j]\n y[i, d] = normalised (reduce[reassoc] Online j. key (s[i, j]) (v[j, d]))\u003c/code>\u003c/pre>\n\u003cp>The score matrix has one entry for every query–key pair. For self-attention, doubling the sequence length quadruples that matrix. Avoiding the cost of storing and rereading it is the motivation behind \u003ca href=\"https://arxiv.org/abs/2205.14135\" rel=\"nofollow ugc noopener\">FlashAttention\u003c/a>.\u003c/p>\n\u003cp>We’d like to compute a block of scores, use it, and discard it. Softmax makes this awkward: it exponentiates each score and divides by the sum of all the exponentials in the row, including scores we haven’t computed yet. To prevent overflow, it also subtracts the row’s largest score before exponentiating. We don’t know that maximum yet either.\u003c/p>\n\u003cp>\u003ccode>Online\u003c/code> keeps a running summary that can be rescaled when a larger score arrives. \u003ccode>key s v\u003c/code> creates a summary for one key, and \u003ccode>reduce[reassoc] Online j.\u003c/code> combines these summaries over \u003ccode>j\u003c/code>, much as \u003ccode>sum\u003c/code> combines numbers. The summary keeps the total weight and the weighted sum of values. At the end, \u003ccode>normalised\u003c/code> divides the weighted sum by the total weight. The \u003ca href=\"#panel-online-attention\">side panel\u003c/a> shows the implementation. The \u003ccode>[reassoc]\u003c/code> annotation is permission to regroup the reduction.\u003c/p>\n\u003cp>The contraction combines keys one at a time. The schedule will instead find the maximum across the old summary and a whole block of scores, rescale the summary once, then add the block’s contributions. Rescaling both the sum of weights and the weighted sum of values by the same factor leaves their ratio unchanged over the reals.\u003c/p>\n\u003cp>Combining a block at a time regroups the reduction, so it can change the answer in floating point. Here are six \u003ccode>f32\u003c/code> values, added one at a time on the left, and in pairs on the right:\u003c/p>\n\u003cp>How addition order affects rounding\u003c/p>\n\u003cp>Each tree adds the same six \u003ccode>f32\u003c/code> values. Every + rounds to the nearest representable value, with ties to even. The exact sum is 1.\u003c/p>\n\u003cp>\u003cstrong>Left to right\u003c/strong>five dependent additions\u003c/p>\n\u003cp>Result: *\u003cem>1*\u003c/em>\u003c/p>\n\u003cp>\u003cstrong>Three partial sums\u003c/strong>three dependency levels\u003c/p>\n\u003cp>Result: *\u003cem>0*\u003c/em>\u003c/p>\n\u003cp>The chain gives 1; the grouped sum gives 0. Both perform five additions. Dependency levels show which additions can run together, not measured time.\u003c/p>\n\u003cp>Both expressions equal one over the reals. In \u003ccode>f32\u003c/code>, adding one to minus 2²⁵ rounds back to minus 2²⁵, so the paired version loses the one and returns zero. Neither order is more accurate in general: with other values, the chain could just as well be the one that loses precision. But they’re different, so Cachet only regroups a reduction that the contraction allows to be regrouped. That’s what \u003ccode>[reassoc]\u003c/code> in \u003ccode>attend\u003c/code> is for: it \u003ca href=\"#panel-reproducible\">permits a different rounding\u003c/a>. Without it, the schedule below is refused:\u003c/p>\n\u003cpre>\u003ccode>a fused block of `j` combines a block's keys at once, regrouping the reduction, which it permits with `[reassoc]`, `reduce[reassoc] Online j.`\u003c/code>\u003c/pre>\n\u003cp>With that permission, we can use a library law that combines a whole block of keys with the running summary. The tile operations do the rest: they can find a maximum or sum along a row, exponentiate each score, and use the resulting weights in another matrix multiplication. The scores stay local throughout, so we never need to write out the full score matrix. As with \u003ca href=\"#panel-epilogue\">a ReLU after a product\u003c/a>, the contraction’s intermediate values only get buffers of their own if the schedule asks for them.\u003c/p>\n\u003cp>We’ll call the scheduled version \u003ccode>flash\u003c/code>. Because we’ve allowed it to change the rounding, we can no longer require it to produce exactly the same result as \u003ccode>attend\u003c/code>. We need a reference that follows the new reduction order. Cachet constructs this \u003cem>shadow\u003c/em> by applying only the order-changing steps to the contraction, leaving plain loops with no grids, tiles or threads. \u003ccode>flash\u003c/code> must produce exactly the same result as this reference, which appears as \u003ccode>flash_shadow\u003c/code> in the claim:\u003c/p>\n\u003cpre>\u003ccode>schedule flash of attend on M4Gpu =\n split i by 32, j by 8, c by 16\n grid over i.outer\n compute s at j.outer\n reduce j.inner by (max: halving, sum: order)\n parts [8, 16]\n element [f32; 8, 8]\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>for i in 0 .. 64 do\n for d in 0 .. 16 do\n var acc'1: Online.Value = Online.empty ()\n for j in 0 .. 32 do\n ... // compute this key's score in acc'0\n acc'1 = Online.combine acc'1 (key acc'0 (load v[j, d]))\n store y[i, d] = normalised acc'1\u003c/code>\u003c/pre>\n\u003cpre>\u003ccode>grid on M4Gpu gi in 0 .. 2\n by tile (si, sj) parts [8, 16]\n writes y[...] as yt do\n ... // initialise the running summary: m, l and o\n for gj in 0 .. 4 do\n ... // compute a 32 × 8 score tile s with mma\n let m2 = max m (reduce Max f32 over cols by halving do s)\n let e = exp (s - m2)\n let alpha = rescale m m2\n l = l * alpha + (reduce Sum f32 over cols by order do e)\n let w: [f32; 8, 16] = load v[...]\n o = o * alpha\n o = mma e w o\n m = m2\n store yt = o / l\u003c/code>\u003c/pre>\n\u003cp>One contraction, with the scores as an intermediate.\u003c/p>\n\u003cp>Each grid iteration handles 32 queries. \u003ccode>compute s at j.outer\u003c/code> keeps a block of scores within the SIMD groups. \u003ccode>reduce\u003c/code> combines eight keys at a time: find the new maximum, rescale the summary, then add the new terms in order. These steps are shown together because the compiler needs the final \u003ccode>element\u003c/code> choice to construct the kernel.\u003c/p>\n\u003cp>\u003ccode>flash: bits of flash_shadow\u003c/code>\u003c/p>\n\u003cp>I’ve left out the timing bar here. With only 64 queries and 32 keys, each of width 16, GPU launch overhead dominates, so this example is too small for a useful comparison of the schedules’ speed.\u003c/p>\n\u003cp>\u003ccode>cachetc scheduled --shadow\u003c/code> prints the reference loops. Here they are, shortened. \u003ccode>m\u003c/code> is the largest score seen so far, \u003ccode>l\u003c/code> is the sum of weights rescaled to that maximum, and \u003ccode>o\u003c/code> is the corresponding weighted sum of values:\u003c/p>\n\u003cpre>\u003ccode>cachetfn flash_shadow\n (reads q: [f32; 64, 16])\n (reads kt: [f32; 16, 32])\n (reads v: [f32; 32, 16])\n -> out y: [f32; 64, 16]\n=\n for i in 0 .. 64 do\n for d in 0 .. 16 do\n var m: f32 = from_bits (4286578688 as u32)\n var l: f32 = -0.0\n var o: f32 = -0.0\n for gj in 0 .. 4 do\n var s_0: f32 = -0.0\n for c in 0 .. 16 do\n s_0 = fma (load q[i, c]) (load kt[c, gj * 8 + 0]) s_0\n ...\n let m2: f32 =\n max\n m\n (max\n (max (max s_0 s_4) (max s_2 s_6))\n (max (max s_1 s_5) (max s_3 s_7)))\n let alpha: f32 = rescale m m2\n l =\n l * alpha +\n (-0.0 + exp (s_0 - m2) + exp (s_1 - m2) + ... + exp (s_7 - m2))\n var mix: f32 = o * alpha\n mix = fma (exp (s_0 - m2)) (load v[gj * 8 + 0, d]) mix\n ...\n mix = fma (exp (s_7 - m2)) (load v[gj * 8 + 7, d]) mix\n o = mix\n m = m2\n store y[i, d] = o / l\u003c/code>\u003c/pre>\n\u003cp>Each iteration of \u003ccode>gj\u003c/code> handles eight keys. It first computes their scores, then finds the block’s maximum by comparing pairs, as \u003ccode>max: halving\u003c/code> in the schedule asks. \u003ccode>m2\u003c/code> is the larger of that maximum and the previous \u003ccode>m\u003c/code>. The summary is rescaled to \u003ccode>m2\u003c/code> once, and the block’s weights are added in order, as \u003ccode>sum: order\u003c/code> asks. The initial \u003ccode>from_bits\u003c/code> value is negative infinity.\u003c/p>\n\u003cp>These loops spell out the arithmetic without any GPU machinery. \u003ccode>flash\u003c/code> must produce exactly the same result as these loops, including the effects of rounding. We can read the shadow to find out which computation we’ve asked the hardware to perform.\u003c/p>\n\u003cp>We still need to relate those loops to \u003ccode>attend\u003c/code>. That depends on \u003ca href=\"#panel-online-attention\">laws for combining the summaries\u003c/a>, which the library states over the reals. Cachet takes these laws on trust; it doesn’t prove them.\u003c/p>\n\u003cp>The resulting claim has two parts: the kernel and its shadow produce identical results, and, assuming the library’s laws, the shadow and \u003ccode>attend\u003c/code> would compute the same result with real-number arithmetic. As with \u003ccode>tiled\u003c/code>, this also relies on the trusted layout steps and matrix instruction’s template. \u003ccode>cachetc scheduled\u003c/code> prints the full claim, including the instruction template and library laws it relies on.\u003c/p>\n\u003ch2 id=\"conclusion\">Conclusion\u003c/h2>\n\u003cp>We still had to choose the loop order, block sizes and instructions. But once we’d made those choices, we could ask the compiler to check them: this rewrite leaves the result unchanged, these buffers fit the cache model, this loop stays within its traffic budget. Changing a choice means passing the checks again.\u003c/p>\n\u003cp>There’s still that asterisk in the subtitle. If we deliberately regroup a sum, the kernel must produce exactly the same result as its shadow, which can differ from the original contraction because of rounding. Additional assumptions from the library or platform, such as the laws for \u003ccode>Online\u003c/code> or an instruction’s template, are listed in the \u003ca href=\"#panel-claim\">claim\u003c/a>.\u003c/p>\n\u003cp>This is what I want from an explicit compiler. I can choose how the kernel runs, keep the definition it came from, and have the compiler tell me when a change breaks one of my assumptions.\u003c/p>\n\u003cp>The \u003ca href=\"#panel-running\">complete example\u003c/a> checks that the smaller kernels produce exactly the same results as \u003ccode>matmul\u003c/code>, and the benchmark does the same for the full-size ones. Attention isn’t included in those runs. The \u003ca href=\"#panel-related\">related work\u003c/a> panel describes where these ideas come from, and where contractions are not sufficient.\u003c/p>\n\u003ch2 id=\"background\">Background\u003c/h2>\n\u003ch3 id=\"matrix-multiplication\">Matrix multiplication\u003c/h3>\n\u003cp>Each element of the product of two matrices A and B is the dot product of a row of A and a column of B:\u003c/p>\n\u003cp>Computing one output element\u003c/p>\n\u003cp>Choose an output in C to follow its six products.\u003c/p>\n\u003cp>Press Play, or advance one step.\u003c/p>\n\u003cp>Current output\u003cstrong>C[0, 0]\u003c/strong>\u003c/p>\n\u003cp>Row 0 of A\u003cbr />\ncolumn 0 of B\u003c/p>\n\u003cp>B\u003c/p>\n\u003cp>01234\u003c/p>\n\u003cp>012345\u003c/p>\n\u003cp>A\u003c/p>\n\u003cp>0123\u003c/p>\n\u003cp>012345\u003c/p>\n\u003cp>C\u003c/p>\n\u003cp>First contributionSecond contributionRunning sum\u003c/p>\n\u003cp>C is drawn below B and to the right of A, so that the row and column feeding an output line up with it. Nothing here depends on any other output. Keeping each output's multiply-adds in order preserves its result; regrouping them can change floating-point rounding.\u003c/p>\n\u003cp>There are three properties of this formula that we can use when deciding how to compute it.\u003c/p>\n\u003cp>First, every output is independent. \u003ccode>C[i, j]\u003c/code> only depends on row \u003ccode>i\u003c/code> of A and column \u003ccode>j\u003c/code> of B, so we can compute all of the outputs at the same time.\u003c/p>\n\u003cp>Computing outputs in parallel\u003c/p>\n\u003cp>One thread per output, all twenty at the same time. Follow one column of A and one row of B as they feed the whole result.\u003c/p>\n\u003cp>Press Play, or advance one step.\u003c/p>\n\u003cp>Working together\u003cstrong>20 threads\u003c/strong>\u003c/p>\n\u003cp>one thread per output\u003c/p>\n\u003cp>B\u003c/p>\n\u003cp>01234\u003c/p>\n\u003cp>012345\u003c/p>\n\u003cp>A\u003c/p>\n\u003cp>0123\u003c/p>\n\u003cp>012345\u003c/p>\n\u003cp>C\u003c/p>\n\u003cp>First contributionSecond contributionRunning sum\u003c/p>\n\u003cp>Thread 1Thread 2Thread 3Combined sum\u003c/p>\n\u003cp>Second, the sum can be split up. In this illustration, three threads compute partial sums and then combine them. Over the reals this preserves the result; in floating point it changes the grouping, so it needs the permission discussed in the main text.\u003c/p>\n\u003cp>Splitting a sum across three threads\u003c/p>\n\u003cp>Three threads share the six products for C[1, 3]. Each builds a partial sum; the last step adds the three sums together.\u003c/p>\n\u003cp>Press Play, or advance one step.\u003c/p>\n\u003cp>Working together\u003cstrong>3 threads\u003c/strong>\u003c/p>\n\u003cp>one output, three partial sums\u003c/p>\n\u003cp>B\u003c/p>\n\u003cp>01234\u003c/p>\n\u003cp>012345\u003c/p>\n\u003cp>A\u003c/p>\n\u003cp>0123\u003c/p>\n\u003cp>012345\u003c/p>\n\u003cp>C\u003c/p>\n\u003cp>First contributionSecond contributionRunning sum\u003c/p>\n\u003cp>Thread 1Thread 2Thread 3Combined sum\u003c/p>\n\u003cp>Third, the formula also works on matrices of blocks. Notice which operations we need to compute each output: \u003ccode>+\u003c/code> and \u003ccode>×\u003c/code> on the elements of A and B. Floating-point numbers support these operations, but so do \u003ca href=\"#panel-semiring\">matrices\u003c/a>! So instead of a matrix of numbers, we can think of A, B and C as matrices of smaller matrices, and multiply them with exactly the same formula. The outer matrices get smaller, and each \u003ccode>×\u003c/code> in the formula becomes a smaller matrix multiplication.\u003c/p>\n\u003cp>A matrix of blocks\u003c/p>\n\u003cp>Four groups compute four output blocks. Each keeps its input blocks while their values contribute to several outputs.\u003c/p>\n\u003cp>Press Play, or advance one step.\u003c/p>\n\u003cp>Working together\u003cstrong>4 groups\u003c/strong>\u003c/p>\n\u003cp>one group per output block\u003c/p>\n\u003cp>B\u003c/p>\n\u003cp>01234\u003c/p>\n\u003cp>012345\u003c/p>\n\u003cp>A\u003c/p>\n\u003cp>0123\u003c/p>\n\u003cp>012345\u003c/p>\n\u003cp>C\u003c/p>\n\u003cp>First contributionSecond contributionRunning sum\u003c/p>\n\u003cp>Thread 1Thread 2Thread 3Combined sum\u003c/p>\n\u003cp>Note\u003c/p>\n\u003cp>There’s one difference: unlike numbers, matrices don’t commute, so \u003ccode>x × y\u003c/code> and \u003ccode>y × x\u003c/code> are not the same. That’s fine, because the formula always multiplies an element of A by an element of B, in that order, and never needs to swap them.\u003c/p>\n\u003cp>None of these properties is specific to GPUs. Independent outputs give us work to distribute across threads, while \u003ca href=\"#panel-matrix-units\">matrix units\u003c/a> provide instructions for multiplying blocks. CPU kernels can use the same decomposition to keep their inputs in cache.\u003c/p>\n\u003ch3 id=\"cache-lines\">Cache lines\u003c/h3>\n\u003cp>The animation uses a deliberately small cache: four lines of four values each. When a new line needs space, it replaces the least recently used one. A read from a cached line takes one tick; fetching a missing line takes eight. Reads run one at a time, with no prefetching.\u003c/p>\n\u003cp>Walking along the rows, each miss pays for the next three reads as well. Walking down the columns, the line is evicted before we come back for its neighbours, so every read misses. Both walks read the same 64 values, but the row walk has 16 misses and the column walk has 64.\u003c/p>\n\u003cp>An M4 Max has 128-byte cache lines, enough for 32 \u003ccode>f32\u003c/code>s, and much larger caches. Whether a line survives depends on the other accesses between uses and which cache slots they compete for. Real processors also prefetch and overlap memory requests. The ticks illustrate the cost of losing reuse; they aren’t a prediction of execution time.\u003c/p>\n\u003ch3 id=\"what-the-blocks-need\">What the blocks need\u003c/h3>\n\u003cp>We want to replace numbers with blocks and keep using the same formula. The algebra we need for that is a \u003cem>semiring\u003c/em>: \u003ccode>+\u003c/code> and \u003ccode>×\u003c/code> are associative, \u003ccode>+\u003c/code> is commutative, \u003ccode>×\u003c/code> distributes over \u003ccode>+\u003c/code>, there are identities \u003ccode>0\u003c/code> and \u003ccode>1\u003c/code>, and multiplying by \u003ccode>0\u003c/code> gives \u003ccode>0\u003c/code>. A ring would also need subtraction, which matrix multiplication never uses.\u003c/p>\n\u003cp>Square matrices over a semiring form another semiring. Commutativity of \u003ccode>×\u003c/code> is not required, which is lucky, since matrices don’t have it. For floating-point elements, these laws describe the corresponding real-number operations; rounding can make them fail, as we’ve seen with associativity.\u003c/p>\n\u003cp>For example, the \u003ccode>f32\u003c/code> implementation in Cachet’s library uses fused multiply-add and states its laws over the reals. Its zero is \u003ccode>-0.0\u003c/code>, so adding zero preserves the sign of a negative zero: \u003ccode>-0.0 + -0.0\u003c/code> is \u003ccode>-0.0\u003c/code>, while \u003ccode>0.0 + -0.0\u003c/code> is \u003ccode>0.0\u003c/code>. (Dividing \u003ccode>1.0\u003c/code> by the two zeroes gives infinities with opposite signs.)\u003c/p>\n\u003cpre>\u003ccode>cachetimpl Semiring for PlusTimes f32 where\n const Value = f32\n fn zero () = -0.0\n fn one () = 1.0\n fn add a b = a + b\n fn mul a b = a * b\n fn mul_add a b acc = fma a b acc\n law add associative over reals\n law add commutative over reals\n law add identity over reals\n law mul associative over reals\n law mul commutative over reals\n law mul identity over reals\n law distributive over reals\n law mul_add over reals\u003c/code>\u003c/pre>\n\u003cp>Nothing in \u003ccode>matmul\u003c/code> depends on these particular operations. Binding \u003ccode>S\u003c/code> to \u003ccode>MinPlus f32\u003c/code>, which adds with \u003ccode>min\u003c/code> and multiplies with \u003ccode>+\u003c/code>, gives one step of a shortest-paths computation:\u003c/p>\n\u003cpre>\u003ccode>cachetmatmul @(S = MinPlus f32) d d e\u003c/code>\u003c/pre>\n\u003cp>Here \u003ccode>d\u003c/code> holds edge distances, and each element of \u003ccode>e\u003c/code> starts from this semiring’s additive identity, positive infinity. The same formula now finds the shortest two-edge path between each pair of nodes. With zeroes on the diagonal of \u003ccode>d\u003c/code>, it also includes shorter paths.\u003c/p>\n\u003ch3 id=\"matrix-hardware\">Matrix hardware\u003c/h3>\n\u003cp>Note\u003c/p>\n\u003cp>NVIDIA introduced Tensor Cores with Volta in 2017; Metal’s \u003ccode>simdgroup_matrix\u003c/code> arrived with the A14 in 2020; Intel added AMX tile registers in Sapphire Rapids; and Apple’s M4 is the first of its chips to expose Arm’s Scalable Matrix Extension (SME). Earlier Apple chips had an undocumented matrix coprocessor, used by the Accelerate framework, which is the kind of thing this post is trying to make visible.\u003c/p>\n\u003ch3 id=\"the-gpu-matrix-instruction\">The GPU matrix instruction\u003c/h3>\n\u003cp>Whether \u003ccode>simdgroup_mma8\u003c/code> really is the multiply-add of \u003ccode>[f32; 8, 8]\u003c/code> depends on how the hardware accumulates a block’s products. Cachet’s description of the M4 declares the instruction like this:\u003c/p>\n\u003cpre>\u003ccode>cachetinstr fn simdgroup_mma8 (a: Vec f32 64) (b: Vec f32 64) (acc: Vec f32 64) -> Vec f32 64 =\n mma_block a b acc\n by_target metal\n "simdgroup_multiply_accumulate({result}, {a}, {b}, {acc});"\u003c/code>\u003c/pre>\n\u003cp>The instruction takes two 8 × 8 blocks and an accumulator, each flattened into a vector of 64 floats. \u003ccode>mma_block a b acc\u003c/code> is its \u003cem>reference body\u003c/em>: for each of the 64 outputs, a chain of eight \u003ccode>fma\u003c/code>s in ascending order of \u003ccode>k\u003c/code>. The checker and Cachet’s interpreter use this body. When compiling for the GPU, the backend replaces it with the Metal code in the \u003cem>template\u003c/em>, a call to Apple’s \u003ccode>simdgroup_multiply_accumulate\u003c/code>.\u003c/p>\n\u003cp>There’s a limit to what we can check here: nothing proves that Apple’s instruction produces exactly the same result as the reference body. The platform file records a measurement instead. On random, cancelling and subnormal inputs, \u003ccode>simdgroup_multiply_accumulate\u003c/code> matched the reference body bit for bit, with the reference \u003ccode>fma\u003c/code>s flushing subnormals to zero as the GPU does. That gives us evidence for using the template, but the claim still lists it as trusted.\u003c/p>\n\u003ch3 id=\"fused-multiply-add\">Fused multiply-add\u003c/h3>\n\u003cp>Note\u003c/p>\n\u003cp>Even \u003ccode>a * b + c\u003c/code> leaves a choice for the compiler: should it round the product separately, or use a fused multiply-add? The instruction first appeared in IBM’s POWER1 in 1990, only made it into IEEE 754 in 2008, and x86 didn’t get it until AMD’s Bulldozer and Intel’s Haswell in the early 2010s. Because the two round differently, C compilers may “contract” \u003ccode>a * b + c\u003c/code> into an FMA (controlled by the \u003ccode>FP_CONTRACT\u003c/code> pragma), which is a classic source of results changing between compilers or optimisation levels. That’s exactly the kind of hidden decision Cachet writes down.\u003c/p>\n\u003ch3 id=\"checking-parallel-writes\">Checking parallel writes\u003c/h3>\n\u003cp>Note\u003c/p>\n\u003cp>Compare this with OpenMP’s \u003ccode>#pragma omp parallel for\u003c/code>, which takes your word for it: if two iterations write to the same location, that’s a data race, and the program has undefined behaviour. Rust’s Rayon is closer to what Cachet does, since \u003ccode>par_chunks_mut\u003c/code> hands out disjoint mutable slices, and the borrow checker enforces the rest. There, however, disjointness comes from how the slice was split, rather than from a window written down for each iteration.\u003c/p>\n\u003ch3 id=\"where-the-blocks-live\">Where the blocks live\u003c/h3>\n\u003cp>Once we’ve loaded a block, we need somewhere to keep it while we reuse it. The processor has several places to do that. The closer the storage is to the core, the less it holds and the faster we can reach it:\u003c/p>\n\u003cp>The memory hierarchy of an M4 Max performance core\u003c/p>\n\u003col>\u003cli>\u003cp>\u003cstrong>SIMD registers\u003c/strong> · 512 B\u003c/p>\u003cp> No memory load between updates. \u003ccode>packed\u003c/code> keeps a 4 × 8 block of \u003ccode>c\u003c/code> here.\u003c/p>\u003c/li>\u003cli>\u003cp>\u003cstrong>L1 cache\u003c/strong> · 128 KiB\u003c/p>\u003cp> A load takes a few cycles. \u003ccode>packed\u003c/code> keeps \u003ccode>packB\u003c/code> here.\u003c/p>\u003c/li>\u003cli>\u003cp>\u003cstrong>L2 cache\u003c/strong> · 16 MiB, shared by six cores\u003c/p>\u003cp> A load takes tens of cycles. \u003ccode>packed\u003c/code> keeps \u003ccode>packA\u003c/code> here.\u003c/p>\u003c/li>\u003cli>\u003cp>\u003cstrong>DRAM\u003c/strong> · tens of GiB\u003c/p>\u003cp> A load takes hundreds of cycles. \u003ccode>packed\u003c/code> keeps \u003ccode>a, b, c\u003c/code> here.\u003c/p>\u003c/li>\u003c/ol>\n\u003cp>The bars are on a logarithmic scale, so each level is far larger than the bar suggests. The register capacity counts the 32 architectural 128-bit SIMD registers, not SME's matrix storage. Load times are illustrative orders of magnitude, not measurements.\u003c/p>\n\u003cp>The figure shows where \u003ccode>packed\u003c/code>, the CPU schedule from the post’s “Scheduling for the CPU” section, intends to keep each block. The checker uses the platform’s cache model to check that the blocks fit. That doesn’t guarantee they’ll stay there on real hardware: other accesses may evict them, and other processes may share the cache. The example uses small blocks for readability.\u003c/p>\n\u003cp>Note\u003c/p>\n\u003cp>Cache blocking has been around for a long time. The block sizes are chosen so that the working set stays in cache instead of being streamed from main memory. Kazushige Goto’s hand-tuned GotoBLAS took this further by also sizing blocks for the TLB, and its descendant OpenBLAS is still what a lot of numerical software runs on today.\u003c/p>\n\u003ch3 id=\"checking-a-traffic-budget\">Checking a traffic budget\u003c/h3>\n\u003cp>A caller can use a \u003ccode>movement\u003c/code> clause to limit how much traffic its calls are allowed to cause. Here is a function that multiplies two 32 × 32 matrices with \u003ccode>packed\u003c/code>, and states its budget:\u003c/p>\n\u003cpre>\u003ccode>cachetfn product\n (reads a: [f32; 32, 32])\n (reads b: [f32; 32, 32])\n (mut c: [f32; 32, 32])\n (mut packA: [f32; 16, 16] in PanelMajor 4 at DRAM)\n (mut packB: [f32; 16, 8] at DRAM)\nproduces Init c\nmovement\n traffic 8 * lines (span_bytes packB.span) from DRAM to L1 and back\n traffic 16 * lines (span_bytes packA.span) from DRAM to L2 and back\n=\n packed a b c packA packB\u003c/code>\u003c/pre>\n\u003cp>The checker must show that the call to \u003ccode>packed\u003c/code> fits this budget. Suppose we allowed only eight blocks to be copied into \u003ccode>packA\u003c/code>, writing \u003ccode>8\u003c/code> instead of \u003ccode>16\u003c/code> in the second row. The call is refused:\u003c/p>\n\u003cpre>\u003ccode>could not prove declared traffic row at DRAM:\n ceil (32 / 16) * ceil (32 / 8) * line_ceil bytes_0 128\n + ceil (32 / 16) * ceil (32 / 8) * ceil (32 / 16) * line_ceil bytes_1 128\n <= 8 * line_ceil bytes_0 128 + 8 * line_ceil bytes_1 128\ncounterexample: bytes_0 = 0, bytes_1 = 1\u003c/code>\u003c/pre>\n\u003cp>The extra copies come from the loop order. The blocks of columns, \u003ccode>gj\u003c/code>, are outside the blocks of rows, \u003ccode>gi\u003c/code>, so we repack A’s blocks for each block of columns. There are two depth blocks, four column blocks and two row blocks: 2 × 4 × 2 = 16 packs in all. We’ve only allowed eight. To make the check pass, we have to change the schedule or allow the extra traffic.\u003c/p>\n\u003ch3 id=\"simd-groups\">SIMD groups\u003c/h3>\n\u003cp>Note\u003c/p>\n\u003cp>Every vendor has a different name for SIMD groups. NVIDIA calls them \u003cem>warps\u003c/em>, a term borrowed from weaving, where the warp is the set of parallel threads on a loom. AMD calls them \u003cem>wavefronts\u003c/em> (traditionally 64 threads, though RDNA also supports 32), and Vulkan calls them \u003cem>subgroups\u003c/em>. “Lockstep” is also a bit of a simplification nowadays: since Volta, threads in an NVIDIA warp have their own program counters, and can diverge and reconverge more freely.\u003c/p>\n\u003ch3 id=\"reading-a-claim\">Reading a claim\u003c/h3>\n\u003cp>\u003ccode>cachetc scheduled\u003c/code> prints a claim after the generated function. Its first line says which computation the function is related to, and in what sense. For \u003ccode>swapped\u003c/code>, \u003ccode>bits of\u003c/code> means that its results are identical to \u003ccode>matmul\u003c/code>’s, including floating-point rounding, for inputs that satisfy the function’s requirements.\u003c/p>\n\u003cp>Some claims have extra lines. \u003ccode>arithmetic\u003c/code> names the device whose floating-point behaviour applies. \u003ccode>by\u003c/code> lists the algebraic laws the schedule uses. \u003ccode>trusted\u003c/code> lists additional assumptions the checker used but didn’t prove, such as a library law stated with a reason, or an instruction template implementing its reference body.\u003c/p>\n\u003cp>The distinction between library steps and built-in steps matters here. A library step such as \u003ccode>hoist\u003c/code> must prove its relation at each use. Built-in layout steps check their side conditions, but their rewrite rules are part of the compiler we trust. For supported host layouts, \u003ccode>cachetc scheduled --relate\u003c/code> can check the relation separately. An empty \u003ccode>trusted\u003c/code> list doesn’t remove our reliance on the compiler, its backend, or the hardware.\u003c/p>\n\u003cp>Resource requirements appear separately in the generated function’s declaration. \u003ccode>working_set\u003c/code> says what must fit in the named caches; \u003ccode>movement\u003c/code> describes the traffic. A caller must satisfy those requirements and any budget of its own. These checks use the platform’s memory model.\u003c/p>\n\u003ch3 id=\"a-library-step-and-its-proof\">A library step and its proof\u003c/h3>\n\u003cp>The \u003ccode>swapped\u003c/code> schedule uses \u003ccode>hoist (j, k) c\u003c/code> to move the sum’s steps outside the loop over output columns. The \u003ccode>cachet:steps\u003c/code> library defines the rewrite and its proof recipe together:\u003c/p>\n\u003cpre>\u003ccode>cachetstep fn hoist (j, k) c =\n from\n for j in $a .. $b do\n store $cell = fold k in $lo .. $hi from (load $cell) as $acc: $E do $step\n to\n for k in $lo .. $hi do\n for j in $a .. $b do\n let $acc = load $cell\n store $cell = $step[$acc]\n relate\n per cell c fold S.k\n per cell c fold T.k\n interchange S.j\u003c/code>\u003c/pre>\n\u003cp>\u003ccode>from\u003c/code> matches a loop over \u003ccode>j\u003c/code> that stores a sum into a cell. \u003ccode>cachetc\u003c/code> writes the sum as a \u003ccode>fold\u003c/code>: it starts from what the cell holds, \u003ccode>load $cell\u003c/code>, and updates the running total \u003ccode>$acc\u003c/code> once for each \u003ccode>k\u003c/code>. \u003ccode>to\u003c/code> runs the steps of the sum outside the loop over \u003ccode>j\u003c/code>, so each visit loads the total from its cell, updates it, and stores it back. In our schedule, \u003ccode>hoist (j, k) c\u003c/code> names the loop over \u003ccode>j\u003c/code>, the sum over \u003ccode>k\u003c/code> and the output \u003ccode>c\u003c/code>.\u003c/p>\n\u003cp>Names starting with \u003ccode>$\u003c/code> are pattern variables: they match parts of the original program. For example, \u003ccode>$step\u003c/code> is the code in the sum, and \u003ccode>$a\u003c/code>, \u003ccode>$b\u003c/code>, \u003ccode>$lo\u003c/code> and \u003ccode>$hi\u003c/code> are the loop bounds.\u003c/p>\n\u003cp>The last part, \u003ccode>relate\u003c/code>, tells the checker how to compare the original program, \u003ccode>S\u003c/code>, with the replacement, \u003ccode>T\u003c/code>. The first two lines read each sum as a sequence of updates to its cell of \u003ccode>c\u003c/code>, one for each \u003ccode>k\u003c/code>. The last asks the checker to show that moving the loop over \u003ccode>j\u003c/code> inside produces identical outputs. Different values of \u003ccode>j\u003c/code> update different cells of \u003ccode>c\u003c/code>, and the inputs are only read. Swapping \u003ccode>j\u003c/code> and \u003ccode>k\u003c/code> changes when we visit each output, but each output still receives its updates in ascending order of \u003ccode>k\u003c/code>.\u003c/p>\n\u003cp>The checker uses an SMT solver, an automated prover, to check the equivalence for the actual program being rewritten. Importing \u003ccode>hoist\u003c/code> doesn’t exempt it from the check: if we break its definition, the schedule is refused, as the \u003ca href=\"#panel-wrong\">side note on broken steps\u003c/a> shows.\u003c/p>\n\u003cp>Not every step needs this much. \u003ccode>interchange\u003c/code>, which \u003ccode>bands\u003c/code> uses to reorder its packing loops, swaps two loops and asks the checker to show that no iteration reads what another writes:\u003c/p>\n\u003cpre>\u003ccode>cachetstep fn interchange (i, j) =\n from\n for i in $A do\n for j in $B do\n $body\n to\n for j in $B do\n for i in $A do\n $body\n relate\n interchange S.i\u003c/code>\u003c/pre>\n\u003ch3 id=\"when-a-step-is-wrong\">When a step is wrong\u003c/h3>\n\u003cp>The library’s \u003ccode>hoist\u003c/code> step works, which doesn’t say much for the checker. Suppose we break it. We’ll copy it into our own program under a new name, keeping its \u003ccode>relate\u003c/code> proof recipe, and use the copy in place of \u003ccode>hoist\u003c/code> in \u003ccode>swapped\u003c/code>.\u003c/p>\n\u003cp>We start with an off-by-one, in a copy called \u003ccode>sloppy\u003c/code>, by changing a single line of \u003ccode>to\u003c/code>:\u003c/p>\n\u003cpre>\u003ccode>cachet for k in $lo + 1 .. $hi do\u003c/code>\u003c/pre>\n\u003cp>The schedule that calls it is refused:\u003c/p>\n\u003cpre>\u003ccode>could not prove relation swapped'1_sloppy: the loops at S.k and T.k run the same number of times\u003c/code>\u003c/pre>\n\u003cp>\u003ccode>S\u003c/code> and \u003ccode>T\u003c/code> are the programs before and after the step, as in \u003ccode>hoist\u003c/code>’s \u003ccode>relate\u003c/code>, and \u003ccode>swapped'1\u003c/code> is the program the step starts from, after \u003ccode>zero\u003c/code>.\u003c/p>\n\u003cp>That one is easy to spot by hand. Here’s one that isn’t. In a copy called \u003ccode>backwards\u003c/code>, we keep the loop bounds but change its body to visit the products in reverse order. \u003ccode>$step[$acc][k := e]\u003c/code> replaces \u003ccode>k\u003c/code> with \u003ccode>e\u003c/code> in the matched sum’s body:\u003c/p>\n\u003cpre>\u003ccode>cachet store $cell = $step[$acc][k := $hi - 1 - (k - $lo)]\u003c/code>\u003c/pre>\n\u003cp>Every product is still added exactly once, and the loop nest it writes out is a correct matrix multiplication over the reals. In floating point, the additions happen in the opposite order, so they round differently:\u003c/p>\n\u003cpre>\u003ccode>could not prove relation swapped'1_backwards: the two runs hold the same words in parameter 3 after each iteration of the loops at S.j and T.j\u003c/code>\u003c/pre>\n\u003cp>Parameter 3 is \u003ccode>c\u003c/code>: the checker couldn’t establish that its contents are identical after the rewrite. Notice that this is a failed proof, rather than a proof that the kernel is wrong: the checker reports “a model the search cannot rule out”. It’s refused all the same, because the burden of proof is on the step.\u003c/p>\n\u003cp>There’s also the requirement that \u003ccode>c\u003c/code> can’t overlap \u003ccode>a\u003c/code> or \u003ccode>b\u003c/code>. A call already has to prove this, without a schedule getting involved. Passing the same matrix as an input and as the output, as in \u003ccode>matmul a b a\u003c/code>, is refused at the call:\u003c/p>\n\u003cpre>\u003ccode>could not prove the call of matmul lends parts of one whole at once, which must be apart: Disjoint (interval (allocated region) 0 (1024 * sizeof f32)) (interval (allocated region) 0 (1024 * sizeof f32))\u003c/code>\u003c/pre>\n\u003cp>The checker has caught the missing iteration, the reversed sum and the overlapping arrays. The backwards loop is the interesting one, though. Neither order is more accurate in general, but we asked for identical results, so the rewrite is refused. Sometimes a different order is exactly what makes a kernel fast, as it is for attention near the end of the post.\u003c/p>\n\u003cp>These examples use library steps, whose relations are checked at each use. The \u003ca href=\"#panel-claim\">claim panel\u003c/a> explains how this differs from built-in layout steps, and how the compiler reports any library laws or instruction templates it takes on trust.\u003c/p>\n\u003ch3 id=\"fusing-an-epilogue\">Fusing an epilogue\u003c/h3>\n\u003cp>A layer of a neural network usually does something to the product before storing it, such as a ReLU, which replaces negative values with zero. In Cachet, that’s part of the contraction:\u003c/p>\n\u003cpre>\u003ccode>cachetcontraction layer\n (reads a: [f32; M, K])\n (reads b: [f32; K, N])\n -> out c: [f32; M, N] =\n c[i, j] = max (sum k. a[i, k] * b[k, j]) 0.0\u003c/code>\u003c/pre>\n\u003cp>We can apply \u003ccode>tiled\u003c/code>’s two steps to this contraction too. Only the last line of the resulting kernel changes:\u003c/p>\n\u003cpre>\u003ccode>cachet t = mma x y t\n store ct_2 = max t 0.0\u003c/code>\u003c/pre>\n\u003cp>The ReLU is applied to the accumulator tile while the SIMD groups still hold it, so the product is never written to memory and read back. We didn’t have to ask for this. A contraction’s equations describe values, not buffers, so an intermediate only gets storage of its own if a schedule asks for it. The same guarantee applies here: the kernel produces exactly the same result as \u003ccode>layer\u003c/code> evaluated using the GPU’s arithmetic.\u003c/p>\n\u003ch3 id=\"the-running-summary-for-attention\">The running summary for attention\u003c/h3>\n\u003cp>\u003ca href=\"https://arxiv.org/abs/2205.14135\" rel=\"nofollow ugc noopener\">FlashAttention\u003c/a> avoids storing the full score matrix by keeping a running summary: the largest score so far, \u003ccode>m\u003c/code>, a sum \u003ccode>l\u003c/code> of weights \u003ccode>e^(s - m)\u003c/code>, and a sum \u003ccode>o\u003c/code> of those weights times the values. When a later block raises the maximum, we rescale both totals by the same factor. Over the reals, this leaves their ratio \u003ccode>o / l\u003c/code> unchanged, so we can adjust the old summary without going back to the old scores. Then we add the new block’s contributions and carry on.\u003c/p>\n\u003cp>The \u003ccode>cachet:attention\u003c/code> library puts these operations in \u003ccode>Online\u003c/code>, an implementation of the \u003ccode>Monoid\u003c/code> interface. A \u003cem>monoid\u003c/em> provides an empty value and an associative operation for combining values. For these summaries, associativity holds over the reals. To combine two summaries, we rescale both to their shared maximum and add them:\u003c/p>\n\u003cpre>\u003ccode>cachetimpl Monoid for Online where\n const Value = Weights\n fn empty () = Weights { m = -Num.infinity (), l = -0.0, o = -0.0 }\n fn combine (a: Weights) (b: Weights) =\n let m = max a.m b.m\n let x = rescale a.m m\n let y = rescale b.m m\n Weights { m, l = a.l * x + b.l * y, o = a.o * x + b.o * y }\u003c/code>\u003c/pre>\n\u003cp>The final weighted value is \u003ccode>o / l\u003c/code>, which the library calls \u003ccode>normalised\u003c/code>. \u003ccode>key s v\u003c/code> makes the summary of a single key, with score \u003ccode>s\u003c/code> and value \u003ccode>v\u003c/code>.\u003c/p>\n\u003cp>To regroup this reduction, the checker needs laws for these operations. For \u003ccode>PlusTimes f32\u003c/code>, Cachet proves the \u003ca href=\"#panel-semiring\">semiring laws\u003c/a> for the corresponding real-number operations. It doesn’t prove \u003ccode>Online\u003c/code>’s laws. The library states them with reasons, which the checker takes on trust.\u003c/p>\n\u003cp>The algebra behind combining summaries is that \u003ccode>(m, l, o)\u003c/code> represents the pair \u003ccode>(e^m l, e^m o)\u003c/code>, and combining summaries adds these pairs. The library also states a \u003cem>block law\u003c/em>, which lets a schedule add a whole block of keys at once:\u003c/p>\n\u003cpre>\u003ccode>cachet law associative over reals = "(m, l, o) stands for (e^m l, e^m o), which combine adds"\n law block over reals = "a block's terms, each e^(s - m2) at the block's largest score m2, add to the summary rescaled to m2 as combine adds them"\u003c/code>\u003c/pre>\n\u003cp>The reasons in these declarations are shortened from the library’s. They explain the algebra, but aren’t proofs checked by the compiler.\u003c/p>\n\u003ch3 id=\"reproducibility\">Reproducibility\u003c/h3>\n\u003cp>Note\u003c/p>\n\u003cp>Running the same computation with different schedules doesn’t always give identical results. GPU libraries often split a reduction across threads and combine the partial sums with atomics, which makes the order (and so the result) vary from run to run. This is why frameworks like PyTorch have a separate “deterministic algorithms” mode, which is often slower. In Cachet, a schedule that changes the order says so in its contraction, and the shadow shows exactly which order it uses.\u003c/p>\n\u003ch3 id=\"related-work\">Related work\u003c/h3>\n\u003cp>\u003ca href=\"https://halide-lang.org/\" rel=\"nofollow ugc noopener\">Halide\u003c/a> separates an image-processing algorithm from its schedule: the algorithm says what each pixel is, and the schedule chooses the order, tiling, vectorisation and parallelism. \u003ca href=\"https://arxiv.org/abs/1802.04799\" rel=\"nofollow ugc noopener\">TVM\u003c/a> brought the same idea to deep learning; its \u003ccode>tensorize\u003c/code> step matches a computation against the description of a hardware intrinsic and replaces it with that intrinsic, much like using the reference body of \u003ccode>simdgroup_mma8\u003c/code>.\u003c/p>\n\u003cp>The closest relative to what I’m trying to do here is \u003ca href=\"https://exo-lang.dev/\" rel=\"nofollow ugc noopener\">Exo\u003c/a>: the programmer chooses the transformations, and the compiler checks them. \u003ca href=\"https://arxiv.org/abs/2411.07211\" rel=\"nofollow ugc noopener\">Exo 2\u003c/a> lets users build scheduling libraries by composing a small set of trusted primitives. Cachet’s library steps also put rewrites in user code, with a relation to check at each use.\u003c/p>\n\u003cp>Index notation has precedents too. \u003ca href=\"https://arxiv.org/html/1802.04730v3#S3\" rel=\"nofollow ugc noopener\">Tensor Comprehensions\u003c/a> generalises Einstein notation for tensor computations. \u003ca href=\"https://github.com/tensor-compiler/taco/blob/master/include/taco/index_notation/README.md\" rel=\"nofollow ugc noopener\">TACO\u003c/a> supports index equations and scheduling operations, including for sparse tensors. \u003ca href=\"https://arxiv.org/abs/2104.05372\" rel=\"nofollow ugc noopener\">Dex\u003c/a> makes index sets part of its type system. Matrix operations with different choices of addition and multiplication are central to \u003ca href=\"https://raw.githubusercontent.com/DrTimothyAldenDavis/GraphBLAS/stable/Doc/GraphBLAS_UserGuide.pdf\" rel=\"nofollow ugc noopener\">GraphBLAS\u003c/a>, where a semiring supplies those operations.\u003c/p>\n\u003cp>The treatment of floating point is where the projects diverge. \u003ca href=\"https://futhark-lang.org/examples/scan-reduce.html\" rel=\"nofollow ugc noopener\">Futhark’s \u003ccode>reduce\u003c/code>\u003c/a> requires an associative operator and a neutral element, but does not verify those laws. Cachet asks for permission to regroup in the contraction, with \u003ccode>[reassoc]\u003c/code>. It then checks the kernel against the exact arithmetic order in its shadow, and relates that shadow to the original contraction using the stated laws.\u003c/p>\n\u003cp>\u003ca href=\"https://triton-lang.org/main/programming-guide/chapter-1/introduction.html\" rel=\"nofollow ugc noopener\">Triton\u003c/a> and \u003ca href=\"https://hazyresearch.stanford.edu/blog/2024-05-12-tk\" rel=\"nofollow ugc noopener\">ThunderKittens\u003c/a> expose blocks or tiles directly to the programmer. This is roughly the level of Cachet’s grids and tiles; contractions and schedules provide a way to construct those programs from a separate definition.\u003c/p>\n\u003cp>That lower layer is still needed. Contractions describe matrix multiplication, convolutions written as contractions, and attention with a monoid like \u003ccode>Online\u003c/code>. But a kernel that stages inputs through shared memory with explicit barriers still needs to be written directly with grids and tiles.\u003c/p>\n\u003ch3 id=\"the-complete-example\">The complete example\u003c/h3>\n\u003cp>\u003ca href=\"https://blog.csongor.co.uk/code/cachet-contractions.cachet\" rel=\"nofollow ugc noopener\">The complete example\u003c/a> uses the final, generic \u003ccode>matmul\u003c/code> throughout, including for \u003ccode>rows\u003c/code>, \u003ccode>swapped\u003c/code>, and \u003ccode>tiled\u003c/code>. The early \u003ccode>f32\u003c/code> examples correspond to binding \u003ccode>S\u003c/code> to \u003ccode>PlusTimes f32\u003c/code>.\u003c/p>\n\u003cp>The file contains the matrix-multiplication schedules compared in the overview; attention is separate. Its \u003ccode>main\u003c/code> compares \u003ccode>rows\u003c/code>, \u003ccode>swapped\u003c/code>, \u003ccode>tiled\u003c/code>, \u003ccode>tower\u003c/code> and \u003ccode>packed\u003c/code> with \u003ccode>matmul\u003c/code> on the same \u003ccode>f32\u003c/code> inputs. The larger \u003ccode>fast\u003c/code>, \u003ccode>bands\u003c/code>, \u003ccode>sme\u003c/code> and \u003ccode>big_tiles\u003c/code> schedules are defined here but aren’t called by \u003ccode>main\u003c/code>; the benchmark checks that their results match \u003ccode>matmul\u003c/code> exactly.\u003c/p>\n\u003cp>The file starts by naming the platform, which is where \u003ccode>M4Gpu\u003c/code> comes from:\u003c/p>\n\u003cpre>\u003ccode>cachetmodule (platform = AppleSilicon)\nimport "../../platforms/apple-silicon.cachet"\nimport "cachet:monoid"\nimport "cachet:simd"\nimport "cachet:steps"\nimport "../../examples/lib/panel-major.cachet"\u003c/code>\u003c/pre>\n\u003cp>Cachet’s compiler isn’t public yet, so the file is here to read rather than to run. We ran it twice: once in Cachet’s interpreter, and once as a native executable on an M4 Max Mac, where its GPU grids use Metal. Both printed:\u003c/p>\n\u003cpre>\u003ccode>1.751874327659607\n0\n0\n0\n0\n0\n3.0\u003c/code>\u003c/pre>\n\u003cp>The first line is an element of the product. The next five lines show how many output elements differ from \u003ccode>matmul\u003c/code> for \u003ccode>rows\u003c/code>, \u003ccode>swapped\u003c/code>, \u003ccode>tiled\u003c/code>, \u003ccode>tower\u003c/code> and \u003ccode>packed\u003c/code>. The comparison is bit for bit, and all five counts are zero. The next line is the shortest path from node 0 to node 2 in a ring, computed by \u003ccode>matmul\u003c/code> at \u003ccode>MinPlus f32\u003c/code>.\u003c/p>\n\u003cp>Note\u003c/p>\n\u003cp>These are correctness examples. The sizes here are small; the \u003ca href=\"#comparing-the-results\">performance measurements\u003c/a> use the same schedules at 1024 × 1024 and larger.\u003c/p>\n\u003ch2 id=\"footnotes\">Footnotes\u003c/h2>\n\u003col>\u003cli>In some cases, such as sums of floating-point numbers, the preservation does not strictly hold. In these cases, we can tell the compiler that we’re willing to treat floating-point addition as associative, which then lets us split a sum across threads. \u003ca href=\"#user-content-fnref-asterisk\">↩\u003c/a>\u003c/li>\u003cli>Billions of floating-point operations per second, counting a multiply-add as two operations. \u003ca href=\"#user-content-fnref-gflops\">↩\u003c/a>\u003c/li>\u003cli>When all you have is a hammer… \u003ca href=\"#user-content-fnref-hammer\">↩\u003c/a>\u003c/li>\u003cli>A grid without \u003ccode>on\u003c/code> runs on the host. A built executable runs its outermost loop on several threads, while Cachet’s interpreter runs the iterations in order. Since no iteration can observe another’s effects, both produce identical results. \u003ca href=\"#user-content-fnref-host\">↩\u003c/a>\u003c/li>\u003c/ol>","headings":[{"level":1,"text":"Write your own kernel optimiser","id":"write-your-own-kernel-optimiser"},{"level":2,"text":"Matrix multiplication by hand","id":"matrix-multiplication-by-hand"},{"level":2,"text":"Say what (not how)","id":"say-what-not-how"},{"level":3,"text":"Rewriting the loop nest","id":"rewriting-the-loop-nest"},{"level":2,"text":"Blocking matrix multiplication","id":"blocking-matrix-multiplication"},{"level":3,"text":"Working through a sum in chunks","id":"working-through-a-sum-in-chunks"},{"level":3,"text":"Reusing inputs across outputs","id":"reusing-inputs-across-outputs"},{"level":2,"text":"Scheduling for the CPU","id":"scheduling-for-the-cpu"},{"level":2,"text":"Making it fast","id":"making-it-fast"},{"level":3,"text":"How much data are we moving?","id":"how-much-data-are-we-moving"},{"level":3,"text":"Tuning the kernel","id":"tuning-the-kernel"},{"level":3,"text":"Using the other cores","id":"using-the-other-cores"},{"level":3,"text":"CPU matrix units","id":"cpu-matrix-units"},{"level":2,"text":"Scheduling for the GPU","id":"scheduling-for-the-gpu"},{"level":3,"text":"Independent outputs","id":"independent-outputs"},{"level":3,"text":"Tiles","id":"tiles"},{"level":3,"text":"Larger tiles","id":"larger-tiles"},{"level":2,"text":"Comparing the results","id":"comparing-the-results"},{"level":2,"text":"Attention","id":"attention"},{"level":2,"text":"Conclusion","id":"conclusion"},{"level":2,"text":"Background","id":"background"},{"level":3,"text":"Matrix multiplication","id":"matrix-multiplication"},{"level":3,"text":"Cache lines","id":"cache-lines"},{"level":3,"text":"What the blocks need","id":"what-the-blocks-need"},{"level":3,"text":"Matrix hardware","id":"matrix-hardware"},{"level":3,"text":"The GPU matrix instruction","id":"the-gpu-matrix-instruction"},{"level":3,"text":"Fused multiply-add","id":"fused-multiply-add"},{"level":3,"text":"Checking parallel writes","id":"checking-parallel-writes"},{"level":3,"text":"Where the blocks live","id":"where-the-blocks-live"},{"level":3,"text":"Checking a traffic budget","id":"checking-a-traffic-budget"},{"level":3,"text":"SIMD groups","id":"simd-groups"},{"level":3,"text":"Reading a claim","id":"reading-a-claim"},{"level":3,"text":"A library step and its proof","id":"a-library-step-and-its-proof"},{"level":3,"text":"When a step is wrong","id":"when-a-step-is-wrong"},{"level":3,"text":"Fusing an epilogue","id":"fusing-an-epilogue"},{"level":3,"text":"The running summary for attention","id":"the-running-summary-for-attention"},{"level":3,"text":"Reproducibility","id":"reproducibility"},{"level":3,"text":"Related work","id":"related-work"},{"level":3,"text":"The complete example","id":"the-complete-example"},{"level":2,"text":"Footnotes","id":"footnotes"}]}}