IF Notes

Reduksi

6 min read

Back to IF3130 Sistem Paralel dan Terdistribusi

Pola Algoritma Paralel: Reduksi (Reduction)

Questions/Cues

  • Apa itu komputasi reduksi?

  • Apa strategi “Partition and Summarize”?

  • Bagaimana cara kerja Reduksi Pohon (Reduction Tree)?

  • Apa itu work-efficiency?

  • Apakah reduksi paralel naif efisien?

  • Bagaimana implementasi reduksi di CUDA?

  • Mengapa __syncthreads() penting dalam reduksi?

  • Bagaimana cara mengurangi control divergence?

  • Apa itu teknik thread compaction?

Reference Points

  • 7 - IF-3230-07-GPU-07-2023.pdf

Apa itu Komputasi Reduksi?

Reduksi adalah operasi untuk “meringkas” sebuah set data input menjadi satu nilai tunggal menggunakan sebuah operasi biner yang bersifat asosiatif dan komutatif.

  • Operasi Umum: Penjumlahan (sum), perkalian (product), nilai maksimum (max), nilai minimum (min).

  • Contoh: Menjumlahkan semua elemen dalam sebuah array untuk mendapatkan totalnya. Atau, mencari suhu tertinggi dari data sensor di seluruh kota.

Sifat asosiatif (a+b)+c = a+(b+c) dan komutatif a+b = b+a sangat penting karena ini berarti urutan pemrosesan elemen tidak mempengaruhi hasil akhir, yang merupakan syarat fundamental untuk paralelisasi yang efektif.

Strategi “Partition and Summarize”

Ini adalah strategi inti di balik banyak framework komputasi terdistribusi (seperti MapReduce) dan merupakan cara alami untuk memparalelkan operasi reduksi.

  1. Partition (Partisi): Kumpulan data input yang besar dipecah menjadi beberapa bagian (chunk) yang lebih kecil.

  2. Process in Parallel: Setiap thread (atau prosesor) secara independen menghitung hasil parsial untuk satu partisi. Misalnya, setiap thread menjumlahkan angka-angka di bagiannya masing-masing.

  3. Summarize (Ringkas): Hasil-hasil parsial dari setiap thread kemudian digabungkan (direduksi lagi) untuk menghasilkan satu nilai akhir. Proses peringkasan ini sering diimplementasikan menggunakan Pohon Reduksi.

Reduksi Pohon (Reduction Tree)

Ini adalah metode yang sangat efisien untuk melakukan fase “Summarize”. Daripada satu thread menjumlahkan semua hasil parsial secara sekuensial, thread-thread bekerja sama dalam struktur seperti turnamen.

  • Cara Kerja:

    • Langkah 1: Setengah dari thread yang aktif mengambil nilai dari setengah thread lainnya dan menambahkannya ke nilainya sendiri. Setelah langkah ini, jumlah data yang perlu diproses berkurang setengahnya.

    • Langkah 2: Proses diulangi. Setengah dari thread yang masih aktif mengambil nilai dari setengah lainnya.

    • Seterusnya: Proses ini berlanjut sampai hanya satu thread yang tersisa, yang memegang hasil akhir.

Untuk N elemen, proses ini hanya membutuhkan log₂(N) langkah, membuatnya sangat cepat secara teoretis.

Analisis Efisiensi Kerja (Work-Efficiency)

Work-efficiency membandingkan jumlah total operasi yang dilakukan oleh algoritma paralel dengan algoritma sekuensial yang paling efisien.

  • Algoritma Sekuensial Efisien: Untuk menjumlahkan N elemen, diperlukan N-1 operasi penjumlahan. Kompleksitasnya adalah O(N).

  • Algoritma Reduksi Pohon Paralel: Jumlah total operasi yang dilakukan di semua langkah adalah N/2 + N/4 + N/8 + ... + 1 = N-1. Kompleksitas kerjanya juga O(N).

Karena jumlah total pekerjaannya sama, algoritma reduksi pohon ini disebut work-efficient. Ini adalah properti yang sangat diinginkan; algoritma paralel yang tidak work-efficient (misalnya, O(N log N)) bisa jadi lebih lambat dari versi sekuensialnya jika sumber daya komputasi terbatas.

Implementasi Reduksi Paralel di CUDA

Implementasi umum di CUDA menggunakan Shared Memory untuk melakukan reduksi di dalam satu thread block.

Alur Kernel:

  1. Setiap thread dalam block memuat satu atau lebih elemen dari Global Memory ke sebuah array di Shared Memory (partialSum[]).

  2. Lakukan sinkronisasi (__syncthreads()) untuk memastikan semua data telah dimuat.

  3. Lakukan reduksi pohon di dalam Shared Memory dalam sebuah loop log(N) langkah.

  4. Setelah loop selesai, thread pertama (threadIdx.x == 0) menulis hasil akhir dari Shared Memory kembali ke Global Memory.

Contoh Kode Reduksi Naif (dalam loop reduksi):

for (unsigned int stride = 1; stride < blockDim.x; stride *= 2) {
    __syncthreads();
    if (threadIdx.x % (2 * stride) == 0) {
        partialSum[threadIdx.x] += partialSum[threadIdx.x + stride];
    }
}

Implementasi ini tidak efisien karena menyebabkan control divergence yang parah. Pada setiap iterasi, setengah dari thread menjadi tidak aktif.

Implementasi yang Lebih Baik: Mencegah Divergence

Untuk menghindari divergence, kita harus memastikan bahwa semua thread yang aktif dalam satu warp selalu berdekatan (kompak). Ini disebut thread compaction.

Kode yang Dioptimalkan (dalam loop reduksi):

for (unsigned int stride = blockDim.x / 2; stride > 0; stride /= 2) {
    __syncthreads();
    if (threadIdx.x < stride) {
        partialSum[threadIdx.x] += partialSum[threadIdx.x + stride];
    }
}

  • Cara Kerja: Alih-alih membuat thread ganjil menjadi tidak aktif, pendekatan ini membuat separuh terakhir dari thread menjadi tidak aktif.

  • Keuntungan: Selama stride lebih besar dari ukuran warp (32), seluruh warp akan aktif atau tidak aktif bersamaan. Ini menghilangkan control divergence untuk sebagian besar iterasi, hanya menyisakannya di beberapa langkah terakhir, sehingga performanya jauh lebih baik.

Summary

Reduksi adalah pola komputasi paralel fundamental untuk meringkas dataset menjadi satu nilai melalui operasi asosiatif. Implementasi yang efisien menggunakan struktur Reduksi Pohon (Reduction Tree) yang memiliki kompleksitas waktu O(log N) dan kerja O(N), menjadikannya work-efficient. Di CUDA, reduksi biasanya diimplementasikan di dalam thread block menggunakan Shared Memory, dan sangat penting untuk menggunakan strategi thread compaction untuk meminimalkan control divergence dan memaksimalkan performa.

Graph View

Backlinks