Multithreaded Asynchronous Graph Traversal for In-Memory and Semi-External Memory
- 1 November 2010
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Processing large graphs is becoming increasingly important for many domains such as social networks, bioinformatics, etc. Unfortunately, many algorithms and implementations do not scale with increasing graph sizes. As a result, researchers have attempted to meet the growing data demands using parallel and external memory techniques. We present a novel asynchronous approach to compute Breadth-First-Search (BFS), Single-Source-Shortest-Paths, and Connected Components for large graphs in shared memory. Our highly parallel asynchronous approach hides data latency due to both poor locality and delays in the underlying graph data storage. We present an experimental study applying our technique to both In-Memory and Semi-External Memory graphs utilizing multi-core processors and solid-state memory devices. Our experiments using synthetic and real-world datasets show that our asynchronous approach is able to overcome data latencies and provide significant speedup over alternative approaches. For example, on billion vertex graphs our asynchronous BFS scales up to 14 x on 16-cores.Keywords
This publication has 20 references indexed in Scilit:
- On Computational Models for Flash Memory DevicesLecture Notes in Computer Science, 2009
- Qthreads: An API for programming with millions of lightweight threads2008 IEEE International Symposium on Parallel and Distributed Processing, 2008
- Graph Analysis with High-Performance ComputingComputing in Science & Engineering, 2008
- Characterizing the Performance of Flash Memory Storage Devices and Its Impact on Algorithm DesignPublished by Springer Science and Business Media LLC ,2007
- Software and Algorithms for Graph Queries on Multithreaded ArchitecturesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- The webgraph framework IPublished by Association for Computing Machinery (ACM) ,2004
- R-MAT: A Recursive Model for Graph MiningPublished by Society for Industrial & Applied Mathematics (SIAM) ,2004
- Δ-stepping: a parallelizable shortest path algorithmJournal of Algorithms, 2003
- An O(logn) parallel connectivity algorithmJournal of Algorithms, 1982
- A note on two problems in connexion with graphsNumerische Mathematik, 1959