A Case Study of an Adaptive Delta-Stepping Algorithm in OpenMP

The
$\Delta$
-stepping algorithm is one of the most popular algorithms implemented in modern graph processing systems for solving the single-source shortest path problem. The algorithm executes in a sequence of steps, processing a subset of vertices in parallel in each step. A user-defined parameter called “delta” determines the number of vertices processed in a single step. Thus, the performance of the
$\Delta$
-stepping algorithm is highly sensitive to the value of the delta parameter. The value of delta that performs well on one graph input may give worse results on another input. As a result, the delta parameter requires exhaustive tuning which is typically a part of preprocessing phase. In this work, we study a case for an adaptive
$\Delta$
-stepping algorithm wherein the delta value is dynamically adjusted during the program runtime. We implement this adaptive policy for delta on top of an existing reference implementation and apply heuristics for optimal parameter calculation. We evaluate our implementation on a diverse set of graph inputs. The results show that, compared to the baseline reference implementation, adjusting delta during the program execution can reduce the performance sensitivity to
$\Delta$
in terms of parallel running time from orders of magnitude of 10 to approximately
$2\times$
the best-performing delta value on all the inputs. In addition, the changes made to the
$\Delta$
-stepping algorithm do not impact the program scalability and incur less than 2 % overhead on the overall performance.