Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Rim, a hermit crab, carries on its back a square frame of 4 by 4 cells: the 4 inner cells are blue and the ring of 12 cells around them is amber, with the 4 corner cells gray. Behind it lies the sandy grid of a heated plate, with the same 4 by 4 square marked out where Rim lifted it. A tag says load the tile and its halo once.

Chapter 20: Tiled Stencils with Halo Cells

Recall that in the Jacobi kernel of Chapter 19, every thread reads its 4 neighbors from global memory, so every value of the grid is read by up to 4 different threads. In Chapter 17, we removed exactly this kind of repetition from the matrix product. The threads of a block copied a piece of the input into shared memory once, and then every thread read its operands from that copy. A stencil can be tiled in the same way, with 1 complication: the cells that a block computes need neighbors that belong to other blocks.

In this chapter, we derive the tiled stencil kernel on the 6 × 6 plate of Chapter 19. We first count how often the direct kernel reads each value. We then define the tile and its halo, compare 2 ways of loading the halo, and break the kernel twice, once without its barrier and once without its halo, to show the exact wrong values that appear. After that, we count the memory traffic as a function of the tile size and measure the result. The measurement holds a lesson of its own. On GPUs whose caches already capture the reuse, the tile saves little traffic and costs instructions. Finally, we study temporal blocking, which performs several steps on each tile and so obtains more reuse, and we measure it as well.

This chapter covers

  • how many times the direct kernel reads each value of the grid
  • tiles, halo cells, and the 2 standard ways of loading a halo
  • the barrier between loading and computing, and the wrong values without it
  • a missing halo and the wrong values it produces
  • a proof that the tiled kernel computes the same grid as the direct one
  • loads per result as a function of the tile size, \((T + 2)^2 / T^2\)
  • why tiling a 5-point stencil gains little on GPUs with large caches
  • temporal blocking: several steps per load, and how its halo grows

The code of the chapter is in code/oxide/ch20_stencil_tiled/ for Rust and in code/cuda/ch20_stencil_tiled/ for C++. We use the notation of Chapter 19: \(u\) is the old grid that a step reads, \(v\) the new grid that it writes, \(W\) and \(H\) are the width and height of the grid, and \([a, b)\) is the range of integers from \(a\) to \(b - 1\).

20.1 Counting the reads

20.1.1 The plate and the direct kernel

We use the plate of Chapter 19, which has 6 × 6 cells, with the top edge held at 100 and the other edges at 0. Consider step 2, which reads the grid after step 1 and writes the grid of step 2. In the grid after step 1, row 1 holds 25 and every other interior cell holds 0. Recall that in the direct kernel of Chapter 19, the thread of each interior cell \((r, c)\) reads the 4 values \(u_{r-1,c}\), \(u_{r+1,c}\), \(u_{r,c-1}\) and \(u_{r,c+1}\) from global memory, which are the values above, below, to the left and to the right of the cell, and writes their mean. For example, the thread of cell (2, 2) reads 25, 0, 0 and 0 and writes 6.25.

20.1.2 Each value is read by its neighbors

So far, we have counted the reads of 1 thread. To find the repetition, we now count the other way round and ask, for 1 value of the old grid, how many threads read it. The value \(u_{2,2}\) is a neighbor of the cells (1, 2), (3, 2), (2, 1) and (2, 3). All 4 of them are interior cells, so 4 threads read \(u_{2,2}\), and each of them fetches it from global memory on its own, as shown in Figure 20.1. A value next to the boundary is read fewer times, because some of its neighbors are boundary cells, which have no thread that computes them. Thus \(u_{1,1}\) is read by 2 threads, \(u_{1,2}\) by 3, and a boundary value such as \(u_{0,2} = 100\) by 1.

Left: the 6 by 6 plate after step 1. Value u(2,2) is highlighted and 4 arrows lead from it to the threads of cells (1,2), (3,2), (2,1) and (2,3), each of which fetches it from global memory. Right: the same plate with the number of threads that read each value: 4 in the 4 center cells, 3 along the edges of the interior, 2 in the interior corners, 1 in the boundary cells next to the interior, 0 in the 4 corners of the plate. Totals: 64 reads of 32 different values.
Figure 20.1 In the direct kernel, value \(u_{2,2}\) is fetched by 4 threads. Over a step, 16 threads make 64 reads of 32 different values.

Let us add up these counts over the whole plate. The 4 center values are read 4 times each, and the 8 other values along the edges of the interior are read 3 times each. The 4 corners of the interior are read 2 times each, and the 16 boundary values next to the interior are read once each. In total, the step makes \(16 + 24 + 8 + 16 = 64\) reads of 32 different values. On a large grid, nearly every value lies far from the boundary, so the direct kernel fetches nearly every value 4 times. A step on a 4096 × 4096 grid thus requests 67 million values, or 268 MB, to read 16.7 million different values, or 67 MB.

Key observation The 4 threads that read \(u_{2,2}\) compute 4 neighboring cells. If those threads belong to the same block, one of them can copy \(u_{2,2}\) into shared memory, and the other 3 can read it from there.

In Chapter 19, we found that the caches already serve many of these repeated reads. The tile makes the reuse explicit instead of leaving it to the caches, and we measure the difference between the 2 in Section 20.7.

Exercises

20.1 How many threads read \(u_{3,1}\) in a step of the plate? Which ones?
20.2 For a grid of \(W \times H\) cells, how many reads does a step of the direct kernel make, and how many different values does it read?

20.2 Tiles and halos

20.2.1 The cells a block needs

To turn the observation into an algorithm, we divide the plate among blocks. For the worked example, we use blocks of \(2 \times 2\) threads with one thread per cell, so the 6 × 6 cells need \(3 \times 3 = 9\) blocks. The programs use blocks of 32 × 8 threads, and everything below carries over to them. We follow block (1, 1), which computes the 4 center cells (2, 2), (2, 3), (3, 2) and (3, 3), as shown in Figure 20.2.

The 6 by 6 plate cut into 9 blocks of 2 by 2 cells, 1 color per block. Block (1, 1) owns cells (2,2), (2,3), (3,2) and (3,3). Its tile, the 4 by 4 square of rows 1 to 4 and columns 1 to 4, is outlined: the 4 owned cells in the middle and 12 cells around them, which belong to the 8 neighboring blocks.
Figure 20.2 9 blocks of 2 × 2 threads. Block (1, 1) computes the 4 center cells and needs the 4 × 4 square around them.

To compute its 4 cells, block (1, 1) needs their neighbors. Some of these neighbors are the block’s own cells; cell (2, 2), for example, has cells (2, 3) and (3, 2) as neighbors. The others lie directly above, below, to the left and to the right of the block’s square, such as cell (1, 2) above cell (2, 2), and they belong to the 4 neighboring blocks. The block copies all of these values into shared memory once. The simplest arrangement copies the whole square of rows 1 to 4 and columns 1 to 4, which holds 16 values. Of these, the 4 corner values (1, 1), (1, 4), (4, 1) and (4, 4) are copied but never read, because a 5-point stencil does not use diagonal neighbors.

Definition 20.1 Shared memory. Shared memory is a memory on each SM that belongs to 1 block. Every thread of the block can read and write it, no other thread can, it responds within a few cycles, and values enter it only when the threads of the block store them there.

Example. The block of 32 × 8 threads in our programs keeps a tile of 34 × 10 floats, 1,360 bytes, in shared memory.

Definition 20.2 Tile and halo. A block that computes a \(\mathsf{blockDim{.}y} \times \mathsf{blockDim{.}x}\) square of cells keeps a tile in shared memory: the \((\mathsf{blockDim{.}y} + 2) \times (\mathsf{blockDim{.}x} + 2)\) square of old values made of its own cells and a ring of cells 1 cell wide around them. The cells of the ring are the halo of the block. Halo cells are read by the block but computed by its neighbors.

Example. Block (1, 1) of the plate has \(\mathsf{blockDim{.}x} = \mathsf{blockDim{.}y} = 2\). Its tile covers rows 1 to 4 and columns 1 to 4: 4 own cells and 12 halo cells, of which 4 are corners that the 5-point stencil does not read.

Here \(\mathsf{blockDim{.}x}\) is the number of cells that a block computes along a row, and \(\mathsf{blockDim{.}y}\) the number along a column. The ring adds 1 cell on each of the two sides, which explains the 2 in \(\mathsf{blockDim{.}x} + 2\) and \(\mathsf{blockDim{.}y} + 2\). For the blocks of our programs, \(\mathsf{blockDim{.}x} = 32\) and \(\mathsf{blockDim{.}y} = 8\), so the tile is \(34 \times 10\), the size given in the example of Definition 20.1.

Next, we need to know where each cell sits inside the tile. Let \((\mathsf{top}, \mathsf{left})\) be the first cell of the block, that is, its upper-left own cell. The tile starts 1 row above and 1 column to the left of this cell, at cell \((\mathsf{top} - 1, \mathsf{left} - 1)\). The block’s cell \((\mathsf{row}, \mathsf{col})\) therefore lies at tile position

\[ (row - top + 1,\; col - left + 1). \]

SymbolMeaningBlock (1, 1), cell (2, 2)
\(\mathsf{top}, \mathsf{left}\)row and column of the block’s first own cell2, 2
\(\mathsf{row}, \mathsf{col}\)row and column of a cell of the grid2, 2
\(\mathsf{row} - \mathsf{top} + 1\)row of the cell inside the tile\(2 - 2 + 1 = 1\)
\(\mathsf{col} - \mathsf{left} + 1\)column of the cell inside the tile\(2 - 2 + 1 = 1\)

The 4 neighbors of the cell lie 1 position above, below, to the left and to the right of it in the tile. In block (1, 1), cell (2, 2) thus sits at tile position (1, 1), and its upper neighbor, cell (1, 2), sits at tile position \((1 - 2 + 1, 2 - 2 + 1) = (0, 1)\).

20.2.2 Computing from the tile

Figure 20.3 shows the tile of block (1, 1) in step 2. It holds the old values of rows 1 to 4 of the plate. Its top row is row 1 of the plate and holds 25, and its other rows hold 0. The thread of cell (2, 2) reads its 4 neighbors from the tile positions (0, 1), (2, 1), (1, 0) and (1, 2). It obtains 25, 0, 0 and 0, which are the same values that it read from global memory in the direct kernel, and it writes 6.25.

The 4 by 4 tile of block (1, 1) in step 2, as it sits in shared memory. Its top row holds 25, 25, 25, 25 (row 1 of the plate) and the other 3 rows hold 0. The 4 inner positions are blue (own cells), the 8 edge positions amber (halo), the 4 corners gray (loaded, never read). For cell (2, 2), at tile position (1, 1), the 4 neighbors at positions (0, 1), (2, 1), (1, 0) and (1, 2) are outlined: 25 + 0 + 0 + 0, times 1/4, gives 6.25.
Figure 20.3 The tile of block (1, 1) in step 2. Cell (2, 2) reads 25, 0, 0 and 0 from shared memory and writes 6.25.

Exercises

20.3 Which cells does the tile of block (0, 1) cover? Which of its slots lie outside the plate?
20.4 At which tile position does cell (3, 3) of block (1, 1) sit, and from which positions does it read its neighbors?

20.3 Loading the halo

20.3.1 More slots than threads

We call each position of the tile a slot. In the tiled matrix product of Chapter 17, a tile had exactly as many slots as the block had threads, so each thread copied 1 value. A stencil tile has more. A block of \(\mathsf{blockDim{.}x} \times \mathsf{blockDim{.}y}\) threads must fill \((\mathsf{blockDim{.}x} + 2)(\mathsf{blockDim{.}y} + 2)\) slots. Block (1, 1) of our example has 4 threads and 16 slots, and a block of 32 × 8 threads has 256 threads and \(34 \times 10 = 340\) slots. There are 2 standard ways to close this gap, which are shown in Figure 20.4.

Two ways to load the 4 by 4 tile of block (1, 1). Left, extra threads: the block has 4 by 4 = 16 threads, 1 per slot; all 16 load, and only the inner 4 compute. Right, a loop: the block has 2 by 2 = 4 threads, and each loads 4 slots, at rows threadIdx.y and threadIdx.y + 2 and columns threadIdx.x and threadIdx.x + 2; the slots are colored by the thread that loads them. A note gives the counts for the programs: 34 by 10 = 340 threads, 256 of which compute; or 256 threads, of which 180 load 1 slot, 72 load 2 and 4 load 4.
Figure 20.4 2 ways to fill a 4 × 4 tile: 16 threads that load 1 slot each, or 4 threads that load 4 slots each.

Extra threads. In the first way, the block is given one thread per slot, that is, \((\mathsf{blockDim{.}x} + 2) \times (\mathsf{blockDim{.}y} + 2)\) threads. We let every thread load the slot at its own position, and after the barrier, only the \(\mathsf{blockDim{.}x} \times \mathsf{blockDim{.}y}\) inner threads compute a cell. For block (1, 1), this means 16 threads, of which 12 only load. In the programs, it means 34 × 10 = 340 threads, of which 256 compute. The loading is a single statement per thread, but 84 of the 340 threads are idle while the others compute.

A loading loop. In the second way, the block keeps one thread per computed cell, and each thread loads several slots. Recall that \((\mathsf{threadIdx{.}y}, \mathsf{threadIdx{.}x})\) gives the row and column of a thread within its block. Thread \((\mathsf{threadIdx{.}y}, \mathsf{threadIdx{.}x})\) starts at slot \((\mathsf{threadIdx{.}y}, \mathsf{threadIdx{.}x})\) and moves down the tile in strides of \(\mathsf{blockDim{.}y}\) rows and across it in strides of \(\mathsf{blockDim{.}x}\) columns, loading every slot that it lands on, as long as the slot lies in the tile. Its rows are therefore \(\mathsf{threadIdx{.}y}, \mathsf{threadIdx{.}y} + \mathsf{blockDim{.}y}, \mathsf{threadIdx{.}y} + 2 \cdot \mathsf{blockDim{.}y}, \ldots\), and its columns are \(\mathsf{threadIdx{.}x}, \mathsf{threadIdx{.}x} + \mathsf{blockDim{.}x}, \mathsf{threadIdx{.}x} + 2 \cdot \mathsf{blockDim{.}x}, \ldots\). In the notation of modular arithmetic, these are the slots with

\[ \mathsf{slotRow} \equiv \mathsf{threadIdx{.}y} \pmod{\mathsf{blockDim{.}y}}, \qquad \mathsf{slotCol} \equiv \mathsf{threadIdx{.}x} \pmod{\mathsf{blockDim{.}x}}. \]

SymbolMeaningThread (0, 0) of block (1, 1)
\(\mathsf{threadIdx{.}y}, \mathsf{threadIdx{.}x}\)row and column of the thread within its block0, 0
\((\mathsf{slotRow}, \mathsf{slotCol})\)row and column of a slot of the tile(0, 0), (0, 2), (2, 0), (2, 2)
\(\mathsf{slotRow} \equiv \mathsf{threadIdx{.}y} \pmod{\mathsf{blockDim{.}y}}\)\(\mathsf{slotRow}\) leaves the remainder \(\mathsf{threadIdx{.}y}\) when divided by \(\mathsf{blockDim{.}y}\)\(\mathsf{slotRow} = 0\) or \(2\), with \(\mathsf{blockDim{.}y} = 2\)
\(\mathsf{slotCol} \equiv \mathsf{threadIdx{.}x} \pmod{\mathsf{blockDim{.}x}}\)\(\mathsf{slotCol}\) leaves the remainder \(\mathsf{threadIdx{.}x}\) when divided by \(\mathsf{blockDim{.}x}\)\(\mathsf{slotCol} = 0\) or \(2\), with \(\mathsf{blockDim{.}x} = 2\)

In block (1, 1), thread (0, 0) therefore loads the slots (0, 0), (0, 2), (2, 0) and (2, 2), and in the same way each of the 4 threads loads 4 slots. With 32 × 8 threads and a tile of 34 × 10 slots, the counts are less even. The row \(\mathsf{slotRow}\) takes the value \(\mathsf{threadIdx{.}y}\), and also \(\mathsf{threadIdx{.}y} + 8\) when \(\mathsf{threadIdx{.}y} < 2\), since the tile has only 10 rows. The column \(\mathsf{slotCol}\) takes the value \(\mathsf{threadIdx{.}x}\), and also \(\mathsf{threadIdx{.}x} + 32\) when \(\mathsf{threadIdx{.}x} < 2\), since the tile has only 34 columns. As a result, 180 threads load 1 slot, 72 threads load 2 slots, and 4 threads load 4 slots, which accounts for all \(180 + 144 + 16 = 340\) slots. We let every thread compute a cell, but a few threads load more slots than the rest.

Both ways give every slot exactly 1 loading thread, which is what the correctness proof of Section 20.5 needs. They differ in cost, and we measure both in Section 20.7.

20.3.2 Slots outside the grid

A block on the edge of the grid has slots that lie outside the grid. Block (0, 0) of the plate, for example, computes the cells (0, 0) to (1, 1), and its tile covers rows −1 to 2 and columns −1 to 2. The loader stores 0 in a slot outside the grid instead of reading it from memory. No thread ever reads such a slot, because only interior cells are computed, and every neighbor of an interior cell lies inside the grid.

Exercises

20.5 With the loading loop and blocks of 32 × 8 threads, which slots does thread (1, 0) load? And thread (5, 20)?
20.6 For blocks of 16 × 16 threads, how many slots does the tile have, and how many threads load 2 slots with the loading loop?

20.4 The tiled algorithm

20.4.1 The barrier

The threads of a block do not move in lockstep. A thread may finish its own loads early and start to compute while another thread is still loading a slot that the first thread needs. In block (1, 1), for example, the thread of cell (2, 2) needs tile position (0, 1), which another thread loads. The block therefore needs a point in the kernel at which all of its threads meet before any of them continues.

Definition 20.3 Barrier. A barrier is a point in a kernel that no thread of a block may pass until every thread of the block has reached it. In CUDA C++, a barrier is __syncthreads(); in cuda-oxide, it is thread::sync_threads(). Writes to shared memory made before the barrier are visible to every thread of the block after it.

Example. In the tiled kernel, the thread of cell (2, 2) waits at the barrier until the thread that loads tile position (0, 1) has stored 25 there.

20.4.2 The kernel

Every thread executes the following procedure, which is written with the loading loop. With extra threads, lines 3 to 7 become a single load, and the condition of line 13 also requires an inner thread.

Tiled-Jacobi-Kernel(\(u, v, W, H\))

  1. \(\mathsf{top} = \mathsf{blockIdx{.}y} \cdot \mathsf{blockDim{.}y}\)
  2. \(\mathsf{left} = \mathsf{blockIdx{.}x} \cdot \mathsf{blockDim{.}x}\)
  3. for \(\mathsf{slotRow} \in [\mathsf{threadIdx{.}y}, \mathsf{blockDim{.}y} + 2)\) stride \(\mathsf{blockDim{.}y}\) {
  4. for \(\mathsf{slotCol} \in [\mathsf{threadIdx{.}x}, \mathsf{blockDim{.}x} + 2)\) stride \(\mathsf{blockDim{.}x}\) {
  5. \(\mathsf{tile}[\mathsf{slotRow}][\mathsf{slotCol}] = u_{\mathsf{top}+\mathsf{slotRow}-1,\, \mathsf{left}+\mathsf{slotCol}-1}\) if that cell is in the grid, else 0
  6. }
  7. }
  8. Barrier() // wait until the whole tile is loaded
  9. \(\mathsf{row} = \mathsf{top} + \mathsf{threadIdx{.}y}\)
  10. \(\mathsf{col} = \mathsf{left} + \mathsf{threadIdx{.}x}\)
  11. \(\mathsf{centerRow} = \mathsf{threadIdx{.}y} + 1\) // the slot of the cell itself
  12. \(\mathsf{centerCol} = \mathsf{threadIdx{.}x} + 1\)
  13. if \(\mathsf{row} \in [1, H - 1)\) and \(\mathsf{col} \in [1, W - 1)\) {
  14. \(\mathsf{up} = \mathsf{tile}[\mathsf{centerRow} - 1][\mathsf{centerCol}]\)
  15. \(\mathsf{down} = \mathsf{tile}[\mathsf{centerRow} + 1][\mathsf{centerCol}]\)
  16. \(\mathsf{toLeft} = \mathsf{tile}[\mathsf{centerRow}][\mathsf{centerCol} - 1]\)
  17. \(\mathsf{toRight} = \mathsf{tile}[\mathsf{centerRow}][\mathsf{centerCol} + 1]\)
  18. \(v_{\mathsf{row},\mathsf{col}} = (\mathsf{up} + \mathsf{down} + \mathsf{toLeft} + \mathsf{toRight}) / 4\)
  19. }

Lines 1 and 2 compute the first own cell \((\mathsf{top}, \mathsf{left})\) of the block. For block (1, 1) of the plate, with blocks of 2 × 2 threads, they give \(\mathsf{top} = 1 \cdot 2 = 2\) and \(\mathsf{left} = 1 \cdot 2 = 2\). Lines 3 to 7 are the loading loop of Section 20.3.1. In line 5, slot \((\mathsf{slotRow}, \mathsf{slotCol})\) receives the cell \((\mathsf{top} + \mathsf{slotRow} - 1, \mathsf{left} + \mathsf{slotCol} - 1)\), because the tile begins 1 row above and 1 column to the left of the first own cell. For example, thread (0, 1) of block (1, 1) loads slot (0, 1) with the cell \((2 + 0 - 1, 2 + 1 - 1) = (1, 2)\), whose value in step 2 is 25. Line 8 is the barrier.

Lines 9 to 19 are Jacobi-Kernel of Chapter 19, with each read from \(u\) replaced by a read from the tile. Lines 9 and 10 compute the cell \((\mathsf{row}, \mathsf{col})\) of the thread, and lines 11 and 12 compute the slot \((\mathsf{centerRow}, \mathsf{centerCol})\) at which that cell sits in the tile, 1 row and 1 column past the thread’s own position. Lines 14 to 17 read the 4 neighbors around that slot, and line 18 writes their mean. For thread (0, 0) of block (1, 1), these are the positions (0, 1), (2, 1), (1, 0) and (1, 2) of Figure 20.3. Note that the barrier in line 8 lies outside every condition, so every thread of the block reaches it, including the threads whose cell is on the boundary or outside the grid. The host loop is unchanged from Chapter 19, with 2 buffers, 1 launch per step, and an exchange of the names after each launch.

Each block thus runs through 3 phases, in which it loads the tile, waits at the barrier, and computes its cells from the tile, as shown in Figure 20.5.

A timeline of the 4 threads of block (1, 1). Each thread loads its 4 slots, taking different times; dotted lines show the early threads waiting at the barrier; then all 4 compute their cell from the tile and write it to buffer v.
Figure 20.5 The 3 phases of a block: load the tile, wait at the barrier, compute from the tile.

20.4.3 Counting the loads again

We can now count how much the tile saves. In the direct kernel, the 4 threads of block (1, 1) make \(4 \cdot 4 = 16\) reads from global memory, 4 per thread. With the tile, the block makes 16 loads, 1 per slot. For a 2 × 2 block, the tile therefore saves nothing, since \((2 + 2)^2 = 16 = 4 \cdot 2^2\). The halo is as large as the block itself in this case. As the block grows, however, its own cells grow with the square of its width, while the halo grows only with its perimeter, so the saving grows with the block.

In general, a block of \(T \times T\) threads makes \(4T^2\) reads in the direct kernel, 4 for each of its \(T^2\) threads, and \((T + 2)^2\) loads with a tile, 1 for each slot. The tile therefore divides the number of reads by

\[ \frac{4T^2}{(T + 2)^2}. \]

SymbolMeaning\(T = 2\)\(T = 16\)
\(T\)width and height of the block, in threads216
\(4T^2\)reads of the direct kernel per block161,024
\((T + 2)^2\)loads of the tiled kernel per block16324
\(4T^2 / (T + 2)^2\)factor by which the tile reduces the reads13.2

The factor is 1 for \(T = 2\), 1.8 for \(T = 4\), 2.6 for \(T = 8\) and 3.2 for \(T = 16\). It approaches 4, the number of reads per cell of the direct kernel, as the block grows. A block of 32 × 8 threads makes \(4 \cdot 256 = 1{,}024\) reads in the direct kernel and 340 loads with a tile, which is 3 times fewer.

It is often more useful to count the loads per computed cell, which we call the loads per result. A tile of a \(\mathsf{blockDim{.}x} \times \mathsf{blockDim{.}y}\) block loads \((\mathsf{blockDim{.}x} + 2)(\mathsf{blockDim{.}y} + 2)\) values for \(\mathsf{blockDim{.}x} \cdot \mathsf{blockDim{.}y}\) results, so it loads \((\mathsf{blockDim{.}x} + 2)(\mathsf{blockDim{.}y} + 2) / (\mathsf{blockDim{.}x} \cdot \mathsf{blockDim{.}y})\) values per result, as plotted in Figure 20.6. For the 32 × 8 block of the programs, this is \(340 / 256 = 1.33\). A value of 1 would mean that every value is loaded exactly once. The part above 1 is the halo overhead, which comes from the halo cells that 2 or more neighboring blocks each load for themselves. The following table gives both numbers for several block shapes.

BlockTileLoads per resultHalo overhead
2 × 24 × 416 / 4 = 4.00300%
4 × 46 × 636 / 16 = 2.25125%
8 × 810 × 10100 / 64 = 1.5656%
16 × 1618 × 18324 / 256 = 1.2727%
32 × 834 × 10340 / 256 = 1.3333%
32 × 3234 × 341,156 / 1,024 = 1.1313%
A chart of global loads per computed cell against the block width T from 2 to 32. The direct kernel is a flat line at 4. The tiled kernel follows the curve (T + 2) squared over T squared: 4 at T = 2, 2.25 at 4, 1.56 at 8, 1.27 at 16, 1.13 at 32. A marked point shows the 32 by 8 block of the programs at 1.33. The cache model of Chapter 19 for the direct kernel, 1.25 loads from memory per cell, is drawn as a dashed line.
Figure 20.6 Loads per result: 4 in the direct kernel, \((T + 2)^2/T^2\) with a tile, and 1.25 from memory when the caches serve the direct kernel.

The largest block in the table would have the smallest overhead, but a block holds at most 1,024 threads. The extra-threads scheme therefore cannot serve a block that computes 32 × 32 cells, because its tile has 34 × 34 = 1,156 slots and would need 1,156 threads. Shared memory, on the other hand, is not the limit, since the 34 × 10 tile of the programs takes only 1,360 bytes. The 32 × 8 block that the programs use costs 1.33 loads per result, which is 3 times fewer than the 4 that the direct kernel requests.

Exercises

20.7 Compute the loads per result for blocks of 64 × 4 and 16 × 16 threads, both of 256 threads. Which shape loads fewer halo cells per result?
20.8 A 2-D stencil of radius 2 reads the 2 nearest cells in each direction. How wide is its halo, and how many loads per result does a 32 × 8 block make?

20.5 Correctness

Compared with the direct kernel, the tiled kernel adds 2 places where it can go wrong, the barrier and the halo. In this section, we remove each of them in turn, show the wrong value that the removal produces on the plate, and run the broken variant.

20.5.1 Without the barrier

Suppose that we delete line 8. In block (1, 1), loaded with the loop, the thread of cell (2, 2) is thread (0, 0). It needs tile position (0, 1), which holds the halo cell (1, 2) and is loaded by thread (0, 1). If thread (0, 0) finishes its own loads early and thread (0, 1) runs late, thread (0, 0) reads position (0, 1) before 25 has been stored there. The slot then holds whatever an earlier block left in that part of shared memory. If it holds 0, cell (2, 2) becomes \((0 + 0 + 0 + 0) / 4 = 0\) instead of 6.25, as shown in Figure 20.7.

A timeline of 2 threads of block (1, 1) without the barrier. Thread (0, 0) loads its 4 slots and goes on to compute cell (2, 2); it reads tile position (0, 1) at a moment marked in red. Thread (0, 1) is delayed and stores 25 into position (0, 1) only afterward. The result: thread (0, 0) reads the stale value 0 and writes 0 instead of 6.25.
Figure 20.7 Without the barrier, thread (0, 0) reads a halo slot before thread (0, 1) fills it, and cell (2, 2) becomes 0 in place of 6.25.

We ran the kernel of the programs, with 32 × 8 threads and the loading loop, without its barrier. It performed 1 step on the 4096 × 4096 plate after 200 correct steps, and we repeated this 3 times and compared each result with the result of the direct kernel. The program printed the following counts.

loop loader without barrier, 4096 x 4096, run 1: 126302 cells differ after 1 step
loop loader without barrier, 4096 x 4096, run 2: 124849 cells differ after 1 step
loop loader without barrier, 4096 x 4096, run 3: 124322 cells differ after 1 step

The count changes from run to run, because it depends on the timing of the threads. On the 6 × 6 plate with 2 × 2 blocks, the extra-threads kernel without its barrier gave the correct values in our runs. There, the 16 threads of each block belong to 1 warp, and they happened to finish their loads together. The error appears when the threads of a block span several warps, as they do in every block of practical size.

20.5.2 Without the halo

Suppose next that the loader copies only the block’s own cells, so that the halo slots stay at 0. In block (1, 1), cell (2, 2) then reads 0 above instead of 25, and it becomes 0 instead of 6.25. Cell (1, 1) belongs to block (0, 0), and its right neighbor (1, 2) belongs to block (0, 1). The halo slot of block (0, 0) that should hold cell (1, 2) therefore holds 0, and cell (1, 1) becomes \((100 + 0 + 0 + 0) / 4 = 25\) instead of 31.25. We ran this variant with 2 × 2 blocks on the plate, and it printed the following grid.

  2 x 2 blocks, halo filled with 0, after step 2
     100.00  100.00  100.00  100.00  100.00  100.00
       0.00   25.00   31.25   31.25   25.00    0.00
       0.00    0.00    0.00    0.00    0.00    0.00
       0.00    0.00    0.00    0.00    0.00    0.00
       0.00    0.00    0.00    0.00    0.00    0.00
       0.00    0.00    0.00    0.00    0.00    0.00

In this grid, 8 of the 16 interior cells are wrong. Row 1 reads 25, 31.25, 31.25 and 25 instead of 31.25, 37.5, 37.5 and 31.25, and row 2 reads 0 instead of 6.25, as Figure 20.8 shows. Step 1 was still correct, because in step 1 every halo value that a computed cell reads is 0 in the correct grid as well. A test of 1 step would therefore have passed.

2 versions of the plate after step 2, side by side. Left, correct: row 1 reads 31.25, 37.5, 37.5, 31.25 and row 2 reads 6.25 in each interior cell. Right, without the halo: row 1 reads 25, 31.25, 31.25, 25 and row 2 reads 0; every differing cell is outlined in red. Block boundaries are drawn as thick lines, showing that each wrong cell has a neighbor in another block.
Figure 20.8 Step 2 without the halo: every cell whose neighbor belongs to another block loses that neighbor.

20.5.3 A proof of correctness

Having seen how each part of the kernel fails when it is removed, we now prove that the complete kernel computes exactly what the direct kernel computes.

Theorem 20.1 Launched on 2 different buffers \(u\) and \(v\), Tiled-Jacobi-Kernel writes the same value into every cell of \(v\) as Jacobi-Kernel of Chapter 19.

Proof. Fix a block with first cell \((\mathsf{top}, \mathsf{left})\). We show three facts.

Every slot is loaded once, with the old value. The loops of lines 3 to 7 let thread \((\mathsf{threadIdx{.}y}, \mathsf{threadIdx{.}x})\) store slot \((\mathsf{slotRow}, \mathsf{slotCol})\) exactly when \(\mathsf{slotRow} \equiv \mathsf{threadIdx{.}y} \pmod{\mathsf{blockDim{.}y}}\) and \(\mathsf{slotCol} \equiv \mathsf{threadIdx{.}x} \pmod{\mathsf{blockDim{.}x}}\). Each slot \((\mathsf{slotRow}, \mathsf{slotCol})\) of the \((\mathsf{blockDim{.}y} + 2) \times (\mathsf{blockDim{.}x} + 2)\) tile has exactly 1 such thread, namely \((\mathsf{slotRow} \bmod \mathsf{blockDim{.}y}, \mathsf{slotCol} \bmod \mathsf{blockDim{.}x})\). For example, with \(\mathsf{blockDim{.}x} = \mathsf{blockDim{.}y} = 2\), slot (2, 3) is stored by thread \((2 \bmod 2, 3 \bmod 2) = (0, 1)\). That thread stores \(u_{\mathsf{top}+\mathsf{slotRow}-1,\,\mathsf{left}+\mathsf{slotCol}-1}\) if the cell is in the grid. No thread of the launch writes \(u\), because \(u\) and \(v\) are different buffers, so the stored value is the old value.

Every load finishes before any read. The barrier of line 8 lies outside every condition, so every thread of the block reaches it. No thread passes it before all threads have finished lines 3 to 7, and their stores are then visible to the whole block. The tile is not written after line 8.

The reads are the right ones. Let \((\mathsf{row}, \mathsf{col}) = (\mathsf{top} + \mathsf{threadIdx{.}y}, \mathsf{left} + \mathsf{threadIdx{.}x})\) be an interior cell. Tile position \((\mathsf{threadIdx{.}y}, \mathsf{threadIdx{.}x} + 1)\) holds the cell \((\mathsf{top} + \mathsf{threadIdx{.}y} - 1, \mathsf{left} + \mathsf{threadIdx{.}x}) = (\mathsf{row} - 1, \mathsf{col})\), the upper neighbor; in the same way, \((\mathsf{threadIdx{.}y} + 2, \mathsf{threadIdx{.}x} + 1)\), \((\mathsf{threadIdx{.}y} + 1, \mathsf{threadIdx{.}x})\) and \((\mathsf{threadIdx{.}y} + 1, \mathsf{threadIdx{.}x} + 2)\) hold the lower, left and right neighbors. All 4 lie in the grid, because \((\mathsf{row}, \mathsf{col})\) is interior, so their slots hold old values and not the 0 of line 5. Line 18 therefore adds the same 4 values, in the same order, as line 4 of Jacobi-Kernel and writes the same result. Cells that are not interior are written by neither kernel.

Each broken variant of this section breaks 1 fact of the proof. Without the barrier, the second fact fails. Without the halo, the first fact fails for every halo slot, and the third fact then reads 0 where it needs a neighbor. Since the tiled kernel writes what the direct kernel writes, Theorem 19.1 carries over unchanged, and with 2 buffers used in turn, the tiled kernel computes Jacobi iteration.

Rule Every thread of the block must reach the barrier between loading the tile and reading it, and the tile must hold every cell that any thread of the block reads, the halo included.

Exercises

20.9 In the variant without the halo, compute cell (2, 1) after step 2 by hand.
20.10 Suppose the loading loop used slot_col < BLOCK_WIDTH + 1 instead of slot_col < TILE_WIDTH. Which slots would stay empty, and which cells of block (1, 1) of the plate would be wrong in step 2?
20.11 Why must a thread whose cell lies outside the grid still execute line 8?

20.6 Implementation

20.6.1 The kernel with a loading loop

Listing 20.1 implements Tiled-Jacobi-Kernel with blocks of 32 × 8 threads and a 34 × 10 tile. The 2 while loops in Rust and the 2 for loops in C++ are lines 3 to 7 of the pseudocode. The test of line 5, whether a cell lies in the grid, is written differently in the two languages. Rust uses wrapping_sub on unsigned positions. For the first block, top + slot_row - 1 is −1, which wrapping_sub turns into the largest usize, so the test cell_row < height fails and the slot receives 0. The C++ version computes signed positions and tests cell_row >= 0 as well. In both languages, the barrier, thread::sync_threads() in Rust and __syncthreads() in C++, lies outside every if.

Listing 20.1 One Jacobi step from a tile, loaded with a loop.

mod kernels {
    // ...
    /// 1 Jacobi step from a 34 x 10 tile; 32 x 8 threads load it, some 2 or 4 cells each.
    #[kernel]
    #[launch_contract(domain = 2, block = (32, 8, 1))]
    pub fn jacobi_tiled(old: &[f32], mut new: DisjointSlice<f32, Runtime2DIndex>) {
        const AREA: usize = TILE_WIDTH * TILE_HEIGHT;
        static mut TILE: SharedArray<f32, AREA> = SharedArray::UNINIT;

        let width = new.row_width() as usize;
        let height = new.len() / width;
        let thread_x = thread::threadIdx_x() as usize;
        let thread_y = thread::threadIdx_y() as usize;
        let top = thread::blockIdx_y() as usize * BLOCK_HEIGHT;
        let left = thread::blockIdx_x() as usize * BLOCK_WIDTH;

        let mut slot_row = thread_y;
        while slot_row < TILE_HEIGHT {
            let mut slot_col = thread_x;
            while slot_col < TILE_WIDTH {
                let cell_row = (top + slot_row).wrapping_sub(1);
                let cell_col = (left + slot_col).wrapping_sub(1);
                let inside = cell_row < height && cell_col < width;
                let value = if inside { old[cell_row * width + cell_col] } else { 0.0 };

                // SAFETY: slot (slot_row, slot_col) is written by 1 thread alone,
                // the thread (slot_row mod 8, slot_col mod 32).
                unsafe { TILE[slot_row * TILE_WIDTH + slot_col] = value };
                slot_col += BLOCK_WIDTH;
            }
            slot_row += BLOCK_HEIGHT;
        }
        thread::sync_threads();

        if let Some(idx) = thread::index_2d_runtime(&new) {
            let (row, col) = (idx.row(), idx.col());
            let interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

            if interior {
                let center = (thread_y + 1) * TILE_WIDTH + thread_x + 1;
                // SAFETY: after the barrier no thread writes the tile.
                let up = unsafe { TILE[center - TILE_WIDTH] };
                // SAFETY: as above.
                let down = unsafe { TILE[center + TILE_WIDTH] };
                // SAFETY: as above.
                let (to_left, to_right) = unsafe { (TILE[center - 1], TILE[center + 1]) };
                let sum = up + down + to_left + to_right;

                if let Some(cell) = new.get_mut(idx) {
                    *cell = 0.25 * sum;
                }
            }
        }
    }
    // ...
}
// 1 Jacobi step from a 34 x 10 tile; 32 x 8 threads load it, some 2 or 4 cells each.
__global__ void jacobiTiled(const float* __restrict__ old, float* __restrict__ next,
                            int width, int height)
{
    __shared__ float tile[TILE_HEIGHT][TILE_WIDTH];
    int top = blockIdx.y * BLOCK_HEIGHT;
    int left = blockIdx.x * BLOCK_WIDTH;

    for (int slot_row = threadIdx.y; slot_row < TILE_HEIGHT; slot_row += BLOCK_HEIGHT) {
        for (int slot_col = threadIdx.x; slot_col < TILE_WIDTH; slot_col += BLOCK_WIDTH) {
            int cell_row = top + slot_row - 1;
            int cell_col = left + slot_col - 1;
            bool row_inside = cell_row >= 0 && cell_row < height;
            bool col_inside = cell_col >= 0 && cell_col < width;
            int cell = cell_row * width + cell_col;
            tile[slot_row][slot_col] = row_inside && col_inside ? old[cell] : 0.0f;
        }
    }
    __syncthreads();

    int row = top + threadIdx.y;
    int col = left + threadIdx.x;
    bool interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

    if (interior) {
        int center_row = threadIdx.y + 1;
        int center_col = threadIdx.x + 1;
        float up = tile[center_row - 1][center_col];
        float down = tile[center_row + 1][center_col];
        float to_left = tile[center_row][center_col - 1];
        float to_right = tile[center_row][center_col + 1];
        next[row * width + col] = 0.25f * (up + down + to_left + to_right);
    }
}

The tile is declared differently in the two languages. In C++, __shared__ float tile[TILE_HEIGHT][TILE_WIDTH] is a 2-D array, and tile[center_row - 1][center_col] reads it like any other array. In Rust, the tile is a static mut TILE: SharedArray<f32, AREA>, a flat array of 340 floats with 1 copy per block, and slot \((\mathsf{slotRow}, \mathsf{slotCol})\) is element slot_row * TILE_WIDTH + slot_col. Every access to it is unsafe, because the compiler cannot check how the threads of a block share a static. Each unsafe block therefore carries a // SAFETY: comment that states why it is sound, and the 2 comments are the first 2 facts of the proof of Theorem 20.1: each slot has 1 writer, and after the barrier the tile is only read. The final write needs no unsafe block. As in Chapter 19, the thread writes its own cell through get_mut of the DisjointSlice.

20.6.2 The kernel with extra threads

Listing 20.2 performs the same step with 34 × 10 threads per block, one thread per slot. Each thread loads 1 slot, all threads wait at the barrier, and only the 32 × 8 inner threads compute a cell.

Listing 20.2 One Jacobi step from a tile, loaded by one thread per slot.

mod kernels {
    // ...
    /// 1 Jacobi step from a 34 x 10 tile; 34 x 10 threads load 1 cell each, 32 x 8 compute.
    #[kernel]
    #[launch_contract(domain = 2, block = (34, 10, 1))]
    pub fn jacobi_halo_threads(old: &[f32], mut new: DisjointSlice<f32, Runtime2DIndex>) {
        const AREA: usize = TILE_WIDTH * TILE_HEIGHT;
        static mut TILE: SharedArray<f32, AREA> = SharedArray::UNINIT;

        let width = new.row_width() as usize;
        let height = new.len() / width;
        let slot_col = thread::threadIdx_x() as usize;
        let slot_row = thread::threadIdx_y() as usize;
        let row = (thread::blockIdx_y() as usize * BLOCK_HEIGHT + slot_row).wrapping_sub(1);
        let col = (thread::blockIdx_x() as usize * BLOCK_WIDTH + slot_col).wrapping_sub(1);
        let slot = slot_row * TILE_WIDTH + slot_col;

        let value = if row < height && col < width { old[row * width + col] } else { 0.0 };
        // SAFETY: the slot belongs to this thread alone.
        unsafe { TILE[slot] = value };
        thread::sync_threads();

        let inner_row = slot_row >= 1 && slot_row <= BLOCK_HEIGHT;
        let inner_col = slot_col >= 1 && slot_col <= BLOCK_WIDTH;
        let interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

        if inner_row && inner_col && interior {
            // SAFETY: after the barrier no thread writes the tile.
            let (up, down) = unsafe { (TILE[slot - TILE_WIDTH], TILE[slot + TILE_WIDTH]) };
            // SAFETY: as above.
            let (to_left, to_right) = unsafe { (TILE[slot - 1], TILE[slot + 1]) };
            let sum = up + down + to_left + to_right;

            // SAFETY: the inner threads of the blocks cover each cell of the grid once,
            // so no other thread writes cell (row, col), which lies inside `new`.
            unsafe { *new.get_unchecked_mut(row * width + col) = 0.25 * sum };
        }
    }
    // ...
}
// 1 Jacobi step from a 34 x 10 tile; 34 x 10 threads load 1 cell each, 32 x 8 compute.
__global__ void jacobiHaloThreads(const float* __restrict__ old, float* __restrict__ next,
                                  int width, int height)
{
    __shared__ float tile[TILE_HEIGHT][TILE_WIDTH];
    int slot_row = threadIdx.y;
    int slot_col = threadIdx.x;
    int row = blockIdx.y * BLOCK_HEIGHT + slot_row - 1;
    int col = blockIdx.x * BLOCK_WIDTH + slot_col - 1;

    bool inside = row >= 0 && row < height && col >= 0 && col < width;
    tile[slot_row][slot_col] = inside ? old[row * width + col] : 0.0f;
    __syncthreads();

    bool inner_row = slot_row >= 1 && slot_row <= BLOCK_HEIGHT;
    bool inner_col = slot_col >= 1 && slot_col <= BLOCK_WIDTH;
    bool interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

    if (inner_row && inner_col && interior) {
        float up = tile[slot_row - 1][slot_col];
        float down = tile[slot_row + 1][slot_col];
        float to_left = tile[slot_row][slot_col - 1];
        float to_right = tile[slot_row][slot_col + 1];
        next[row * width + col] = 0.25f * (up + down + to_left + to_right);
    }
}

In this kernel, the thread at position \((\mathsf{threadIdx{.}y}, \mathsf{threadIdx{.}x})\) of the block no longer owns cell \((\mathsf{top} + \mathsf{threadIdx{.}y}, \mathsf{left} + \mathsf{threadIdx{.}x})\). Instead, it owns slot \((\mathsf{threadIdx{.}y}, \mathsf{threadIdx{.}x})\), which holds cell \((\mathsf{top} + \mathsf{threadIdx{.}y} - 1, \mathsf{left} + \mathsf{threadIdx{.}x} - 1)\). Thread (0, 0), for example, owns the corner slot of the halo, and thread (1, 1) owns the block’s first own cell \((\mathsf{top}, \mathsf{left})\). The launch contract of the Rust kernel states the new block shape, block = (34, 10, 1). Because the thread’s position is no longer its cell, index_2d_runtime and get_mut no longer apply, and the Rust kernel writes with get_unchecked_mut(row * width + col). Its // SAFETY: comment gives the argument that the type system gave before: the inner threads of the blocks cover each cell exactly once, so no 2 threads write the same element. The C++ kernel writes next[row * width + col] and relies on the same argument without stating it.

20.6.3 The 6 × 6 plate

Both programs run each tiled kernel on the plate and compare its result, bit for bit, with the result of the direct kernel. The Rust program prints the following output.

$ cargo oxide run
GPU: Orin, 8 SMs
1. 6 x 6 plate, top edge at 100
  after step 2, tiled
     100.00  100.00  100.00  100.00  100.00  100.00
       0.00   31.25   37.50   37.50   31.25    0.00
       0.00    6.25    6.25    6.25    6.25    0.00
       0.00    0.00    0.00    0.00    0.00    0.00
       0.00    0.00    0.00    0.00    0.00    0.00
       0.00    0.00    0.00    0.00    0.00    0.00
  loop loader              same bits as the plain kernel after 4 steps: true
  extra threads            same bits as the plain kernel after 4 steps: true
  4 steps per load         same bits as the plain kernel after 4 steps: true

The grid after step 2 agrees with the values of Chapter 19, and all 3 tiled kernels agree with the direct kernel in every bit. The third kernel, 4 steps per load, is the subject of Section 20.8.

Exercises

20.12 Rewrite the loading loop of Listing 20.1 as a single loop over the slot number \(k = \mathsf{threadIdx{.}y} \cdot 32 + \mathsf{threadIdx{.}x}, k + 256, \ldots\), with \(\mathsf{slotRow} = k / 34\) and \(\mathsf{slotCol} = k \bmod 34\). Which threads now load 2 slots? Measure the two versions.
20.13 In the Rust extra-threads kernel, which fact of the proof of Theorem 20.1 does the // SAFETY: comment of the final write rely on?

20.7 Measurements

20.7.1 Results

The measurements come from a Jetson Orin NX, an integrated GPU with 8 SMs and 102 GB/s of memory bandwidth. Both programs time each kernel on a 4096 × 4096 plate after 0.4 s of warm-up and average 50 launches. They report the effective bandwidth of Chapter 19, that is, 8 bytes per cell per step divided by the time of a step. Repeated runs differ by 10 to 20%. On the measured GPU, the C++ program printed the following results.

2. 4096 x 4096 plate, 8 bytes per cell per step (1 read, 1 write)
  copy kernel               1.752 ms     76.6 GB/s
  plain                     1.966 ms     68.3 GB/s
  loop loader               3.089 ms     43.4 GB/s
  extra threads             2.931 ms     45.8 GB/s
  4 steps per load          2.112 ms     63.5 GB/s
  loop loader              same bits as the plain kernel after 8 steps: true
  extra threads            same bits as the plain kernel after 8 steps: true
  4 steps per load         same bits as the plain kernel after 8 steps: true
PASSED

The following table collects these results together with those of the Rust program, and adds the number of global loads per result of each kernel.

KernelGlobal loads per resultC++Rust
copy176.6 GB/s75.0 GB/s
direct (plain)4 requested, about 1.25 from memory68.3 GB/s58.0 GB/s
tiled, loading loop1.3343.4 GB/s34.6 GB/s
tiled, extra threads1.3345.8 GB/s39.2 GB/s
4 steps per load (Section 20.8)0.44 per step63.5 GB/s54.3 GB/s

The tiled kernels load 3 times fewer values than the direct kernel requests, yet they run at 64% and 67% of its speed in C++, and at 60% and 68% in Rust. In other words, the tile made the kernel slower, not faster. The Rust kernels are slower than the C++ kernels throughout, for the reason measured in Section 19.8.4: they compute positions in 64-bit integers and derive the height with a division.

Horizontal bars of effective bandwidth on a 4096 by 4096 grid on the measured GPU, for C++ and Rust: copy, direct kernel, tiled with a loading loop, tiled with extra threads, and 4 steps per load. In C++: 76.6, 68.3, 43.4, 45.8 and 63.5 GB/s. The direct kernel is the fastest stencil kernel in both languages.
Figure 20.9 Effective bandwidth on the measured GPU: neither tiled kernel beats the direct kernel.

20.7.2 Why the tile gains nothing here

Recall from Section 19.8.3 that the direct kernel already moves only about 9 bytes per cell from memory, namely 1.25 reads and 1 write, and that it runs within 12% of a copy. The 4 reads per cell that the direct kernel requests are mostly answered by the L1 and L2 caches, which keep the rows that neighboring warps share (Figure 19.11). The tile loads 1.33 values per result, 340 cells for 256 results, and with the write, this amounts to \(4 \cdot 1.33 + 4 = 9.3\) bytes per cell. The direct kernel already moves this much or less. A tile can remove only the traffic that reaches memory, and in this case, the caches have already removed it.

Two further measurements support this explanation. First, we bypassed the L1 cache in the direct kernel by reading each neighbor with the C++ intrinsic __ldcg, which reads through the L2 cache only. The kernel then ran at 61.4 to 63.7 GB/s, which is 7 to 10% slower. The L2 cache alone thus captures most of the reuse, since the 2 MiB L2 of the measured GPU holds the few rows that the blocks running at the same time share. Second, the tile is not free. The tiled kernels compute a tile position for every slot, store the value to shared memory and read it back, and wait at a barrier. During the wait, a warp that has finished its loads issues no instructions. When we deleted the barrier from the loop loader, which gives wrong results, its time fell from 3.10 ms to 2.83 ms, so the barrier alone costs about 9%. The remaining difference from the direct kernel is instructions. The loading loop runs 1 or 2 iterations per thread with a test at each, and the extra-threads kernel keeps 84 of its 340 threads idle while the others compute.

The result depends on the GPU. On a GPU whose caches are small compared with the number of threads in flight, or that does not cache global loads in L1, the 4 reads per cell of the direct kernel reach memory, and the tile’s 1.33 loads per result reduce the traffic 3-fold. On the measured GPU, the caches capture the reuse of a 5-point stencil, and the tile only adds work. A stencil with more reuse per value leaves more for the tile to capture. Examples are a 3-D stencil of radius 4, which reads 25 values per result, and a kernel that performs several steps on 1 tile. We measure the second in the next section.

Exercises

20.14 The extra-threads kernel launches 340 threads per block. How many warps is that, and how many threads of its last warp have no slot?
20.15 Estimate the time of the tiled kernel from its traffic alone, 9.3 bytes per cell at the copy’s rate. How much of the measured 3.089 ms is not explained by traffic?

20.8 Temporal blocking

20.8.1 Several steps per load

In Section 20.7, we saw that a single step reuses each value too little for the tile to pay. We can increase the reuse by letting a block perform more than 1 step on the values that it has loaded. The tile holds a block’s cells and their neighbors, which is exactly what 1 step of the block’s cells needs. If the tile had 1 more ring of halo, it would hold everything needed to compute 2 steps of the block’s cells. The first step would be computed on the block’s cells and on the inner ring of the halo, and the second step on the block’s cells alone, from the values of the first. In general, \(K\) steps need a halo \(K\) cells wide, because each step can compute correct values only 1 ring further in than the step before.

Definition 20.4 Temporal blocking. In temporal blocking, a block loads a tile with a halo \(K\) cells wide, performs \(K\) steps on it in shared memory, and writes only its own cells after the last step. After the step with number \(\mathsf{step}\), the values are correct on the tile without its outer \(\mathsf{step}\) rings.

Example. Our programs use a tile of 32 × 32 threads with \(K = 4\). The tile holds a 24 × 24 square of the block’s own cells and a halo 4 cells wide; after steps 1, 2, 3 and 4 the correct region is 30 × 30, 28 × 28, 26 × 26 and 24 × 24.

In this section, \(K\) is the number of steps per load and \(\mathsf{step}\) the number of the step inside the tile, from 1 to \(K\). In the example, the 32 × 32 tile loses 1 ring on each of its 4 sides in every step, so its correct region shrinks by 2 cells in each direction per step, from 32 to 30, 28, 26 and finally \(32 - 2 \cdot 4 = 24\) cells. The block’s own cells are the \(24 \times 24\) square that remains after 4 steps.

The steps inside the tile need 2 buffers, for the same reason as in Chapter 19: a step must not overwrite a value that another thread of the same step still has to read. The kernel therefore keeps 2 tiles in shared memory and uses them in turn, with a barrier between steps. This is ping-pong buffering in shared memory. Figure 20.10 shows the 2 tiles and the correct region that shrinks from step to step.

A 32 by 32 tile drawn as nested squares. The outer ring 4 cells wide is the halo, loaded from global memory. After step 1 the correct region is 30 by 30, after step 2 28 by 28, after step 3 26 by 26, after step 4 24 by 24, the block's own cells, which are written to global memory. Beside it, 2 tiles in shared memory, A and B, with arrows A to B for steps 1 and 3 and B to A for steps 2 and 4.
Figure 20.10 Temporal blocking with \(K = 4\): each step loses 1 ring, and after 4 steps the block's own 24 × 24 cells are correct.

Every thread executes the following procedure. Each of the 32 × 32 threads owns 1 slot of the tile, and \(A\) and \(B\) are the 2 tiles in shared memory.

Temporal-Jacobi-Kernel(\(u, v, W, H\))

  1. \((\mathsf{row}, \mathsf{col})\) = cell of this thread, \(K\) cells before the block's first own cell
  2. \(A[\mathsf{threadIdx{.}y}][\mathsf{threadIdx{.}x}] = u_{\mathsf{row},\mathsf{col}}\) if \((\mathsf{row}, \mathsf{col})\) is in the grid, else 0
  3. Barrier()
  4. for \(\mathsf{step} \in [1, K]\) { // src = A, dst = B for odd steps, the reverse for even steps
  5. if \(\mathsf{threadIdx{.}x}, \mathsf{threadIdx{.}y} \in [\mathsf{step}, 32 - \mathsf{step})\) {
  6. \(\mathsf{dst}[\mathsf{threadIdx{.}y}][\mathsf{threadIdx{.}x}]\) = mean of the 4 neighbors in \(\mathsf{src}\) if \((\mathsf{row}, \mathsf{col})\) is interior, else \(\mathsf{src}[\mathsf{threadIdx{.}y}][\mathsf{threadIdx{.}x}]\)
  7. }
  8. Barrier()
  9. }
  10. if \(\mathsf{threadIdx{.}x}, \mathsf{threadIdx{.}y} \in [K, 32 - K)\) and \((\mathsf{row}, \mathsf{col})\) is interior {
  11. \(v_{\mathsf{row},\mathsf{col}}\) = the tile written in step \(K\), at \([\mathsf{threadIdx{.}y}][\mathsf{threadIdx{.}x}]\)
  12. }

Line 1 places the tile \(K\) cells above and to the left of the block’s own cells, so that the halo of width \(K\) surrounds them. Line 2 loads the whole tile, 1 slot per thread, and line 3 waits until the tile is complete. In the step with number \(\mathsf{step}\), line 5 lets only the threads whose slot lies at least \(\mathsf{step}\) positions from every edge of the tile compute. In step 1, for example, these are the positions 1 to 30 in each direction, which form the 30 × 30 region of Definition 20.4. Line 6 reads from the tile written in the previous step, called \(\mathsf{src}\), and writes into the other tile, called \(\mathsf{dst}\). Line 8 is the barrier between steps. Finally, lines 10 to 12 write the block’s own cells, the positions \([K, 32 - K)\), from the tile written in step \(K\).

Theorem 20.2 Launched on 2 different buffers holding the grid \(u^{(k)}\) and its boundary, Temporal-Jacobi-Kernel writes \(u^{(k+K)}\) into every interior cell of \(v\).

Proof. We show that the loop of lines 4 to 9 maintains the invariant: at the start of the pass for step \(\mathsf{step}\), for every position \((\mathsf{threadIdx{.}y}, \mathsf{threadIdx{.}x})\) with \(\mathsf{threadIdx{.}x}, \mathsf{threadIdx{.}y} \in [\mathsf{step} - 1, 33 - \mathsf{step})\) whose cell lies in the grid, the tile \(\mathsf{src}\) holds \(u^{(k+\mathsf{step}-1)}\) of that cell.

Initialization. At \(\mathsf{step} = 1\) the region is the whole tile, and line 2 stored \(u^{(k)}\) in every position whose cell is in the grid; the barrier of line 3 makes the stores visible.

Maintenance. Let \((\mathsf{threadIdx{.}y}, \mathsf{threadIdx{.}x})\) lie in \([\mathsf{step}, 32 - \mathsf{step})\) with its cell in the grid. If the cell is interior, its 4 neighbors lie at positions in \([\mathsf{step} - 1, 33 - \mathsf{step})\) and in the grid, so by the invariant line 6 reads 4 values of \(u^{(k+\mathsf{step}-1)}\) and stores \(u^{(k+\mathsf{step})}\). If the cell is a boundary cell, line 6 copies its value, which is the same in every step. The 2 tiles are different arrays, so no thread writes a value that another reads in the same pass, and the barrier of line 8 completes every store before the next pass reads them. The roles of the tiles exchange, and the invariant holds for \(\mathsf{step} + 1\) on the region \([\mathsf{step}, 32 - \mathsf{step})\).

Termination. After pass \(K\), the tile written last holds \(u^{(k+K)}\) on \([K, 32 - K)\), the block’s own cells, and lines 10 to 12 write them. The own squares of the blocks cover the grid without overlap.

20.8.2 Traffic and work

We now count what temporal blocking saves and what it costs. A launch loads a 32 × 32 tile, 1,024 values, and writes \((32 - 2K)^2\) cells, and it does so for \(K\) steps at once. Per kept cell, the block therefore reads \(1024 / (32 - 2K)^2\) values and writes 1 value, each of 4 bytes, and this traffic is shared among \(K\) steps. The traffic per cell and step is

\[ \frac{4}{K} \left( \frac{1024}{(32 - 2K)^2} + 1 \right) \text{ bytes}. \]

SymbolMeaning\(K = 4\)
\(K\)steps per load4
\(32 - 2K\)width of the block’s own square24
\(1024 / (32 - 2K)^2\)values loaded per kept cell\(1024 / 576 = 1.78\)
\(+ 1\)the 1 value written per kept cell1
\(4 / K\)4 bytes per value, shared among \(K\) steps1

For \(K = 4\), the traffic is \(1 \cdot (1.78 + 1) = 2.78\) bytes per cell and step, against about 9 bytes for the direct kernel. The price of this saving is work. In every step, all 1,024 threads of the block run the loop and wait at the barrier, although only \((32 - 2K)^2\) cells per block are kept. Per kept cell and step, a launch therefore runs \(1024 / (32 - 2K)^2\) thread-steps, where a thread-step is 1 pass of 1 thread through the loop. For \(K = 4\), this is 1.78 thread-steps. We measured the C++ kernel for several values of \(K\) in 1 run, in which the direct kernel reached 65.0 GB/s. The following table gives the results.

\(K\)Own cells per blockBytes per cell and stepThread-steps per cell and stepMeasured
130 × 308.551.1430.3 GB/s
228 × 284.611.3148.4 GB/s
424 × 242.781.7862.4 GB/s
620 × 202.372.5657.1 GB/s
816 × 162.504.0043.7 GB/s
A chart over K = 1, 2, 4, 6, 8 steps per load. Bars give the modeled bytes per cell and step: 8.55, 4.61, 2.78, 2.37, 2.50. Under each bar, the thread-steps per kept cell and step: 1.14, 1.31, 1.78, 2.56, 4.00. Points give the measured effective bandwidth: 30.3, 48.4, 62.4, 57.1, 43.7 GB/s, highest at K = 4. A dashed line marks the direct kernel in the same run at 65.0 GB/s.
Figure 20.11 Temporal blocking on the measured GPU: traffic falls with \(K\), work grows, and the speed peaks at \(K = 4\), below the direct kernel.

From \(K = 1\) to \(K = 4\), the traffic falls by a factor of 3, and the speed doubles. Beyond \(K = 4\), the traffic hardly changes, while the work per cell grows from 1.78 to 4 thread-steps, and the speed falls again. The time of the kernel now follows its work rather than its traffic. At its best, with \(K = 4\), the temporal kernel reached 62.4 GB/s in this run, 96% of the direct kernel’s 65.0 GB/s, while moving a third of the bytes. In the run of Section 20.7, the two kernels reached 63.5 and 68.3 GB/s, a ratio of 93%. On the measured GPU, with 8 SMs, a 5-point step costs about as much in instructions as in memory traffic once the caches have done their part, so neither tiling nor temporal blocking beats the direct kernel. On a GPU with more arithmetic per byte of bandwidth, such as those with ridge points of 60 to 110 FLOP per byte in Chapter 2, the same reduction of traffic leaves more room for the extra work. Temporal blocking is used on such GPUs, and for stencils with more work per cell.

Exercises

20.16 Derive the traffic formula of Section 20.8.2. What is its limit for large tiles and fixed \(K\)?
20.17 With 1,024 threads per block and 8 KiB of shared memory per block, how many blocks of the temporal kernel fit on an SM with 1,536 threads and 100 KiB of shared memory? What limits the number?
20.18 Design a temporal kernel in which each thread computes 2 cells of a 64 × 32 tile, so that fewer threads idle in the outer rings. Predict its thread-steps per cell for \(K = 4\).

20.9 The complete programs

Listing 20.3 The complete programs. code/oxide/ch20_stencil_tiled/src/main.rs code/cuda/ch20_stencil_tiled/stencil_tiled.cu

//! Chapter 20: tiled Jacobi steps with halo cells in shared memory, in Rust.
//!
//!     cargo oxide run

use std::sync::Arc;
use std::time::Instant;

use cuda_core::{CudaContext, CudaStream, DeviceBuffer, LaunchConfig1D, LaunchConfig2D};
use cuda_device::thread::Runtime2DIndex;
use cuda_device::{DisjointSlice, SharedArray, cuda_module, kernel, launch_contract, thread};
use cuda_host::RowWidth;

const BLOCK_WIDTH: usize = 32; // cells computed by a block, across
const BLOCK_HEIGHT: usize = 8; // cells computed by a block, down
const TILE_WIDTH: usize = BLOCK_WIDTH + 2; // the block's cells and a 1-cell halo
const TILE_HEIGHT: usize = BLOCK_HEIGHT + 2;
const TEMPORAL_TILE: usize = 32; // temporal blocking: a 32 x 32 tile, 1 thread per cell
const STEPS: usize = 4; // temporal blocking: Jacobi steps per load
const OWN_WIDTH: usize = TEMPORAL_TILE - 2 * STEPS; // temporal blocking: cells written
const HOT: f32 = 100.0; // the top edge; the other edges are held at 0

type Error = Box<dyn std::error::Error>;

#[cuda_module]
mod kernels {
    use super::*;

    /// 1 Jacobi step, 1 thread per cell, every neighbor read from global memory.
    #[kernel]
    #[launch_contract(domain = 2, block = (32, 8, 1))]
    pub fn jacobi(old: &[f32], mut new: DisjointSlice<f32, Runtime2DIndex>) {
        let width = new.row_width() as usize;
        let height = new.len() / width;

        if let Some(idx) = thread::index_2d_runtime(&new) {
            let (row, col) = (idx.row(), idx.col());
            let interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

            if interior {
                let center = row * width + col;
                let (up, down) = (old[center - width], old[center + width]);
                let (to_left, to_right) = (old[center - 1], old[center + 1]);
                let sum = up + down + to_left + to_right;

                if let Some(cell) = new.get_mut(idx) {
                    *cell = 0.25 * sum;
                }
            }
        }
    }

    /// 1 Jacobi step from a 34 x 10 tile; 32 x 8 threads load it, some 2 or 4 cells each.
    #[kernel]
    #[launch_contract(domain = 2, block = (32, 8, 1))]
    pub fn jacobi_tiled(old: &[f32], mut new: DisjointSlice<f32, Runtime2DIndex>) {
        const AREA: usize = TILE_WIDTH * TILE_HEIGHT;
        static mut TILE: SharedArray<f32, AREA> = SharedArray::UNINIT;

        let width = new.row_width() as usize;
        let height = new.len() / width;
        let thread_x = thread::threadIdx_x() as usize;
        let thread_y = thread::threadIdx_y() as usize;
        let top = thread::blockIdx_y() as usize * BLOCK_HEIGHT;
        let left = thread::blockIdx_x() as usize * BLOCK_WIDTH;

        let mut slot_row = thread_y;
        while slot_row < TILE_HEIGHT {
            let mut slot_col = thread_x;
            while slot_col < TILE_WIDTH {
                let cell_row = (top + slot_row).wrapping_sub(1);
                let cell_col = (left + slot_col).wrapping_sub(1);
                let inside = cell_row < height && cell_col < width;
                let value = if inside { old[cell_row * width + cell_col] } else { 0.0 };

                // SAFETY: slot (slot_row, slot_col) is written by 1 thread alone,
                // the thread (slot_row mod 8, slot_col mod 32).
                unsafe { TILE[slot_row * TILE_WIDTH + slot_col] = value };
                slot_col += BLOCK_WIDTH;
            }
            slot_row += BLOCK_HEIGHT;
        }
        thread::sync_threads();

        if let Some(idx) = thread::index_2d_runtime(&new) {
            let (row, col) = (idx.row(), idx.col());
            let interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

            if interior {
                let center = (thread_y + 1) * TILE_WIDTH + thread_x + 1;
                // SAFETY: after the barrier no thread writes the tile.
                let up = unsafe { TILE[center - TILE_WIDTH] };
                // SAFETY: as above.
                let down = unsafe { TILE[center + TILE_WIDTH] };
                // SAFETY: as above.
                let (to_left, to_right) = unsafe { (TILE[center - 1], TILE[center + 1]) };
                let sum = up + down + to_left + to_right;

                if let Some(cell) = new.get_mut(idx) {
                    *cell = 0.25 * sum;
                }
            }
        }
    }

    /// 1 Jacobi step from a 34 x 10 tile; 34 x 10 threads load 1 cell each, 32 x 8 compute.
    #[kernel]
    #[launch_contract(domain = 2, block = (34, 10, 1))]
    pub fn jacobi_halo_threads(old: &[f32], mut new: DisjointSlice<f32, Runtime2DIndex>) {
        const AREA: usize = TILE_WIDTH * TILE_HEIGHT;
        static mut TILE: SharedArray<f32, AREA> = SharedArray::UNINIT;

        let width = new.row_width() as usize;
        let height = new.len() / width;
        let slot_col = thread::threadIdx_x() as usize;
        let slot_row = thread::threadIdx_y() as usize;
        let row = (thread::blockIdx_y() as usize * BLOCK_HEIGHT + slot_row).wrapping_sub(1);
        let col = (thread::blockIdx_x() as usize * BLOCK_WIDTH + slot_col).wrapping_sub(1);
        let slot = slot_row * TILE_WIDTH + slot_col;

        let value = if row < height && col < width { old[row * width + col] } else { 0.0 };
        // SAFETY: the slot belongs to this thread alone.
        unsafe { TILE[slot] = value };
        thread::sync_threads();

        let inner_row = slot_row >= 1 && slot_row <= BLOCK_HEIGHT;
        let inner_col = slot_col >= 1 && slot_col <= BLOCK_WIDTH;
        let interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

        if inner_row && inner_col && interior {
            // SAFETY: after the barrier no thread writes the tile.
            let (up, down) = unsafe { (TILE[slot - TILE_WIDTH], TILE[slot + TILE_WIDTH]) };
            // SAFETY: as above.
            let (to_left, to_right) = unsafe { (TILE[slot - 1], TILE[slot + 1]) };
            let sum = up + down + to_left + to_right;

            // SAFETY: the inner threads of the blocks cover each cell of the grid once,
            // so no other thread writes cell (row, col), which lies inside `new`.
            unsafe { *new.get_unchecked_mut(row * width + col) = 0.25 * sum };
        }
    }

    /// STEPS Jacobi steps from 1 load: a 32 x 32 tile, ping-pong in shared memory.
    #[kernel]
    #[launch_contract(domain = 2, block = (32, 32, 1))]
    pub fn jacobi_temporal(old: &[f32], mut new: DisjointSlice<f32, Runtime2DIndex>) {
        const AREA: usize = TEMPORAL_TILE * TEMPORAL_TILE;
        static mut TILES: SharedArray<f32, { 2 * AREA }> = SharedArray::UNINIT;

        let width = new.row_width() as usize;
        let height = new.len() / width;
        let slot_col = thread::threadIdx_x() as usize;
        let slot_row = thread::threadIdx_y() as usize;
        let first_row = thread::blockIdx_y() as usize * OWN_WIDTH;
        let first_col = thread::blockIdx_x() as usize * OWN_WIDTH;
        let row = (first_row + slot_row).wrapping_sub(STEPS);
        let col = (first_col + slot_col).wrapping_sub(STEPS);
        let slot = slot_row * TEMPORAL_TILE + slot_col;
        let inside = row < height && col < width;
        let interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

        let value = if inside { old[row * width + col] } else { 0.0 };
        // SAFETY: this slot of the first tile belongs to this thread alone.
        unsafe { TILES[slot] = value };
        thread::sync_threads();

        let mut step = 1;
        #[unroll]
        while step <= STEPS {
            let src = (step - 1) % 2 * AREA + slot;
            let dst = step % 2 * AREA + slot;
            let last = TEMPORAL_TILE - step;
            let valid_row = slot_row >= step && slot_row < last;
            let valid_col = slot_col >= step && slot_col < last;

            if valid_row && valid_col {
                // SAFETY: in this step the tile at src is only read, slot dst belongs to
                // this thread alone, and the barrier below separates the steps.
                unsafe {
                    let up = TILES[src - TEMPORAL_TILE];
                    let down = TILES[src + TEMPORAL_TILE];
                    let (to_left, to_right) = (TILES[src - 1], TILES[src + 1]);
                    let sum = up + down + to_left + to_right;
                    TILES[dst] = if interior { 0.25 * sum } else { TILES[src] };
                }
            }
            thread::sync_threads();
            step += 1;
        }

        let end = TEMPORAL_TILE - STEPS;
        let owned_row = slot_row >= STEPS && slot_row < end;
        let owned_col = slot_col >= STEPS && slot_col < end;
        if owned_row && owned_col && interior {
            let last = STEPS % 2 * AREA + slot;
            // SAFETY: the owned squares of the blocks cover each cell of the grid once,
            // so no other thread writes cell (row, col), which lies inside `new`.
            unsafe { *new.get_unchecked_mut(row * width + col) = TILES[last] };
        }
    }

    /// A copy: 1 read and 1 write per cell, the least traffic a step can have.
    #[kernel]
    #[launch_contract(domain = 1, block = (256, 1, 1))]
    pub fn copy(input: &[f32], mut out: DisjointSlice<f32>) {
        let idx = thread::index_1d();
        let index = idx.get();

        if let Some(out_cell) = out.get_mut(idx) {
            *out_cell = input[index];
        }
    }
}

/// The 4 ways to advance the plate: 1 step per launch, or STEPS steps per launch.
#[derive(Clone, Copy, PartialEq)]
enum Kind {
    Plain,
    Tiled,
    HaloThreads,
    Temporal,
}

impl Kind {
    fn steps_per_launch(self) -> usize {
        if self == Kind::Temporal { STEPS } else { 1 }
    }
}

type Buffer = DeviceBuffer<f32>;

/// The 4 kernels prepared for a plate of `width` x `height` cells, as 1 launch function.
fn stepper<'a>(
    module: &'a kernels::LoadedModule,
    stream: &'a Arc<CudaStream>,
    width: usize,
    height: usize,
) -> Result<impl Fn(Kind, &Buffer, &mut Buffer) -> Result<(), Error> + 'a, Error> {
    let block_columns = width.div_ceil(BLOCK_WIDTH) as u32;
    let block_rows = height.div_ceil(BLOCK_HEIGHT) as u32;
    let blocks = (block_columns, block_rows);
    let squares = (width.div_ceil(OWN_WIDTH) as u32, height.div_ceil(OWN_WIDTH) as u32);

    let block = (BLOCK_WIDTH as u32, BLOCK_HEIGHT as u32);
    let tile_block = (TILE_WIDTH as u32, TILE_HEIGHT as u32);
    let square = (TEMPORAL_TILE as u32, TEMPORAL_TILE as u32);

    let one_per_cell = LaunchConfig2D::new(blocks, block, 0);
    let one_per_tile_cell = LaunchConfig2D::new(blocks, tile_block, 0);
    let several_steps = LaunchConfig2D::new(squares, square, 0);

    let plain = module.prepare_jacobi(one_per_cell)?;
    let tiled = module.prepare_jacobi_tiled(one_per_cell)?;
    let halo = module.prepare_jacobi_halo_threads(one_per_tile_cell)?;
    let temporal = module.prepare_jacobi_temporal(several_steps)?;

    Ok(move |kind: Kind, old: &Buffer, new: &mut Buffer| {
        let new = RowWidth::new(new, width as u32);
        match kind {
            Kind::Plain => module.jacobi(stream, &plain, old, new)?,
            Kind::Tiled => module.jacobi_tiled(stream, &tiled, old, new)?,
            Kind::HaloThreads => module.jacobi_halo_threads(stream, &halo, old, new)?,
            Kind::Temporal => module.jacobi_temporal(stream, &temporal, old, new)?,
        }
        Ok(())
    })
}

/// The plate after `steps` Jacobi steps of `kind`, starting from `start`.
fn run(
    stream: &Arc<CudaStream>,
    launch: &impl Fn(Kind, &Buffer, &mut Buffer) -> Result<(), Error>,
    kind: Kind,
    start: &[f32],
    steps: usize,
) -> Result<Vec<f32>, Error> {
    let mut current = DeviceBuffer::from_host(stream, start)?;
    let mut next = DeviceBuffer::from_host(stream, start)?;

    for _ in 0..steps / kind.steps_per_launch() {
        launch(kind, &current, &mut next)?;
        std::mem::swap(&mut current, &mut next);
    }
    Ok(current.to_host_vec(stream)?)
}

/// A plate of `width` x `height` cells: the top row at HOT, every other cell at 0.
fn initial_grid(width: usize, height: usize) -> Vec<f32> {
    let mut grid = vec![0.0; width * height];
    grid[..width].fill(HOT);
    grid
}

fn print_grid(label: &str, grid: &[f32], width: usize) {
    println!("  {label}");
    for row in grid.chunks(width) {
        let cells: Vec<String> = row.iter().map(|value| format!("{value:7.2}")).collect();
        println!("    {}", cells.join(" "));
    }
}

/// Average time of `runs` calls of `launch`, in milliseconds, after 0.4 s of warm-up.
fn time_ms(
    stream: &Arc<CudaStream>,
    runs: u32,
    mut launch: impl FnMut() -> Result<(), Error>,
) -> Result<f64, Error> {
    let warm = Instant::now();
    while warm.elapsed().as_secs_f64() < 0.4 {
        launch()?;
        stream.synchronize()?;
    }

    let start = Instant::now();
    for _ in 0..runs {
        launch()?;
    }
    stream.synchronize()?;

    Ok(start.elapsed().as_secs_f64() * 1e3 / runs as f64)
}

fn main() -> Result<(), Error> {
    let ctx = CudaContext::new(0)?;
    let stream = ctx.default_stream();
    // SAFETY: the loaded code was compiled from the `kernels` module above.
    let module = unsafe { kernels::load(&ctx)? };

    let name = ctx.device_name()?;
    let sms = ctx.multiprocessor_count()?;
    println!("GPU: {name}, {sms} SMs");

    let kinds = [Kind::Tiled, Kind::HaloThreads, Kind::Temporal];
    let names = ["loop loader", "extra threads", "4 steps per load"];

    // 1. The 6 x 6 plate of the text: every tiled kernel against the plain kernel.
    let (width, height) = (6, 6);
    let start = initial_grid(width, height);
    let small = stepper(&module, &stream, width, height)?;

    println!("1. 6 x 6 plate, top edge at {HOT}");
    let after_two = run(&stream, &small, Kind::Tiled, &start, 2)?;
    print_grid("after step 2, tiled", &after_two, width);

    let mut small_same = true;
    let reference = run(&stream, &small, Kind::Plain, &start, 4)?;
    for (kind, name) in kinds.iter().zip(names) {
        let same = run(&stream, &small, *kind, &start, 4)? == reference;
        println!("  {name:24} same bits as the plain kernel after 4 steps: {same}");
        small_same &= same;
    }

    // 2. A 4096 x 4096 plate: time per step and effective bandwidth.
    let (width, height) = (4096, 4096);
    let cells = width * height;
    let start = initial_grid(width, height);
    let big = stepper(&module, &stream, width, height)?;
    let mut current = DeviceBuffer::from_host(&stream, &start)?;
    let mut next = DeviceBuffer::from_host(&stream, &start)?;
    let copy = module.prepare_copy(LaunchConfig1D::new((cells / 256) as u32, 256, 0))?;

    let gb = |ms: f64| (2 * cells * 4) as f64 / 1e9 / (ms / 1e3);
    println!("2. 4096 x 4096 plate, 8 bytes per cell per step (1 read, 1 write)");

    let copy_once = || Ok(module.copy(&stream, &copy, &current, &mut next)?);
    let ms = time_ms(&stream, 50, copy_once)?;
    println!("  {:24} {ms:6.3} ms   {:6.1} GB/s", "copy kernel", gb(ms));

    let all_kinds = [Kind::Plain, Kind::Tiled, Kind::HaloThreads, Kind::Temporal];
    let all_names = ["plain", names[0], names[1], names[2]];
    for (kind, name) in all_kinds.iter().zip(all_names) {
        let two_launches = time_ms(&stream, 50, || {
            big(*kind, &current, &mut next)?;
            big(*kind, &next, &mut current)
        })?;
        let ms = two_launches / (2 * kind.steps_per_launch()) as f64;
        println!("  {name:24} {ms:6.3} ms   {:6.1} GB/s", gb(ms));
    }

    let mut big_same = true;
    let reference = run(&stream, &big, Kind::Plain, &start, 8)?;
    for (kind, name) in kinds.iter().zip(names) {
        let same = run(&stream, &big, *kind, &start, 8)? == reference;
        println!("  {name:24} same bits as the plain kernel after 8 steps: {same}");
        big_same &= same;
    }

    let passed = small_same && big_same;
    println!("{}", if passed { "PASSED" } else { "FAILED" });
    Ok(())
}
// Chapter 20: tiled Jacobi steps with halo cells in shared memory.
// Build: nvcc -O3 -arch=native stencil_tiled.cu -o stencil_tiled

#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <vector>
#include <cuda_runtime.h>

using Grid = std::vector<float>;

const int BLOCK_WIDTH = 32;                   // cells computed by a block, across
const int BLOCK_HEIGHT = 8;                   // cells computed by a block, down
const int TILE_WIDTH = BLOCK_WIDTH + 2;       // the block's cells and the halo
const int TILE_HEIGHT = BLOCK_HEIGHT + 2;
const int TEMPORAL_TILE = 32;                 // temporal blocking: a 32 x 32 tile
const int STEPS = 4;                          // temporal blocking: Jacobi steps per load
const int OWN_WIDTH = TEMPORAL_TILE - 2 * STEPS;  // temporal blocking: cells written
const float HOT = 100.0f;                     // the top edge; the others are held at 0

enum Kind { PLAIN, TILED, HALO_THREADS, TEMPORAL };

void check(cudaError_t err)
{
    if (err != cudaSuccess) {
        std::fprintf(stderr, "CUDA error: %s\n", cudaGetErrorString(err));
        std::exit(1);
    }
}

// 1 Jacobi step, 1 thread per cell, every neighbor read from global memory.
__global__ void jacobi(const float* __restrict__ old, float* __restrict__ next,
                       int width, int height)
{
    int row = blockIdx.y * BLOCK_HEIGHT + threadIdx.y;
    int col = blockIdx.x * BLOCK_WIDTH + threadIdx.x;
    bool interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

    if (interior) {
        int center = row * width + col;
        float up = old[center - width];
        float down = old[center + width];
        float sum = up + down + old[center - 1] + old[center + 1];
        next[center] = 0.25f * sum;
    }
}

// 1 Jacobi step from a 34 x 10 tile; 32 x 8 threads load it, some 2 or 4 cells each.
__global__ void jacobiTiled(const float* __restrict__ old, float* __restrict__ next,
                            int width, int height)
{
    __shared__ float tile[TILE_HEIGHT][TILE_WIDTH];
    int top = blockIdx.y * BLOCK_HEIGHT;
    int left = blockIdx.x * BLOCK_WIDTH;

    for (int slot_row = threadIdx.y; slot_row < TILE_HEIGHT; slot_row += BLOCK_HEIGHT) {
        for (int slot_col = threadIdx.x; slot_col < TILE_WIDTH; slot_col += BLOCK_WIDTH) {
            int cell_row = top + slot_row - 1;
            int cell_col = left + slot_col - 1;
            bool row_inside = cell_row >= 0 && cell_row < height;
            bool col_inside = cell_col >= 0 && cell_col < width;
            int cell = cell_row * width + cell_col;
            tile[slot_row][slot_col] = row_inside && col_inside ? old[cell] : 0.0f;
        }
    }
    __syncthreads();

    int row = top + threadIdx.y;
    int col = left + threadIdx.x;
    bool interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

    if (interior) {
        int center_row = threadIdx.y + 1;
        int center_col = threadIdx.x + 1;
        float up = tile[center_row - 1][center_col];
        float down = tile[center_row + 1][center_col];
        float to_left = tile[center_row][center_col - 1];
        float to_right = tile[center_row][center_col + 1];
        next[row * width + col] = 0.25f * (up + down + to_left + to_right);
    }
}

// 1 Jacobi step from a 34 x 10 tile; 34 x 10 threads load 1 cell each, 32 x 8 compute.
__global__ void jacobiHaloThreads(const float* __restrict__ old, float* __restrict__ next,
                                  int width, int height)
{
    __shared__ float tile[TILE_HEIGHT][TILE_WIDTH];
    int slot_row = threadIdx.y;
    int slot_col = threadIdx.x;
    int row = blockIdx.y * BLOCK_HEIGHT + slot_row - 1;
    int col = blockIdx.x * BLOCK_WIDTH + slot_col - 1;

    bool inside = row >= 0 && row < height && col >= 0 && col < width;
    tile[slot_row][slot_col] = inside ? old[row * width + col] : 0.0f;
    __syncthreads();

    bool inner_row = slot_row >= 1 && slot_row <= BLOCK_HEIGHT;
    bool inner_col = slot_col >= 1 && slot_col <= BLOCK_WIDTH;
    bool interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

    if (inner_row && inner_col && interior) {
        float up = tile[slot_row - 1][slot_col];
        float down = tile[slot_row + 1][slot_col];
        float to_left = tile[slot_row][slot_col - 1];
        float to_right = tile[slot_row][slot_col + 1];
        next[row * width + col] = 0.25f * (up + down + to_left + to_right);
    }
}

// STEPS Jacobi steps from 1 load: a 32 x 32 tile, ping-pong in shared memory.
__global__ void jacobiTemporal(const float* __restrict__ old, float* __restrict__ next,
                               int width, int height)
{
    __shared__ float tiles[2][TEMPORAL_TILE][TEMPORAL_TILE];
    int slot_row = threadIdx.y;
    int slot_col = threadIdx.x;
    int row = blockIdx.y * OWN_WIDTH + slot_row - STEPS;
    int col = blockIdx.x * OWN_WIDTH + slot_col - STEPS;
    bool inside = row >= 0 && row < height && col >= 0 && col < width;
    bool interior = row >= 1 && row + 1 < height && col >= 1 && col + 1 < width;

    tiles[0][slot_row][slot_col] = inside ? old[row * width + col] : 0.0f;
    __syncthreads();

    #pragma unroll
    for (int step = 1; step <= STEPS; ++step) {
        int src = (step - 1) % 2;
        int dst = step % 2;
        int last = TEMPORAL_TILE - step;
        bool valid_row = slot_row >= step && slot_row < last;
        bool valid_col = slot_col >= step && slot_col < last;

        if (valid_row && valid_col) {
            float up = tiles[src][slot_row - 1][slot_col];
            float down = tiles[src][slot_row + 1][slot_col];
            float to_left = tiles[src][slot_row][slot_col - 1];
            float to_right = tiles[src][slot_row][slot_col + 1];
            float mean = 0.25f * (up + down + to_left + to_right);
            float same = tiles[src][slot_row][slot_col];
            tiles[dst][slot_row][slot_col] = interior ? mean : same;
        }
        __syncthreads();
    }

    int end = TEMPORAL_TILE - STEPS;
    bool owned = slot_col >= STEPS && slot_col < end && slot_row >= STEPS && slot_row < end;
    if (owned && interior) {
        next[row * width + col] = tiles[STEPS % 2][slot_row][slot_col];
    }
}

// A copy: 1 read and 1 write per cell, the least traffic a step can have.
__global__ void copy(const float* __restrict__ in, float* __restrict__ out, int n)
{
    int index = blockIdx.x * blockDim.x + threadIdx.x;
    if (index < n) {
        out[index] = in[index];
    }
}

int stepsPerLaunch(Kind kind)
{
    return kind == TEMPORAL ? STEPS : 1;
}

// 1 launch of `kind` on a plate of width x height cells, reading `old`, writing `next`.
void launch(Kind kind, const float* old, float* next, int width, int height)
{
    int block_columns = (width + BLOCK_WIDTH - 1) / BLOCK_WIDTH;
    int block_rows = (height + BLOCK_HEIGHT - 1) / BLOCK_HEIGHT;
    dim3 blocks(block_columns, block_rows);
    dim3 squares((width + OWN_WIDTH - 1) / OWN_WIDTH, (height + OWN_WIDTH - 1) / OWN_WIDTH);
    dim3 block(BLOCK_WIDTH, BLOCK_HEIGHT);
    dim3 tile_block(TILE_WIDTH, TILE_HEIGHT);
    dim3 square(TEMPORAL_TILE, TEMPORAL_TILE);

    switch (kind) {
    case PLAIN:
        jacobi<<<blocks, block>>>(old, next, width, height);
        break;
    case TILED:
        jacobiTiled<<<blocks, block>>>(old, next, width, height);
        break;
    case HALO_THREADS:
        jacobiHaloThreads<<<blocks, tile_block>>>(old, next, width, height);
        break;
    case TEMPORAL:
        jacobiTemporal<<<squares, square>>>(old, next, width, height);
        break;
    }
}

// A plate of width x height cells: the top row at HOT, every other cell at 0.
Grid initialGrid(int width, int height)
{
    Grid grid(size_t(width) * height, 0.0f);
    for (int col = 0; col < width; ++col) {
        grid[col] = HOT;
    }
    return grid;
}

// The plate after `steps` Jacobi steps of `kind`, starting from `start`.
Grid run(Kind kind, const Grid& start, int width, int height, int steps)
{
    size_t bytes = start.size() * sizeof(float);
    float *current, *next;
    check(cudaMalloc(&current, bytes));
    check(cudaMalloc(&next, bytes));
    check(cudaMemcpy(current, start.data(), bytes, cudaMemcpyHostToDevice));
    check(cudaMemcpy(next, start.data(), bytes, cudaMemcpyHostToDevice));

    for (int launches = 0; launches < steps / stepsPerLaunch(kind); ++launches) {
        launch(kind, current, next, width, height);
        std::swap(current, next);
    }
    check(cudaGetLastError());

    Grid result(start.size());
    check(cudaMemcpy(result.data(), current, bytes, cudaMemcpyDeviceToHost));
    check(cudaFree(current));
    check(cudaFree(next));
    return result;
}

void printGrid(const char* label, const Grid& grid, int width)
{
    std::printf("  %s\n", label);
    for (size_t i = 0; i < grid.size(); ++i) {
        const char* gap = i % width == 0 ? "    " : " ";
        const char* end = i % width == size_t(width - 1) ? "\n" : "";
        std::printf("%s%7.2f%s", gap, grid[i], end);
    }
}

double nowMs()
{
    using namespace std::chrono;
    return duration<double, std::milli>(steady_clock::now().time_since_epoch()).count();
}

// Average time of `runs` calls of `launch`, in milliseconds, after 0.4 s of warm-up.
template <typename F>
double timeMs(F launch, int runs)
{
    double warm = nowMs();
    while (nowMs() - warm < 400.0) {
        launch();
        check(cudaDeviceSynchronize());
    }

    double t0 = nowMs();
    for (int timed = 0; timed < runs; ++timed) {
        launch();
    }
    check(cudaGetLastError());
    check(cudaDeviceSynchronize());

    return (nowMs() - t0) / runs;
}

int main()
{
    cudaDeviceProp prop;
    check(cudaGetDeviceProperties(&prop, 0));
    std::printf("GPU: %s, %d SMs\n", prop.name, prop.multiProcessorCount);

    Kind kinds[] = {TILED, HALO_THREADS, TEMPORAL};
    const char* names[] = {"loop loader", "extra threads", "4 steps per load"};

    // 1. The 6 x 6 plate of the text: every tiled kernel against the plain kernel.
    int width = 6;
    int height = 6;
    Grid start = initialGrid(width, height);

    std::printf("1. 6 x 6 plate, top edge at %.0f\n", HOT);
    printGrid("after step 2, tiled", run(TILED, start, width, height, 2), width);

    bool smallSame = true;
    Grid reference = run(PLAIN, start, width, height, 4);
    for (int index = 0; index < 3; ++index) {
        bool same = run(kinds[index], start, width, height, 4) == reference;
        std::printf("  %-24s same bits as the plain kernel", names[index]);
        std::printf(" after 4 steps: %s\n", same ? "true" : "false");
        smallSame = smallSame && same;
    }

    // 2. A 4096 x 4096 plate: time per step and effective bandwidth.
    width = 4096;
    height = 4096;
    int cells = width * height;
    start = initialGrid(width, height);
    size_t bytes = start.size() * sizeof(float);
    float *current, *next;
    check(cudaMalloc(&current, bytes));
    check(cudaMalloc(&next, bytes));
    check(cudaMemcpy(current, start.data(), bytes, cudaMemcpyHostToDevice));
    check(cudaMemcpy(next, start.data(), bytes, cudaMemcpyHostToDevice));

    auto gb = [&](double ms) { return 2.0 * cells * 4 / 1e9 / (ms / 1e3); };
    std::printf("2. 4096 x 4096 plate, 8 bytes per cell per step (1 read, 1 write)\n");

    double ms = timeMs([&] { copy<<<cells / 256, 256>>>(current, next, cells); }, 50);
    std::printf("  %-24s %6.3f ms   %6.1f GB/s\n", "copy kernel", ms, gb(ms));

    Kind allKinds[] = {PLAIN, TILED, HALO_THREADS, TEMPORAL};
    const char* allNames[] = {"plain", names[0], names[1], names[2]};
    for (int index = 0; index < 4; ++index) {
        Kind kind = allKinds[index];
        auto twoLaunches = [&] {
            launch(kind, current, next, width, height);
            launch(kind, next, current, width, height);
        };
        ms = timeMs(twoLaunches, 50) / (2 * stepsPerLaunch(kind));
        std::printf("  %-24s %6.3f ms   %6.1f GB/s\n", allNames[index], ms, gb(ms));
    }
    check(cudaFree(current));
    check(cudaFree(next));

    bool bigSame = true;
    reference = run(PLAIN, start, width, height, 8);
    for (int index = 0; index < 3; ++index) {
        bool same = run(kinds[index], start, width, height, 8) == reference;
        std::printf("  %-24s same bits as the plain kernel", names[index]);
        std::printf(" after 8 steps: %s\n", same ? "true" : "false");
        bigSame = bigSame && same;
    }

    bool passed = smallSame && bigSame;
    std::printf("%s\n", passed ? "PASSED" : "FAILED");
    return passed ? 0 : 1;
}

Common mistakes

  • Leaving out the barrier between loading and computing. Threads then read slots that other threads have not filled; on small tests inside 1 warp, the error may not appear (Section 20.5.1).
  • Placing the barrier inside a condition. A thread whose cell is on the boundary or outside the grid must still reach the barrier.
  • Loading only the block’s own cells. The cells on the edge of the block then lose the neighbors that belong to other blocks. Step 1 of the plate is still correct, so test more than 1 step (Section 20.5.2).
  • Reading outside the grid while loading the halo. Blocks on the edge of the grid have slots outside it; store 0 there and never read it.
  • Expecting a tile to beat the caches. Measure the direct kernel first. A 5-point stencil reuses each value only 4 times, and the L1 and L2 caches already capture most of that reuse.
  • Growing the halo of temporal blocking without counting the work. Each extra step removes a ring of results; past a few steps, the idle threads cost more than the saved traffic.

Summary

  • In the direct kernel, each value of the grid is read by up to 4 threads: on the 6 × 6 plate, 16 threads make 64 reads of 32 values.
  • A block copies a tile into shared memory, made of its own cells and a halo 1 cell wide. Block (1, 1) of the plate loads a 4 × 4 tile, 4 own cells and 12 halo cells, and computes cell (2, 2) = 6.25 from it.
  • The halo is loaded either by extra threads, 1 per slot, or by a loop in which some threads load 2 or more slots.
  • Without the barrier, a thread reads a slot before it is filled: 124,322 to 126,302 wrong cells per step on a 4096 × 4096 grid. Without the halo, row 1 of the plate becomes 25, 31.25, 31.25, 25 in step 2.
  • Theorem 20.1 shows that the tiled kernel writes exactly what the direct kernel writes, given 1 loader per slot, the barrier, and a tile that covers every neighbor.
  • A tile of \(T \times T\) costs \((T + 2)^2 / T^2\) loads per result: 1.33 for 32 × 8, against 4 requested by the direct kernel.
  • On the measured GPU, the caches already reduce the direct kernel to about 1.25 loads per cell, so the tiled kernels ran slower, at 43.4 and 45.8 GB/s against 68.3 GB/s.
  • Temporal blocking with \(K = 4\) steps per load cuts the traffic to 2.78 bytes per cell and step and reached 63.5 GB/s, 93% of the direct kernel; beyond \(K = 4\), the extra work outweighs the saved traffic.

Exercises

  1. Draw the tile of block (0, 2) of the plate with 2 × 2 blocks in step 2, and compute its 4 cells from the tile.
  2. A 9-point stencil also reads the 4 diagonal neighbors. Which slots of the tile become necessary, and how does the reuse per value change?
  3. Implement a 3-D 7-point stencil on a 256 × 256 × 256 grid, directly and with a tile of 32 × 8 cells in each of 3 consecutive planes. Count the loads per result of both and measure them.
  4. Change the tiled kernel so that each thread computes 2 cells in the same column. How does the ratio of halo to own cells change, and what happens to the speed?
  5. Extend Theorem 20.2 to a tile that is not square, of \(\mathsf{blockDim{.}x} \times \mathsf{blockDim{.}y}\) threads.

Sources and further reading

  • A. Pathak, An Introduction to Tiled Parallel Programming, Simplified, 2026. Tiles, the 2 barriers, and a loop-invariant proof for the matrix product.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th edition, MIT Press, 2022. Pseudocode conventions and loop invariants.
  • P. Micikevicius, “3D Finite Difference Computation on GPUs using CUDA”, Proceedings of the 2nd Workshop on General Purpose Processing on Graphics Processing Units, 2009. Tiles with halos for high-order 3-D stencils.
  • A. Nguyen, N. Satish, J. Chhugani, C. Kim and P. Dubey, “3.5-D Blocking Optimization for Stencil Computations on Modern CPUs and GPUs”, Proceedings of SC10, 2010. Spatial and temporal blocking of stencils.
  • NVIDIA, CUDA C++ Programming Guide: shared memory, __syncthreads(), and the caching of global loads.