PARALLEL RADIX SORT CUDA IF3230
Petunjuk penggunaan program
- Buka terminal
- Pada terminal, ketik "make"
- Lalu untuk melakukan run, ketik "./radix_sort"
Keterangan:
Nilai N yang diuji diubah pada konstanta N_uji yang terdapat pada program
Pembagian tugas:
13516150 - Mengerjakan tugas bersama-sama
13516153 - Mengerjakan tugas bersama-sama
Pengujian:
Deskripsi solusi paralel. Berikan ilustrasi jika perlu.
Solusi paralel yang dibuat adalah dengan membagi pekerjaan sekuensial ke dalam beberapa proses untuk dilakukan secara paralel. Untuk melakukan eksekusi pada device (GPU), data array pada host (CPU) harus disalin menggunakan cudaMemcpy. Pekerjaan yang dibagi adalah:
- Pembangkitan nilai acak pada array menggunakan cudaRand.
- Pencarian nilai maksimum untuk menentukan digit terbesar diantara elemen array. Pencarian dilakukan dengan pararel yang direduksi, menggunakan CUDA threads.
- Perhitungan kemunculan angka pada setiap digit. Pembagian dilakukan dengan mengelompokkan masing-masing elemen array kepada digit tertentu menggunakan CUDA threads, kemudian masing-masing thread menggabungkan hasil perhitungan ke dalam sebuah bucket global (yang menyimpan seluruh kemunculan digit) dengan memanfaatkan atomicAdd sebagai implementasi dari critical section.
Setelah perhitungan kemunculan angka telah digabung, array pada device disalin ke array pada host untuk dilakukan pemetaan elemen array berdasarkan kemunculan angka pada digit yang sedang diperiksa. Lalu pengulangan dilakukan dari digit terkecil hingga digit terbesar.
Analisis solusi yang anda berikan. Apakah mungkin terdapat solusi yang memberikan kinerja lebih baik?
Solusi yang dibuat dapat mempercepat kinerja dengan membagi pekerjaan. Ilustrasinya apabila terdapat 50 elemen array, maka sebanyak 25 CUDA thread digunakan untuk melakukan 1 kali perbandingan elemen, berbeda dengan eksekusi di host yang harus melakukan perbandingan sebanyak 100 kali menggunakan 1 CPU thread. Waktu perhitungan kemunculan angka pada setiap digit juga tereduksi karena setiap CUDA thread melakukan pengelompokkan digit untuk setiap elemen pada array. Mungkin saja terdapat solusi lain yang lebih cepat. Untuk pemetaan elemen array yang dilakukan oleh proses utama, mungkin saja dapat diparallelkan, tetapi algoritma yang telah dibuat tidak menerapkannya. Tetapi tentu saja tidak menutup kemungkinan terdapat solusi lain yang lebih cepat. Untuk pemetaan elemen array yang dilakukan oleh proses utama, mungkin saja dapat diparalelkan, tetapi algoritma yang telah dibuat tidak menerapkannya.
Jelaskan pemetaan thread ke komputasi, dan jumlah thread per block yang digunakan. Kenapa anda memilih angka tersebut?
Thread yang digunakan untuk menentukan nilai maksimum pada array adalah sebanyak N/2, dengan N adalah banyak elemen array. Hal ini dilakukan karena dengan algoritma yang digunakan, setiap thread melakukan perbandingan satu elemen array dengan satu elemen lainnya. Thread yang digunakan untuk melakukan sorting pada array adalah sebanyak N. Setiap thread bertugas untuk mengelompokkan setiap elemen array pada bucket digit yang ada.
Pengukuran kinerja untuk tiap kasus uji (jumlah N pada array) dibandingkan dengan radix sort serial.
Untuk pengujian setiap N, perlu pengubahan nilai konstanta N_uji pada program.
N = 5000
Serial : Waktu eksekusi: 1825 microseconds
Parallel : Waktu eksekusi: 2575 microseconds
N = 50000
Serial : Waktu eksekusi: 17423 microseconds
Parallel : Waktu eksekusi: 17622 microseconds
N = 100000
Serial : Waktu eksekusi: 22458 microseconds
Parallel : Waktu eksekusi: 22133 microseconds
N = 200000
Serial : Waktu eksekusi: 42411 microseconds
Parallel : Waktu eksekusi: 37665 microseconds
N = 400000
Serial : Waktu eksekusi: 79963 microseconds
Parallel : Waktu eksekusi: 62689 microseconds
Analisis perbandingan kinerja serial dan paralel. Analisis yang diharapkan adalah analisis yang minimal dapat menjelaskan setiap hasil pengukuran kinerja sebelumnya.
Untuk parameter N yang kecil (pada kasus ini 5000 dan 50000), waktu eksekusi paralel lebih lama dibandingkan dengan waktu eksekusi serial. Ini berarti program perlu dioptimasi dengan mengubah algoritma dalam memetakan array setelah perhitungan kemunculan angka tiap digit. Dan juga perlu dianalisis lebih lanjut mengenai stride pada algoritma untuk dapat memanfaatkan pengaksesan memori yang lebih efisien.