Geodesic
Solution of graph problems by means of the STAR-machine being implemented on GPUs
Prikladnaâ diskretnaâ matematika, no. 3 (2016), pp. 98-115

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

Efficient algorithms have been developed for the solution of many graph problems. The solution is performed with associative parallel processors. At present there are no widely used associative architectures. Nevertheless, the recent development of the GPUs has made it possible to implement the associative parallel models with no significant efficiency loss. It enables to use the associative algorithms in practice. The implementation of the abstract model of the associative parallel data processor is given (the STAR-machine) with the GPUs by means of the CUDA technology. The performance is being analysed as well as the efficiency of the solution of the graph problems. The test case is the Warshall algorithm for finding the transitive closure of a directed graph. A graph with 5000 nodes was processed by the sequential Warshall algorithm for 884,622 s, by the associative parallel version for 64,454 s (speed-up is 13 times) and by the GPU-adopted associative parallel version for 0,372 s (speed-up is 2 378 times).
Keywords: associative parallel processor, vertical data processing, SIMD, GPU, directed graph, adjacency matrix, transitive closure. 
@article{PDM_2016_3_a8,
     author = {T. V. Snytnikova and A. Sh. Nepomniaschaya},
     title = {Solution of graph problems by means of the {STAR-machine} being implemented on {GPUs}},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {98--115},
     publisher = {mathdoc},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2016_3_a8/}
}
TY  - JOUR
AU  - T. V. Snytnikova
AU  - A. Sh. Nepomniaschaya
TI  - Solution of graph problems by means of the STAR-machine being implemented on GPUs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2016
SP  - 98
EP  - 115
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2016_3_a8/
LA  - ru
ID  - PDM_2016_3_a8
ER  - 
%0 Journal Article
%A T. V. Snytnikova
%A A. Sh. Nepomniaschaya
%T Solution of graph problems by means of the STAR-machine being implemented on GPUs
%J Prikladnaâ diskretnaâ matematika
%D 2016
%P 98-115
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2016_3_a8/
%G ru
%F PDM_2016_3_a8
T. V. Snytnikova; A. Sh. Nepomniaschaya. Solution of graph problems by means of the STAR-machine being implemented on GPUs. Prikladnaâ diskretnaâ matematika, no. 3 (2016), pp. 98-115. http://geodesic.mathdoc.fr/item/PDM_2016_3_a8/