Search

This paper focuses on energy minimization for the mapping and scheduling of real-time workflows under reliability constraints. Workflow instances are input periodically to the system. Each instance is composed of several tasks and must complete execution before the arrival of the next instance, and with a prescribed reliability threshold. While the shape of the dependence graph is identical for each instance, task execution times are stochastic and vary from one instance to the next. The reliability threshold is met by using several replicas for each task. The target platform consists of identical processors equipped with Dynamic Voltage and Frequency Scaling (DVFS) capabilities. A different frequency can be assigned to each task replica.This difficult tri-criteria mapping and scheduling problem (energy, deadline, reliability) has been studied only recently for workflows with arbitrary dependence constraints [20, 11]. We investigate new mapping and scheduling strategies based upon layers in the task graph, and which better balance replicas across processors, thereby decreasing the time overlap between the different replicas of the same task and saving energy. We compare these strategies with the two competitor approaches [20, 11] and a reference baseline [33] on a variety of benchmark workflows. Our best heuristics achieve an average energy gain of 40% over the competitors and of 80% over the baseline.; Ce travail s’intéresse à la minimisation de la consommation énergétique lors du placement et de l’ordonnancement de graphes de tâches temps-réel soumis à des contraintes de fiabilité. Des instances d’un graphe de tâches sont soumises périodiquement à un système. Chaque instance est composée de plusieurs tâches et son exécution doit être terminée avant l’arrivée de l’instance suivante tout en respectant un niveau de fiabilité donné. Ce niveau de fiabilité est atteint en répliquant un certain nombre de fois chacune des tâches. La plateforme de calcul est constituée de processeurs identiques dont le voltage et la fréquence peuvent être modifiés (système DVFS). Chaque réplica de tâche peut se voir attribuer sa propre fréquence.Ce problème tri-critère de placement et d’ordonnancement (énergie, dates butoir, fiabilité) n’a commencé à être étudié que très récemment avec des dépendances arbitraires [20, 11]. Nous étudions de nouvelles stratégies de placement et d’ordonnancement basées sur une notion de couche du graphe de tâches, et qui équilibrent mieux les réplicas entre les processeurs, ce qui permet de réduire le recouvrement temporel entre les différents réplicas d’une même tâche et, de ce fait, la consommation énergétique. Nous comparons ces stratégies à deux approches concurrentes [20, 11] et à une approche de référence [33], sur un tout un ensemble de graphes de tâches. Nos meilleures heuristiques obtiennent un gain d’énergie de 40% par rapport aux approches concurrentes et de 80% vis-à-vis de l’approche de référence.