Presentation
Modeling Single-Source Shortest Path Algorithm Dynamics to Control Performance and Power Tradeoffs
Event Type
ACM Student Research Competition
Poster
TP
EX
TimeTuesday, November 13th8:30am - 5pm
LocationC2/3/4 Ballroom
DescriptionThis 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.
Archive
