Hardware/Software Vectorization for Closeness Centrality on Multi-/Many-Core Architectures

A.E. Sarıyuce, E. Saule, K. Kaya, U.V. Çatalyurek
Depts. Biomedical Informatics, Computer Science and Engineering, Electrical and Computer Engineering, The Ohio State University; Dept. Computer Science, University of North Carolina at Charlotte, US


   title={Hardware/Software Vectorization for Closeness Centrality on Multi-/Many-Core Architectures},

   author={Sar{i}y{"u}ce, Ahmet Erdem and Saule, Erik and Kaya, Kamer and Cataly{"u}rek, Umit V}


Download Download (PDF)   View View   Source Source   



Centrality metrics have shown to be highly correlated 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 concurrent breadth-first search operations and significantly increases the performance. We provide a comparison of different vectorization 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 beneficial 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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: