NUMA-aware Scalable Graph Traversal on SGI UV Systems
NUMA-aware Scalable Graph Traversal on SGI UV Systems
复制标题
DOI：
10.1145/2915516.2915522
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Yuichiro Yasui;K. Fujisawa;E. L. Goh;John Baron;A. Sugiura;Takashi Uchiyama
中科院分区：
文献类型：
--
作者：
Yuichiro Yasui;K. Fujisawa;E. L. Goh;John Baron;A. Sugiura;Takashi Uchiyama
宽度优先搜索（BFS）是图论中最基本的处理算法之一。我们以前提出了一个可扩展的BFS算法的基础上Beamer的方向优化算法的非均匀存储器访问（NUMA）为基础的系统，其中NUMA架构进行了仔细考虑。本文提出了我们的新的实现，减少远程内存访问的自顶向下方向的方向优化算法。我们还讨论了SGI UV 2000和UV 300系统，这是共享内存的超级计算机的基础上的高速缓存一致性（CC）-NUMA架构，可以处理数千个线程在一个单一的操作系统上获得的数值结果。我们的实现已经实现了每秒2190亿条边的性能速率的Kronecker图上的234个顶点和238个边的SGI UV 300系统的机架上的1,152个线程。这个结果超过了2015年11月发布的当前Graph 500列表中共享内存系统的最快条目，其中包括我们之前的实现。
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.