New Challenges in Scheduling Theory

October 21 - 27, 2012 --- Centre CNRS "La Villa Clythia", Frejus, France

Optimal Energy Consumption and Throughput for Workflow Applications on Distributed Architectures with Failures

SpeakerJean-Marc Nicod

Coauthors: Abdallah Ben Othman, Laurent Philippe, and Veronika Rehn-Sonigo

In this article, we study both the throughput and the energy optimization problems for a distributed system subject to failures that executes a work- flow at different speed levels. The application is modeled as a directed acyclic graph composed of typed tasks linked by dependency constraints. A continuous flow, or a great number of application instances, has to be pro- cessed. Optimizing the collaborative system performance implies to increase the throughput – the number of application instances processed by time unit – or to decrease the period, the time needed to output one instance of the system. The system is designed as a collaborative platform of distributed machines. Each machine collaborates with others by performing all the in- stances of at least one task of the DAG. The problem we tackle is to optimize the configuration of the platform. In this paper we propose two polynomial algorithms that optimize the two objectives of period (i.e., throughput) min- imization and energy minimization. We prove that the proposed algorithms give optimal results. Our optimization approach is hierarchic in the sens that we either minimize the energy consumption for an optimal period or mini- mize the period for the optimal energy consumption. For the cases where one of the constraints is not compliant with the optimal values we propose an implementation of the algorithms that provides the Pareto curve that links the two optimal values.