Improving Betweenness Centrality Algorithm Performance with Hybrid Parallelism using OpenMP and CUDA

Calculating betweenness centrality in a graph to measure the significance of a node is considered computationally heavy. The expansion rate of today’s graphs in sizeandpropertypushesanalyststofind a more efficient way to calculate BC. One of the methods that can be widel...

Full description

Saved in:
Bibliographic Details
Main Author: Yustalim, Wenny
Format: Final Project
Language:Indonesia
Online Access:https://digilib.itb.ac.id/gdl/view/43708
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Institut Teknologi Bandung
Language: Indonesia
Description
Summary:Calculating betweenness centrality in a graph to measure the significance of a node is considered computationally heavy. The expansion rate of today’s graphs in sizeandpropertypushesanalyststofind a more efficient way to calculate BC. One of the methods that can be widely used is calculating BC in parallel while maximizing the hardware utilization––namely CPU and GPU. Hybrid parallelization that exploits CPU and GPU can be implemented using APIs from OpenMP and CUDA respectively. Increasing hardware utilizationmaydecreasetheexecutiontimeofcalculatingBCcomparedtojustusing solely CPU or solely GPU. In this paper, the load is balanced between the two computing power. It is concluded that large datasets would perform better when heavier load is given to GPU, and vice versa. This load balancingnumberiscalledathresholdthatcanbeextrapolatedtoachievea3.96xspeedupfrom using only CPU or GPU in the best condition.ThisresultisobtainedusingoneIntelXeon16-coresCPU and NVIDIA GeForce GTX 1080 GPU with 2560 CUDA cores.