Parallel machines

Take a thread, one stream of instructions, that requests 16 bytes from memory and waits a latency $L$ before requesting again. Its rate is $16/L$ bytes a second, so at $L=100$ billionths of a second it transfers 160 million bytes a second, since 16 bytes every $10^{-7}$ seconds is $16/10^{-7}$ bytes a second. The accelerator around it, the graphics processor that shares the memory, can deliver 900 billion bytes a second. The difference is a factor of 5,625, and the architecture of a graphics processor, a processor built for many independent threads, is an answer to that discrepancy. The 100 billionths is an assumption rather than a figure from the guide, which gives only a single thread that accesses 16 bytes and performs 16,000 operations, and the request count below scales linearly with the latency [S:99:19].

What does a GPU, a graphics processor, do differently? It does not make one instruction execute faster than a processor core, one of the units that executes instructions, does. It maintains thousands of instructions in flight, issued but not yet finished, instead, so that the delay of one thread is concealed by another thread that is ready [S:99:17]. The difference is the number of requests each machine can keep open, which is the subject of the count below. !One request at a time cannot fill the link. A thread that asks for 16 bytes, waits 100 nanoseconds and asks again sustains 160 million bytes a second, while the link delivers 900 billion, a factor of 5,625. The lower lane is that thread, with the wire idle between requests. The upper lane keeps 5,625 requests outstanding, which is 90,000 bytes in flight, and the wait is covered by requests already sent. Status: schematic.

The 16 bytes in the opening request belong to one thread. Thirty-two threads form a warp, and an instruction is issued to the warp, so one load asks for thirty-two requests of 16 bytes at once [S:245:2][S:100:22]. When the threads in a warp take different branches the warp issues both paths in turn, and that is divergence. Occupancy is the fraction of the warps a processor could hold that it actually holds, where the warps resident, present at the same time, are the reserve of computation available while one warp waits. Latency is how long one request takes, and throughput is how many finish per second.

The relationship that connects the last two quantities is an accounting identity about a queue. In steady state, a window in which the rate in and the rate out have settled, the average number of requests in the system equals the arrival rate times the average time a request spends there. Only when every request has the same fixed latency is that number exactly the requests issued during the last delay; with variable latency the identity holds for the averages, as the formal statement in the Deepen layer says. Consequently the bytes outstanding equal the rate at which bytes depart multiplied by the time each byte waits.

$$\text{bytes in flight}=\text{rate}\times \text{wait}$$

That line says: to sustain a rate across a delay, maintain enough requests open to cover it. [F01]

Worked example. Take the accelerator at 900 billion bytes a second and a delay of 100 billionths of a second, and multiply the two quantities to obtain 90,000 bytes outstanding at every instant. Each request requires 16 bytes, so the processor needs 5,625 requests in flight, and that is the number the hardware must supply. Expressed the other way round, one request at a time transfers 160 million bytes a second, and the ratio of 900 billion to 160 million is again 5,625.

The arithmetic explains why thread counts on a graphics processor appear absurd next to core counts, since a V100 contains 640 tensor cores, units that multiply small matrices. Each can perform a small matrix multiplication, a product of two small arrays of numbers, while the others do the same [S:99:126]. The cores are not the explanation for the threads; the memory delay is, and a thread is a mechanism for having one request outstanding while the majority of the others wait. A thread that issues its load and stalls, waiting for the answer, is not idle in the accountant's sense, because the stall is what permits another warp to execute.

Additional threads do not assist if they all diverge or all wait for the same cache line, the block of bytes memory delivers. A warp that splits pays for both paths, and occupancy counts warps that could execute rather than work that is ready [S:99:17]. The number of threads is therefore a poor first diagnostic, and the number of requests actually in flight is the one that predicts the throughput. A kernel can have a high intensity and still run slowly when its parallelism, the number of independent requests, is spread over the wrong delays.

The formal statement. Consider a system in steady state that admits requests at an average rate, holds each for an average time, and loses none. The average number of requests inside the system equals the rate times the time. The identity is Little's law, and it needs only those three hypotheses: conservation, steady state, and a long enough window for the averages to settle [S:104:12]. Apply it to bytes and you get the rule the section uses, with the achieved bandwidth in place of the rate and the memory latency in place of the time. The identity is about averages: the number in the system equals the requests issued during the last delay only when every request has the same fixed latency.

$$\text{bytes in flight}=\text{achieved rate}\times \text{latency}$$

That line says: to carry a rate across a wait, keep that many bytes requested at every instant.

The derivation. Watch the system for a long window. The number of arrivals is the rate times the length of the window. Each arrival stays for the average time, so the total time spent inside the system by all requests is the number of arrivals times that average. Divide by the length of the window, and the average number present is the rate times the time. The argument uses no distribution and no assumption about the queue discipline, which is why it applies to a memory system as readily as to a bank.

The edge case. The identity uses the achieved rate, not the peak. A kernel that issues fewer requests than the machine can serve runs below peak, and the outstanding bytes that the peak would demand are never present. That is why a kernel with high intensity can still run slowly: the arithmetic is there and the machine is idle [S:99:19]. Read the identity as the number of requests needed to reach a rate, not as a description of what the hardware is doing.

What the core hid. The core said a thread holds one request open. A thread can have several loads outstanding, so the number of threads needed is the requests in flight divided by the requests each thread can keep open. The core's count of 5,625 is a count of requests. It equals a count of threads only when every thread carries exactly one.

Where the analogy breaks. "Threads are the currency" suggests that more threads always buy more throughput. A warp that diverges issues both branches one after the other, so half its threads wait while the other half runs, and occupancy counts warps that could execute rather than work that is ready [S:100:22]. Past the point where the memory system is saturated, extra threads buy queueing rather than bandwidth.

Original sources. The identity is Little's law, listed in the roofline paper's bibliography as a proof of the queueing formula that sets the number in a system equal to arrival rate times time in system [S:104:12]. Its GPU reading is in the NVIDIA performance guide, which states that a GPU hides dependent instruction latency by switching to other threads [S:99:17]. The warp, the unit an instruction is issued to, is defined in FlashAttention-2 [S:245:2].

An open question. Which quantity predicts the speed of a kernel is unsettled. Thread count, occupancy and requests in flight are three different numbers, and the guide says the threads needed exceed the cores by a wide margin without giving a rule [S:99:17]. Evidence that would settle it: stall-reason counters and achieved bandwidth measured together across a sweep of occupancy, on kernels whose only difference is the number of outstanding loads per thread. A predictor has to work when the kernel is memory-bound and when it is not, so a single fit on one kernel proves nothing.

A frontier result. FlashAttention-2 is an exercise in this accounting. The first version reached a fraction of peak because work was partitioned poorly across blocks and warps. The second reorganised the partition to raise occupancy and to cut shared-memory traffic, and it reached a much larger fraction of peak with the same output [S:245:1]. Both versions compute the same attention. The difference is which requests are open at each moment.

What to read next. Read section 3 of the NVIDIA guide for the latency-hiding argument [S:99:17]. Read section 2.1 of FlashAttention-2 for the hardware model and the warp definition [S:245:2]. Then compute the requests in flight for a kernel you know and compare the number with its thread count.