Modeling Single-Source Shortest Path Algorithm Dynamics to Control Performance and Power Tradeoffs

Student: Sara Karamati (Georgia Institute of Technology), Jeffrey Young (Georgia Institute of Technology), Rich Vuduc (Georgia Institute of Technology)
Supervisor: Richard Vuduc (Georgia Institute of Technology)

Abstract: This work presents a new methodology to improve the performance of parallel algorithms by tuning the amount of available parallelism for execution throughout the runtime. As such, we expose key parameters controlling the performance and parallelism of the algorithm and build a software-based controller with the objective of maintaining the optimal performance. Our controller allows for tuning the level of parallelism executed in each time epoch to optimize for performance while preserving power usage. More specifically, our experimental evaluation focuses on a tunable variation of a GPU-based delta-stepping algorithm for computing the single-source shortest path (SSSP); As the available parallelism for the delta-stepping SSSP is highly irregular and strongly input-dependent, our extensive experiments show that average power can be reduced while average parallelism is increased. This increase in average parallelism provides substantial energy savings, independent of the hardware.

ACM-SRC Semi-Finalist: no

Poster: PDF
Poster Summary: pdf


Back to Poster Archive Listing