title: Parallelizing graph computation with automated vectorization
Creators: name: Zhao, Wenyue
Publisher: name: The University of Edinburgh
Year: 2025
Subjects: subject: Multi-instance processing (MIP)
subject: MITra
subject: AutoMI
subject: Vectorization
subject: Frontier-ranking model

description: Graph computations have found widespread use in social network analysis, bioinformatics, and web search. Applications often need to evaluate the same graph query multiple times over the same data graph, starting from different source vertices, referred to as multi-instance processing (MIP). There are mainly two approaches to MIP. The first approach is to use highly optimized multi-instance graph algorithms that interleave the evaluation of multiple query instances to exploit computation sharing across instances. These multi-instance algorithms are efficient but challenging to implement. The other approach is to use general-purpose graph processing frameworks and obtain answers to multiple query instances through serial or batch evaluation. These frameworks are easy to program but shown to be significantly less efficient than multi-instance algorithms. With these two existing approaches, users have to choose between efficiency and ease of programming. In response to the challenge, this thesis presents a systematic approach to get the best of both worlds. In the first part of this thesis, we present MITra, a framework for composing Multi- Instance graph Traversal algorithms that traverse from multiple source vertices simultaneously over a single thread. Underlying MITra is a frontier-ranking model, which provides an abstraction for graph algorithms, separating traversal logic from computation logic. Based on this model, MITra offers an easy-to-use programming interface. MITra enables user to compose multi-instance algorithms by programming computation logic in a dedicated edge function following textbook algorithms, and choosing traversal logic via frontier-ranking configuration. On the backend, MITra synthesizes and executes the multi-instance algorithm by automatically organizing vertices into frontiers based on their numeric rank values, automatically sharing computation across instances and benefiting from SIMD vectorization. We further showcase the ease of use, expressiveness, and efficiency of MITra by developing a plug-and-play web demo. In addition, we extend MITra to take advantage of multi-core parallelization, and evaluate the performance of MITra through extensive experiments. The second part of this thesis presents AutoMI, a framework for automatically converting vertex-centric graph algorithms into their vectorized multi-instance versions. A well-developed multi-instance algorithm runs significantly faster than traditional serial and batch evaluation, however, its design and implementation are notoriously challenging. AutoMI relieves the burden of writing delicate multi-instance algorithms from developers and achieves superior performance through vectorization. In addition, we propose TrackFree optimization in AutoMI, yielding simpler and more efficient multiiii instance algorithm implementation. To aid the decision of whether to use TrackFree in AutoMI, we develop an algebraic characterization. AutoMI targets vertex-centric algorithms written in the GAS (Gather-Apply-Scatter) programming model, as promoted by major distributed graph processing frameworks. We implement AutoMI and demonstrate its performance advantage through extensive experiments on real-life and synthetic data graphs. Putting together, MITra and AutoMI provide a systematic approach to easily program multi-instance graph algorithms and achieve high performance through automated and effective vectorization.