Perpustakaan Digital ITB

Komputasi nilai betweenness centrality (BC) untuk pengukuran tingkat kepentingan sebuah node merupakan komputasi yang berat. Seiring dengan perkembangan ukuran serta jenis graf yang ada, dibutuhkan metode yang lebih efisien dalam menghitung nilai BC. Salah satu metode yang dapat digunakan adalah melakukan komputasi algoritma BC secara paralel dengan memaksimalkan utilisasi perangkat komputasi yang dimiliki pada komputer, yaitu CPU dan GPU. Paralelisasi hybrid yang memanfaatkan CPU dan GPU dapatdibantudenganduabuahAPI,yakniOpenMPpadaCPUdanCUDA pada GPU. Dengan meningkatkan utilisasi perangkat, komputasi nilai BC dapat dilakukan dengan lebih optimal. Pada penelitian ini, pembagian beban node yang diberatkan pada CPU akan lebih baik untuk dataset graf yang kecil, sedangkan pembagian beban node yang diberatkan pada GPU akan lebih baik untuk dataset yang besar. Dengan ekstrapolasi nilai pembagi beban, didapatkan bahwa waktu komputasi dapat mengalami 3,96x speedup dalam keadaan terbaik dibandingkan dengan hanya menggunakan CPU ataupun hanya menggunakan GPU. HasilinididapatkanmenggunakansatubuahCPUIntelXeon16core dan GPU NVIDIA GeForce GTX 1080 dengan 2560 CUDA core. Kata kunci: betweenness centrality, CUDA, OpenMP, optimasi algoritma, utilisasi perangkat.