Write your own kernel optimiser
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.
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
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.
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. An optimising compiler makes these decisions based on a model of the hardware that’s hidden from the source language. In hand-optimised code, we keep these in our head, or in comments in the source file.
When performance matters, I would rather not have a clever compiler. Instead, I want the compiler to be explicit. That’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.
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.
This post is about the transformations themselves. In Cachet, we write down what to compute and, separately, how to compute it. A sequence of transformations, a schedule, turns the computation into an optimised program. The compiler then checks that each transformation preserves the meaning of the original.1
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.
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.
Matrix multiplication is very easy to do correctly, but notoriously difficult to do quickly. The definition fits on one line:
c[i, j] = sum k. a[i, k] * b[k, j]
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:
c// c starts out as all zeroes for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) for (int k = 0; k < K; k++) c[i][j] += a[i][k] * b[k][j];
2
Billions of floating-point operations per second, counting a multiply-add as two operations.
This loop nest reaches just 1.17 GFLOP/s2 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:
100% = OpenBLAS · CPU · one core · 108 GFLOP/s
The colours show how often each variable changes: i the least, j more often, and k on every multiplication. The hottest variable controls how the inner loop moves through the arrays. Here, k walks along a row of a, but down a column of b.
The arrays are stored row by row: b[0][0], b[0][1], and so on, followed by the next row. This is called row-major order. The processor doesn’t fetch single values. When a value isn’t in its cache (the small, fast memory close to the core), it fetches a whole chunk of neighbouring bytes called a cache line. Reading those neighbours can then use the cached copy, avoiding another trip to main memory.
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:
Each row of squares is a row of b, 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.
This cache model 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.
We can get the row-wise access pattern just by swapping the two inner loops:
c// c starts out as all zeroes for (int i = 0; i < M; i++) for (int k = 0; k < K; k++) for (int j = 0; j < N; j++) c[i][j] += a[i][k] * b[k][j];
The hottest variable is now j, the last subscript of b and c, so the inner loop walks along their rows, using neighbouring values while their line is still cached. (a[i][k] stays the same throughout that loop.) For large matrices, this makes a big difference:
100% = OpenBLAS · CPU · one core · 108 GFLOP/s
Swapping the loops makes the same multiplication about 28 times faster, though it’s still only 30% of OpenBLAS’s speed on one core.
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 shortly, keeps a block of inputs in cache until we’ve done as much work with it as possible.
Swapping loops doesn’t preserve a program’s meaning in general, though. Here, provided c doesn’t overlap either input, different values of j update different outputs. Each output still receives the same products in ascending order of k; 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.
We’d like the compiler to check these conditions for us.
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.3
We can now write the definition as a Cachet function, starting with ordinary 32-bit floats:
cachetcontraction matmul (reads a: [f32; M, K]) (reads b: [f32; K, N]) -> out c: [f32; M, N] = c[i, j] = sum k. a[i, k] * b[k, j]
This is a contraction: a function defined by an equation for each output element. The body is the formula we started with. [f32; M, K] is an array with M rows and K columns, and reads lets the function read it. -> out c names the result: the caller provides space for c, and matmul fills it.
M, K, and N are the dimensions. The equation tells us which outputs are independent, which inputs to add up, and which operations to use:
Since the free indices say nothing about order, the outputs can be computed in any order, or all at once.
A contraction has a precise meaning as a loop nest. You can ask Cachet’s compiler, cachetc, to print it with cachetc scheduled.
A schedule 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.
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. ... leaves out code that isn’t relevant to the step:
schedule swapped of matmul = zero (i, j) c hoist (j, k) c
← PreviousNext →for i in 0 .. M do for j in 0 .. N do var acc'0: f32 = -0.0 for k in 0 .. K do acc'0 = fma (load a[i, k]) (load b[k, j]) acc'0 store c[i, j] = acc'0
for zi in 0 .. M do for zj in 0 .. N do store c[zi, zj] = -0.0 for i in 0 .. M do for j in 0 .. N do for k in 0 .. K do let acc'0 = load c[i, j] store c[i, j] = fma ... acc'0
for zi in 0 .. M do for zj in 0 .. N do store c[zi, zj] = -0.0 for i in 0 .. M do for k in 0 .. K do for j in 0 .. N do let acc'0 = load c[i, j] store c[i, j] = fma ... acc'0
Each output adds up its products in ascending order of k, starting from zero.
100% = OpenBLAS · CPU · one core · 108 GFLOP/s
zero 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.
100% = OpenBLAS · CPU · one core · 108 GFLOP/s
hoist 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.
100% = OpenBLAS · CPU · one core · 108 GFLOP/s
In the starting loop nest, load reads a value and store writes one. The running total, acc'0, starts from zero, written -0.0 for a reason the semiring panel explains, and is stored once at the end. Each step uses a fused multiply-add: fma a b acc computes a * b + acc with a single rounding, rather than rounding the product separately.
This is the behaviour a schedule must preserve: each output receives the same chain of multiply-adds, in ascending order of k.
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 k. Its total has to survive between visits.
The first step, zero (i, j) c, prepares for this. It writes zero to every element of c 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.
Now hoist (j, k) c moves the steps of the sum outside the loop over j. Each visit loads a cell’s total, adds the next product, and stores it back.
After both steps, the line at the bottom summarises the schedule’s claim: what the compiler has checked. Here, swapped and matmul’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 matmul, so we call it as swapped a b c.
The hoist we used for matmul is a step function from the cachet:steps library: a rewrite with a proof recipe. Its definition 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.
Most other steps are defined in cachet:steps in the same way. A few layout steps, such as split and order, are built into the compiler.
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.
The inner kernel alone can take hundreds of lines: BLIS’s double-precision kernel for Haswell 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.
The struct
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。