New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Performance and energy optimization of concurrent pipelined applications

SpeakerAnne Benoit

Co-authorPaul Renaud-Goud and Yves Robert

In this talk, we study the problem of finding optimal mappings for several independent but concurrent linear chain workflow applications, in order to optimize performance-related criteria together with energy consumption. The goal is to select an execution speed for each processor, and then to assign application stages to processors, with the aim of optimizing several concurrent optimization criteria. There is a clear trade-off to reach, since running faster and/or more processors leads to better performance, but the energy consumption is then very high. Energy savings can be achieved at the price of a lower performance, by reducing processor speeds or enrolling fewer resources. We establish the complexity of several multi-criteria optimization problems, whose objective functions combine period, latency and energy criteria. We demonstrate the difficulty of performance/energy trade-offs by proving that the tri-criteria problem is NP-hard, even with a single application on a fully homogeneous platform. On the experimental side, we design polynomial-time heuristics, and assess their absolute performance thanks to a linear program. One main goal is to evaluate the impact of processor sharing on the quality of the solution