Skip to content

parallel-algorithms.md

Latest commit

 

History

History
221 lines (166 loc) · 11.8 KB

parallel-algorithms.md

File metadata and controls

221 lines (166 loc) · 11.8 KB
Raw

Parallel Algorithms & Execution Policies

Executive Abstract

Parallel Algorithms are overloaded implementations of standard algorithms in <algorithm> and <numeric> that accept an Execution Policy Tag (std::execution::seq, par, par_unseq, unseq) as their first parameter. Introduced in C++17 and expanded in C++20, parallel algorithms democratize multi-threaded and hardware SIMD vectorized data processing. They allow standard algorithms (std::sort, std::for_each, std::transform) and parallel mathematical reductions (std::reduce, std::transform_reduce) to scale transparently across multi-core CPUs and SIMD vector units with zero vendor lock-in or manual thread management boilerplate.

Motivation & Historical Context

Pre-C++17 Deficiencies: The Single-Threaded STL Bottleneck

In C++98, C++11, and C++14, all Standard Template Library (STL) algorithms executed strictly sequentially on a single CPU thread.

// Pre-C++17 Single-Threaded Execution Bottleneck
std::vector<double> dataset(100'000'000);
std::sort(dataset.begin(), dataset.end()); // Utilizes EXACTLY 1 CPU core!

Deficiencies of Pre-C++17 STL Algorithms:

  1. Hardware Under-Utilization: Sorting or transforming 100 million elements on a 64-core server executed on a single thread, leaving 98% of hardware processing capacity idle.
  2. Third-Party Framework Fragmentation: To achieve multi-core speedups, developers relied on non-standard vendor APIs (Intel TBB tbb::parallel_for, OpenMP #pragma omp parallel, OpenCL, or CUDA), polluting codebases with non-portable directives and build system dependencies.
  3. Sequential Reduction Constraints: std::accumulate enforced strict left-to-right evaluation order ($((a_1 + a_2) + a_3) + \dots$), preventing parallel tree reductions across worker threads.

Solution: C++17 added execution policy tags to over 80 standard algorithms and introduced parallel-friendly numeric reduction primitives (std::reduce), enabling policy-driven parallel execution directly in standard C++.

Technical Mechanics & Execution Policy Taxonomy

1. The Four Standard Execution Policies (<execution>)

                                Execution Policies
                                        │
      ┌──────────────────┬──────────────┴──────────────┬──────────────────┐
      ▼                  ▼                             ▼                  ▼
1. std::execution::seq  2. std::execution::par    3. std::execution::par_unseq 4. std::execution::unseq (C++20)
Sequential Execution    Multi-Threaded Parallel   Multi-Threaded + SIMD Vectorized Single-Threaded SIMD Vectorized
Order strictly preserved Threads execute in parallel Threads + SIMD vector lanes  Vectorized on single thread

Policy Execution Matrix

Execution Policy Multi-Threading SIMD Vectorization Permitted Inside Element Operations
std::execution::seq Single Thread No All standard operations (Mutexes, malloc/new permitted).
std::execution::par Multi-Threaded No Must be thread-safe. Mutexes permitted across threads.
std::execution::par_unseq Multi-Threaded Yes (SIMD Interleaved) STRICT: NO LOCKS / NO DYNAMIC ALLOCATIONS! (Risk of self-deadlock!).
std::execution::unseq (C++20) Single Thread Yes (SIMD Vectorized) STRICT: NO LOCKS / NO DYNAMIC ALLOCATIONS! Vector lane safety required.

2. Strict Concurrency Rules for Vectorized Policies (par_unseq & unseq)

When using par_unseq or unseq, execution within a single thread may be interleaved across SIMD vector lanes:

Critical Vector Safety Invariant: Element operations executed under par_unseq or unseq MUST NOT acquire locks (std::mutex), allocate dynamic memory (malloc/new), or invoke thread-unsafe atomic waiting primitives. If a vector lane interrupts a thread holding a lock to acquire that same lock on another vector lane, the process triggers an immediate Self-Deadlock / Undefined Behavior.

3. Sequential std::accumulate vs. Parallel std::reduce

  • std::accumulate: Requires strict left-to-right sequential ordering: $((a_1 + a_2) + a_3) + a_4$.
  • std::reduce (C++17): Requires the reduction operator to be associative and commutative. Allows the runtime to group operations arbitrarily into parallel tree reductions: $(a_1 + a_2) + (a_3 + a_4)$.

Evolution Across Standards (C++17 to C++26/C++29)

┌──────────────────────────────────────────────────────────────────┐
│ C++17                                                            │
├──────────────────────────────────────────────────────────────────┤
│ • Introduced <execution> header and 80+ parallel algorithms      │
│ • Defined seq, par, and par_unseq execution policies             │
│ • Added std::reduce, std::transform_reduce, std::inclusive_scan  │
└──────────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
┌──────────────────────────────────────────────────────────────────┐
│ C++20                                                            │
├──────────────────────────────────────────────────────────────────┤
│ • Introduced std::execution::unseq (Single-threaded SIMD)        │
│ • Integration with C++20 Ranges concepts                         │
└──────────────────────────────────────────────────────────────────┘
                                 │
                                 ▼
┌──────────────────────────────────────────────────────────────────┐
│ C++23 / C++26                                                    │
├──────────────────────────────────────────────────────────────────┤
│ • SIMD Data-Parallel Types (std::simd in C++26 P1928)            │
│ • Interoperability with C++26 Senders and Receivers (P2300)      │
└──────────────────────────────────────────────────────────────────┘

Comprehensive Code Examples

Example 1: Parallel Sorting & Multi-Threaded In-Place Transformation (std::execution::par)

Demonstrates sorting and modifying large arrays using multi-threaded execution policies.

#include <iostream>
#include <vector>
#include <algorithm>
#include <execution> // C++17 Execution Policies
#include <random>

int main() {
    constexpr std::size_t ELEMENT_COUNT = 10'000'000;
    std::vector<int> data(ELEMENT_COUNT);

    // Populate vector with random data
    std::mt19937 gen(42);
    std::generate(data.begin(), data.end(), gen);

    std::cout << "Sorting 10 Million Elements in Parallel (std::execution::par)...\n";

    // 1. Parallel Multi-Threaded Sort
    std::sort(std::execution::par, data.begin(), data.end());

    // 2. Parallel In-Place Transformation
    std::for_each(std::execution::par, data.begin(), data.end(), [](int& val) {
        val *= 2;
    });

    std::cout << "Parallel processing complete. First sorted element: " << data[0] << "\n";
    return 0;
}

Example 2: Parallel Mathematical Reduction (std::transform_reduce)

Demonstrates performing a parallel MapReduce-style operation (Dot Product) using std::transform_reduce.

#include <iostream>
#include <vector>
#include <numeric>
#include <execution>

int main() {
    std::vector<double> vector_a(5'000'000, 2.0);
    std::vector<double> vector_b(5'000'000, 3.0);

    // Computes Parallel Dot Product: sum of (a[i] * b[i]) across all elements!
    // 1st Lambda: Plus reduction operator (+)
    // 2nd Lambda: Multiplication transform operator (*)
    double dot_product = std::transform_reduce(
        std::execution::par,
        vector_a.begin(), vector_a.end(),
        vector_b.begin(),
        0.0,                      // Initial reduction accumulator
        std::plus<double>{},       // Binary reduction operator
        std::multiplies<double>{}  // Binary transform operator
    );

    std::cout << "Parallel Dot Product Result: " << dot_product
              << " (Expected: 30,000,000.0)\n";

    return 0;
}

Example 3: Modern C++20 Single-Threaded SIMD Vectorization (std::execution::unseq)

Demonstrates vectorizing a single-threaded loop without spawning extra OS threads.

#include <iostream>
#include <vector>
#include <algorithm>
#include <execution>

int main() {
    std::vector<float> signal = {1.0f, 2.0f, 3.0f, 4.0f, 5.0f};

    // C++20 std::execution::unseq: Vectorized SIMD execution on a SINGLE thread!
    // No thread creation/context-switch overhead!
    std::for_each(std::execution::unseq, signal.begin(), signal.end(), [](float& val) {
        val = val * 2.5f + 1.0f; // Executed via CPU SIMD vector registers (AVX/NEON)
    });

    std::cout << "Vectorized Signal[0]: " << signal[0] << " (Expected: 3.5)\n";
    return 0;
}

Engineering Best Practices & Common Pitfalls

  1. Do NOT Use Mutexes inside par_unseq or unseq:

    • Acquiring a lock (std::mutex) inside a vectorized policy causes Deadlock or Undefined Behavior.
    • Rule: Use std::execution::par if mutexes or lock guards are required across thread boundaries.

  2. Verify Dataset Size Thresholds Before Parallelizing:

    • Spawning parallel threads incurs OS context-switching overhead. Calling std::sort(std::execution::par, ...) on small vectors ($N &lt; 10,000$) will run slower than plain sequential std::sort. Reserve std::execution::par for large datasets ($N &gt; 100,000$).

  3. Ensure Operations Are Associative for std::reduce:

    • Floating-point addition is non-associative due to rounding errors ($(a + b) + c \neq a + (b + c)$). std::reduce on floating-point vectors under par may produce minor floating-point differences between runs due to non-deterministic thread reduction trees.

Relationships

Back to C++17 section.