Memory Access Patterns

The idea in one minute#

The 32 threads of a warp issue their memory requests together. If their 32 addresses are neighbours, the GPU fetches them as one or two wide transactions. If the addresses are scattered, it needs up to 32 separate transactions for the same amount of useful data.

Merging neighbouring requests is called coalescing. A coalesced kernel gets the bandwidth on the data sheet. An uncoalesced one can get a tenth of it — with identical arithmetic.

An analogy#

Thirty-two people want books. If they want volumes 1 to 32 of the same encyclopedia, one trolley trip brings the whole shelf. If they each want a book from a different floor, that is thirty-two trips, and each trip drags along a shelf of books nobody asked for.

A picture#

flowchart TB
  subgraph GOOD["Coalesced: thread i reads element i"]
    direction LR
    W1["Warp<br/>32 threads"] -->|"1 transaction"| M1[("32 neighbouring floats<br/>128 bytes")]
  end
  subgraph BAD["Scattered: thread i reads element i x 1000"]
    direction LR
    W2["Warp<br/>32 threads"] -->|"32 transactions"| M2[("32 separate cache lines<br/>most bytes fetched are unused")]
  end
  class W1,W2 compute
  class M1 memory
  class M2 warn

How it really works#

Transactions#

Global memory is delivered in fixed-size chunks (think 32–128 bytes, like cache lines). When a warp executes a load, the hardware works out which chunks cover the 32 requested addresses and fetches each needed chunk once.

• 32 threads reading 32 consecutive 4-byte floats → 128 bytes → 1 transaction, every byte useful.
• 32 threads reading addresses 4,000 bytes apart → 32 transactions, and only 4 useful bytes out of each chunk.

Effective bandwidth = data-sheet bandwidth × (useful bytes ÷ fetched bytes).

The pattern that breaks it: array of structures#

Go programmers naturally write:

type Particle struct{ X, Y, Z, Mass float32 }   // 16 bytes
particles []Particle                            // "array of structures" (AoS)

A kernel that only needs X reads bytes 0–3 of every 16. Three quarters of the traffic is wasted.

The GPU-friendly layout is a structure of arrays (SoA):

type Particles struct{ X, Y, Z, Mass []float32 }

Now thread i reads X[i], neighbours read neighbours, and every fetched byte is used.

Row-major, column-major and strides#

A matrix stored row by row is contiguous along rows. Walking it down a column jumps a full row width each step: scattered. If a kernel must traverse columns, either transpose the data once or assign threads so that adjacent threads still touch adjacent memory.

The rule is about neighbours in the warp, not about the loop inside one thread:

Adjacent threads should access adjacent memory.

Gather and scatter#

Some access is irregular by nature: looking up embedding rows by token ID, or indexing through a table. That is a gather, and it is inherently uncoalesced across rows. The usual defence is to make each gathered item large and contiguous (a whole row at a time), so the cost is one jump per row rather than one per element.

Shared memory as a fix#

When the natural access pattern is awkward, copy a tile into shared memory with a clean, coalesced read, then access it in any order you like — shared memory has no coalescing requirement (II.02).

Code#

The same effect exists on your CPU, driven by cache lines instead of warp transactions. This program sums one field stored AoS and then SoA.

// layout.go — same data, same arithmetic, different memory traffic.
package main

import (
	"fmt"
	"time"
)

type Particle struct {
	X, Y, Z, Mass float32
	Pad           [12]float32 // real structs carry fields the hot loop never reads
}

func main() {
	const n = 20_000_000
	aos := make([]Particle, n) // 64 bytes per element
	soaX := make([]float32, n) // 4 bytes per element
	for i := range aos {
		aos[i].X, soaX[i] = 1, 1
	}

	t0 := time.Now()
	var a float32
	for i := range aos {
		a += aos[i].X
	}
	tAoS := time.Since(t0)

	t0 = time.Now()
	var b float32
	for _, x := range soaX {
		b += x
	}
	tSoA := time.Since(t0)

	fmt.Printf("array of structures: %v  (%.0f MB touched)\n", tAoS, float64(n*64)/1e6)
	fmt.Printf("structure of arrays: %v  (%.0f MB touched)\n", tSoA, float64(n*4)/1e6)
	fmt.Printf("speedup %.1fx, sums %v %v\n", float64(tAoS)/float64(tSoA), a, b)
}

(The sums print 1.6777216e+07, not twenty million: a float32 cannot count past 2^24 in steps of one. That is II.04’s precision lesson appearing uninvited.)

Both loops do twenty million additions. One of them drags sixteen times more bytes through memory to do it. On a GPU the gap is typically larger.

Remember this#

• A warp’s 32 memory requests are merged when their addresses are adjacent (coalescing).
• Scattered access can cut effective bandwidth by 10x or more.
• Prefer structure-of-arrays. Make adjacent threads touch adjacent memory.
• When access must be irregular, gather large contiguous pieces, or stage through shared memory.

Try it#

1. Run layout.go. Change Pad to 0 and to 60 elements. How does the gap move?
2. Write a function that sums a 4096×4096 matrix (stored row-major in one slice) by rows, then by columns. Measure both. Explain the difference in terms of this lesson.
3. An embedding table has 100,000 rows of 4,096 FP16 values. A lookup gathers 512 rows. Is the traffic within each row coalesced? Across rows?

Check yourself#

1. What is coalescing?
2. Why is structure-of-arrays better than array-of-structures on a GPU?
3. State the rule about adjacent threads.