Direction de recherche : Evripidis BAMPIS

Co-encadrement : PASCUAL Fanny

Energy Minimisation, Data Movement and Uncertainty: models and algorithms

Les plateformes de calcul haute performance (HPC) sont la solution idéale pour exécuter des applications exigeantes en termes de calcul. Étant donné leur consommation importante en énergie, le besoin d’algorithmes plus efficaces en termes d’énergie est indispensable. De meilleurs algorithmes d’ordonnancement peuvent être conçus en exploitant les caractéristiques essentielles d’une plateforme HPC, telles que sa topologie de réseau et l’hétérogénéité de ses machines. On peut également obtenir de meilleures performances en concevant des modèles plus réalistes, qui saisissent les fonctionnalités d’applications réelles. Ainsi, permettre aux algorithmes d’ordonnancement de décider de la quantité de ressources allouées à une application, ou de la vitesse d’exécution des machines peut ouvrir la voie à de nouvelles implémentations compatibles avec la plateforme.
Dans la première partie de la thèse, nous introduisons un modèle qui prend en compte à la fois la topologie et l’hétérogénéité d’une plateforme en introduisant deux types de machines. Nous augmentons le problème d’ordonnancement avec des contraintes dont le but est de réduire implicitement le mouvement des données pendant l’exécution des tâches sur des machines parallèles, et lors de la communication avec le système de fichiers. Nous proposons des algorithmes qui ordonnancent les tâches au cours du temps, et décident du nombre de ressources allouées à une tâche, en tenant compte de ces contraintes supplémentaires.
Dans la deuxième partie de la thèse, on s’intéresse à l’incertitude liée à la charge de travail d’une application, cette charge étant directement liée au temps nécessaire à son exécution. La plupart des travaux de la littérature considèrent cette valeur connue à l’avance. C’est cependant rarement le cas dans les systèmes réels. Dans notre approche, la charge de travail donnée est une charge possible, mais qui peut éventuellement être réduite. On introduit alors des tests spécifiques à l’application qui peuvent réduire la charge de travail d’une tâche. Étant donné que le test (par exemple, la compression) doit également être exécuté, et que la quantité de réduction (par exemple, la taille) est inconnue avant la fin du test, la décision d’exécuter ou non le test pour une tâche doit être prise. On propose des algorithmes compétitifs pour le problème d’ordonnancement de telles tâches, dans le but de minimiser l’énergie consommée par un ensemble de machines pour lesquelles on peut modifier la vitesse.
Dans la troisième partie de la thèse, nous nous intéressons à un contexte similaire d’entrées incertaines et nous considérons un modèle dans lequel les temps d’exécution des tâches ne sont pas connus à l’avance. Nous augmentons l’entrée du problème en introduisant des valeurs prédites des temps d’exécution. Nous concevons alors des algorithmes qui ont d’excellentes performances lorsque les prédictions sont exactes, tout en restant compétitifs lorsque les prédictions se révèlent inexactes.

Publications 2020-2022

• 2022
  • K. Dogeas : “Minimisation de l’énergie, mouvements de données, et données incertaines: modèles et algorithmes”, soutenance de thèse, soutenance 06/04/2022, direction de recherche Bampis, Evripidis, co-encadrement : Pascual, Fanny (2022)
  • E. Bampis, K. Dogeas, A. Kononov, G. Lucarelli, F. Pascual : “Scheduling with Untrusted Predictions”, Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}, Vienna, Austria, pp. 4581-4587, (International Joint Conferences on Artificial Intelligence Organization) (2022)
• 2021
  • E. Bampis, K. Dogeas, A. Kononov, G. Lucarelli, F. Pascual : “Speed Scaling with Explorable Uncertainty”, SPAA '21: Proceedings of the 33^rd ACM Symposium on Parallelism in Algorithms and Architectures, virtual conference, United States, pp. 83-93, (ACM) (2021)
• 2020
  • E. Bampis, K. Dogeas, A. Kononov, G. Lucarelli, F. Pascual : “Scheduling Malleable Jobs Under Topological Constraints”, 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS), New Orleans, LA, United States, pp. 316-325, (IEEE) (2020)