6 juillet 2023

LIG Bâtiment IMAG - 700 avenue Centrale
Domaine universitaire de Saint-Martin-d'Hères

Programme

Matin

9h30 Accueil café

10h00 Mathilde Jay
An experimental comparison of software-based power meters
The global energy demand for digital activities is constantly growing. Computing nodes and cloud services are at the heart of these activities. Understanding their energy consumption is an important step towards reducing it. On one hand, physical power meters are very accurate in measuring energy but they are expensive, difficult to deploy on a large scale, and are not able to provide measurements at the service level. On the other hand, power models and vendor-specific internal interfaces are already available or can be implemented on existing systems. Plenty of tools, called software-based power meters, have been developed around the concepts of power models and internal interfaces, in order to report the power consumption at levels ranging from the whole computing node to applications and services. However, we have found that it can be difficult to choose the right tool for a specific need.
In this work, we qualitatively and experimentally compare several software-based power meters able to deal with CPU or GPU-based infrastructures. For this purpose, we evaluate them against high-precision physical power meters while executing various intensive workloads. We extend this empirical study to highlight the strengths and limitations of each software-based power meter.

10h30 Louis-Claude Canon
Low-Cost Algorithms for the Restricted Assignment Problem on Intervals of Machines
We consider a special case of the Restricted Assignment problem where processing sets of jobs consist in contiguous intervals of machines. This problem is known as the Restricted Assignment problem on Intervals (RAI), and arises, for instance, when partitioning multi-get requests in distributed and replicated NoSQL databases. These databases aim at providing high availability and very low latency, i.e., the algorithms used to schedule requests must have good execution time. In this paper, we propose optimal and approximation algorithms for some variants of the RAI problem that apply to these systems. On the basis of previous work done by Lin et al. (European Journal of Operational Research, 2004), we present an efficient (2 − 1/m)-approximation algorithm, where m is the number of machines. We also provide a generalization of the RAI problem on so-called circular intervals, i.e., intervals that appear when machines are arranged in a circular fashion, and we call this new problem the Restricted Assignment problem on Circular Intervals (RACI). We give a procedure that computes an optimal solution when there are K possible processing times, assuming that one already knows an optimal algorithm for the corresponding non-circular problem. This enables us, for instance, to obtain an optimal algorithm with complexity O(n log n) for the RACI problem with a fixed number of machines and unitary jobs.

11h00 Lucas Pérotin
Scheduling Algorithms for Variable Capacity Resources
The drive to decarbonize the power grid to slow the pace of climate change has caused dramatic variation in the cost, availability, and carbon-intensity of power. This has begun to shape the planning and operation of datacenters. This presentation focuses on the design of scheduling algorithms for independent jobs that are submitted to a platform whose resource capacity varies over time.

11h30 Table ronde

Expression libre et travaux en petits groupes

Après Midi

14h00 Vincent Fagnon (soutenance de thèse)
Prédiction et augmentation de ressources à la rescousse de l'algorithmique
(Amphi F018 - BatF), thèse dirigée par Denis Trystram et co-encadrée par Giorgio Lucarelli.

Une retransmission en ligne sera accessible en suivant ce lien :
https://meet.univ-grenoble-alpes.fr/b/vin-qx6-fby-glc

Résumé : Actuellement, la tendance est à la mutualisation des ressources informatiques. Cette centralisation offre plusieurs avantages, notamment une meilleure gestion des variations de charge de travail, l'évitement de pics d'utilisation extrêmes et une optimisation simplifiée des calculs avec les données déjà en place. Cependant, l'avènement de l'Internet des objets (IoT) a créé une augmentation des besoins de traitement et d'analyse de données à des endroits éloignés des data-centers. Pour un traitement plus rapide et efficace, il est important de limiter les transferts de données et de les traiter près de leur lieu de production. Ainsi, il est essentiel de trouver un équilibre entre l'utilisation de plateformes centralisées pour mutualiser les ressources de calcul et les modèles décentralisés pour traiter les données localement. Cette thèse porte sur la mise en œuvre de plusieurs mécanismes visant à concevoir des algorithmes d'ordonnancement pour plusieurs agents ayant des objectifs distincts sur une plateforme composée de ressources de calcul. Tout d'abord, nous nous interrogeons sur l'utilisation d'un mécanisme externe (oracle) pour révéler les incertitudes relatives aux durées d'exécution de tâches séquentielles à exécuter sur une ressource de calcul. Nous proposons des algorithmes qui garantissent des performances moyennes optimales sur l'objectif classique du "sum flowtime" et étudions, via une campagne de simulations, leurs performances, leurs robustesses et la pertinence du modèle d'oracle en moyenne. Nous nous interrogeons également sur l'efficacité d'un tel modèle si l'on souhaite garantir de bonnes performances au pire des cas. Ensuite, nous étudions un problème bi-agent dans lequel chaque agent est soumis à des contraintes et des objectifs différents. Nous proposons un algorithme mettant en œuvre de l'augmentation de ressources (vitesse et rejet) et prouvons, grâce à la technique du dual fitting, un rapport de compétitivité dépendant, entre autres, de ces paramètres d'augmentation. Enfin, nous abordons un problème plus classique d'ordonnancement d'une application de tâches séquentielles pour laquelle nous souhaitons minimiser le "makespan" sur une plateforme hybride multicœurs (CPU/GPU). Nous proposons un algorithme basé sur l'étude de "l'intégrality gap" de la relaxation d'une programmation linéaire, algorithme pour lequel nous donnons une preuve de garantie de performances sous la forme d'un rapport d'approximation constant.