An Energy-Efficient Single-Source Shortest Path Algorithm
Sara Karamati, Jeffrey Young, Richard W. Vuduc · 2018
We present a novel strategy to control the energy-efficiency of an algorithm from software, which is to make the degree of parallelism dynamically and automatically tunable. The specific algorithm is a variation of delta-stepping for computing a single-source shortest path (SSSP); its available parallelism is highly irregular and strongly input-dependent. Informed by an analysis of these runtime characteristics, we propose a software-based controller that uses online learning techniques to tune parallelism to meet a given target, thereby improving the average available parallelism while reducing its variability. We show experimentally the efficacy of our self-tuning algorithm in managing tradeoffs among performance and power. Our experimental apparatus is based on the SSSP implementation available in the Gunrock GPU library running on an embedded CPU+GPU, whose hardware has GPU core and memory frequency knobs.