Skip to content
Snippets Groups Projects
Jose H's avatar
Jose Hosea authored
847b7c06
Forked from IF3230-2019 / CUDA
10 commits ahead of the upstream repository.
Name Last commit Last update
doc
src
test
README.md
makefile

PARALLEL RADIX SORT

Petunjuk penggunaan program:

  1. Buka terminal
  2. Pada terminal, ketik
make

untuk melakukan build.

  1. Pada terminal, ketik
./radix

untuk melakukan run.

Karena compiler program (nvcc) tidak mengijinkan alokasi dinamik menggunakan variabel maka argumen program tidak dapat digunakan untuk mengalokasikan array yang digunakan untuk melakukan pembangkitan integer acak. Sehingga banyak elemen array integer ditentukan dengan menggunakan nilai konstan ARRAY_SIZE yang terdapat pada bagian awal kode program.

Pembagian tugas:

13516003 - Perbaikan program paralel dan format keluaran

13516027 - Inisiasi program sekuensial dan paralel

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:

  1. Pembangkitan nilai acak pada array menggunakan cudaRand.
  2. Pencarian nilai maksimum untuk menentukan digit terbesar diantara elemen array. Pencarian dilakukan dengan pararel yang direduksi, menggunakan CUDA threads.
  3. 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 sudah membagi pekerjaan yang harusnya dapat mempercepat kinerja. Contohnya apabila terdapat 100 elemen array dan maka sebanyak 50 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. 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.

Jumlah thread 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.

Pengukuran dilakukan dengan menjalankan program paralel yang telah dibuat dengan pengubahan ARRAY_SIZE sesuai dengan N yang akan diuji. Waktu pengujian dirata-rata dari 3 kali percobaan.

N = 5000

Serial : The sorting process took 1325 microseconds to run.

Paralel : The sorting process took 2684 microseconds to run.

N = 50000

Serial : The sorting process took 16312 microseconds to run.

Paralel : The sorting process took 16504 microseconds to run.

N = 100000

Serial : The sorting process took 23058 microseconds to run.

Paralel : The sorting process took 22182 microseconds to run.

N = 200000

Serial : The sorting process took 42182 microseconds to run.

Paralel : The sorting process took 38141 microseconds to run.

N = 400000

Serial : The sorting process took 79765 microseconds to run.

Paralel : The sorting process took 63011 microseconds to run.

Analisis perbandingan kinerja serial dan paralel. Analisis yang diharapkan adalah analisis yang minimal dapat menjelaskan setiap hasil pengukuran kinerja sebelumnya.

Pembagian kerja secara paralel belum cukup optimal karena dapat dilihat untuk parameter N yang kecil, waktu eksekusi paralel lebih lama dibandingkan dengan waktu eksekusi serial. Program dapat dioptimasi dengan mengubah algoritma dalam memetakan elemen array setelah perhitungan kemunculan angka pada setiap digit (memanfaatkan proses selain proses utama). Dan mungkin perlu dianalisis lebih lanjut mengenai stride pada algoritma untuk dapat memanfaatkan pengaksesan memori yang lebih efisien.