We present the most recent release of our parallel implementation of the BFS and BC algorithms for the study of large scale graphs. Although our reference platform is a high-end cluster of new generation NVIDIA GPUs and some of our optimizations are CUDA specific, most of our ideas can be applied to other platforms offering multiple levels of parallelism. We exploit multi level parallel processing through a hybrid programming paradigm that combines highly tuned CUDA kernels, for the computations performed by each node, and explicit data exchange through the Message Passing Interface (MPI), for the communications among nodes. The results of the numerical experiments show that the performance of our code is comparable or better with respect to other state-of-the-art solutions. For the BFS, for instance, we reach a peak performance of 200 Giga Teps on a single GPU and 5.5 Terateps on 1024 Pascal GPUs. We release our source codes both for reproducing the results and for facilitating their usage as a building block for the implementation of other algorithms.

Multilevel parallelism for the exploration of large-scale graphs / Bernaschi, M.; Bisson, M.; Mastrostefano, E.; Vella, F.. - In: IEEE TRANSACTIONS ON MULTI-SCALE COMPUTING SYSTEMS. - ISSN 2332-7766. - ELETTRONICO. - 4:3(2018), pp. 204-216. [10.1109/TMSCS.2018.2797195]

Multilevel parallelism for the exploration of large-scale graphs

Vella F.
2018-01-01

Abstract

We present the most recent release of our parallel implementation of the BFS and BC algorithms for the study of large scale graphs. Although our reference platform is a high-end cluster of new generation NVIDIA GPUs and some of our optimizations are CUDA specific, most of our ideas can be applied to other platforms offering multiple levels of parallelism. We exploit multi level parallel processing through a hybrid programming paradigm that combines highly tuned CUDA kernels, for the computations performed by each node, and explicit data exchange through the Message Passing Interface (MPI), for the communications among nodes. The results of the numerical experiments show that the performance of our code is comparable or better with respect to other state-of-the-art solutions. For the BFS, for instance, we reach a peak performance of 200 Giga Teps on a single GPU and 5.5 Terateps on 1024 Pascal GPUs. We release our source codes both for reproducing the results and for facilitating their usage as a building block for the implementation of other algorithms.
2018
3
Bernaschi, M.; Bisson, M.; Mastrostefano, E.; Vella, F.
Multilevel parallelism for the exploration of large-scale graphs / Bernaschi, M.; Bisson, M.; Mastrostefano, E.; Vella, F.. - In: IEEE TRANSACTIONS ON MULTI-SCALE COMPUTING SYSTEMS. - ISSN 2332-7766. - ELETTRONICO. - 4:3(2018), pp. 204-216. [10.1109/TMSCS.2018.2797195]
File in questo prodotto:
File Dimensione Formato  
Multilevel_Parallelism_for_the_Exploration_of_Large-Scale_Graphs.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.25 MB
Formato Adobe PDF
1.25 MB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/332870
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact