Fast Parallel Graph-Search with Splittable and Catenable Frontiers

Umut A. Acar 1, 2 Arthur Charguéraud 3, 4, * Mike Rainey 2
* Auteur correspondant
3 TOCCATA - Certified Programs, Certified Tools, Certified Floating-Point Computations
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : With the increasing processing power of multicore computers, parallel graph search (or graph traversal) using shared memory machines has become increasingly feasible and important. There has been a lot of progress on parallel breadth first search, but this algorithm can be suboptimal in certain applications, such as in reachability, where the level-ordered visit schedule of breadth first search is unnecessary and even sometimes undesirable. The fundamental problems in developing fast parallel graph-search algorithms can be characterized as: (1) the ability to create parallelism as needed, (2) the ability to load balance effectively, and (3) keep overheads low for not just some but all graphs. In this paper, we present a new \emph{frontier} data structure for representing the work in graph algorithms that solve the aforementioned three challenges, enabling highly efficient and scalable parallel executions. As the primary application of our frontier data structure, we present a parallel (pseudo) depth-first-search based algorithm, prove work efficiency bound for the algorithm, and evaluate its effectiveness empirically. As a secondary application, we consider parallel breadth first search. Our empirical evaluation shows that our parallel DFS algorithm significantly improves over prior work and almost uniformly outperforms parallel BFS.
Type de document :
Rapport
[Technical Report] Inria. 2015
Liste complète des métadonnées

https://hal.inria.fr/hal-01089125
Contributeur : Arthur Charguéraud <>
Soumis le : mardi 3 février 2015 - 14:46:22
Dernière modification le : samedi 18 février 2017 - 01:10:15
Document(s) archivé(s) le : mercredi 27 mai 2015 - 16:21:35

Fichier

psearch.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01089125, version 2

Citation

Umut A. Acar, Arthur Charguéraud, Mike Rainey. Fast Parallel Graph-Search with Splittable and Catenable Frontiers. [Technical Report] Inria. 2015. <hal-01089125v2>

Partager

Métriques

Consultations de
la notice

382

Téléchargements du document

360