Tiling Through Shared Memory and Overlapping the Load

Shared memory earns its place by being the right size for the job: too large to fit everything, too small to hold nothing, and fast enough that a programmer will accept the bookkeeping. Nearly all of the bookkeeping reduces to one ratio, bytes read from a slower level per arithmetic operation performed, and nearly all of the tuning questions are that ratio under different names. This is the arithmetic that decides whether a tile is 16, 32, or 64 elements on a side, and it is also the arithmetic that shows why a scratchpad alone is not enough.

Reuse expressed as bytes per float

Take an operation where every output depends on a row and a column of inputs, which describes matrix multiplication and, in a looser sense, direct convolution and stencil codes. Without any staging, each thread computing one output reads its whole row and column from global memory. Neighbouring threads read overlapping data, so the same bytes are fetched many times, and the total traffic is proportional to the size of the problem raised to a power above one.

Staging fixes this by making each byte serve many threads. A block that loads an N by N tile of one operand and an N by N tile of the other into shared memory, and then advances through the reduction dimension in steps of k, moves 2Nk values per step and performs 2N²k floating-point operations, counting a multiply and an add separately. The traffic per operation is therefore 4/N bytes per floating-point operation when values are four bytes wide. A 32-by-32 tile moves one eighth of a byte per operation. A 64-by-64 tile moves half that. The relationship is a formula, not a measurement, and it holds on any machine.

What it means concretely is that a block of 256 threads can cover a working set far larger than the sum of its registers, provided the working set stays inside the scratchpad and the accesses to it are conflict-free. It also means that doubling the tile size halves the global traffic but quadruples the scratchpad footprint and, if the block is fixed in threads, quadruples the per-thread work per step. Tile size is the knob that trades occupancy for arithmetic intensity.

A second level of reuse, in registers

The scratchpad itself has a bandwidth limit, and in a well-tiled kernel it is often reached before the same kernel runs out of global bandwidth. The fix is a second level of reuse, entirely inside threads. If each thread computes a c by r rectangle of the output rather than a single element, then for each step along the reduction dimension it reads c + r values from shared memory and performs c·r multiply-accumulate operations. The shared-memory traffic is 4·(c + r)/(c·r) bytes per multiply-accumulate, so a 2 by 2 register tile halves the scratchpad traffic per product and an 8 by 8 tile reduces it eightfold, all at the same block size and the same loop length.

// Inner step of a tiled multiply-accumulate with a 2 by 2 register tile.
// Each shared-memory word read feeds two products: four reads, four MACs.
for (int k = 0; k < TILE_K; ++k) {
    float a0 = a_shared[ty * TILE_K + k];          // one shared read
    float a1 = a_shared[(ty + 1) * TILE_K + k];    // one shared read
    float b0 = b_shared[k * TILE_N + tx];          // one shared read
    float b1 = b_shared[k * TILE_N + tx + 1];      // one shared read
    acc00 += a0 * b0;  acc01 += a0 * b1;          // four products, no memory
    acc10 += a1 * b0;  acc11 += a1 * b1;
}

Four shared-memory reads feed four multiply-accumulates, which is the c + r over c·r ratio with c = r = 2. Widening the register rectangle to 8 by 8 takes sixteen reads per cycle of the loop and sixty-four products from them, and the loop over the reduction dimension is the same length in both cases. Register pressure is the limit: the accumulators alone occupy c·r registers, and every doubling of the rectangle’s side quadruples the accumulator count each thread carries. There is a documented ceiling on registers per thread that caps the rectangle, and past it the compiler spills to local memory, which puts the values back into memory and forfeits the gain.

Overlapping the load with the arithmetic

A tiled kernel that loads a tile, synchronizes, computes, synchronizes, and loads the next tile has a stall in every iteration. The stall equals the latency of the global load, and the load cannot begin until the previous tile has been fully consumed because both tiles would occupy the same scratchpad region. With a single buffer, a block of 256 threads on a machine with a long DRAM latency can spend most of each step waiting.

The remedy is to hold two buffers: one being read by the arithmetic, one being filled by the memory system. The load for step i+1 is issued before step i is computed, so the latency of the fill is absorbed by the work. This costs one extra tile of scratchpad per pipelined operand and turns the loop from a sequence of stalls into a pipeline whose depth is the number of buffers.

On architectures that provide an asynchronous copy path from global memory into shared memory without routing through registers, the overlap is expressible directly. The copy is issued, explicitly committed as a group, and later waited on by the consumer, so the compiler does not have to hoist the load and hope. The pattern that the hardware supports well is a fixed number of stages, each with its own buffer, with the wait structured so that the stage about to be consumed is the one that was committed long enough ago. Three or four stages are enough to cover a long latency; each adds one tile of shared memory per operand and one turn of the loop.

Without the asynchronous path, double buffering is still possible: the compiler can issue the loads into registers early and write them to the alternate buffer before the barrier. That costs registers instead of scratchpad and is limited by how many outstanding loads a thread can hold. The two costs are the currency of the same trade, and the version with the dedicated copy path moves the burden off the register file.

Where the tile size stops helping

The tile shapes that keep a warp’s accesses conflict-free at every phase of the loop are the ones that survive. A tile whose row pitch is a multiple of the bank count, combined with a register rectangle that reads down a column of it, reintroduces the serialization described in the bank conflict analysis, and it does so in the loop that was supposed to be the fast part. The same care that goes into the global load must go into the scratchpad read.

The overlap also depends on how the load itself is structured. A tile whose elements arrive out of order must be assembled before use, and shared memory has no notion of a partially valid line: the barrier is the only mechanism that says the data is ready. Every stage therefore costs one synchronization of the block, and the number of blocks per SM divides the work available to hide it. A kernel with few blocks per SM and a deep pipeline therefore tends to trade a stage of buffering for a resident block.

Finally, the whole scheme is bounded by the size of the scratchpad and by the choice of how much of the unified L1 and shared array each block may use. Beyond the per-block allowance, the launch must request a larger carve-out, and that request reduces the number of blocks that can be resident. The relevant constraint is not the raw array size but the number of blocks per SM that survives the division, which is why tile sizes are often chosen from the occupancy target backwards rather than from the arithmetic-intensity target forwards, and why the optimal shape for a given part is not the optimal shape for its successor.