Execution Policies

  • Modern computers support four different ways:

    • Sequential

      • A single instruction processes one data item

    • Vectorized

      • A single instruction processes several data items
      • Requires suitable data structure and hardware support

    • Parallelized

      • Several instructions each process one data item, at the same time
      • Requires suitable algorithm

    • Parallelized + Vectorized

      • Several instructions each process several data items, at the same time
      • Requires suitable algorithm, data structure and hardware support

C++17 Execution Policies

  • Choice of "execution policies" for an algorithm call

    • Sequenced execution
    • Parallel execution
    • Parallel and vectorized execution
    • Vectorized execution only (not until C++20)

  • Not supported by all compilers

  • "Request" which may be ignored

    • If parallel and / or vectorized execution is not supported
    • If insufficient system resources are available
    • If parallel and / or vectorized version has not been implemented

Execution Policy Objects

  • Global objects in <execution>

    • In the std::execution namespace

  • We can pass a policy as an optional first argument:

// Non policy (sequential)
std::sort(vec.begin(), vec.end());

namespace se = std::execution;
std::sort(se::seq, vec.begin(), vec.end());         // Sequential
std::sort(se::par, vec.begin(), vec.end());         // Parallel
std::sort(se::par_unseq, vec.begin(), vec.end());   // Parallel and vectorized
std::sort(se::unseq, vec.begin(), vec.end());       // Vectorized

Sequenced Execution

  • All operations are performed on a single thread
    • The thread which calls the algorithm
  • Operations will not be interleaved
    • May not necessarily be executed in a specific order
// Sort the elements of vec in reverse order
std::sort(se::seq, vec.begin(), vec.end(),
    [](int a, int b) { return b < a; });

Parallel Execution

  • Operations performed in parallel across a number of threads

    • May include the thread which calls the algorithm

  • Guarantees

    • An operation will run on the same thread for its entire duration
    • Operations performed on the same thread will not be interleaved
    • But may not necessarily be executed in a specific order

  • Cautions

    • Operations performed on different threads may interleave
    • The programmer must prevent data races

Parallel Execution with Data Race

  • A variable is shared between threads without any protection
std::vector<int> vec(20'000);
int count = 0;

// Data race!
std::for_each(se::par, vec.begin(), vec.end(), 
                        [&count](int &x) { x = ++count; } 
);

Unsequenced Execution (C++20)

  • Operations are performed on a single thread

    • The thread which calls the algorithm

  • Guarantees

    • Operations will not be interleaved

  • Cautions

    • Operations may not necessarily be executed in specific order
    • The programmer must avoid any modification of shared state between elements or between threads
    • Memory allocation and deallocation
    • Mutexes, locks and other forms of synchronization

Parallel Unsequenced Execution

  • Operations performed in parallel across a number of threads

    • May include the thread which calls the algorithm

  • Cautions

    • Operations performed on the same thread may be interleaved
    • They may not necessarily be executed in a specific order
    • An operation may be migrated from one thread to another
    • The programmer must avoid data races
    • The programmer must avoid any modification of shared state between elements or between threads