Geodesic
Workload balancing in GPU implementation of breadth-first search
Numerical methods and programming, Tome 14 (2013) no. 3, pp. 54-62.

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

Parallel processing of unstructured data пшмут in a graph-like form can be a severe computational challenge because of significant overheads caused by the irregular nature of graph algorithms and the hardware latency of intensive data access. The GPU implementation of the load balancing method that allows one to dramatically improve the parallel breadth-first search algorithm compared to its sequential analog on CPU is considered. This work was partially supported by the Russian Foundation for Basic Research (project 14-07-00435) and by UB RAS (projects 12-P-1-1029 and RCP-13-P18). Numerical experiments were performed using the “Uran” supercomputer installed at IMM UB RAS. This paper was recommended for publication by the Program Committee of the International Scientific Conference “Scientific service in the Internet: all aspects of parallelism” (http://agora.guru.ru/abrau2013).
Keywords: breadth-first search; parallel algorithm; graphics processing units. 
@article{VMP_2013_14_3_a20,
     author = {M. A. Chernoskutov and D. G. Ermakov},
     title = {Workload balancing in {GPU} implementation of breadth-first search},
     journal = {Numerical methods and programming},
     pages = {54--62},
     publisher = {mathdoc},
     volume = {14},
     number = {3},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMP_2013_14_3_a20/}
}
TY  - JOUR
AU  - M. A. Chernoskutov
AU  - D. G. Ermakov
TI  - Workload balancing in GPU implementation of breadth-first search
JO  - Numerical methods and programming
PY  - 2013
SP  - 54
EP  - 62
VL  - 14
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMP_2013_14_3_a20/
LA  - ru
ID  - VMP_2013_14_3_a20
ER  - 
%0 Journal Article
%A M. A. Chernoskutov
%A D. G. Ermakov
%T Workload balancing in GPU implementation of breadth-first search
%J Numerical methods and programming
%D 2013
%P 54-62
%V 14
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMP_2013_14_3_a20/
%G ru
%F VMP_2013_14_3_a20
M. A. Chernoskutov; D. G. Ermakov. Workload balancing in GPU implementation of breadth-first search. Numerical methods and programming, Tome 14 (2013) no. 3, pp. 54-62. http://geodesic.mathdoc.fr/item/VMP_2013_14_3_a20/