C++

Παράλληλοι αλγόριθμοι & πολιτικές εκτέλεσης

Αξιοποιήστε το παράλληλο STL του C++17 για να παραλληλίσετε την ταξινόμηση, τον μετασχηματισμό και τη μείωση με τις πολιτικές εκτέλεσης. Κατανοήστε πότε βοηθά ο παραλληλισμός, ο νόμος του Amdahl και ο πρακτικός σχεδιασμός πισίνας νημάτων.

Parallel STL — Εύκολος Παραλληλισμός

Το C++17 πρόσθεσε πολιτικές εκτέλεσης στις περισσότερες συναρτήσεις. Περνώντας μια πολιτική ως πρώτο όρισμα, λέτε στην υλοποίηση να παραλληλίσει τον αλγόριθμο — ενδεχομένως χρησιμοποιώντας πολλαπλά νήματα, SIMD ή και τα δύο — χωρίς να αλλάξετε κανέναν άλλο κώδικα.

Αυτός είναι ο ευκολότερος τρόπος για να προσθέσετε παραλληλισμό στο C++: λάβετε την υπάρχουσα κλήσηstd::sort,std::transformήstd::for_each, προσαρτήστε τοstd::execution::parκαι αφήστε την υλοποίηση να κάνει τα υπόλοιπα. Φυσικά, πρέπει να βεβαιωθείτε ότι οι λειτουργίες σας είναι ασφαλείς για ταυτόχρονη εκτέλεση (χωρίς φυλές δεδομένων σε κατηγόρημα, καμία κοινή μεταβλητή κατάσταση).

Επεξήγηση των πολιτικών εκτέλεσης

Υπάρχουν τρεις τυπικές πολιτικές εκτέλεσης που ορίζονται στο. Το καθένα παρέχει διαφορετικές εγγυήσεις σχετικά με τον παραλληλισμό και τη διανυσματοποίηση.

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επεξεργάζεται στοιχεία αυστηρά από αριστερά προς τα δεξιά και δεν μπορεί να παραλληλιστεί. Τοstd::reduce(C++17) επιτρέπει στην υλοποίηση να επεξεργάζεται στοιχεία με οποιαδήποτε σειρά και να συνδυάζει μερικά αποτελέσματα — επιτρέποντας την παράλληλη εκτέλεση. Η λειτουργία πρέπει να είναι συσχετιστική και ανταλλαγή για τοreduceγια να παράγει σωστά αποτελέσματα.

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;
}
Παγίδα

Όταν χρησιμοποιείτε πολιτικές παράλληλης εκτέλεσης, το καλούμενο (κατηγόρημα, συνάρτηση μετασχηματισμού, τελεστής μείωσης) που μεταβιβάζετε στον αλγόριθμο μπορεί να καλείται ταυτόχρονα από πολλαπλά νήματα. Εάν η δυνατότητα κλήσης σας έχει πρόσβαση σε κοινή μεταβλητή κατάσταση, έχετε μια κούρσα δεδομένων:

int count = 0;
std::for_each(std::execution::par, v.begin(), v.end(),
    [&count](int x) {
        if (x > 0) ++count;  // DATA RACE! Multiple threads increment count
    });

Use std::atomic, thread-local accumulators, or better yet, use std::reduce / std::count_if που χειρίζονται τη συγκέντρωση με ασφάλεια.

Νόμος του Άμνταλ - Όταν ο Παραλληλισμός βοηθάει

Ο νόμος του Amdahl δηλώνει ότι η μέγιστη επιτάχυνση από τον παραλληλισμό περιορίζεται από το διαδοχικό κλάσμα του προγράμματός σας. Εάν το 10% της εργασίας πρέπει να γίνει διαδοχικά, τότε ακόμη και με άπειρα νήματα, η μέγιστη επιτάχυνση είναι 10x.

Speedup = 1 / (S + P/N), όπου S είναι το διαδοχικό κλάσμα, P είναι το παράλληλο κλάσμα και N είναι ο αριθμός των νημάτων.

Ο παραλληλισμός έχει επίσης επιβάρυνση: δημιουργία νημάτων, συγχρονισμό, διαμάχη προσωρινής μνήμης και ψευδή κοινή χρήση. Για μικρά σύνολα δεδομένων, τα γενικά έξοδα μπορεί να υπερβούν το όφελος. Εμπειρικοί κανόνες:

- Ταξινόμηση: Το παράλληλοstd::sortσυνήθως βοηθά πάνω από ~100K στοιχεία.
- Transform/for_each: Οφέλη πάνω από ~10.000 στοιχεία με μη τετριμμένη εργασία ανά στοιχείο.
- Μείωση: Οφέλη πάνω από ~100.000 στοιχεία ή με ακριβές λειτουργίες.
- Πάντα μετρήστε — προφίλ με και χωρίςstd::execution::par.

Πρακτική επισκόπηση της πισίνας νημάτων

Το πρότυπο C++ δεν παρέχει μια ομάδα νημάτων (όπως και στο C++23), αλλά το μοτίβο είναι απλό: ένα σταθερό σύνολο νημάτων εργασίας τραβάει εργασίες από μια κοινόχρηστη ουρά. Εδώ είναι ένα minimal σκίτσο.

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;
}
Βέλτιστη πρακτική

Προτιμήστε τοstd::execution::parέναντι του παραλληλισμού με το χέρι για τυπικούς αλγόριθμους — η υλοποίηση γνωρίζει το υλικό σας. Πάντα να βεβαιώνεστε ότι η δυνατότητα κλήσης σας δεν έχει κούρσες δεδομένων και παρενέργειες. Χρησιμοποιήστεstd::reduceαντί γιαstd::accumulateόταν χρειάζεστε παραλληλισμό. Σημείο αναφοράς με ρεαλιστικά μεγέθη δεδομένων. για μικρές εισόδους, η διαδοχική μπορεί να είναι ταχύτερη. Θυμηθείτε ότι τοpar_unseqαπαγορεύει την κλήση οτιδήποτε αποκτά κλειδαριά (συμπεριλαμβανομένης της εκχώρησης μνήμης σε ορισμένες πλατφόρμες).

Βασικά συμπεράσματα
  • Οι πολιτικές εκτέλεσης C++17 (seq,par,par_unseq) προσθέτουν παραλληλισμό σε τυπικούς αλγόριθμους με ελάχιστες αλλαγές κώδικα
  • Τοstd::reduceείναι η παράλληλη φιλική αντικατάσταση τουstd::accumulate— η λειτουργία σας πρέπει να είναι συνειρμική και ανταλλακτική
  • Ο νόμος του Amdahl περιορίζει την επιτάχυνση: το διαδοχικό τμήμα του κώδικά σας γίνεται το σημείο συμφόρησης
  • Οι παράλληλοι αλγόριθμοι έχουν επιβάρυνση — ωφέλιμο μόνο για αρκετά μεγάλα σύνολα δεδομένων ή δαπανηρή εργασία ανά στοιχείο
  • Βεβαιωθείτε ότι τα καλούμενα που μεταβιβάζονται σε παράλληλους αλγόριθμους δεν περιέχουν φυλές δεδομένων
  • Οι ομάδες νημάτων επαναχρησιμοποιούν ένα σταθερό σύνολο νημάτων για να αποφύγουν το κόστος δημιουργίας νημάτων για πολλές μικρές εργασίες

Κουίζ — Δοκιμάστε τις γνώσεις σας

(15 XP)

1. Γιατί δεν μπορεί να χρησιμοποιηθεί το`std::accumulate`με πολιτικές εκτέλεσης;

2. Τι περιορισμό θέτει το`std::execution::par_unseq`στο καλούμενο;

3. Σύμφωνα με το νόμο του Amdahl, ποια είναι η μέγιστη επιτάχυνση εάν το 20% ενός προγράμματος είναι διαδοχικό;

Προηγούμενο
Atomic Operations & Memory Ordering
Επόμενο
C++17: Το Πρακτικό Πρότυπο