THESIS
2014
xi, 53 pages : illustrations ; 30 cm
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 edge-based versus virtualization-based
parallelization strategies for GPU-based BC computation on unweighted graphs, and propose to
optimize the two strategies to achieve the best performance. Furthermore, we examine the performance
tradeoff of Distance-sensitive/insensitiveGPU-based BC on weighted graphs. 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 NVIDI...[
Read more ]
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 edge-based versus virtualization-based
parallelization strategies for GPU-based BC computation on unweighted graphs, and propose to
optimize the two strategies to achieve the best performance. Furthermore, we examine the performance
tradeoff of Distance-sensitive/insensitiveGPU-based BC on weighted graphs. 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.
Post a Comment