Hardware/software vectorization for closeness centrality on multi-/many-core architectures

Abstract—Centrality metrics have shown to be highly corre-lated with the importance and loads of the nodes in a network. Given the scale of today’s social networks, it is essential to use efficient algorithms and high performance computing techniques for their fast computation. In this work, we exploit hardware and software vectorization in combination with fine-grain parallelization to compute the closeness centrality values. The proposed vectorization approach enables us to do concur-rent breadth-first search operations and significantly increases the performance. We provide a comparison of different vector-ization schemes and experimentally evaluate our contributions with respect to the existing parallel CPU-based solutions on cutting-edge hardware. Our implementations achieve to be 11 times faster than the state-of-the-art implementation for a graph with 234 million edges. The proposed techniques are ben-eficial to show how the vectorization can be efficiently utilized to execute other graph kernels that require multiple traversals over a large-scale network on cutting-edge architectures. Keywords-Centrality, closeness centrality, vectorization, breadth-first search, Intel Xeon Phi. I