Laboratoire d'Informatique de Grenoble

La consommation d'énergie est un enjeu crucial pour les systèmes temps réel, c'est pourquoi l'optimisation en ligne, c'est-à-dire pendant l'exécution du processeur, est devenue essentielle. Cette optimisation se fait en adaptant la vitesse du processeur lors de l'exécution des tâches. Cette thèse aborde plusieurs situations avec des connaissances différentes sur les caractéristiques des tâches passées, actuelles et futures. Tout d'abord, nous considérons que toutes les caractéristiques des tâches sont connues (le cas hors ligne), et nous proposons un algorithme linéaire en temps pour déterminer les choix de vitesses pour exécuter n tâches sur un seul processeur. Deuxièmement, en utilisant les processus de décision de Markov, nous résolvons le cas où les caractéristiques des tâches passées et actuelles sont entièrement connues, et pour les futures tâches, seule la distribution de probabilité des caractéristiques des tâches (dates d'arrivée, temps d'exécution et délais) est connue. Troisièmement, nous étudions un cas plus général : la situation où le temps d'exécution n'est découvert que lorsque la tâche est terminée. En outre, nous considérons également le cas où nous n'avons aucune connaissance statistique des tâches, nous devons donc utiliser des méthodes d'apprentissage pour déterminer les vitesses optimales du processeur en ligne. Enfin, nous proposons une analyse de faisabilité (la capacité du processeur à exécuter toutes les tâches avant leurs échéances quand il fonctionne toujours à vitesse maximale) de plusieurs politiques en ligne classiques, et nous montrons que notre algorithme de programmation dynamique est également le meilleur en terme de faisabilité.