R. Pearce, M. Gokhale, and N.M. Amato,
"Multithreaded Asynchronous Graph Traversal for In-Memory and Semi-External Memory,"
ACM/IEEE Supercomputing Conference 2010 (SC10)
, November 2010.
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 14x on 16-cores. © 2010 IEEE.
Associated Project(s):SHIELD (Smuggled HEU Interdiction through Enhanced anaLysis and Detection): A Framework for Developing Novel Detection Systems Focused on Interdicting Shielded HEU