Pemrosesan Graf Berskala Besar Secara Paralel

Abstract

Masalah pencarian rute terpendek untuk graf statis berskala besar dapat dilakukan dengan menggunakan algoritma yang dijalankan secara paralel. Dua algoritma yang dapat digunakan adalah algoritma Djikstra yang bersifat greedy dan algoritma Bellman-Ford yang menggunakan dynamic programming. Dijkstra lebih sulit diparalelkan namun memiliki waktu eksekusi yang relatif lebih cepat dibandingkan Bellman-Ford yang mudah diparalelkan namun waktu eksekusinya lebih panjang. Optimasi kedua algoritma dilakukan dengan menyimpan data graf dalam bentu Compact Spare Row, dan mendesain algoritma agar membagi data antar prosesor dengan efisien dan meminimalisir komunikasi antar prosesor. Kata Kunci: paralel, shortest path, graf, algoritma Djikstra, algoritma Bellman-Ford, performansi.