Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikl. Diskr. Mat., 2016, Number 3(33), Pages 98–115 (Mi pdm557)  

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

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.

DOI: https://doi.org/10.17223/20710410/33/9

Full text: PDF file (1313 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 591.68

Citation: 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
\Bibitem{SnyNep16}
\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.
\yr 2016
\issue 3(33)
\pages 98--115
\mathnet{http://mi.mathnet.ru/pdm557}
\crossref{https://doi.org/10.17223/20710410/33/9}


Linking options:
  • http://mi.mathnet.ru/eng/pdm557
  • http://mi.mathnet.ru/eng/pdm/y2016/i3/p98

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. 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  mathnet  crossref
  • Прикладная дискретная математика
    Number of views:
    This page:108
    Full text:171
    References:14

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021