Compute-bound and memory-bound jobs

A job is memory-bound when moving its data takes longer than doing its sums, and compute-bound when the sums take longer. Which one it is decides whether a faster chip helps at all.

A GPU can do trillions of sums a second but can only fetch so many bytes a second. Many everyday jobs spend their time waiting for the bytes.

A chip can do so many sums a second, its compute rate. Its memory can move so many bytes a second, its bandwidth.

A job needs both. The time to move its bytes is bytes divided by bandwidth. The time to do its sums is sums divided by the rate. Whichever is longer is the bottleneck, and the job takes at least that long.

# A made-up device: 200 gigabytes a second, 4 teraflops (4 million million sums a second).
bandwidth = 200 * 10**9
rate = 4 * 10**12

# Scaling 5 million numbers by 2: read 1 vector, write 1 vector of 4-byte numbers.
n = 5000000
bytes_moved = 2 * n * 4
sums = n
memory_us = bytes_moved / bandwidth * 10**6
compute_us = sums / rate * 10**6
print("microseconds to move the bytes:", round(memory_us, 2))
print("microseconds to do the sums:", round(compute_us, 2))
if memory_us > compute_us:
    print("limited by: memory")
else:
    print("limited by: compute")
# Try sums = n * 2000, then run again.

The number of sums for each byte moved is a job's arithmetic intensity. Doubling a number does one sum for 8 bytes of traffic. Multiplying two 1000 by 1000 matrices does about 167 sums for each byte, because each number is used again and again.

Low intensity means memory-bound. High intensity means compute-bound.

The lab's transfer.py works out both times for two jobs on another made-up device. It prints the bytes moved, the sums done, the two times in microseconds and a last line saying what limits the job.

Read the two last lines. One job is limited by memory and the other by compute, though both run on the same device.

docker exec jupyter python3 steps/transfer.py

Memory is fetched in lines, here of 32 bytes. If 8 threads read 8 neighbouring 4-byte numbers, one line serves them all.

If each thread reads every 8th number, each needs a line of its own and 8 lines are fetched. This is coalescing. The lab's coalesce.py prints the addresses touched and the lines fetched for both patterns.

docker exec jupyter python3 steps/coalesce.py

A GPU has memory of its own, so data from the main memory must be copied across first, and the answer copied back. That transfer goes over a slower link than the GPU's own memory.

A small job can spend longer in transfer than in sums. The usual cure is to move the data once and do a lot of work on it before moving it back.