A lightweight infrastructure for graph analytics

By Donald Nguyen, Andrew Lenharth, Keshav Pingali. Symposium on Operating Systems Principles, 2013

608 citations recorded by the source corpus.

Several domain-specific languages (DSLs) for parallel graph analytics have been proposed recently. In this paper, we argue that existing DSLs can be implemented on top of a general-purpose infrastructure that (i) supports very fine-grain tasks, (ii) implements autonomous, speculative execution of these tasks, and (iii) allows application-specific control of task scheduling policies. To support this claim, we describe such an implementation called the Galois system. We demonstrate the capabilities of this infrastructure in three ways. First, we implement more sophisticated algorithms for some of the graph analytics problems tackled by previous DSLs and show that end-to-end performance can be improved by orders of magnitude even on power-law graphs, thanks to the better algorithms facilitated by a more general programming model. Second, we show that, even when an algorithm can be expressed in existing DSLs, the implementation of that algorithm in the more general system can be orders of magnitude faster when the input graphs are road networks and similar graphs with high diameter, thanks to more sophisticated scheduling. Third, we implement the APIs of three existing graph DSLs on top of the common infrastructure in a few hundred lines of code and show that even for power-law graphs, the performance of the resulting implementations often exceeds that of the original DSL systems, thanks to the lightweight infrastructure.

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

View Paper: https://www.semanticscholar.org/paper/3d985a05e4a49be71d497e7a2ff3fcbeb74c4bc8

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

Navigating the maze of graph analytics frameworks using massive graph datasets (2014, background): “[24] looks at a variety of vertex programming frameworks but at a lower level (Bulk synchronous vs autonomous, scheduling policies etc.”
PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs (2019, methodology): “One machine of our six-node cluster (24 cores and 64GB DRAM) is used to run in-memory (Polymer [92] and Galois [53]) and out-of-core (X-Stream 22 [57] and GraphChi [39]) systems for both in-memory and out-of-core graphs using PageRank with 10 iterations.”
GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning (2015, methodology): “Galois [18] provides a machine-topology-aware scheduler, a priority scheduler and a library of scalable data structures, and uses a CSR format of graphs in its out-of-core implementation.”
The RAMCloud Storage System (2015, methodology): “…will have two overall characteristics: (a) they will access large amounts of data in an irregular fashion (applications such as graph processing [Nguyen et al. 2013; Gonzalez et al. 2012] or large-scale machine learning could be candidates), and (b) they will operate at interactive timescales…”
The GAP Benchmark Suite (2015, methodology): “To create our benchmark, we learned from the best practices of the community, and we co-developed this benchmark with our graph workload characterization [5].”
Gunrock: a high-performance graph processing library on the GPU (2015, background): “…graph libraries [20]; PowerGraph, a popular distributed graph library [12]; and Ligra, one of the highest-performing multi-core shared-memory graph libraries [28] (Galois [23, 25] would have also been a good choice here; Galois and Ligra represent the best-performing CPU implementations).”
EmptyHeaded: A Relational Engine for Graph Processing (2015, methodology): “For example, optimized sparse matrix layouts are often used to represent the edgelist relation [36].”
Scalability! But at what COST? (2015, background): “Both Galois [17] and Ligra [23] are shared-memory systems that significantly out-perform their distributed peers when run on single machines.”
Gemini: A Computation-Centric Distributed Graph Processing System (2016, unknown): “While these systems are able to take advantage of multiple machines to achieve scalability, their performance is often unsatisfactory compared with state-of-the-art shared-memory counterparts [36, 47, 49, 57].”
GraphMat: High performance graph analytics made productive (2015, background): “…recent work [28] that has compared different graph frameworks including Giraph [1] and GraphLab [5, 22] which are two popular vertex programming models; CombBLAS [3, 11], a matrix programming model; Socialite [29], a functional programming model; and Galois [26, 4, 25], a task-based abstraction.”
Handbook of Big Data (2016, background): “These lenses have a simple history mechanism in that the consecutive x – y variable names are collected in a list that can be traversed and edited: Hit • PgUp to take one step back in the history.”