NUMA aware Scalable Graph Traversal on SGI UV Systems
Breadth first search (BFS) is one of the most fundamental processing algorithms in graph theory. We previously presented a scalable BFS algorithm based on Beamer's direction optimizing algorithm for non uniform memory access (NUMA) based systems, in which the NUMA architecture was carefully considered. This paper presents our new implementation that reduces remote memory access in a top down direction of direction optimizing algorithm. We also discuss numerical results obtained on the SGI UV 2000 and UV 300 systems, which are shared memory supercomputers based on a cache coherent (cc) NUMA architecture that can handle thousands of threads on a single operating system. Our implementation has achieved performance rates of 219 billion edges per second on a Kronecker graph with 234 vertices and 238 edges on a rack of an SGI UV 300 system with 1,152 threads. This result exceeds the fastest entry for a shared memory system on the current Graph500 list presented in November 2015, which includes our previous implementation.
HPGP@HPDC