Tugas IF3230 Dijkstra CUDA
Petunjuk Penggunaan Program
Dalam direktori root lakukan kompilasi program dengan makefile:
- Untuk melakukan kompilasi dijkstra versi serial:
make serial
bin/serial [number of vertices]
- Untuk melakukan kompilasi dijkstra versi paralel (CUDA):
make parallel_cuda nt=[jumlah thread] nv=[jumlah nodes]
Pembagian Tugas
- 13517035 - Hilmi Naufal Yafie : Paralel Dijkstra CUDA, Laporan, Eksplorasi
- 13517122 - M. ALgah Fattah I. : Paralel Dijkstra CUDA, Laporan, Eksplorasi
Laporan Pengerjaan
Deskripsi Solusi Paralel
Solusi paralel yang kami buat adalah paralelisasi dalam menjalankan algoritma dijkstra secara keseluruhan. Sebagaimana yang diketahui, algoritma dijkstra dapat mencari jarak terdekat dari suatu node ke semua node lain. Oleh karena pada persoalan yang diberikan kita diminta untuk mencari jarak dari semua node ke semua node lain, paralelisasi yang kami lakukan adalah setiap thread menjalankan dijkstra dari titik asal (source) yang berbeda-beda, lalu kemudian menuliskan hasil jarak antara titik-titik lain dengan source tersebut pada baris yang bersangkutan di matriks yang merepresentasikan hasil akhir.
Misalkan ada 3 anak proses dan ada 3 node pada graf yang di-proses, maka diparalelisasi sehingga thread pertama memproses node A, thread kedua memproses node B, dan thread ketiga memproses node C. Misalkan pula sebuah matriks akhir result
yang menyimpan matriks akhir, maka thread pertama akan menuliskan ke baris pertama result
yang merepresentasikan jarak dari node A ke node-node lain, dst.
Analisis Solusi
Dalam konteks memparalelisasi algoritma dijkstra, menurut kami jika beban komputasi didistribusi kepada thread-thread yang dikerjakan oleh core pada gpu, maka waktu untuk melakukan perhitungan jarak secara total akan menjadi lebih singkat
Hasil Uji
Berikut Merupakan hasil uji yang kami lakukan untuk node 100, 500, 1000, dan 3000 baik untuk Serial Dijkstra dan Paralel Dijkstra (dalam microseconds):
- Serial Dijkstra
N | Percobaan 1 | Percobaan 2 | Percobaan 3 | Rata-rata |
---|---|---|---|---|
100 | 20.1025 | 20.0155 | 18.46475 | 19.52758 |
500 | 2537.57925 | 1734.28625 | 1661.24725 | 1977.70425 |
1000 | 13798.4025 | 13938.675 | 15880.503 | 14539.1935 |
3000 | 762352.86125 | 663569.772 | 790499.578 | 738807.40375 |
- Paralel Dijkstra CUDA
N | Percobaan 1 | Percobaan 2 | Percobaan 3 | Rata-rata |
---|---|---|---|---|
100 | 86.368 | 58.231 | 39.25525 | 61.28475 |
500 | 1115.20125 | 941.9165 | 943.5145 | 1000.21075 |
1000 | 4191.5325 | 6223825 | 7646.94175 | 6020.76641666 |
3000 | 232189.652940250002 | 238495.246832749981 | 241372.985165749997 | 237352.628313 |
untuk setiap kasus uji, block size = 256 threads
Analisis Uji
Dari seluruh percobaan yang dilakukan, didapatkan bahwa program paralel selalu lebih cepat daripada program serial. Hal ini tentu karena paralelisasi lebih mengutilisasi resource yang ada dengan thread yang lebih dari 1 menjadikan proses lebih cepat.