Numerical methods and programming
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Num. Meth. Prog.:
Year:
Volume:
Issue:
Page:
Find






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


Num. Meth. Prog., 2013, Volume 14, Issue 3, Pages 54–62 (Mi vmp152)  

Программирование

Workload balancing in GPU implementation of breadth-first search

M. A. Chernoskutov, D. G. Ermakov

Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg

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

Full text: PDF file (315 kB)
UDC: 004.021
Received: 25.08.2013

Citation: M. A. Chernoskutov, D. G. Ermakov, “Workload balancing in GPU implementation of breadth-first search”, Num. Meth. Prog., 14:3 (2013), 54–62

Citation in format AMSBIB
\Bibitem{CheErm13}
\by M.~A.~Chernoskutov, D.~G.~Ermakov
\paper Workload balancing in GPU implementation of breadth-first search
\jour Num. Meth. Prog.
\yr 2013
\vol 14
\issue 3
\pages 54--62
\mathnet{http://mi.mathnet.ru/vmp152}


Linking options:
  • http://mi.mathnet.ru/eng/vmp152
  • http://mi.mathnet.ru/eng/vmp/v14/i3/p54

    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
  • Numerical methods and programming
    Number of views:
    This page:109
    Full text:51

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