  Betweenness centrality (BC) is an important graph analytical application for
large-scale graphs. While there are many efforts for parallelizing betweenness
centrality algorithms on multi-core CPUs and many-core GPUs, in this work, we
propose a novel fine-grained CPU-GPU hybrid algorithm that partitions a graph
into CPU and GPU partitions, and performs BC computations for the graph on both
the CPU and GPU resources simultaneously with very small number of CPU-GPU
communications. The forward phase in our hybrid BC algorithm leverages the
multi-source property inherent in the BC problem. We also perform a novel
hybrid and asynchronous backward phase that performs minimal CPU-GPU
synchronizations. Evaluations using a large number of graphs with different
characteristics show that our hybrid approach gives 80% improvement in
performance, and 80-90% less CPU-GPU communications than an existing hybrid
algorithm based on the popular Bulk Synchronous Paradigm (BSP) approach.
