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 melalui komputer pribadi, kami menemukan bahwa jika nilai thread lebih dari 2, ada kemungkinan program MPI tersebut stuck. Walaupun hal ini tidak pernah kami temukan di komputer remote. Maka dari itu untuk mendapatkan data yang konsisten kami memutuskan untuk menggunakan 2 thread saja

Pengukuran Kinerja

Analisis Pengukuran Kinerja

Dari data kinerja diatas, sebenarnya kami lebih cenderung merasa bahwa faktor terbesar berkurangnya waktu bukanlah jumlah thread yang digunakan, tapi bagaimana kondisi cache dari prosesor. Walaupun dari data diatas dapat kita temukan perbedaan, tapi perbedaan tersebut sifatnya random dan tidak memiliki arah yang jelas. Oleh karena itu setiap pengurangan waktu yang terjadi ketika jumlah thread ditambahkan (atau penambahan waktu) lebih cenderung disebabkan oleh kondisi cache pada saat itu.

Tapi karena radix sort parallel jauh lebih unggul ketika jumlah data banyak maka mungkin saja penurunan drastis yang terjadi ketika menggunakan dua thread ketika size = 200000 disebabkan oleh penggunaan parallel programming dan bukan kondisi cache saja.