Maciej Besta, F. Marending, Edgar Solomonik, Torsten Hoefler:
SlimSell: A Vectorized Graph Representation for Breadth-First Search
(In Proceedings of the 31st IEEE International Parallel & Distributed Processing Symposium (IPDPS'17), presented in Orlando, FL, USA, IEEE, May 2017)
Abstract
Vectorization and GPUs will profoundly change
graph processing. Traditional graph algorithms tuned for
32- or 64-bit based memory accesses will be inefficient on
architectures with 512-bit wide (or larger) instruction units
that are already present in the Intel Knights Landing (KNL)
manycore CPU. Anticipating this shift, we propose SlimSell: a
vectorizable graph representation to accelerate Breadth-First
Search (BFS) based on sparse-matrix dense-vector (SpMV)
products. SlimSell extends and combines the state-of-the-art
SIMD-friendly Sell-C-σ matrix storage format with tropical,
real, boolean, and sel-max semiring operations. The resulting
design reduces the necessary storage (by up to 50%) and thus
pressure on the memory subsystem. We augment SlimSell with
the SlimWork and SlimChunk schemes that reduce the amount
of work and improve load balance, further accelerating BFS.
We evaluate all the schemes on Intel Haswell multicore CPUs,
the state-of-the-art Intel Xeon Phi KNL manycore CPUs, and
NVIDIA Tesla GPUs. Our experiments indicate which semiring
offers highest speedups for BFS and illustrate that SlimSell
accelerates a tuned Graph500 BFS code by up to 33%. This
work shows that vectorization can secure high-performance in
BFS based on SpMV products; the proposed principles and
designs can be extended to other graph algorithms.
Documents
download article: download slides:
Recorded talk (best effort)
BibTeX
@inproceedings{slimsell, author={Maciej Besta and F. Marending and Edgar Solomonik and Torsten Hoefler}, title={{SlimSell: A Vectorized Graph Representation for Breadth-First Search}}, year={2017}, month={May}, booktitle={Proceedings of the 31st IEEE International Parallel \& Distributed Processing Symposium (IPDPS'17)}, location={Orlando, FL, USA}, publisher={IEEE}, source={http://www.unixer.de/~htor/publications/}, }
