Data Structures and Algorithms for Robust and Fast Parallel Graph Search

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 : Graph traversal based on algorithms such as depth-first search and breadth-first-search is a critical part of many applications. With the advent of multicore computers and the ability to furnish them with large shared random-access-memory, it has become possible to process large-scale graphs in parallel. For such parallel algorithms to be effective in general, they should be highly parallel, exposing as much parallelism as possible and remain work-efficient with respect to optimal serial graph-traversal algorithms. Since the topology of graphs can vary dramatically, simultaneously achieving these two properties is challenging. In this paper, we present two highly parallel and work-efficient algorithms for performing graph traversals on directed (and undirected) graphs. Our first algorithm is a Parallel Breadth-First Search (PBFS) that improves over the state of the art by exposing more parallelism without detrimentally effecting work efficiency. Our second algorithm is a Parallel Depth-First Search (PDFS) algorithm that improves over the state of the art by guaranteeing work efficiency while remaining highly parallel. Both of our algorithms take advantage of our novel frontier data structure that supports very efficiently several key operations on the set of outgoing edges of visited vertices (the frontier), including push, iteration, split in half, and merge. Also based on this data structure, we present techniques for controlling granularity for improved practical efficiency. We implement our algorithms and evaluate them carefully by considering both synthetic and real-world graphs and by comparing with the state of the art. The experiments show that, for the graphs considered, our algorithms remain robust, outperforming the state of the art except in a few cases, and dramatically outperforming them in certain cases.
Type de document :
Rapport
[Technical Report] Inria. 2014
Liste complète des métadonnées

https://hal.inria.fr/hal-01089125
Contributeur : Arthur Charguéraud <>
Soumis le : lundi 1 décembre 2014 - 11:10:45
Dernière modification le : jeudi 11 janvier 2018 - 06:25:27
Document(s) archivé(s) le : lundi 2 mars 2015 - 13:29:04

Fichier

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

Identifiants

  • HAL Id : hal-01089125, version 1

Citation

Umut A. Acar, Arthur Charguéraud, Mike Rainey. Data Structures and Algorithms for Robust and Fast Parallel Graph Search. [Technical Report] Inria. 2014. 〈hal-01089125v1〉

Partager

Métriques

Consultations de la notice

78

Téléchargements de fichiers

44