Geodesic
Performance evaluation of breadth-first search on Intel Xeon Phi
Numerical methods and programming, Tome 15 (2014) no. 1, pp. 49-58.

Voir la notice de l'article provenant de la source Math-Net.Ru

Breadth-First Search (BFS) is one of the most important kernels in graph computing. It is the main kernel of the Graph500 rating that evaluates performance of large supercomputers and multiprocessor nodes in terms of traversed edges per second (TEPS). In this paper we present the results of BFS performance evaluation on a recently released high-performance Intel Xeon Phi coprocessor. We examine the previously proposed Queue-based and Read-based approaches to BFS implementation. We also apply several optimization techniques, such as manual loop unrolling and prefetching, that significantly improve performance on Intel Xeon Phi. On a representative graph set, Intel Xeon Phi 7120P demonstrates 78% maximum and 37% average speedup as compared to the Intel Xeon E5-2660 processor. We achieve 4366 MTEPS on Intel Xeon Phi 7120P for a graph with scale 25, and have 89th place on the November 2013 Graph500 list. This is the fourth place among research teams in the class of single node x86-based systems. The authors would like to thank the Svet Computers company for the provided IntellectDigital SciPhi 470 desktop supercomputer with Intel Xeon Phi 7120P coprocessor.
Mots-clés : BFS
Keywords: Intel Xeon Phi, Breadth-First Search, graph algorithms. 
@article{VMP_2014_15_1_a4,
     author = {E. A. Golovina and A. S. Semenov and A. S. Frolov},
     title = {Performance evaluation of breadth-first search on {Intel} {Xeon} {Phi}},
     journal = {Numerical methods and programming},
     pages = {49--58},
     publisher = {mathdoc},
     volume = {15},
     number = {1},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMP_2014_15_1_a4/}
}
TY  - JOUR
AU  - E. A. Golovina
AU  - A. S. Semenov
AU  - A. S. Frolov
TI  - Performance evaluation of breadth-first search on Intel Xeon Phi
JO  - Numerical methods and programming
PY  - 2014
SP  - 49
EP  - 58
VL  - 15
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMP_2014_15_1_a4/
LA  - ru
ID  - VMP_2014_15_1_a4
ER  - 
%0 Journal Article
%A E. A. Golovina
%A A. S. Semenov
%A A. S. Frolov
%T Performance evaluation of breadth-first search on Intel Xeon Phi
%J Numerical methods and programming
%D 2014
%P 49-58
%V 15
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMP_2014_15_1_a4/
%G ru
%F VMP_2014_15_1_a4
E. A. Golovina; A. S. Semenov; A. S. Frolov. Performance evaluation of breadth-first search on Intel Xeon Phi. Numerical methods and programming, Tome 15 (2014) no. 1, pp. 49-58. http://geodesic.mathdoc.fr/item/VMP_2014_15_1_a4/