2015 · 51 citations · 27 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureHeterogeneous ComputingParallel ComputingData LocalityData ParallelismGraph AlgorithmsHardware AccelerationHeterogeneous System ArchitectureParallel ArchitecturesGraph ExplorationGraph ProcessingGraph Traversal AlgorithmsHeterogeneous Computing SystemsHeterogeneous Fpga ArchitecturesMemory Access PatternsRedundant ComputationSpatial Locality
Large and sparse small-world graphs are ubiquitous across many scientific domains from bioinformatics to computer science. As these graphs grow in scale, traversal algorithms such as breadth-first search (BFS), fundamental to many graph processing applications and metrics, become more costly to compute. The cause is attributed to poor temporal and spatial locality due to the inherently irregular memory access patterns of these algorithms. A large body of research has targeted accelerating and parallelizing BFS on a variety of computing platforms, including hybrid CPU-GPU approaches for exploiting the small-world property. In the same spirit, we show how a single-die FPGA-CPU heterogeneous device can be used to leverage the varying degree of parallelism in small-world graphs. Additionally, we demonstrate how dense rather than sparse treatment of the BFS frontier vector yields simpler memory access patterns for BFS, trading redundant computation for DRAM bandwidth utilization and faster graph exploration. On a range of synthetic small-world graphs, our hybrid approach performs 7.8× better than software-only and 2× better than accelerator-only implementations. We achieve an average traversal speed of 172 MTEPS (millions of traversed edges per second) on the ZedBoard platform, which is more than twice as effective as the best previously published FPGA BFS implementation in terms of traversals per bandwidth.
27
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Maximizing the spread of influence through a social network
David Kempe, Jon Kleinberg, Éva Tardos · 2003 · 7.3K citations
1990 · 3.1K citations
R-MAT: A Recursive Model for Graph Mining
Deepayan Chakrabarti, Yiping Zhan, Christos Faloutsos · 2004 · 1.3K citations · Full text
Jonathan Bachrach, Huy T. Vo, Brian Richards et al. · 2012 · 905 citations