Understanding Work-Efficiency of label correcting Single Source Shortest Path Algorithms - How does relaxed data structures affect the work-efficiency of parallel algorithms?

Abstract

Relaxed priority schedulers have been successfully used to improve the scalability of parallel Single-Source Shortest Path (SSSP) algorithms by reducing synchronization overhead. However, relaxation introduces deviations from strict priority ordering, which may generate redundant work and reduce work-efficiency. This thesis investigates the relationship between scheduling relaxation and work-efficiency in label-correcting parallel SSSP algorithms. To study this relationship, we extend an existing benchmarking framework with extra measurements. In addition, we introduce a configurable relaxed scheduler, DrPQ, which enables controlled experimentation with different degrees of relaxation. Experiments are conducted on road networks, Random Hyperbolic Graphs (RHGs), and grid graphs using several state-of-the-art relaxed priority scheduler implementations. Our results show that relaxation error is correlated with redundant work, but is not sufficient on its own to explain work-efficiency. The relationship between relaxation and work-efficiency is influenced by graph structure, queue size, and algorithm design. High-degree RHGs generally tolerate larger relaxation errors while maintaining high work-efficiency, whereas road and grid graphs are more sensitive to the same level of relaxation. Furthermore, the skew between median rank error and delay provides additional information about scheduler behavior: some schedulers achieve high work-efficiency despite large skew, although this skew is not a universal predictor of redundant work. Overall, the thesis demonstrates that work-efficiency in label-correcting parallel SSSP algorithms emerges from the interaction between relaxation errors, graph characteristics, and scheduler design. No single relaxation metric consistently predicts redundant work across all graph classes, reinforcing that work-efficiency depends on the interplay of multiple factors rather than any isolated measure of relaxation.