In our previous post we followed one LDG.E down through all the hardware units on an RTX 4090 — through its L1, translation, through the crossbar to its L2 slice, and thence to DRAM. The request retrieved its result, and then came back up through its waystations, returning its result to its warp, which then continued to execute its part in the kernel.

The part it was playing was in a kernel that performed a vector add. The same kernel, once it has loaded elements of both vectors, adds them together, and then stores the result.

/*00c0*/  IMAD.WIDE R6, R6, R7, c[0x0][0x170] ;   // &c[i]
/*00d0*/  FADD R9, R4, R3 ;                       // a[i] + b[i]
/*00e0*/  STG.E [R6.64], R9 ;                     // c[i] = ...
/*00f0*/  EXIT ;

STG.E is the instruction that’s responsible for writing the calculated sum back to global memory. In this post we’re going to follow STG.E through the same waystations, figuring out what happens at each step. As before, this information is not all publicly available; where it isn’t, we’ll run new experiments.

Setting the scene: the LDG.E has returned to the warp, the FADD has added together the contents of R4 and R3 into R9, and now, the contents of that register must be stored. The warp has become eligible within its subpartition, and its lanes start to execute STG.E.

STG.E [R6.64], R9 is a global store of the 32 bits in register R9 to the 64-bit address in R6 and R7. Where in LDG.E, we read two rows of the register file, in STG.E, we must read three: the two making up the address to which we’re going to store the data, and the data itself.

The instruction then issues to the load/store unit. The LSU sends on the opcode (‘store to these addresses’), the 32-bit mask of active lanes, and the 32 computed addresses.

The next stop is the coalescer. Its job is to take 32 four-byte accesses and turn them into the smallest achievable number of 32-byte sectors. Our kernel writes 128 contiguous bytes, so that’s four sectors, or one line².

Loads always pull in all 32 bytes per sector, and then in the LSU the results are filtered to write to the registers what the SASS actually asked for. For stores, each sector request issues with a byte mask, indicating which bytes of the sector this instruction is writing.

Four sectors, four masks, and 128 bytes of data go on to the L1.

The four sectors then reach the L1 cache. Last time we showed that the L1 cache is per-SM 4-way set associative, virtually indexed, and virtually tagged. Regardless of whether or not the line is present, the sectors, their masks and the data go straight on towards the L2: the L1 is write-through³.

If our store needs space in its set, old slots make way in strict LRU order.

Below the L1, the store’s virtual address is translatedSee the translation section of the reads post., and the four sectors cross the crossbar to the L2 slice that owns the line.

The request is sent across the crossbar to one of the 36 L2 slices, the slice picked by the same function of the physical address that we reverse-engineered last time.

It carries the line’s address, up to four sectors of data, and those sectors’ masks. Stores issue one request per line⁴.

Inside a slice, each cache is 16-way set-associative, with 1024 sets, hashed by physical address. If a line is already resident when we look it up, the bytes selected by each sector’s mask are written into the slot and the sectors are marked dirty. If the line is not resident, the slice needs to find a slot for it — doing so might mean evicting bytes from other lines out to DRAM. Once it’s found its place, it writes its bytes into the slot, and the mask records which bytes of the sector are valid. Once the bytes are in the slot the slice sends an acknowledgement back across the crossbar to the SM.

After the acknowledgement the four sectors sit in their slot, dirty under their masks.

The acknowledgement then comes back across the crossbar to the SM that sent the store. The warp that issued the store has long since moved on: in fact, here, the whole kernel has finished. So the acknowledgement reaches the LSU and is consumed there.

In fact, for this kernel, the data never actually makes it to DRAM! The kernel in our original post reads back these written results with a cudaMemcpyDeviceToHost, taking them straight from L2 across the PCIe bus to host DRAM. That in itself is an interesting thread to follow, for another day.

The hardware now holds our data dirty in L2. We’ve completed our STG.E instruction: for that to mean anything, any pointer to our data from any subsequent kernel ought to find our data there. But it’s dirty in a cache: it hasn’t hit DRAM yet. How does it get there? When does it make the trip?

The L2 serves as the serialization point for all the chip’s traffic, but at some point it runs out of space, and something needs to be evicted.

Our data is sitting in the L2. Another kernel will come along after ours. That kernel might read data, or write it, it might want our lines, or it might want other lines. As that kernel runs, our data will have to make its way to DRAM.

How data gets to DRAM

Each line in our data is stored with its 2-bit ‘re-reference prediction value’ (RRPV)⁵, set to either $0$, $1$, or $2$This is schematic, there's no sense that the numbers 0, 1, or 2 actually appear in the hardware, but timing experiments pin it at three levels.: lower numbers mean that the cache thinks a line will be used again soon. Our cache lines sit at $1$, having just been inserted.

Each line has a ‘dirty mask’, indicating whether the L2 is the only place in which this version of the line exists — our lines are all completely dirty. Each line also has counters for its last use, and last store.

A new load or store comes in for a line. What happens?

1. On a resident hit: When the load comes in looking for one of our lines, it gets it. The line’s RRPV is set to $0$. If a store comes in and hits the line, its sectors hit the line and its ‘dirty mask’ is updated.
2. On a miss: The L2 needs to bring the missed value into the cache. To do so, it needs to find a victim.

The replacement policy works like this:

First, we scan all the 16 ways in the set for one that’s at RRPV=2: i.e., that the cache thinks won’t be used again. If we can’t find any, we increment all the RRPV values, and then scan again. Of all the RRPV=2 values, we pick the least recently used one.

Then we decide what to do with our victim. If our victim is dirty — that is, the L2 is the only place that it exists, and evicting it would force us to talk to DRAM straight away, we don’t kick it out of the cache yet, but we do start cleaning it up, the only way we can, by handing its dirty sectors off to the memory controller to write back to DRAM. The line goes into the set’s FIFO write-back bufferThe FIFO write-back buffer decides which 'writing-back' lines are readable. Every two fills, the oldest line in the buffer is popped, freeing its way. This is fine, since the write-back of that line has already started., and stays readable. Then we go scanning the ways again for clean victims. Once we find one, we kick it out and steal its way.

The new line just slots into that way, with its RRPV set to 1.

Keeping sets clean

The policy we’ve described governs how we do evictions to make room for new data. But if we just keep hitting dirty resident lines, our policy has no way to write them back.

On a store to a set that holds $\geq 8$

To see why you need an extra rule like this, imagine what would happen without it. Take a set full of dirty lines. Imagine a miss comes in, needing a fill from DRAM. By the policy above, we pick the oldest, dirty, so we send it to the write-back buffer. Then we pick the next oldest, dirty, send it to the write-back buffer. Then the next oldest, then the next oldest, all dirty, all start writing back, all sit in the write-back buffer. All 16 lines end up writing back, all at once, in a single burst of DRAM traffic. Until the buffer drains, this set has almost no capacity for the next few misses — and, worse, the burst of writes queues at the memory controller, so any other reads or writes on that controller queue behind.

The 8-dirty rule works as a janitor, cleaning lines proactively so that we always find a clean victim, and so that the flow of traffic to DRAM is smoother.

One L2 set, run by the policy above, under a kernel that writes sixteen lines of output followed by one that streams through thirty-two lines of input. Click a line to read it. The dots under a line are its RRPV.

Writing back

These writes can be asynchronous with respect to incoming stores to the L2 right up until the point a memory controller’sReminder from the last post: each memory controller is shared between 3 slices. write backlog is full, at which point new stores must stall⁶.

When a write is performed, the sectors go to the memory controller and from there to the DRAM chip as writes: the controller activates the row, as it did for our load, and then issues a write per sector, 32 bytes down the same 16 pins in the other direction, with the byte mask, so that only the written bytes are stored⁷The 4090's GDDR6X applies the byte mask directly. HBM with ECC can't do it directly, since it operates in codewords, so it does partial writes by reading, merging, then writing back..

A LDG.E took 255 ns, the warp waiting all the way. STG.E takes only 6 cycles, just enough to set the store in motion.

Stores have a long afterlife, as they make their way through the units, the warp happily oblivious unless it wants to read them back. They pass through L1, then to L2, at which point they signal back to the SM that issued them. In L2, they sit dirty, aging as up-and-coming stores and loads push them towards the exit. Eventually a miss picks them as its victim, and they’re ushered out through the memory controller into DRAM, landing long after the warp that wrote them has gone.

The die, under a kernel that writes 128 MB of output followed by one that streams through 96 MB of input. The L2 is one pixel per set, coloured by how many of its sixteen lines are dirty.

When the write becomes visible

Our STG.E was fire-and-forget — the warp issued it, and then the program unceremoniously exited. This is in general useful to be able to do: a kernel that issues stores can then run ahead and do other work while the store is completing. But it means we need to be careful: since data is not written durably as soon as an instruction completes, we need some way of knowing when the write has finished. The answer is fences.

A fence is an instruction that holds the warp until every store it has issued is visible. There are three, one per scope: membar.cta waits for the stores to be visible to the warp’s own block, membar.gl to every SM on the chip, and membar.sys to the host and other devices as wellThese are PTX instructions, they expand to more than one SASS instruction..

To our block: rendezvous at L1

membar.cta on a warp will wait for any stores in the same CTA to become visible. The coherence point for all memory traffic in and out of the SM is the shared L1. So a membar.cta only needs to wait for the store to be visible in L1, which it knows, since once it’s successfully handed off to the L1, by definition, it’s visible. membar.cta adds about 1 ns or 3 cycles to a STG.E⁸.

To all the SMs: rendezvous at L2

membar.gl needs to wait for the store to be visible to every SM on the chip. In order for this to be the case we don’t need to broadcast anything to those SMs because, just as in the SM itself, we have a pinch point through which all traffic flows. So once we’ve landed our write in L2, and received the ack, we know that it’s globally visible. membar.gl completes in about 140 ns, the same time as L2.

It’s only globally visible in principle — in order to come and get it, the reader needs to get it from the L2 (its own L1 can hold stale lines). It has to do that deliberately: an instruction like LDG.E.STRONG.GPU will bypass its L1. An instruction like ld.acquire.gpu — designed for this kind of visibility negotiation, compiles to SASS that contains CCTL.IVALL, which invalidates that whole SM’s L1.

The fences themselves are two-way: they are also responsible for making sure that that thread’s later loads see the data that that thread has written. And so they also contain instructions to invalidate their L1cuobjdump -sass on the probes: membar.gl compiles to MEMBAR.SC.GPU ; ERRBAR ; CCTL.IVALL, membar.sys to MEMBAR.SC.SYS ; ERRBAR ; CCTL.IVALL, fence.acq_rel.gpu to MEMBAR.ALL.GPU ; ERRBAR ; CCTL.IVALL, and an ld.acquire.gpu is an LDG.E.STRONG.GPU followed by the same CCTL.IVALL. membar.cta is a bare MEMBAR.SC.CTA..

To the whole world: membar.sys

membar.sys orders the store with respect to the rest of the world: peers over NVLink, the host over either PCIe or NVLink-C2C, etc. For the narrower scopes, this could be achieved by just looking at the coherence points: here, the ordering question is more difficult to answer, so it takes longer. A membar.sys takes about 1 µs.

What did reading our store wait for?

The PTX for our kernel doesn’t contain a fence: it just wrote the data and then exited. The semantics that it needs are exactly those of membar.sys: the cudaMemcpyDeviceToHost needs to wait for the data to be visible to the whole system.

In fact: the driver scheduled an analogous system-scope membar at the end of the kernel⁹. Once that membar resolves, the data becomes visible to the host, and can be sent back to be printed to the screen.