Praktikum 03

CUDA - Radix Sort

How To

Run make then open the executable file by typing ./radix_sort_cuda

Pembagian Tugas

13516067 - Dinda Yora Islami

• Counting Sort
• Radix Sort
• Convert to parallel
• Testing
• Doc and README

13516091 - Yasya Rusyda Aslina

• Counting Sort
• GetMax
• Convert to parallel
• Testing
• Doc and README

Deskripsi Solusi Paralel

CUDA (Compute Unified Device Architecture) merupakan platform parallel computing dan programming model yang dibat oleh NVIDIA dan diimplementasi dari graphics processing units (GPUs) yang diproduksi. Perlu dibuat sebuah solusi radix sort yang menggunakan sistem pengiriman pesan antar proses. Salah satu cara termudahnya adalah

1. Data akan dibagi menjadi array-array berdasarkan digitnya
2. Hitung nilai count dari setiap data yang akan di sort
3. Sort data lokal pada tiap-tiap proses (per digit)
4. Gabungkan semua data lokal yang ada dari proses (count_sort)
5. Gabungkan nilai count dari tiap proses
6. Lakukan sort secara global
7. Ulangi langkah 1

Dari langkah-langkah tersebut langkah countsort (penghitungan jumlah digit dari data ) dapat dilakukan secara parallel dengan mendesain sedemikian rupa menggunakan CUDA. Hal ini dapat dicapai dengan mengalokasikan memori host dan menginisalisasinya, kemudian mengalokasikan memori device, transfer input data, eksekusi kernels, dan transfer output dari device

Analisis Solusi

Setelah penulis menulis kode diatas, penulis menemukan banyak hal yang dapat diefektifkan. Salah satunya adalah bagaimana program ini melakukan sorting. Jika kita melihat langkah yang telah dideskripsikan diatas, maka kita menemukan bahwa:

• counting terhadap angka digital 0-9, seharusnya dapat menggunakan operasi bitwise sehingga cukup menghitung digit 0-1
• kemungkinan ada operasi yang dapat dibuat paralel mengingat proses penghitungan dan assign masing-masing bisa dibuat operasi parallel yang berbeda pada countosrt

Jumlah Thread yang Digunakan

32

Ketika melakukan pengerjaan kami menemukan bahwa program yang kami modifikasi menjadi paralel lebih cocok pada saat thread 32.

Pengukuran Kinerja

Pada pengukuran ini kami membandingkan program radix sort paralel di cuda dengan program radix sort serial di cuda

Analisis Pengukuran Kinerja

Dari hasil pengukuran diatas dapat kita lihat bahwa radix sort paralel dengan cuda lebih cepat dari pada radix sort secara serial. Selain itu dengan bertambahnya ukuran array maka kecepatan radix sort paralel makin lebih cepat dari serial.