X-Stream: Edge-centric Graph Processing using Streaming Partitions
Intervenant(s) : Willy Zwaenepoel (Ecole Polytechnique Fédérale de Lausanne)
X-Stream is a system for processing both in-memory and out-of-core graphs on a single shared-memory machine. While retaining the scatter-gather programming model with state stored in the vertices, X-Stream is novel in (i) using an edge-centric rather than a vertex-centric implementation of this model, and (ii) streaming completely unordered edge lists rather than performing random access. This design is motivated by the fact that sequential bandwidth for all storage media (main memory, magnetic disk and SSD) is significantly larger than random access bandwidth. We also detail how a sequential access model exposes parallelism in both memory access as well as I/O. Our implementation competes favorably with existing systems, and its performance and scalability is bounded purely by the amount of streaming bandwidth and storage available. For example with synthetic scale-free graphs, X-Stream identifies weakly connected components in graphs with upto 128 million edges in memory within 23 seconds, with upto 2 billion edges from SSD in 26 minutes, and with upto 32 billion edges from magnetic disk in under 23 hours.
Marc.Shapiro (at) nulllip6.fr