Breadth-First Search on Heterogeneous Platforms: A Case of Study on Social Networks

Luis Remis, Maria Jesus Garzaran, Rafael Asenjo, Angeles Navarro

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Breadth-First Search (BFS) is the core of many graph analysis algorithms and it is used in many problems, such as social network, computer network analysis, and data organization. BFS is an iterative algorithm that due to its irregular behavior is quite challenging to parallelize. Several approaches implement efficient algorithms for BFS for multicore architectures and for Graphics Processors, but it is still an open problem how to distribute the work among the main cores and the accelerators. In this paper, we assess several approaches to perform BFS on different heterogenous architectures (highend and embedded mobile processors composed of a multi-core CPU and an integrated GPU) with a focus on social network graphs. In particular, we propose two heterogenous approaches to exploit both devices. The first one, called Selective, selects on which device to execute each iteration. It is based on a previous approach, but we have adapted it to take advantage of the features of social network graphs (fewer iterations but more unbalanced). The second approach, referred as Concurrent, allows the execution of specific iterations concurrently in both devices. Our heterogenous implementations can be up to 1.56x faster and 1.32x more energy efficient with respect to the best of only-CPU or only-GPU baselines. We have also found that for a highly memory bound problem like BFS, the CPU-GPU collaborative execution is limited by the shared-memory bus bandwidth.

Original languageEnglish (US)
Title of host publicationProceedings - 28th IEEE International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2016
PublisherIEEE Computer Society
Pages118-125
Number of pages8
ISBN (Electronic)9781509061082
DOIs
StatePublished - Dec 16 2016
Event28th IEEE International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2016 - Los Angeles, United States
Duration: Oct 26 2016Oct 28 2016

Publication series

NameProceedings - Symposium on Computer Architecture and High Performance Computing
ISSN (Print)1550-6533

Other

Other28th IEEE International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2016
CountryUnited States
CityLos Angeles
Period10/26/1610/28/16

Keywords

  • Graphs
  • bfs
  • breadth first search
  • gpu
  • heterogeneous
  • social networks

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'Breadth-First Search on Heterogeneous Platforms: A Case of Study on Social Networks'. Together they form a unique fingerprint.

  • Cite this

    Remis, L., Garzaran, M. J., Asenjo, R., & Navarro, A. (2016). Breadth-First Search on Heterogeneous Platforms: A Case of Study on Social Networks. In Proceedings - 28th IEEE International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2016 (pp. 118-125). [7789331] (Proceedings - Symposium on Computer Architecture and High Performance Computing). IEEE Computer Society. https://doi.org/10.1109/SBAC-PAD.2016.23