Algorithm-Level Optimizations for Scalable Parallel Graph Processing
Abstract
Efficiently processing large graphs is challenging, since parallel graph algorithms suffer from
poor scalability and performance due to many factors, including heavy communication and load-imbalance.
Furthermore, it is difficult to express graph algorithms, as users need to understand
and effectively utilize the underlying execution of the algorithm on the distributed system. The
performance of graph algorithms depends not only on the characteristics of the system (such as
latency, available RAM, etc.), but also on the characteristics of the input graph (small-world scalefree,
mesh, long-diameter, etc.), and characteristics of the algorithm (sparse computation vs. dense
communication). The best execution strategy, therefore, often heavily depends on the combination
of input graph, system and algorithm.
Fine-grained expression exposes maximum parallelism in the algorithm and allows the user to
concentrate on a single vertex, making it easier to express parallel graph algorithms. However,
this often loses information about the machine, making it difficult to extract performance and
scalability from fine-grained algorithms.
To address these issues, we present a model for expressing parallel graph algorithms using a
fine-grained expression. Our model decouples the algorithm-writer from the underlying details
of the system, graph, and execution and tuning of the algorithm. We also present various graph
paradigms that optimize the execution of graph algorithms for various types of input graphs and
systems. We show our model is general enough to allow graph algorithms to use the various graph
paradigms for the best/fastest execution, and demonstrate good performance and scalability for
various different graphs, algorithms, and systems to 100,000+ cores.
Subject
Graph ProcessingDistributed Systems
Graph Algorithms
High Performance Computing
Parallel Graph Algorithms
Scalable Graph Algorithms
Distributed Graph Processing Systems
Large-scale Graph Processing
Citation
Harshvardhan (2018). Algorithm-Level Optimizations for Scalable Parallel Graph Processing. Doctoral dissertation, Texas A & M University. Available electronically from https : / /hdl .handle .net /1969 .1 /173407.
Related items
Showing items related by title, author, creator and subject.
-
Weyand, Tracy Kathleen (2014-07-07)In this dissertation, we analyze characteristics of eigenfunctions of the Schrödinger operator on graphs. In particular, we are interested in the zeros of the eigenfunctions and their relation to the spectrum of the magnetic ...
-
Pearce, Roger Allan (2013-12-05)Efficiently storing and processing massive graph data sets is a challenging problem as researchers seek to leverage “Big Data” to answer next-generation scientific questions. New techniques are required to process large ...
-
Xia, Liangzhen (2017-12-09)My thesis would focus on analyzing the estimation of node similarity in streaming bipartite graph. As an important model in many applications of data mining, the bipartite graph represents the relationships between two ...