A memory system can deliver 25.6 GB/s. Its latency is 100 ns. A processor core issues 64-byte cache-line reads and is allowed 10 outstanding at a time. It measures 6.4 GB/s and the memory team insists their side is fine. Both are right. The core's limit of 10 outstanding reads caps its throughput at exactly 6.4 GB/s, and one line of arithmetic shows it.

How many requests must be in flight to reach a given throughput, and why?

The obvious answer, and why it breaks

The obvious expectation is that a requester gets whatever bandwidth the target offers. But a requester can only use the bandwidth if it keeps enough requests in the pipe. Each request occupies the pipe for one latency; if too few are in flight, the pipe is mostly empty however wide it is. The relationship between "in flight", throughput and latency is exact, and it has a name.

The idea: Little's law

It holds for averages in any stable system, whatever the arrival pattern and whatever the distribution of latencies. Read it in whichever direction you need:

• To reach a throughput, you need throughput × latency items in flight: that sizes outstanding-request limits, tags (lesson 6.4) and receive buffers.

• With a limit of N in flight, throughput is at most N / latency, however much bandwidth exists.

• Credits are the same law: B credits over a credit round trip give at most B / RTT (lesson 4.5).

Worked numbers: the opening example

Throughput wanted:      25.6 GB/s / 64 B per line   = 400 million lines per second
Latency:                100 ns
Lines in flight needed: 400e6 x 100e-9               = 40 reads outstanding
With a limit of 10:     10 / 100 ns x 64 B           = 6.4 GB/s   (a quarter of the bandwidth)

Build it: a closed-loop model

The model issues a request each cycle whenever fewer than N are outstanding, completes each after a fixed latency of 20 cycles (and, in a second run, a random latency with the same mean), and measures throughput and the average number in flight.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

"""Little's law in a closed loop: a requester with a limit on outstanding requests.

Each cycle the requester issues one request if fewer than N are outstanding. Every
request takes `latency` cycles to complete (fixed, or random with the same mean).
The model measures throughput (completions per cycle) and the average number in
flight, and checks Little's law: in flight = throughput x latency.
"""
import random


def run(N, latency_of, cycles=20000):
    random.seed(1)
    done_at, in_flight_sum, completed, lat_sum = [], 0, 0, 0
    for t in range(cycles):
        done_at = [d for d in done_at if d > t]            # retire what finished
        if len(done_at) < N:
            lat = latency_of()
            done_at.append(t + lat)
            if t >= cycles // 2:
                lat_sum += lat
        if t >= cycles // 2:
            completed += sum(1 for d in done_at if d == t + 1)
            in_flight_sum += len(done_at)
    half = cycles - cycles // 2
    thr, inflight = completed / half, in_flight_sum / half
    return thr, inflight


L = 20
print(f"fixed latency {L} cycles: N, throughput, in flight, throughput x latency")
for N in (1, 2, 4, 8, 16, 20, 32):
    thr, inflight = run(N, lambda: L)
    print(f"  N={N:<3} {thr:6.3f} {inflight:6.2f} {thr * L:6.2f}")
    assert abs(thr - min(1, N / L)) < 0.01 and abs(inflight - thr * L) < 0.2

thr, inflight = run(8, lambda: random.randint(10, 30))
print(f"random latency 10-30 (mean 20), N=8: throughput {thr:.3f}, in flight {inflight:.2f}, throughput x 20 = {thr * 20:.2f}")
assert abs(inflight - thr * 20) < 0.3

need = 25.6e9 / 64 * 100e-9
print(f"25.6 GB/s of 64-byte lines at 100 ns needs {need:.0f} reads outstanding")
print("PASS: average in flight = throughput x latency in every case, so throughput = min(1, N / latency)")

It prints:

fixed latency 20 cycles: N, throughput, in flight, throughput x latency
  N=1    0.050   1.00   1.00
  N=2    0.100   2.00   2.00
  N=4    0.200   4.00   4.00
  N=8    0.400   8.00   8.00
  N=16   0.800  16.00  16.00
  N=20   1.000  20.00  20.00
  N=32   1.000  20.00  20.00
random latency 10-30 (mean 20), N=8: throughput 0.395, in flight 7.90, throughput x 20 = 7.91
25.6 GB/s of 64-byte lines at 100 ns needs 40 reads outstanding
PASS: average in flight = throughput x latency in every case, so throughput = min(1, N / latency)

Every row satisfies in flight = throughput × latency, so throughput is N/20 until N = 20 fills the pipe. The random-latency run shows the law does not care about the distribution: with a mean of 20 it still holds. The last line re-derives the opening example.

Try it

Where the law sizes hardware

What breaks

The opening system (illustrative): the core's miss-handling logic allowed 10 outstanding reads, sized years earlier for a memory with 25 ns latency, when 10 was plenty (400 million lines/s × 25 ns = 10). The new memory system was faster in bandwidth but slower in latency, and the same core now got a quarter of the bandwidth. Every resource sized by Little's law must be re-sized when latency changes.

Key takeaways

• Little's law: items in flight = throughput × latency, for averages in any stable system.

• A limit of N in flight caps throughput at N / latency, whatever the bandwidth.

• Size tags, outstanding limits, credits and buffers with it, and re-size them when latency changes.

Related topics

• Part 6 overview: Concurrency and Performance

• Lesson 4.5: The Credit Loop and Buffer Sizing