One Graph, Many Sources: Automating Vectorization Safely
ACM SIGMOD Record · 23.04.2026 · 55 (1) · 20-29
DOI: 10.1145/3810900.3810904 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGMOD Record, online erschienen am 23.04.2026. Verfasst von Wenyue Zhao und 2 weiteren Autor:innen. Die Arbeit nennt 42 Literaturangaben.
Abstract (Originalsprache)
Many graph workloads repeatedly run the same traversal or iterative computation from many different source vertices. Multi-instance execution can share work across sources and, if implemented carefully, exploit SIMD by packing per-source state into vectors. However, in vertex-centric graph processing systems, naive ''vectorize everything'' transformations can be wrong: a vertex may be active for only a subset of sources in a round, yet unguarded SIMD updates implicitly advance all lanes, leading to incorrect answers. We present AutoMI, a source-to-source compilation framework that automatically converts a single-instance program into a provably correct SIMD-vectorized multi-instance program runnable on existing vertex-centric engines. AutoMI uses a per-message bit-vector track to recover per-source activation and generate masked SIMD updates. It further provides a TrackFree optimization, guided by an algebraic idempotence characterization, that safely drops track and produces streamlined code when over-activation is harmless. On six real graphs (up to billions of edges) and up to 256 sources, AutoMI achieves 9.6 to 29.5x speedup over parallelized serial evaluation, 7.1 to 26.4x over batch processing, and 2.6 to 4.6x over prior handcrafted multi-instance code.
Zitieren
APA
Zhao, W., Cao, Y., & Buneman, P. (2026). One Graph, Many Sources: Automating Vectorization Safely. ACM SIGMOD Record, 55(1), 20-29. https://doi.org/10.1145/3810900.3810904
Vancouver
Zhao W, Cao Y, Buneman P. One Graph, Many Sources: Automating Vectorization Safely. ACM SIGMOD Record. 2026;55(1):20-29. doi:10.1145/3810900.3810904
BibTeX
@article{Zhao2026,
author = {Zhao, Wenyue and Cao, Yang and Buneman, Peter},
title = {One Graph, Many Sources: Automating Vectorization Safely},
journal = {ACM SIGMOD Record},
year = {2026},
volume = {55},
number = {1},
pages = {20--29},
doi = {10.1145/3810900.3810904}
}
EUVIMED