GPU Glossary
/
Performance·1 min read

Little's Law

A queueing law stating that the concurrency needed to hide latency equals latency multiplied by throughput.

Little's Law gives the amount of concurrency needed to fully hide latency with throughput:

concurrency (ops) = latency (s) × throughput (ops/s)

The classic quantitative systems textbook by Lazowska and others calls it "the most important of the fundamental laws" of analysis.

Applying it to GPUs#

On GPUs, Little's Law tells you how many instructions must be "in flight" to hide latency by having warp schedulers switch between warps. This is fine-grained thread-level parallelism, like simultaneous multi-threading in CPUs.

For example, with a peak throughput of 1 instruction per cycle and a memory access latency of 400 cycles, a program needs 400 concurrent memory operations across all its active warps. If throughput rises to 10 instructions per cycle, it needs 4000 concurrent memory operations to benefit from the increase. See latency hiding for more.

Memory vs. arithmetic latency#

Section 4.3 of Vasily Volkov's PhD thesis on latency hiding makes a non-obvious observation: hiding pure memory access latency takes not many more warps than hiding pure arithmetic latency (30 vs. 24 in his experiment).

You might expect memory's longer latency to demand much more concurrency. But concurrency depends on throughput as well as latency, and memory bandwidth is much lower than arithmetic bandwidth.

Key idea Because concurrency = latency × throughput, memory's higher latency is offset by its lower throughput, so the concurrency required for memory and arithmetic ends up roughly the same — a useful balance for a latency-hiding system that mixes both kinds of operation.