This article is cited in 1 scientific paper (total in 1 paper)
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
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).
associative parallel processor, vertical data processing, SIMD, GPU, directed graph, adjacency matrix, transitive closure.
PDF file (1313 kB)
T. V. Snytnikova, A. Sh. Nepomniaschaya, “Solution of graph problems by means of the STAR-machine being implemented on GPUs”, Prikl. Diskr. Mat., 2016, no. 3(33), 98–115
Citation in format AMSBIB
\by T.~V.~Snytnikova, A.~Sh.~Nepomniaschaya
\paper Solution of graph problems by means of the STAR-machine being implemented on GPUs
\jour Prikl. Diskr. Mat.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
A. Sh. Nepomnyaschaya, T. V. Snytnikova, “Assotsiativnyi parallelnyi algoritm dlya dinamicheskoi obrabotki dereva kratchaishikh putei posle dobavleniya novoi dugi”, PDM, 2019, no. 46, 58–71
|Number of views:|