Skip to content
Snippets Groups Projects
Hilmi Naufal Yafie's avatar
bb51a447
Forked from IF3230-2020 / CUDA
11 commits ahead of the upstream repository.
Name Last commit Last update
src
.gitignore
Makefile
README.md

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.