Parallel Reductions & Race Conditions

Reductions Are Shared-State Updates (Theory)

A reduction computes an aggregate (sum/min/max/product) over many elements.

In parallel, the tempting approach is:

• each worker computes partial work
• each worker adds into one shared accumulator

That shared accumulator becomes a race condition hotspot.

Example of a race (conceptually)

Two threads do:

1. read accumulator value
2. add their partial
3. write accumulator back

If interleaving happens, one update can overwrite the other.

Code Example 1 — Race Condition in C++ (No Sync)

#include <thread>
#include <vector>
#include <iostream>

int main() {
  const int N = 1'000'000;
  const int T = 8;

  std::vector<int> a(N, 1);
  long long sum = 0; // shared, unprotected (race)

  auto worker = [&](int tid) {
    long long local = 0;
    int start = tid * (N / T);
    int end   = (tid + 1) * (N / T);
    for (int i = start; i < end; i++) local += a[i];

    // RACE: multiple threads update sum concurrently
    sum += local;
  };

  std::vector<std::thread> threads;
  for (int tid = 0; tid < T; tid++) threads.emplace_back(worker, tid);
  for (auto& th : threads) th.join();

  long long expected = 1LL * N;
  std::cout << "expected=" << expected << " got=" << sum << "\n";
}

Code Example 2 — Correct Reduction Using a Mutex

#include <thread>
#include <vector>
#include <iostream>
#include <mutex>

int main() {
  const int N = 1'000'000;
  const int T = 8;

  std::vector<int> a(N, 1);
  long long sum = 0;
  std::mutex m;

  auto worker = [&](int tid) {
    long long local = 0;
    int start = tid * (N / T);
    int end   = (tid + 1) * (N / T);
    for (int i = start; i < end; i++) local += a[i];

    // Critical section: only one thread updates sum at a time
    std::lock_guard<std::mutex> lock(m);
    sum += local;
  };

  std::vector<std::thread> threads;
  for (int tid = 0; tid < T; tid++) threads.emplace_back(worker, tid);
  for (auto& th : threads) th.join();

  std::cout << "sum=" << sum << "\n";
}

Common Gotchas

• Too much contention: using one global lock for every element kills performance.
• Using local variables then forgetting to sync: local is safe; shared write must be synchronized.
• Non-associativity surprises: floating-point addition isn’t strictly associative; result order can change slightly.

Quick Checklist

• Compute partials locally first
• Combine partials with a safe strategy:
  • mutex/lock
  • atomic updates
  • reduction tree / two-stage reduce
• Validate with deterministic tests (and allow small FP tolerance)