This article is cited in 2 papers

Mathematical Foundations of Informatics and Programming

Solution of graph problems by means of the STAR-machine being implemented on GPUs

T. V. Snytnikova, A. Sh. Nepomniaschaya

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk, Russia

Abstract: 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.

UDC: 591.68

DOI: 10.17223/20710410/33/9

Bibliographic databases:

•