Perpustakaan Digital ITB

Algoritma Louvain adalah algoritma yang digunakan untuk pendeteksian komunitas pada graf. Implementasi algoritma Louvain paralel pada GPU memberikan peningkatan kinerja yang baik namun dibatasi oleh memori dan throughput dari satu GPU. Seiring dengan perkembangan ukuran graf yang ada pada dunia nyata, dibutuhkan metode untuk melakukan pemrosesan algoritma Louvain untuk graf yang besar dengan kinerja yang baik, ini dapat dicapai dengan memanfaatkan multi-GPU. Tugas akhir ini bertujuan untuk melakukan implementasi algoritma Louvain paralel pada lingkungan multi-GPU. Implementasi multi-GPU dilakukan dengan cara melakukan adaptasi dari algoritma single-GPU dari penelitian Naim, 2017. Pada implementasi multi-GPU yang dirancang, masing-masing GPU yang digunakan bertanggung jawab untuk pemrosesan satu partisi dari graf utuh, kemudian terdapat sinkronisasi data antar partisi dengan cara komunikasi antar GPU. Implementasi ini memanfaatkan NVIDIA CUDA untuk pemrograman GPU dan pustaka NCCL untuk komunikasi antar GPU. Dibandingkan implementasi single-GPU, implementasi multi-GPU yang dirancang membutuhkan tambahan memori dalam pemrosesannya. Persentase overhead memori ini semakin kecil untuk graf dengan rasio jumlah sisi banding jumlah simpul yang besar. Selain itu, dengan penggunaan 8 GPU, algoritma multi-GPU yang dirancang memberikan speedup sampai 1.2x untuk graf dengan derajat terbesar yang rendah, dan speedup sampai 3.4x untuk graf dengan derajat terbesar yang tinggi dengan derajat simpul-simpul yang bervariasi.