Shelf schedules for independent moldable tasks to minimize the energy consumption

Scheduling independent tasks on a parallel platform is a widely-studied problem, in particular when the goal is to minimize the total execution time, or makespan ($P||C max$ problem in Graham's notations). Also, many applications do not consist of sequential tasks, but rather of parallel moldable tasks that can decide their degree of parallelism at execution (i.e., on how many processors they are executed). Furthermore, since the energy consumption of data centers is a growing concern, both from an environmental and economical point of view, minimizing the energy consumption of a schedule is a main challenge to be addressed. One should decide, for each task, on how many processors it is executed, and at which speed the processors are operated, with the goal to minimize the total energy consumption. We further focus on co-schedules, where tasks are partitioned into shelves, and we prove that the problem of minimizing the energy consumption remains NP-complete when static energy is consumed during the whole duration of the application. We are however able to provide an optimal algorithm for the schedule within one shelf, i.e., for a set of tasks that start at the same time. Several approximation results are derived, and simulations are performed to show the performance of the proposed algorithms.L’ordonnancement de tâches indépendantes sur une plateforme parallèle est un problème vastement étudié, en particulier lorsque le but est de minimiser le temps d’exécution total, ou makespan ($P||C max$ en utilisant la notation de Graham). De nombreuses applications ne sont pas séquentielles, et sont plutôt des tâches parallélisables moldables, dont le degré de parallélisation peut être choisi à l’exécution (i.e., sur combien de processeurs elles sont exécutées). De plus, étant donné que la consommation énergétique des centres de données devient un sujet de plus en plus important, que ce soit d’un point de vue environnemental ou économique, la minimisation de la consommation d’énergie est un défi majeur à relever. La décision algorithmique à prendre concerne, pour l’exécution de chaque tâche, le nombre de processeurs ainsi que la vitesse des dits processeurs, dans le but de minimiser la consommation totale d’énergie. Nous nous intéressons plus précisément aux co-ordonnancements, dans lesquels les tâches sont partitionnées en étagères, et nous prouvons que la minimisation de la consommation d’énergie est un problème NP-complet lorsque l’énergie statique est consommée pendant la totalité de l’exécution de l’application. Nous fournissons tout de même un algorithme optimal dans le cas d’un ordonnancement sur une seule étagère, i.e., pour un ensemble de tâches commençant simultanément. Plusieurs résultats d’approximation sont prouvés, et des simulations sont effectuées pour exhiber la performance des algorithmes proposé