Vestnik Yuzhno-Ural'skogo Gosudarstvennogo Universiteta. Seriya "Vychislitelnaya Matematika i Informatika"
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



Vestn. YuUrGU. Ser. Vych. Matem. Inform.:
Year:
Volume:
Issue:
Page:
Find






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


Vestnik Yuzhno-Ural'skogo Gosudarstvennogo Universiteta. Seriya "Vychislitelnaya Matematika i Informatika", 2018, Volume 7, Issue 2, Pages 5–21
DOI: https://doi.org/10.14529/cmse180201
(Mi vyurv186)
 

Computational Mathematics

The fastest and energy-efficient breadth-first search algorithm on a single node with various parallel architectures according to Graph500

A. S. Kolganovab

a Lomonosov Moscow State Universisty (GSP-1, Leninskie Gory 1, Moscow, 119991 Russia)
b Keldysh Institute of Applied Mathematics (Miusskaya sq. 4, Moscow, 125047 Russia)
References:
Abstract: The breadth-first search algorithm is one of the basic algorithms for graph traversing and is used in many other algorithms of high-level graph analysis. BFS is characterized with intensive irregular memory accesses and a random data dependency, which greatly complicates its parallelization to all existing architectures. The paper considers the implementation of the BFS algorithm (the core benchmark of the Graph500 rating) for processing large graphs on different architectures: Intel x86, IBM Power8+, Intel KNL and NVidia GPU. Algorithms for implementing breadth-first search will be considered, such as top-down traverse, bottom-up traverse, and a hybrid traverse that includes both top-down and bottom-up traverses. The features of the algorithm implementation on shared memory will be shown, as well as graph transformations (local sorting of graph vertices, global sorting of graph vertices, renumbering of all graph vertexes, compressed representation of graph vertices), which allow achieving the best performance and energy-efficiency in this algorithm among all single-node systems of Graph500 and GreenGraph500 ratings.
Keywords: BFS, CUDA, Power8, KNL, Graph500, parallel graph processing.
Received: 08.04.2018
Bibliographic databases:
Document Type: Article
UDC: 004.021
Language: Russian
Citation: A. S. Kolganov, “The fastest and energy-efficient breadth-first search algorithm on a single node with various parallel architectures according to Graph500”, Vestn. YuUrGU. Ser. Vych. Matem. Inform., 7:2 (2018), 5–21
Citation in format AMSBIB
\Bibitem{Kol18}
\by A.~S.~Kolganov
\paper The fastest and energy-efficient breadth-first search algorithm on a single node with various parallel architectures according to Graph500
\jour Vestn. YuUrGU. Ser. Vych. Matem. Inform.
\yr 2018
\vol 7
\issue 2
\pages 5--21
\mathnet{http://mi.mathnet.ru/vyurv186}
\crossref{https://doi.org/10.14529/cmse180201}
\elib{https://elibrary.ru/item.asp?id=32611426}
Linking options:
  • https://www.mathnet.ru/eng/vyurv186
  • https://www.mathnet.ru/eng/vyurv/v7/i2/p5
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Vestnik Yuzhno-Ural'skogo Gosudarstvennogo Universiteta. Seriya "Vychislitelnaya Matematika i Informatika"
    Statistics & downloads:
    Abstract page:195
    Full-text PDF :84
    References:29
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024