Accelerating Betweenness Centrality Computation on Heterogeneous Processors

MPhil Thesis Defence


Title: "Accelerating Betweenness Centrality Computation on Heterogeneous 
Processors"

By

Miss Yan ZHAO


Abstract

The betweenness centrality (BC) measure of nodes in a graph is widely used 
in graph analysis. As both multicore CPUs and manycore GPUs are becoming 
greatly competitive in their parallel computation power, we propose to 
utilize these heterogeneous processors on a single machine to accelerate 
the BC computation. Specifically, we study vertex-based versus edge-based 
parallelization strategies for GPU-based BC computation on unweighted 
graphs, and propose to combine the two strategies to achieve the best 
performance. Furthermore, we examine the performance tradeoff with and 
without sorting in computing BC of weighted graphs on the GPU. We have 
implemented representative BC algorithms on the CPU and the GPU, and 
evaluated them on a server with two Intel E5-2650 CPUs and four NVIDIA 
M2090 GPUs. Our results show that, with suitable parallelization and 
optimization, BC computation can be scaled well on the set of 
heterogeneous processors.


Date:			Thursday, 22 May 2014

Time:			9:00am - 11:00am

Venue:			Room 4480
 			Lifts 25/26

Committee Members:	Dr. Qiong Luo (Supervisor)
 			Dr. Ke Yi (Chairperson)
 			Dr. Raymond Wong


**** ALL are Welcome ****