Shared Memory Atomic throughput

Many operations that we think of logically as a single operation are composed of multiple smaller operations. Let's say you have a web server serving requests with many threads and you want to count how many requests you receive. You do this by incrementing a value in memory by 1 for every request: in C(*request_counter)++. We think of "incrementing a value in memory by 1" as being a single logical operation but in fact it is composed of three operations:

1. Load value from memory into registers
2. Increment value in register by one
3. Write value from register to memory

Thread 1       | Thread 2
Read value(0)  | Read value (0)
Increment (1)  | Increment (1)
Write back (1) | Write back (1)

The counter now records you have received one request when you actually received two.

To fix this, we make the single logical operation a single physical operation ("atomic", in the sense of "indivisible"). It now becomes a single instruction that the hardware guarantees will always be consistent.

Compare-And-Swap

while (compare_and_swap(memory_location=lock_ptr, compare=0, replace_with=1) == 1) {} // take lock
// write value to end of array
*lock_ptr = 0; // release lock

int old = *request_counter; // load the value initially
int assumed;
while (assumed != old) {
    assumed = old;
    int incremented = assumed + 1;
    // get the value it was before the compare-and-swap attempt. If it was the value we thought it was, exit out. Otherwise, try to compare-and-swap again with the incremented new value.
    old = compare_and_swap(memory_location=request_counter, compare=old, replace_with=incremented);
}

Because CAS is so flexible, we can implement anything we want as the operation -- atomic cosine, atomic multiplication, atomic XOR, etc.

In general, the more localized and limited communication is, the more efficient it is to implement in hardware. Therefore NVIDIA hardware is optimized to provide several levels of communication of different flexibility so your programs can use the least expensive communication possible.

In CUDA, programs execute in units of what NVIDIA calls a "warp"⁴ which is analogous to a CPU thread. Each warp has 32 "threads", analogous to SIMD lanes. GPUs have many registers, 256KB per SMs, which allows them to implement an aggressive form of hyperthreading where up to 64 warps can be running at the same time. This makes masking the latency of expensive memory accesses easy, because while one warp is waiting for data other threads can be computing. Communication between threads in a warp can be done using warp shuffle functions.

The next highest level of hierarchy is that multiple warps can be grouped into a "CTA" or "block" which are all guaranteed to run on the same SM, which consists of 4 SMSPs plus 128KB of "shared memory" which is like very fast addressible L1 cache. Multiple warps can communicate and work together through shared memory. For example in a matrix multiplication kernel many warps do different computations on the same data, reducing memory bandwidth.

In order for the warps in a block to communicate together they often need atomics: to track the maximum value they've seen, to calculate a sum, to keep a list or queue.