Distributed control: priority scheduling for single source shortest paths without synchronization
Marcin Zalewski, Thejaka Amila Kanewala, Jesun Firoz, Andrew Lumsdaine · Irregular Applications: Architectures and Algorithms · 2014
Massively parallel computers provide unprecedented computing power that is only expected to grow. With great power comes great responsibility---parallel overheads may dominate and must be minimized. The synchronization overhead in particular is deeply rooted in the programming practice because it makes algorithms easier to design and implement. In the effort to eliminate it, we introduce the idea of distributed control where global synchronization is reduced to termination detection and each worker optimistically proceeds ahead, based on the local knowledge of the global computation. We propose a distributed priority scheduler to (approximately) prioritize useful work without synchronization, and we implement the single-source shortest paths (SSSP) algorithm using the scheduler. We show significant improvements over a previous implementation of SSSP using Δ-stepping.