Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 31 ยท Synchronization and Parallel Patterns

Synchronization and Atomics

Understand race conditions in CUDA, when __syncthreads is enough, how atomicAdd and atomicCAS work, what contention costs and what memory fences do.

Thousands of threads run at the same time, and sooner or later two of them want the same piece of memory. If both only read it, nothing goes wrong. If one writes while the other reads or writes, the result depends on timing, and a program whose answer depends on timing is broken even if it sometimes gives the right answer. This is a race condition, and avoiding it is the heart of this chapter.

CUDA gives you two main tools. A barrier such as __syncthreads() makes threads of one block wait for each other, which orders phases of work. An atomic operation such as atomicAdd performs a read-modify-write on one memory location as a single indivisible step, so concurrent updates are never lost. This lesson shows the race, fixes it both ways, builds a histogram, explains what atomics cost, and ends with memory fences.

CUDA code in this lesson is read-only; the site has no GPU. The Python examples are simulations: tiny schedulers where each "thread" is a generator that gives up control between steps. They reproduce lost updates deterministically by choosing the interleaving, something real hardware does for you unpredictably.

The classic race: counting

Imagine every thread adds 1 to a shared counter:

C++
__global__ void countWrong(int* counter) {
    *counter = *counter + 1;     // load, add, store: three separate steps
}
// countWrong<<<1, 64>>>(d_counter);   // you would expect 64, you will get far less

The line looks like one operation but compiles to three: load the value, add one, store the result. If thread A and thread B both load 5, both compute 6, and both store 6, then two increments produced one. The update from one thread was lost.

sequenceDiagram
    participant A as Thread A
    participant M as counter in memory
    participant B as Thread B
    A->>M: load (reads 5)
    B->>M: load (reads 5)
    A->>M: store 6
    B->>M: store 6
    Note over M: two increments, final value 6

Both threads read the old value before either wrote, so one increment disappears.

The simulator below makes each thread do exactly that: load, yield (so others may run), store. With several different schedules you can see how bad it gets.

Python Lost updates and the atomic fix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With the round-robin schedule every thread loads before anybody stores, so 64 increments yield a final count of 1. With a random order you get something in between. With one thread at a time the answer is right, which is exactly why such bugs survive testing: the program is correct for some schedules and wrong for others. The atomic version is right under every schedule because its read-modify-write cannot be split.

Atomic functions

CUDA provides atomic functions that operate on 32-bit and 64-bit words in global or shared memory. The common ones:

Function Effect
atomicAdd(addr, v) *addr += v
atomicSub(addr, v) *addr -= v
atomicMin(addr, v), atomicMax(addr, v) keep the smaller or larger value
atomicExch(addr, v) store v and return the old value
atomicCAS(addr, expected, v) compare-and-swap: store v only if *addr == expected
atomicAnd, atomicOr, atomicXor bitwise updates
atomicInc, atomicDec wrapping counters

Each one returns the old value, which is very useful: int slot = atomicAdd(&next, 1); hands every thread a unique ticket, a pattern used for stream compaction and for appending results to a shared output buffer. Floating-point atomicAdd exists too (for double it needs a GPU of compute capability 6.0 or newer). Remember that floating-point addition is not associative, so a sum built with atomics can differ slightly from run to run because the order of additions changes.

So the fixed counter is:

C++
__global__ void countRight(int* counter) {
    atomicAdd(counter, 1);       // indivisible read-modify-write
}

Building your own atomic with atomicCAS

If CUDA has no atomic for your operation, atomicCAS lets you build one. The idea is a retry loop: read the current value, compute the new value, and ask the hardware to install it only if nobody changed the cell in between. If someone did, try again with the fresh value.

C++
__device__ int atomicMulBy3(int* addr) {
    int old = *addr, assumed;
    do {
        assumed = old;
        old = atomicCAS(addr, assumed, assumed * 3);   // succeeds only if unchanged
    } while (old != assumed);
    return old;
}

Here is the same loop simulated. Five "threads" multiply a cell by 3; the plain version loses updates, the CAS version retries until each multiplication lands.

Python A compare-and-swap retry loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The CAS loop reaches 243 but pays for it with 10 failed attempts: in each round only one of the competing threads wins, and the others retry. That wasted work is the cost of contention, and it grows with the number of threads fighting over one address.

Histograms: many threads, few bins

A histogram counts how many input values fall into each bin. It is a natural atomic workload: each thread reads one input and increments the bin it belongs to.

C++
__global__ void histogram(const unsigned char* data, int n, int* bins) {
    int i = blockIdx.x * blockDim.x + threadIdx.x;
    if (i < n) {
        atomicAdd(&bins[data[i] % 8], 1);   // 8 bins
    }
}

The model below runs a histogram of 400 values into 8 bins two ways: a "racy" version where each thread's store of loaded value + 1 may happen after others have updated the bin, and an atomic version. NumPy's bincount provides the ground truth.

Python Racy histogram versus atomic histogram

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The racy histogram loses almost a third of the counts (276 of 400 here). The atomic one is exact. The last two lines point at the cost: atomics on one address are executed one after another, so the time is governed by the longest queue. With uniform data the busiest bin gets 55 updates; when 70 percent of the values fall into one bin it gets 287, and that bin serializes most of the work.

What atomics cost

  • Atomics on global memory are resolved in the L2 cache. Modern GPUs make them fast when different threads hit different addresses, but updates to one address are serialized.
  • Atomics on shared memory are resolved on the SM and are much cheaper, which leads to the standard cure for histograms: give each block its own private histogram in shared memory, update it with shared-memory atomics, and merge the block histograms into the global result with one atomicAdd per bin at the end. Scan, Histogram and Other Patterns develops this.
  • Atomics do not order other memory operations. They make one location's update safe; they do not make the rest of your data consistent.
  • Because the order of competing updates is unspecified, anything that depends on that order (floating-point sums, "first writer wins" logic) is non-deterministic.

The best atomic is the one you avoid. Reduce within a warp or block first (see Parallel Reduction), and let only one thread per block touch the global counter.

Barriers and fences

__syncthreads() (from Shared Memory and Tiling) synchronizes threads of one block only. There is no barrier across blocks inside a normal kernel launch: blocks may run in any order, and some may not even start before others finish. To wait for all blocks, end the kernel and launch another, or use cooperative launches (see Warp Primitives and Cooperative Groups).

A memory fence is different from a barrier. It does not make threads wait for each other; it orders your own memory operations as seen by others:

  • __threadfence_block() makes your earlier writes visible to threads of your block before your later writes.
  • __threadfence() does so for all threads of the device.

The standard use is "publish then flag": a thread writes its result, executes __threadfence(), then sets a flag with an atomic. Any thread that sees the flag set is guaranteed to see the result. A classic application is the "last block done" pattern, where the final block to finish combines the partial results of all the others. Pair fences with atomics, and declare shared flag variables volatile (or use atomic loads) so the compiler does not cache them in registers.

C++
__device__ unsigned int blocksDone = 0;

__global__ void sumAll(const float* in, float* partial, float* result, int n) {
    // ... each block writes its partial sum to partial[blockIdx.x] ...
    __threadfence();                                // publish the partial sum first
    __shared__ bool amLast;
    if (threadIdx.x == 0) {
        unsigned int ticket = atomicAdd(&blocksDone, 1);
        amLast = (ticket == gridDim.x - 1);
    }
    __syncthreads();
    if (amLast) {
        // this block now reads every partial[...] and writes *result
    }
}

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does *counter = *counter + 1; lose updates when many threads run it?

    Two threads can load the same value, both add one and both store the same result, so one increment is lost.
  2. 2. What does atomicAdd return?

    All CUDA atomics return the previous value. atomicAdd(&next, 1) is a handy way to give each thread a unique ticket.
  3. 3. Does __syncthreads() synchronize all blocks of a kernel?

    It is a block-level barrier. Blocks are scheduled independently, so waiting across blocks requires ending the kernel or using cooperative groups.
  4. 4. A histogram has 70 percent of its inputs in one bin. Why can atomicAdd on global memory be slow here?

    Atomic updates to one address execute one at a time, so the hot bin becomes a queue. Private shared-memory histograms spread that cost out.
  5. 5. What does __threadfence() do?

    A fence orders your own memory operations; it does not block other threads. It is combined with atomics or flags to publish data safely.

Summary

  • A race condition happens when threads access the same location without ordering and at least one writes; results then depend on timing.
  • __syncthreads() orders phases inside one block; it does not synchronize blocks.
  • Atomics (atomicAdd, atomicMin, atomicCAS and friends) make a read-modify-write on one location indivisible and return the old value.
  • atomicCAS retry loops build custom atomic operations; contention shows up as failed attempts.
  • Updates to one address serialize, so skewed data hurts; use shared-memory private copies and reduce before touching global atomics.
  • Floating-point atomic sums are order-dependent, and fences such as __threadfence() order your own writes for other threads.

Next, the most important atomic-free pattern: Parallel Reduction.