C++

Parallele Algorithmen & Ausführungsrichtlinien

Nutze die parallele STL aus C++17, um Sortieren, Transformieren und Reduzieren über Ausführungsrichtlinien zu parallelisieren. Verstehe, wann Parallelität etwas bringt, was das Amdahlsche Gesetz besagt und wie ein praxistauglicher Thread-Pool aufgebaut ist.

Parallele STL — Parallelität leicht gemacht

C++17 hat den meisten Funktionen aus Ausführungsrichtlinien hinzugefügt. Indem du eine Richtlinie als erstes Argument übergibst, teilst du der Implementierung mit, den Algorithmus zu parallelisieren — möglicherweise über mehrere Threads, über SIMD oder beides — ohne dass du sonst irgendetwas am Code änderst.

Das ist der einfachste Weg, C++-Code zu parallelisieren: Nimm deinen bestehenden Aufruf von std::sort, std::transform oder std::for_each, stelle std::execution::par voran und überlasse den Rest der Implementierung. Natürlich musst du sicherstellen, dass deine Operationen sicher für nebenläufige Ausführung sind (keine Data Races in den Prädikaten, kein gemeinsamer veränderlicher Zustand).

Ausführungsrichtlinien erklärt

In sind drei standardisierte Ausführungsrichtlinien definiert. Jede gibt andere Garantien in Bezug auf Parallelisierung und Vektorisierung.

execution_policies.cpp
#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>
#include <chrono>

int main() {
    std::vector<int> data(10'000'000);
    std::iota(data.begin(), data.end(), 0);

    // Sequential — same as no policy
    auto t1 = std::chrono::high_resolution_clock::now();
    std::sort(std::execution::seq, data.begin(), data.end(),
              std::greater<>{});
    auto t2 = std::chrono::high_resolution_clock::now();

    // Parallel — may use multiple threads
    std::sort(std::execution::par, data.begin(), data.end());
    auto t3 = std::chrono::high_resolution_clock::now();

    // Parallel + vectorized — threads AND SIMD
    std::sort(std::execution::par_unseq, data.begin(), data.end(),
              std::greater<>{});
    auto t4 = std::chrono::high_resolution_clock::now();

    auto ms = [](auto a, auto b) {
        return std::chrono::duration_cast<std::chrono::milliseconds>(b - a).count();
    };
    std::cout << "seq: " << ms(t1, t2) << "ms\n";
    std::cout << "par: " << ms(t2, t3) << "ms\n";
    std::cout << "par_unseq: " << ms(t3, t4) << "ms\n";
    return 0;
}

std::reduce vs. std::accumulate

std::accumulate verarbeitet die Elemente streng von links nach rechts und kann nicht parallelisiert werden. std::reduce (C++17) erlaubt der Implementierung, die Elemente in beliebiger Reihenfolge zu verarbeiten und Teilergebnisse zusammenzuführen — und ermöglicht damit parallele Ausführung. Damit reduce korrekte Ergebnisse liefert, muss die Operation assoziativ und kommutativ sein.

reduce_demo.cpp
#include <numeric>
#include <execution>
#include <vector>
#include <iostream>

int main() {
    std::vector<double> data(1'000'000, 1.0);

    // Sequential accumulate — always left-to-right
    double sum1 = std::accumulate(data.begin(), data.end(), 0.0);

    // Parallel reduce — may split and combine in any order
    double sum2 = std::reduce(std::execution::par,
                              data.begin(), data.end(), 0.0);

    // Transform-reduce: parallel dot product
    std::vector<double> a(1'000'000, 2.0);
    std::vector<double> b(1'000'000, 3.0);
    double dot = std::transform_reduce(
        std::execution::par,
        a.begin(), a.end(), b.begin(),
        0.0);  // default: multiply + add

    std::cout << "accumulate: " << sum1 << "\n";
    std::cout << "reduce:     " << sum2 << "\n";
    std::cout << "dot product: " << dot << "\n";  // 6'000'000
    return 0;
}
Stolperfalle

Beim Einsatz paralleler Ausführungsrichtlinien kann das aufrufbare Objekt (Prädikat, Transformationsfunktion, Reduktionsoperator), das du dem Algorithmus übergibst, nebenläufig aus mehreren Threads aufgerufen werden. Greift es auf gemeinsamen veränderlichen Zustand zu, hast du ein Data Race:

int count = 0;
std::for_each(std::execution::par, v.begin(), v.end(),
    [&count](int x) {
        if (x > 0) ++count;  // DATA RACE! Mehrere Threads erhöhen count
    });

Nutze std::atomic, thread-lokale Akkumulatoren oder — noch besser — std::reduce bzw. std::count_if, die die Zusammenführung sicher erledigen.

Das Amdahlsche Gesetz — wann Parallelität hilft

Das Amdahlsche Gesetz besagt, dass die maximale Beschleunigung durch Parallelität vom sequenziellen Anteil deines Programms begrenzt wird. Müssen 10 % der Arbeit sequenziell erledigt werden, liegt die maximale Beschleunigung selbst mit unendlich vielen Threads bei Faktor 10.

Beschleunigung = 1 / (S + P/N), wobei S der sequenzielle Anteil, P der parallele Anteil und N die Anzahl der Threads ist.

Parallelität verursacht außerdem Overhead: Thread-Erzeugung, Synchronisation, Cache-Konkurrenz und False Sharing. Bei kleinen Datenmengen kann der Overhead den Nutzen übersteigen. Faustregeln:

- Sortieren: Paralleles std::sort lohnt sich typischerweise ab etwa 100.000 Elementen.
- Transform/for_each: Bringt ab etwa 10.000 Elementen etwas, sofern pro Element nichttriviale Arbeit anfällt.
- Reduce: Lohnt sich ab etwa 100.000 Elementen oder bei teuren Operationen.
- Miss immer nach — profiliere mit und ohne std::execution::par.

Ein Thread-Pool in der Praxis — Überblick

Der C++-Standard bietet (Stand C++23) keinen Thread-Pool, doch das Muster ist unkompliziert: Eine feste Menge von Worker-Threads holt Aufgaben aus einer gemeinsamen Queue. Hier eine minimale Skizze.

thread_pool.cpp
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <functional>
#include <vector>

class ThreadPool {
    std::vector<std::thread> workers_;
    std::queue<std::function<void()>> tasks_;
    std::mutex mtx_;
    std::condition_variable cv_;
    bool stop_ = false;

public:
    explicit ThreadPool(size_t n) {
        for (size_t i = 0; i < n; ++i) {
            workers_.emplace_back([this] {
                while (true) {
                    std::function<void()> task;
                    {
                        std::unique_lock lock(mtx_);
                        cv_.wait(lock, [this] {
                            return stop_ || !tasks_.empty();
                        });
                        if (stop_ && tasks_.empty()) return;
                        task = std::move(tasks_.front());
                        tasks_.pop();
                    }
                    task();  // run outside the lock
                }
            });
        }
    }

    void enqueue(std::function<void()> task) {
        {
            std::lock_guard lock(mtx_);
            tasks_.push(std::move(task));
        }
        cv_.notify_one();
    }

    ~ThreadPool() {
        {
            std::lock_guard lock(mtx_);
            stop_ = true;
        }
        cv_.notify_all();
        for (auto& w : workers_) w.join();
    }
};

int main() {
    ThreadPool pool(4);
    for (int i = 0; i < 20; ++i) {
        pool.enqueue([i] {
            std::cout << "Task " << i << " on thread "
                      << std::this_thread::get_id() << "\n";
        });
    }
    // pool destructor waits for all tasks
    return 0;
}
Best Practice

Bevorzuge bei Standardalgorithmen std::execution::par gegenüber selbstgebauter Parallelität — die Implementierung kennt deine Hardware. Vergewissere dich immer, dass dein aufrufbares Objekt frei von Data Races und Seiteneffekten ist. Nutze std::reduce statt std::accumulate, wenn du Parallelität brauchst. Miss mit realistischen Datenmengen; bei kleinen Eingaben kann sequenziell schneller sein. Denk daran, dass par_unseq alles verbietet, was eine Sperre erwirbt (auf manchen Plattformen gehört dazu auch die Speicherallokation).

Wichtigste Erkenntnisse
  • Die Ausführungsrichtlinien aus C++17 (seq, par, par_unseq) bringen Parallelität mit minimalen Codeänderungen in Standardalgorithmen
  • std::reduce ist der parallelisierbare Ersatz für std::accumulate — deine Operation muss assoziativ und kommutativ sein
  • Das Amdahlsche Gesetz begrenzt die Beschleunigung: Der sequenzielle Teil deines Codes wird zum Flaschenhals
  • Parallele Algorithmen verursachen Overhead — sie lohnen sich nur bei ausreichend großen Datenmengen oder teurer Arbeit pro Element
  • Stelle immer sicher, dass die an parallele Algorithmen übergebenen aufrufbaren Objekte frei von Data Races sind
  • Thread-Pools nutzen eine feste Menge von Threads wieder und sparen so die Kosten der Thread-Erzeugung bei vielen kleinen Aufgaben

Quiz — Teste dein Wissen

(15 XP)

1. Warum lässt sich `std::accumulate` nicht mit Ausführungsrichtlinien verwenden?

2. Welche Einschränkung legt `std::execution::par_unseq` dem aufrufbaren Objekt auf?

3. Wie hoch ist nach dem Amdahlschen Gesetz die maximale Beschleunigung, wenn 20 % eines Programms sequenziell sind?

Zurück
Atomare Operationen & Memory Ordering
Weiter
C++17: Der praxisnahe Standard