Graph analytics elicits insights from large graphs to inform critical decisions for business, safety and security. Several large-scale graph processing frameworks feature efficient runtime systems; however, they often provide programming models that are low-level and subtly different from each other. Therefore, end users can find implementation and specially optimization of graph analytics error-prone and time-consuming. This paper regards the abstract interface of the graph processing frameworks as the instruction set for graph analytics, and presents Grafs, a high-level declarative specification language for graph analytics and a synthesizer that automatically generates efficient code for five high-performance graph processing frameworks. It features novel semantics-preserving fusion transformations that optimize the specifications and reduce them to three primitives: reduction over paths, mapping over vertices and reduction over vertices. Reductions over paths are commonly calculated based on push or pull models that iteratively apply kernel functions at the vertices. This paper presents conditions, parametric in terms of the kernel functions, for the correctness and termination of the iterative models, and uses these conditions as specifications to automatically synthesize the kernel functions. Experimental results show that the generated code matches or outperforms handwritten code, and that fusion accelerates execution.
Fri 17 JunDisplayed time zone: Pacific Time (US & Canada) change
15:30 - 16:50
|(ICFP 2020) Achieving high-performance the functional way: a functional pearl on expressing high-performance optimizations as rewrite strategies|
Bastian Hagedorn NVIDIA, Johannes Lenfers University of Münster, Thomas Koehler University of Glasgow, Xueying Qin University of Glasgow, United Kingdom, Sergei Gorlatch University of Münster, Germany, Michel Steuwer University of EdinburghLink to publication DOI Authorizer link Pre-print
|(PLDI 2020) Optimizing Homomorphic Evaluation Circuits by Program Synthesis and Term Rewriting|
|(ICFP 2021) Grafs: Declarative Graph Analytics|
|(POPL 2022) Verified Tensor-Program Optimization Via High-level Scheduling Rewrites|