In this paper we explore scheduling and runtime
system support for unordered distributed graph computations
that rely on optimistic (speculative) execution. Performance of
such algorithms is impacted by two competing trends: the higher
degree of parallelism enabled by optimistic execution in turn
requires substantial runtime support. To address the potentially
high overhead and scheduling complexity introduced by the
runtime, we investigate customizable scheduling policies that
augment the scheduler of the underlying runtime to adapt it to
a specific graph application. We present several implementations
of Distributed Control (DC), a data-driven unordered approach
with work prioritization and demonstrate that customizable
scheduling policies result in the most efficient implementation,
outperforming the well-known -stepping Single-Source Shortest
Paths (SSSP) and Jones-Plassmann vertex-coloring algorithms.
We apply two scheduling techniques, flow control and adaptive
frequency of network progress, which allow application-level
control over the balance of domain work and the runtime work.
Experimental results show the benefit of such application-aware
scheduling for irregular distributed graph algorithms.
Revised: June 14, 2019 |
Published: August 6, 2018
Citation
Firoz J.S., M.J. Zalewski, A. Lumsdaine, and M. Barnas. 2018.Runtime Scheduling Policies for Distributed Graph Algorithms. In IEEE International Parallel and Distributed Processing Symposium (IPDPS 2018), May 21-25, 2018, Vancouver, BC, 640-649. Los Alamitos, California:IEEE Computer Society.PNNL-SA-134903.doi:10.1109/IPDPS.2018.00073