Challenges in Parallel Graph Processing

By Andrew Lumsdaine, D. Gregor, Bruce Hendrickson, J. Berry. Parallel Processing Letters, 2007

442 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/87ee99d4cc4e0601cbb519f6ddbac85772bdc49e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Hardware and Architecture

Citations in the corpus

A Distributed Graph Engine for Web Scale RDF Data (2013, background): “To see this, we must first understand that most graph operations do not have locality [23, 31], and rely exclusively on random accesses.”
PIM-enabled instructions: A low-overhead, locality-aware processing-in-memory architecture (2015, background): “Such a 3D-stacked organization of logic and memory brings multiple opportunities in optimizing main memory subsystems.”
PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs (2019, background): “Graph computation usually exhibits poor data access locality [44, 50] due to irregular traversal of neighboring vertices along edges as well as frequent message exchanges between master and mirror vertices.”
Pregel: a system for large-scale graph processing (2010, methodology): “The Parallel BGL [22, 23] specifies several key generic concepts for defining distributed graphs, provides implementations based on MPI [18], and implements a number of algorithms based on them.”
Scalable SPARQL querying of large RDF graphs (2011, methodology): “Instead, our system adopts an owner-computes model [21] popular in parallel graph computation.”
Trinity: a distributed graph engine on a memory cloud (2013, background): “Despite the diversity of graph applications, graph computation has some unique characteristics [26]: It usually has a high data-access-to-computation ratio, in other words, it is I/O intensive.”
Efficient Parallel Graph Exploration on Multi-Core CPU and GPU (2011, background): “Parallelism has usually failed to alleviate matters, because parallel speedup of these applications is severely limited by the random nature of their memory access patterns, a fundamental property of graph processing algorithms [6].”
Large Vocabulary Speech Recognition on Parallel Architectures (2013, methodology): “In this form, the computation of acoustic probabilities is perfectly suitable for SIMD parallel architectures such as SSE or GPUs, since each distribution can be independently computed, and the results rest upon basic dot product operations.”
X-Stream: edge-centric graph processing using streaming partitions (2013, background): “ing systems challenge: the lack of access locality when traversing edges makes obtaining good performance difficult [39].”
Green-Marl: a DSL for easy and efficient graph analysis (2012, background): “While modern commodity computer systems provide a significant amount of computational power measured in the tera-flops, efficient execution of graph analysis algorithms on large datasets remains difficult on these systems [26].”