Tugas Besar IF3230-CUDA-2020

Petunjuk Penggunaan Program

1. make compile untuk melakukan kompilasi
2. make run n={jumlah_node} untuk menjalankan program

Pembagian Tugas

• 13517089 mengerjakan fungsi dijkstra CUDA, Laporan, Testing, Debugging
• 13517032 mengerjakan fungsi dijkstra CUDA, Testing, Laporan, Debugging

Analisis

Deskripsi Solusi Paralel

Solusi paralel yang kami gunakan adalah dengan membagi pengerjaan dijkstra dilakukan oleh beberapa thread, dengan setiap thread mengerjakan satu node. Dalam proses berjalannya program, setiap thread memiliki memori sendiri, dan tidak terhubung dengan thread lainnya.

Analisis Solusi

Solusi yang kami tawarkan dengan memaksimalkan jumlah total thread, sehingga setiap node dapat dikerjakan oleh satu thread sudah tergolong efektif, Dengan solusi ini kita dapat memaksimalkan kinerja GPU seefisien mungkin, dengan menghidupkan banyak thread secara bersamaan. Pengembangan yang mungkin dapat dilakukan untuk membuat solusi kami lebih baik adalah mengatur pembagian tugas setiap thread yang masih dilakukan didalam main program dapat dipindahkan ke dalam thread, sehingga thread dapat langsung dihidupkan tanpa harus menunggu main program memberi instruksi untuk mengerjakan node tertentu.

Jumlah Thread

jumlah thread dalam satu blok yang digunakan adalah sebanyak 256. Jumlah blok yang digunakan, kita menggunakan rumus jumlah_blok = (n + jumlah_thread - 1) / jumlah_thread. Kelompok kami menggunakan jumlah blok yang dinamis, karena semakin banyak n dari sebuah graf, maka akan semakin banyak pula total thread yang digunakan untuk mencari jarak terpendek, sehingga setiap node dapat dikerjakan oleh thread masing - masing. Dengan adanya total thread yang dinamis, dapat dilihat bahwa hasil waktu paralel dari pencarian djikstra untuk setiap n relatif sama.

Hasil Pengujian

Serial

Paralel

Analisis Perbandingan Kinerja Serial dan Paralel

Dari hasil percobaan yang telah kami lakukan, dapat dilihat bahwa proses djikstra yang dilakukan secara paralel jauh lebih cepat dibandingkan proses djikstra yang dilakukan secara serial. Hal ini dikarenakan djikstra secara paralel berjalan pada GPU yang pengerjaannya dipecah per node. Selain itu, GPU yang digunakan memiliki spesifikasi yang gahar, sehingga performa yang dihasilkan sangat memuaskan.