Parallel Algorithms

Sejak C++17, algoritma standar seperti std::sort dan std::reduce menerima argumen tambahan bernama execution policy: cara berkata kepada implementasi, “algoritma ini boleh dijalankan paralel”. Menariknya, tanda tangan fungsi tidak berubah — yang berubah hanya penambahan satu argumen, sehingga kode sekuensial bisa naik kelas tanpa restrukturisasi. Namun ada catatan lingkungan yang wajib kita pahami sebelum menulisnya di GCC: implementasi paralel libstdc++ bersandar pada Intel TBB, dan pustaka itu belum tersedia di sandbox course ini. Chapter ini menunjukkan bentuk kodenya sebagai blok display, membuktikan pesan error yang muncul, lalu membangun alternatif yang benar-benar teruji: partisi manual dengan std::thread.

Execution Policy pada Algoritma Standar #

Bentuk umumnya sederhana — policy disisipkan sebagai argumen pertama:

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

int main() {
    std::vector<int> data{5, 3, 1, 4, 2};
    std::sort(std::execution::par, data.begin(), data.end());
    for (int v : data) {
        std::cout << v << " ";
    }
    std::cout << "\n";
}

Policy yang tersedia: std::execution::seq (sekuensial, sama seperti tanpa policy), unseq (vektorisasi single-thread), par (paralel multi-thread, boleh terseling), dan par_unseq (paralel plus vektorisasi). Untuk par, standar memberi kebebasan penting: implementasi boleh menjalankan elemen secara bersamaan, sehingga function yang kita berikan ke algoritma harus AMAN dipanggil dari banyak thread — tanpa data race pada state yang dibagi. Di sisi hasil, std::reduce adalah mitra paralel yang tepat untuk penjumlahan, karena operasinya bebas asosiatif terhadap urutan; std::accumulate yang mengandalkan urutan tidak disediakan versinya.

Kenapa Kode Ini Belum Bisa Dijalankan di Sandbox #

libstdc++ (pustaka standar GCC) mengimplementasikan versi paralel algoritma di atas backend Intel TBB (Threading Building Blocks). Header <execution> ada di sistem, dan kompilasi sampai tahap object berjalan mulus; ketergantungan baru terasa saat linking. Begini bunyi persis yang dihasilkan sandbox ini saat mencoba menghubungkan program di atas:

g++ -std=c++23 -Wall -Wextra sort-par.cpp -o sort-par -ltbb

Output yang Dihasilkan:

/usr/bin/ld: cannot find -ltbb: No such file or directory
collect2: error: ld returned 1 exit status

Pesan itu berbunyi jelas: linker mencari pustaka -ltbb dan tidak menemukannya. Di lingkungan yang TBB-nya terinstal (misalnya lewat apt install libtbb-dev), perintah yang sama akan berhasil dan program siap dijalankan. Untuk course ini kita berpegang pada keadaan sandbox: setiap contoh std::execution::par diperlakukan sebagai blok display seperti di atas — bentuknya diajarkan, tetapi tidak ada output yang diklaim. Dukungan pustaka per compiler selalu bisa dicek pada cppreference — compiler support .

Alternatif Teruji: Partisi Manual #

Ide di balik execution policy sebenarnya sudah kita kuasai sejak chapter pertama: bagi pekerjaan, serahkan ke beberapa thread, gabungkan hasilnya setelah join(). Program berikut melakukannya secara manual untuk penjumlahan 4.000.000 angka — dan seluruh outputnya deterministik:

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

long long jumlahPotongan(const std::vector<int>& data,
                         std::size_t awal, std::size_t akhir) {
    return std::accumulate(data.begin() + awal, data.begin() + akhir, 0LL);
}

int main() {
    std::vector<int> data(4'000'000);
    std::iota(data.begin(), data.end(), 1);   // isi 1..4000000

    // Partisi manual: dua rentang, dua thread, hasil digabung setelah join
    std::size_t tengah = data.size() / 2;
    long long hasilA = 0;
    long long hasilB = 0;

    std::thread tA([&] { hasilA = jumlahPotongan(data, 0, tengah); });
    std::thread tB([&] { hasilB = jumlahPotongan(data, tengah, data.size()); });

    tA.join();
    tB.join();

    std::cout << "bagian A : " << hasilA << "\n";
    std::cout << "bagian B : " << hasilB << "\n";
    std::cout << "total    : " << hasilA + hasilB << "\n";
    return 0;
}

Output yang Dihasilkan:

bagian A : 2000001000000
bagian B : 6000001000000
total    : 8000002000000

Bedah barisnya:

1. Baris 12-13 (data + iota): vektor 4 juta elemen diisi 1 sampai 4.000.000. Data ini read-only bagi kedua thread — sesuai aturan aman kita, banyak pembaca tanpa penulis tidak butuh kunci.
2. Baris 16 (tengah): partisi dua bagian yang sama besar. Pada praktik nyata partisi bisa lebih dari dua potong, biasanya sebanyak nilai hardware_concurrency().
3. Baris 20-21 (dua thread): tiap thread menjumlahkan rentangnya ke variabel LOKAL sendiri (hasilA, hasilB) — tidak ada data bersama yang ditulis, tidak ada kunci yang dibutuhkan.
4. Baris 23-24 (join()): main() menunggu kedua potongan selesai; tanpa ini, hasilnya belum pasti.
5. Baris 26-28 (penggabungan): penjumlahan akhir dilakukan setelah join, sehingga angkanya selalu sama: 2.000.001.000.000 + 6.000.001.000.000 = 8.000.002.000.000.

Pola ini — partisi, hitung lokal, gabung setelah join — adalah inti konseptual dari semua komputasi paralel data. std::reduce dengan policy par pada dasarnya mengotomatiskan langkah-langkah yang tadi kita tulis tangan, termasuk penggabungan bertingkat yang lebih pintar daripada dua bagian.

Sampai di sini perangkat kita lengkap, dari std::thread sampai partisi manual. Satu kecakapan terakhir yang membedakan pengguna dari perancang: mendiagnosis program konkuren yang berperilaku aneh — dan itu seluruh isi chapter penutup section ini.

Referensi: cppreference — std::reduce , cppreference — compiler support .