@inproceedings{8fe07661cbf04fc9b831fff8684d84ce,
title = "SlimSell: A Vectorizable Graph Representation for Breadth-First Search",
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.",
keywords = "BFS, Graph Algorithms, Graph Processing, Graph Representations, Graph Storage, Vectorization",
author = "MacIej Besta and Florian Marending and Edgar Solomonik and Torsten Hoefler",
note = "Funding Information: Acknowledgements: We thank Hussein Harake, Colin McMurtrie, and the whole CSCS team granting access to the Greina, Piz Dora, and Daint machines, and for their excellent technical support. We thank Moritz Kreutzer and the anonymous reviewers for their insightful comments. Maciej Besta is supported by Google European Doctoral Fellowship. Edgar Solomonik conducted part of this work while supported by an ETH Postdoctoral Fellowship. Publisher Copyright: {\textcopyright} 2017 IEEE.; 31st IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017 ; Conference date: 29-05-2017 Through 02-06-2017",
year = "2017",
month = jun,
day = "30",
doi = "10.1109/IPDPS.2017.93",
language = "English (US)",
series = "Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium, IPDPS 2017",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "32--41",
booktitle = "Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium, IPDPS 2017",
address = "United States",
}