Gagasan Pohon Reduksi
Kurangi separuh thread aktif pada setiap langkah.
Gagasan Pohon Reduksi adalah pelajaran CUDA Academy gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar CUDA Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus CUDA Academy mencakup 4 pelajaran total.
Makna Reduksi
Reduksi meringkas seluruh array menjadi satu nilai, seperti menjumlahkan setiap elemen hingga menjadi satu total. Reduksi adalah salah satu pola GPU yang paling umum. 🌳
Cara Berurutan Itu Lambat
Pada CPU, Anda menambahkan elemen satu per satu. Itu berarti langkah berurutan O(n), sehingga satu juta angka memerlukan satu juta penjumlahan yang saling bergantung secara berurutan.
Penjumlahan Bersifat Asosiatif
Triknya adalah penjumlahan bersifat asosiatif: (a+b)+c sama dengan a+(b+c). Jadi, Anda bebas menjumlahkan pasangan dalam pengelompokan apa pun.
Menjumlahkan Pasangan secara Paralel
Karena pengelompokan tidak menjadi masalah, Anda dapat menjumlahkan banyak pasangan independen pada saat yang sama. Setiap utas menangani satu pasangan, semuanya dalam satu langkah paralel.
Membagi Dua pada Setiap Langkah
Setelah satu lintasan, separuh elemen telah selesai. Ulangi prosesnya, dan jumlah yang aktif terus dibagi dua: 8 menjadi 4, lalu 2, lalu 1.
Kedalaman Logaritmik
Pembagian dua berarti Anda selesai dalam log2(n) langkah, bukan n. Satu juta elemen dapat diringkas dalam sekitar 20 langkah, bukan satu juta.
Bayangkan Pohonnya
Menggambar pasangan-pasangan tersebut membentuk pohon biner. Daun adalah masukan, setiap tingkat membagi dua simpul, dan akar adalah jumlah akhir Anda.
Langkah Lompatan Berlipat Dua pada Setiap Lintasan
Salah satu cara mengodekannya: pada setiap langkah, sebuah utas menambahkan tetangganya pada jarak stride, dan jarak tersebut berlipat dua pada setiap lintasan melalui data.
for (int s = 1; s < blockDim.x; s *= 2) {
if (tid % (2 * s) == 0)
data[tid] += data[tid + s];
__syncthreads();
}Sinkronisasi Antar-Langkah
Setiap tingkat bergantung pada selesainya tingkat sebelumnya, sehingga utas harus menunggu di penghalang sebelum membaca hasil pasangannya.
Pekerjaan dan Rentang
Jumlah penjumlahan tetap sekitar n, yaitu pekerjaan. Namun, rantai ketergantungan terpanjang, yaitu rentang, menyusut menjadi log2(n). Pekerjaannya sama, tetapi waktu menunggunya jauh lebih sedikit.
Bukan Hanya Penjumlahan
Pohon yang sama dapat digunakan untuk operasi asosiatif apa pun: maksimum, minimum, perkalian, atau logika AND. Ganti operatornya, dan strukturnya tetap sama.
Pemeriksaan Singkat
Pikirkan berapa banyak langkah paralel yang diperlukan reduksi pohon.
Ringkasan
Anda mempelajari pohon reduksi: menjumlahkan pasangan secara paralel, membagi dua pada setiap langkah, dan selesai dalam log2(n). Cara ini berlaku untuk operator asosiatif apa pun. Selanjutnya, buat warp tetap sibuk! 🎉
Belajar C++ dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Gagasan Pohon Reduksi” gratis?
Ya — teks lengkap “Gagasan Pohon Reduksi” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus CUDA Academy, upgrade ke CoddyKit PRO. Kursus CUDA Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Gagasan Pohon Reduksi”?
Kurangi separuh thread aktif pada setiap langkah. Kamu berlatih CUDA Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai CUDA Academy?
Tidak diperlukan pengalaman sebelumnya. CUDA Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Gagasan Pohon Reduksi” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran CUDA Academy ini?
Ya. Setiap pelajaran CUDA Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Gagasan Pohon Reduksi
- Hilangkan Divergensi Warp
- Pengalamatan Sekuensial
- Reduksi Akhir Multi-Blok