Source-linked AI summary
GraphMat: High performance graph analytics made productive
Narayanan Sundaram, Nadathur Rajagopalan Satish, Md Mostofa Ali Patwary, Subramanya R Dulloor, Satya Gautam Vadlamudi, Dipankar Das, Pradeep Dubey
TL;DR
Large-scale graph analytics needs frameworks that improve performance without sacrificing programming productivity. GraphMat maps vertex programs onto optimized sparse matrix operations, achieving performance improvements over competing frameworks while remaining close to native hand-optimized code. Its sparse-matrix basis also supports multicore scaling and connections to array-processing systems.
Problem
Graph analytics needs productive frameworks, but vertex programming lacks a strong mathematical model for analyzing and optimizing backend performance, while matrix models are harder to program.
Method
GraphMat uses a vertex-programming frontend mapped to a generalized sparse matrix vector multiplication backend.
Results
GraphMat improves performance by 1.2-7X over GraphLab, CombBLAS, and Galois and averages about 1.2X off native, hand-optimized code across graph algorithms.
Takeaways & Limitations
GraphMat provides vertex-programming users an easier path to higher graph-analytics performance and offers a basis for scaling across platforms.
Takeaways & Limitations
Performance-test results may vary with the specific processors, systems, software, operations, and functions used, with cited optimizations intended for Intel microprocessors.
Abstract
from arXiv · showhide
Given the growing importance of large-scale graph analytics, there is a need to improve the performance of graph analysis frameworks without compromising on productivity. GraphMat is our solution to bridge this gap between a user-friendly graph analytics framework and native, hand-optimized code. GraphMat functions by taking vertex programs and mapping them to high performance sparse matrix operations in the backend. We get the productivity benefits of a vertex programming framework without sacrificing performance. GraphMat is in C++, and we have been able to write a diverse set of graph algorithms in this framework with the same effort compared to other vertex programming frameworks. GraphMat performs 1.2-7X faster than high performance frameworks such as GraphLab, CombBLAS and Galois. It achieves better multicore scalability (13-15X on 24 cores) than other frameworks and is 1.2X off native, hand-optimized code on a variety of different graph algorithms. Since GraphMat performance depends mainly on a few scalable and well-understood sparse matrix operations, GraphMatcan naturally benefit from the trend of increasing parallelism on future hardware.
1. INTRODUCTION
GraphMat bridges graph-programming productivity and high performance by mapping vertex programs to an optimized sparse-matrix backend. It reports performance near native code, faster execution than competing frameworks, and strong multicore scalability.
- The framework addresses the need for graph-analysis systems that handle larger graphs and more complex queries with minimal programming effort.
- GraphMat maps vertex programs to generalized sparse matrix vector multiplication, combining a familiar frontend with a high-performance matrix backend.The abstraction avoids exposing users to underlying matrix primitives while retaining a vertex-programming workflow.
- 1.2X off native, hand-coded optimized code across varied graph algorithms, while running 5-7X faster than GraphLab and CombBLAS and 1.2X faster than Galois on one node.
- 13-15X speedup over a single-threaded implementation on 24 cores, compared with 2-12X scaling for GraphLab, CombBLAS, and Galois.
- GraphMat supports productivity for users and developers by preserving vertex programming and reducing backend optimization to well-studied sparse matrix algebra.
- GraphMat can connect graph analytics with array-processing systems by treating graphs as special cases of sparse matrices.The passage also identifies transactional support, concurrency control, and fault tolerance as capabilities offered by such systems.
2. MOTIVATION AND RELATED WORK
Graph analytics frameworks trade off vertex-programming ease against the mathematical structure and optimization potential of matrix models. GraphMat adopts a vertex frontend with a generalized sparse-matrix backend to pursue productivity and HPC-like performance.
- Vertex programming is productive and popular, whereas matrix models provide a stronger mathematical foundation for reasoning and optimization but are harder to program.
- Some computations, including triangle counting, are difficult to express efficiently as pure matrix operations, causing long runtimes and increased memory consumption.
- GraphMat targets vertex-programming productivity with performance informed by optimized sparse matrix-vector multiplication routines from high-performance computing.
- GraphMat’s sparse-matrix perspective offers a route for connecting graph stores with array databases and leveraging sparse-array database developments.
- PEGASUS uses MapReduce and faces I/O bottlenecks, while GreenMarl improves productivity and performance at the cost of learning a new language.
- The paper compares GraphMat with GraphLab, CombBLAS, and Galois across high-performing vertex, matrix, and task-based programming models.
3. ALGORITHMS
The paper evaluates five graph algorithms spanning machine learning, traversal, and statistics, with varied data, communication, and iteration patterns.
- Algorithm selection: Five algorithms cover machine learning, graph traversal, and graph statistics across diverse functionality and execution characteristics.The selection varies in traversal versus statistics, data per vertex, communication, and iterative versus non-iterative behavior.
- Page Rank: Page Rank iteratively ranks web pages using the probability that a hyperlink random walk ends at each page.Vertex ranks are repeatedly updated, with r denoting the probability of random surfing.
- Breadth First Search: Breadth First Search explores connected vertices from a root and assigns each vertex its minimum edge distance from that root.A vertex becomes active in the next iteration when its distance changes from infinity to t+1.
- Collaborative Filtering: Collaborative filtering estimates missing user-item ratings by factorizing a rating matrix into two low-dimensional dense matrices.The factors represent latent user and item features, and optimization can use Gradient Descent or Stochastic Gradient Descent.
- Triangle Counting: Triangle Counting computes the number of triangles by sharing neighbor lists and intersecting each vertex’s list with received neighbor lists.For undirected graphs, each triangle contributes three times to the intersection count.
- Single Source Shortest Path: Single Source Shortest Path computes shortest paths from one source to all vertices in a weighted directed graph.GraphMat uses a Bellman-Ford variation that updates vertices adjacent to those whose distances changed previously.
4. GRAPHMAT
GraphMat maps vertex programs onto generalized sparse matrix operations, preserving vertex-program productivity while using a high-performance matrix backend. Its iterative framework generates messages, performs generalized SPMV, applies updates, and exploits sparse data structures and multicore parallelism.
- Mapping Vertex Programs: GraphMat converts vertex programs into generalized sparse matrix-vector multiplication over a graph’s adjacency matrix or transpose.Edge traversals from active vertices become sparse matrix-sparse vector multiplication routines.
- Programming model: SEND MESSAGE, PROCESS MESSAGE, REDUCE, and APPLY define GraphMat programs and their vertex, edge, message, and state-update behavior.PROCESS MESSAGE can use the incoming message, edge data, and destination vertex properties.
- Generalized SPMV: In single-source shortest path, PROCESS MESSAGE adds edge length to the current distance and REDUCE selects the minimum.Together, these operations implement the sparse matrix-sparse vector multiplication for each iteration.
- Generalized SPMV: Generalized SPMV replaces traditional multiply-and-add with user-defined PROCESS MESSAGE and REDUCE operations, enabling multiple graph algorithms.The implementation traverses nonzero columns of G^T, processes columns present in the sparse input vector, and accumulates results in y.
- Productivity: GraphMat’s vertex abstraction improves productivity over matrix frameworks because message processing can access destination vertex properties.This access is especially useful for algorithms such as collaborative filtering and triangle counting.
- Overall framework: Each GraphMat superstep sends messages from active vertices, runs generalized SPMV, applies outputs, and marks changed vertices active again.Execution stops at a user-specified maximum or when no vertices change state.
- Implementation and optimization: GraphMat uses DCSC sparse matrices, bitvector-based sparse vectors, compiler inter-procedural optimization, and partitioned multicore SPMV.The sparse-vector representation and SPMV optimizations target cache behavior and parallel processing.
5. RESULTS
GraphMat combines vertex-programming productivity with sparse-matrix performance, outperforming competing frameworks across diverse algorithms while approaching native optimized code and scaling effectively on multicore systems.
- Framework comparisons: 5-7X speedup over GraphLab and CombBLAS and about 1.2X over Galois was achieved across the evaluated algorithms and datasets.The geometric-mean comparison summarizes GraphMat’s performance advantage across the reported workload range.
- Native-code comparison: 1.2X slowdown relative to native optimized code was measured on average across datasets.GraphMat was comparable to native code for PageRank and BFS, while retaining a higher-level vertex-program abstraction.
- Multicore scalability: 13-15X speedup over a single-threaded implementation was achieved on 24 cores, compared with 2-12X for competing frameworks.The scalability comparison covers GraphLab, CombBLAS, and Galois on representative workloads.
- Performance analysis: GraphMat’s performance advantages reflect fewer instructions and stall cycles than GraphLab and CombBLAS, while Galois can outperform it on selected workloads.Galois is 1.35X faster on SSSP through asynchronous execution, whereas GraphMat performs better on PageRank and collaborative filtering.
- Performance analysis: GraphMat’s generalized sparse matrix backend and vertex-state access improve performance and code flexibility relative to matrix-based alternatives.The backend is heavily optimized, and vertex-state access is particularly useful for triangle counting and collaborative filtering.
- Productivity: GraphMat requires little user-side performance tuning because backend optimizations are abstracted behind the vertex-program interface.Users primarily tune the number of threads and desired matrix partitions.
6. CONCLUSION AND FUTURE WORK
GraphMat bridges the productivity-performance gap with a vertex-programming frontend and optimized matrix backend, improving performance and multicore scaling while approaching native code.
- GraphMat combines a vertex programming frontend with an optimized matrix backend to bridge the productivity-performance gap.
- GraphMat improves performance by 1.2-7X over GraphLab, CombBLAS, and Galois, while remaining about 1.2X off native, hand-optimized code on average.
- GraphMat provides an easier performance-improvement path for users accustomed to vertex programming.
- GraphMat is expected to scale well to multiple nodes because it is based on SPMV.
- Improved single-node efficiency can reduce node requirements for a given problem size and improve cluster utilization.
- GraphMat’s backend optimizations can also be adopted by other frameworks, and array-processing systems can support graph analytics through vertex-programming frontends.
APPENDIX
The appendix provides GraphMat source code for single-source shortest path (SSSP) as a reference.
- The appendix provides GraphMat source code for single-source shortest path (SSSP) as a reference.
A. SSSP SOURCE CODE
The SSSP source code defines a GraphMat vertex program and runs it on a graph initialized with a source vertex and infinite distances. The program propagates weighted distances, reduces competing values by minimum, and runs until convergence.
- A. SSSP SOURCE CODE: The SSSP program uses distance_type for messages, processed values, and vertex properties.
- A. SSSP SOURCE CODE: The program sends each source vertex property as a message and computes candidate distances by adding the message to the edge weight.
- A. SSSP SOURCE CODE: Competing reduced values are combined with a minimum operation, and the resulting value updates the vertex property.
- A. SSSP SOURCE CODE: The driver partitions the input matrix across 8×nthreads, initializes all distances to infinity, activates source vertex 6 at distance zero, and runs until convergence.