ERPOT: Une heuristique d’ordonnancement quadri-critère pour optimiser le temps d’exécution, le taux de défaillance, la puissance électrique et la température sur les multi-cœurs

We investigate multi-criteria optimization and Pareto front generation. Given an application modeled as a Directed Acyclic Graph (DAG) of tasks and a multicore architecture, we produce a set of non-dominated (in the Pareto sense) static schedules of this DAG onto this multicore. The criteria we address are the execution time, reliability, power consumption, and peak temperature. These criteria exhibit complex antagonistic relations, which make the problem challenging. For instance, improving the reliability requires adding some redundancy in the schedule, which penalizes the execution time. To produce Pareto fronts in this 4-dimension space, we transform three of the four criteria into constraints (the reliability, the power consumption, and the peak temperature), and we minimize the fourth one (the execution time of the schedule) under these three constraints. By varying the thresholds used for the three constraints, we are able to produce a Pareto front of non-dominated solutions. We propose two algorithms to compute static schedules. The first is a ready list scheduling heuristic called ERPOT (Execution time, Reliability, POwer consumption and Temperature). ERPOT actively replicates the tasks to increase the reliability, uses Dynamic Voltage and Frequency Scaling to decrease the power consumption, and inserts cooling times to control the peak temperature. The second algorithm uses an Integer Linear Programming (ILP) program to compute an optimal schedule. However, because our multi-criteria scheduling problem is NP-complete, the ILP algorithm is limited to very small problem instances. Comparisons showed that the schedules produced by ERPOT are on average only 10% worse than the optimal schedules computed by the ILP program, and that ERPOT outperforms the PowerPerf-PET heuristic from the literature on average by 33%.Nous nous attaquons à l’optimisation multi-critères et à la génération de fronts de Pareto. Etant données une application modélisée sous la forme d’un graphe orienté sans cycle (DAG) de tâches et une architecture multi-cœurs, nous calculons un ensemble d’ordonnancements statiques non dominés (au sens de Pareto) de ce DAG sur ce multi-cœurs. Les critères que nous considérons sont le temps d’exécution, la fiabilité, la puissance électrique et la température de crête. Ces critères présentent des relations complexes d’antagonisme, ce qui fait de notre problème d’ordonnancement un vrai défi. Par exemple, améliorer la fiabilité requiert d’ajouter de la redondance dans l’ordonnancement, ce qui pénalise le temps d’exécution. Afin de produire des fronts de Pareto dans cet espace à quatre dimensions, nous transformons trois de ces quatre critères en contraintes (la fiabilité, la puissance électrique et la température de crête) et nous minimisons le quatrième (le temps d’exécution) sous ces trois contraintes. En faisant varier les seuils utilisés pour les trois contraintes, nous sommes capables de produire un front de Pareto de solutions non-dominées. Nous proposons deux algorithmes pour calculer des ordonnancements statiques. Le premier est une heuristique de liste appelé ERPOT (Execution time, failure Rate, POwer consumption and Temperature). ERPOT réplique activement la tâches pour améliorer la fiabilité, utilise l’Ajustement Dynamique de la Fréquence et de la Tension (ADFT) pour réduire la puissance électrique, et insère des intervalles d’inactivité pour contrôler la température de crête. Le second algorithme repose sur un Programme Linéaire en Nombres Entiers (PLNE) pour construire un ordonnancement optimal. Toutefois, dans la mesure où notre problème d’ordonnancement multi-critères est NP-complet, l’algorithme PLNE est limité à des instances de très petite taille. Les comparaisons montrent que les ordonnancements produits par ERPOT sont en moyenne 10% moins bons que les ordonnancements optimaux calculés par l’algorithme PNLE, et que ERPOT améliore en moyenne de 33% les ordonnancements produit par l’heuristique PowerPerf-PET de la littérature