Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2915516.2915522 | HPGP@HPDC |
Keywords | DocType | Citations |
Graph algorithm, NUMA-aware, Graph500 benchmark | Conference | 6 |
PageRank | References | Authors |
0.44 | 15 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuichiro Yasui | 1 | 6 | 0.44 |
| Katsuki Fujisawa | 2 | 248 | 28.63 |
| Eng Lim Goh | 3 | 6 | 0.78 |
| John Baron | 4 | 6 | 0.44 |
| Atsushi Sugiura | 5 | 6 | 0.44 |
| Uchiyama, T. | 6 | 28 | 6.18 |