Source-linked AI summary
GraphIt: A High-Performance DSL for Graph Analytics
Yunming Zhang, Mengjiao Yang, Riyadh Baghdadi, Shoaib Kamil, Julian Shun, Saman Amarasinghe
TL;DR
Graph applications require different optimization choices for different algorithms and graph structures, while existing frameworks expose limited flexibility. GraphIt separates algorithms from schedules, composes and validates optimizations, and autotunes schedules; across 32 experiments, it was faster than the next fastest framework in 24 and up to 4.8× faster, while never exceeding a 43% slowdown on the remainder.
Problem
Graph performance depends on algorithms, hardware, and graph structure, but existing frameworks support limited optimizations and do not expose broad composition of tuning choices.
Method
GraphIt uses separate algorithm and scheduling languages, a graph iteration space to validate composed edge-traversal optimizations, and autotuning to search schedules.
Results
GraphIt outperforms the next fastest shared-memory framework on 24 of 32 experiments by up to 4.8× and is never more than 43% slower on the others.
Takeaways & Limitations
GraphIt provides performance-competitive implementations across algorithms and graphs with different sizes and structures while reducing code by up to an order of magnitude.
Takeaways & Limitations
GraphIt restricts vertex data vectors to read-only, write-only, or commutative and associative reduction access patterns for transformations to remain valid independently of traversal order.
Abstract
from arXiv · showhide
The performance bottlenecks of graph applications depend not only on the algorithm and the underlying hardware, but also on the size and structure of the input graph. Programmers must try different combinations of a large set of techniques to develop the best implementation for a specific algorithm and type of graph. Existing graph frameworks lack flexibility, supporting only a limited set of optimizations. This paper introduces GraphIt, a new DSL for graph computations that generates fast implementations for algorithms with different performance characteristics running on graphs with different sizes and structures. GraphIt separates what is computed (algorithm) from how it is computed (schedule). Programmers specify the algorithm using an algorithm language, and performance optimizations are specified using a scheduling language. The algorithm language simplifies expressing the algorithms. We formulate graph optimizations, including edge traversal direction, data layout, parallelization, cache, NUMA, and kernel fusion optimizations, as tradeoffs among locality, parallelism, and work-efficiency. The scheduling language enables programmers to easily search through this complicated tradeoff space by composing together optimizations. We also built an autotuner to automatically find high-performance schedules. The compiler uses a new scheduling representation, the graph iteration space, to model, compose, and ensure the validity of the large number of optimizations. GraphIt outperforms the next fastest of six state-of-the-art shared-memory frameworks (Ligra, Green-Marl, GraphMat, Galois, Gemini, and Grazelle) on 24 out of 32 experiments by up to 4.8$\times$, and is never more than 43% slower than the fastest framework on the other experiments. GraphIt also reduces the lines of code by up to an order of magnitude compared to the next fastest framework.
1 INTRODUCTION
GraphIt addresses the difficulty of achieving high performance across algorithms and graph inputs by separating algorithm specifications from composable performance schedules. Its compiler and autotuner generate and search valid optimization combinations, delivering strong performance across diverse benchmarks.
- Graph performance bottlenecks vary with the algorithm, hardware, and graph size and structure, forcing programmers to balance locality, work-efficiency, and parallelism.
- GraphIt separates high-level algorithm specifications from a scheduling language for edge traversal, data layout, and program-structure optimizations.
- The graph iteration space represents, composes, and validates edge-traversal optimizations for compiler analysis and code generation.
- Its scheduling language composes optimization choices, while autotuning searches the large scheduling space for high-performance schedules.
- GraphIt outperforms the next fastest shared-memory framework on 24 of 32 experiments by up to 4.8× and is never more than 43% slower on the others.
2 TRADEOFF SPACE AND OPTIMIZATIONS
GraphIt frames graph optimization as a tradeoff among locality, work-efficiency, and parallelism, illustrated through PageRankDelta traversal and data-access choices. Different traversal modes exchange work, synchronization, memory behavior, and parallelism, while hybrid schedules adapt to frontier size.
- GraphIt characterizes graph optimizations through locality, work-efficiency, and parallelism, whose effects can trade off against one another.Locality includes cache reuse and NUMA placement; work-efficiency reflects instruction cost, while parallelism reflects independent work, load balance, and synchronization.
- 2.1 PageRankDelta: PageRankDelta updates only vertices with sufficiently changed ranks, using a frontier to propagate changes across iterations.The algorithm sends each active vertex’s delta to out-neighbors, then recomputes ranks and forms the next frontier.
- 2.2 Graph Optimizations: DensePull increases parallelism and removes update atomics but can perform more work than SparsePush, which processes only active vertices.DensePull uses random reads and mostly sequential writes, while SparsePush performs outgoing-neighbor updates from frontier vertices.
- 2.2 Graph Optimizations: DensePush scans all vertices to increase parallelism and avoid sparse-frontier maintenance, sacrificing work-efficiency relative to SparsePush.
- 2.2 Graph Optimizations: Hybrid traversal switches between dense and sparse modes according to active-set size, favoring DensePull early and SparsePush as the frontier shrinks.
- 2.2 Graph Optimizations: Cache partitioning can improve locality by fitting graph segments into the LLC, but it sacrifices work-efficiency through data replication and result merging.NUMA partitioning similarly improves locality by minimizing slow inter-socket memory accesses.
3 ALGORITHM LANGUAGE
GraphIt’s algorithm language expresses graph computations with high-level vertexset and edgeset abstractions while separating edge processing from traversal, filtering, synchronization, and deduplication. This separation exposes optimization opportunities and reduces low-level implementation detail.
- Data Model: GraphIt uses elements, vertexsets, edgesets, and associated vertex and edge data to model graph algorithms.
- Language Constructs and Operators: The language separates edge-processing logic from traversal, filtering, synchronization, and modified-vertex tracking.
- Language Constructs and Operators: GraphIt’s operators let the compiler generate traversal-specific code while inserting appropriate data-access and synchronization instructions.
- Language Constructs and Operators: The applyModified operator tracks updated vertices and can disable deduplication when an algorithm guarantees each vertex is inserted only once.
- Control Flow: Traditional for, while, and if constructs express fixed iterations, convergence loops, and conditional control flow.
4 SCHEDULING LANGUAGE
GraphIt’s scheduling language lets programmers compose traversal, data-structure, parallelization, partitioning, NUMA, and program-structure choices separately from algorithm code. Schedules can select direction-specific implementations and transform generated code through fusion and hybrid traversal.
- Scheduling Functions: Scheduling functions compose edge direction, frontier representation, parallelization, cache, NUMA, data-layout, and program-structure optimizations.
- Scheduling Functions: Programmers choose a traversal direction first, then configure partitioning, parallelization, NUMA, and dense-vertex-set options for that direction.
- Traversal Scheduling: Hybrid schedules can generate both DensePull and SparsePush implementations and choose between them using active-vertex out-degree information.
- Program Structure Optimizations: Scoped labels preserve references to operations after loop fusion, allowing individual fused operators to remain schedulable.
- Program Structure Optimizations: GraphIt schedules loop and function fusion through commands that identify loops and apply operators by their scoped labels.
5 SCHEDULING REPRESENTATION
GraphIt represents edge traversal and related optimizations with a graph iteration space, a tagged multidimensional model that supports composition, validity reasoning, and code generation. Its dimensions encode subgraph partitioning, traversal order, direction, parallelism, filtering, and locality choices.
- Graph Iteration Space: The graph iteration space represents combinations of edge-traversal optimizations as multidimensional vectors that the compiler can compose and validate.
- Tags: Direction, partitioning, parallelization, and filtering tags encode traversal and optimization strategies for graph-iteration-space dimensions.
- Dimensions: GraphIt’s four dimensions are SSG_ID, BSG_ID, OuterIter, and InnerIter, abbreviated as S, B, O, and I.
- Dimensions: OuterIter and InnerIter identify edge endpoints, with their vertex-set ranges reversed between push and pull traversal directions.
- Subgraph Partitioning: BSG_ID partitions the OuterIter dimension, while SSG_ID partitions InnerIter and restricts random-access ranges for cache and NUMA locality.
- Data Layout and Program Structure: Vertex data vectors use AoS or SoA tags, while scoped labels support program-structure transformations alongside graph-iteration-space tags.
6 COMPILER IMPLEMENTATION
The GraphIt compiler generates optimized C++ from an algorithm and schedule, using graph-iteration-space analysis to produce traversal code, parallelization, synchronization, subgraph, NUMA, and data-layout transformations. An autotuner searches for high-performance schedules.
- Compiler Overview: GraphIt compiles an algorithm and schedule into optimized C++ and provides an autotuner for finding high-performance schedules.
- Traversal Code Generation: The code generator emits separate traversal implementations for hybrid modes and selects between them using active-vertex out-degree information.
- Traversal Code Generation: SparsePush generation iterates over frontier sources, while DensePull generation iterates over destination vertices with filtered source access.
- Subgraph and NUMA Code Generation: BSG and SSG code generation supports edge-aware or fixed partitioning, parallel scheduling, cache locality, and NUMA placement across sockets.
- Validity: GraphIt uses read-only, write-only, or commutative-associative reduction restrictions to support valid optimization transformations.
- Dependence Analysis: Dependence analysis determines required synchronization when parallelizing traversal dimensions, including reductions with unknown cross-iteration dependencies.
- NUMA Code Generation: The compiler generates NUMA-local buffers and merge phases when parallel updates require cross-socket synchronization.
- Data Layout: Vertex data-layout transformations lower vector assignments into vertexset operations and preserve execution ordering.
7 EVALUATION
GraphIt is evaluated across diverse graph algorithms, datasets, frameworks, and schedules, showing that performance depends strongly on optimization choices and input characteristics. It outperforms competing shared-memory systems broadly, while autotuning and kernel fusion provide additional performance benefits.
- 7 EVALUATION: GraphIt is evaluated on seven algorithms and graphs with varied sizes, structures, and application domains, using six state-of-the-art shared-memory frameworks as baselines.The evaluation includes PR, BFS, CC, SSSP, CF, BC, and PRDelta, with social, web, road, and recommendation graphs.
- 7.1 Comparisons with State-of-the-Art Frameworks: 24 out of 32 experiments favor GraphIt over the next fastest framework, with speedups of up to 4.8×; on the remaining experiments, it is never more than 43% slower than the fastest framework.GraphIt also reduces code size by up to an order of magnitude compared with the next fastest framework.
- 7.2 Performance of Different Schedules: GraphIt’s best schedules vary by algorithm and graph: direction, bitvector, cache, and NUMA choices can improve performance in some cases while reducing it in others.For example, CC gains from direction, bitvector, and cache optimizations on several graphs but is slower on USAroad than specialized alternatives.
- 7.2 Performance of Different Schedules: BFS reaches up to 30× speedup on several graphs with DensePullSparsePush and cache optimization, whereas SparsePush reduces overhead on USAroad.The result demonstrates that no single schedule is best across all inputs.
- 7.2 Performance of Different Schedules: The edge-aware-dynamic-vertex-parallel scheme is 2.4× faster than dynamic-vertex-parallel for CF because it improves load balance, while different schemes suit PRDelta and BFS.The edge-parallel approach is omitted because extra synchronization makes it consistently worse than edge-aware-dynamic-vertex-parallel.
- 7.4 Fusion of Multiple Graph Kernels: Kernel fusion for PageRank and Eigenvector Centrality improves spatial locality and reduces L1 data-cache stall cycles and L2 cache misses, producing speedups.The fused kernels share similar memory access patterns and fuse the vectors they access.
8 RELATED WORK
Related graph systems and DSLs support selected graph models or optimizations, but generally expose only a limited subset of the available optimization combinations. GraphIt targets this gap with a graph-specific scheduling language that composes broader optimization choices.
- Shared-Memory Graph Processing Libraries and DSLs: Many shared-memory frameworks use frontier-based processing, but existing systems support only a few traversal directions and provide limited support for parallelization and data-layout alternatives.GraphIt expands the optimization space by enabling combinations of these choices.
- Shared-Memory Graph Processing Libraries and DSLs: NUMA and cache techniques exist across prior systems, but CSR segmenting and cache blocking had not been integrated into a general programming model or combined with direction optimization.This leaves prior techniques less composable than GraphIt’s scheduling approach.
- Shared-Memory Graph Processing Libraries and DSLs: Vertex-centric and sparse-matrix-vector models expose data parallelism, but they cannot easily integrate direction optimization because different directions require different synchronization strategies.This limits their flexibility for algorithms whose traversal behavior changes with the active set.
- Shared-Memory Graph Processing Libraries and DSLs: Green-Marl can express BFS concisely through a built-in primitive, but other programs require explicit vertex and edge loops, making direction optimization harder to integrate.The lower-level structure becomes a barrier to composing traversal strategies for non-BFS programs.
- Other Graph Processing Systems: GPU systems were outside this paper’s focus because current GPU memory capacities do not support processing very large graphs in memory, while out-of-core systems are slower than shared-memory frameworks when graphs fit in memory.Distributed systems face a different tradeoff space dominated by network communication and load balancing.
- Scheduling Languages: Unlike scheduling languages for dense-array loop nests, GraphIt’s scheduling language is designed specifically for graph applications and their optimization tradeoffs.The comparison positions GraphIt alongside Halide, CHiLL, and HMPP while distinguishing its graph-specific scope.
9 CONCLUSION
GraphIt is a DSL that separates graph algorithms from performance schedules, enabling validated composition of optimizations and automated schedule search. Its evaluations show substantial speedups over state-of-the-art graph frameworks.
- GraphIt separates algorithm specifications from performance optimizations, allowing algorithms to be expressed independently of schedules.The algorithm language simplifies expression, while the scheduling language explores optimization tradeoffs.
- GraphIt models optimization tradeoffs among locality, parallelism, and work-efficiency through a scheduling language and graph iteration space.The graph iteration space supports composing optimizations and ensuring the validity of edge traversal transformations.
- GraphIt is up to 4.8× faster than state-of-the-art graph frameworks across algorithms and graphs with varying performance characteristics.The separation of algorithm and schedule, together with correctness guarantees for edge traversal optimizations, enables an autotuner for high-performance schedules.