We are happy to announce that Marco’s paper was accepted as Supercomputing 2025, taking place the 16-21 November in St. Louis. Marco will present its research paper on Thursday 20th at 3:30pm in the “Algorithms: Matching System Capabilities” session.

Abstract

The Single-Source Shortest Path (SSSP) problem is a fundamental graph problem with an extensive set of real-world applications. State-of-the-art parallel algorithms for SSSP, such as the ∆-stepping algorithm, create parallelism through priority coarsening. Priority coarsening results in redundant computations that diminish the benefits of parallelization and limit parallel scalability.

This paper introduces Wasp, a novel SSSP algorithm that reduces parallelism-induced redundant work by utilizing asynchrony and an efficient priority-aware work stealing scheme. Contrary to previous work, Wasp introduces redundant computations only when threads have no high-priority work locally available to execute. This is achieved by a novel priority-aware work stealing mechanism that controls the inefficiencies of indiscriminate priority coarsening.

Experimental evaluation shows competitive or better performance compared to GAP, GBBS, MultiQueues, Galois, ∆*-stepping, and ρ-stepping on 13 diverse graphs with geometric mean speedups of 2.2x on AMD Zen 3 and 2.1x on Intel Sapphire Rapids using 128 threads.

Source Code

The source code is available at: https://github.com/DIPSA-QUB/wasp
Paper available at: https://dl.acm.org/doi/10.1145/3712285.3759872