Politiques de gestion d’Énergie et de Température dans les Systèmes Informatiques

Nowadays, the energy consumption and the heat dissipation of computing environmentshave emerged as crucial issues. Indeed, large data centers consume as much electricityas a city while modern processors attain high temperatures degrading their performanceand decreasing their reliability. In this thesis, we study various energy and temperatureaware scheduling problems and we focus on their complexity and approximability.A dominant technique for saving energy is by proper scheduling of the jobs through theoperating system combined with appropriate scaling of the processor’s speed. This techniqueis referred to as speed scaling in the literature. The theoretical study of speed scalingwas initiated by Yao, Demers and Shenker (1995) who considered the single-processorproblem of scheduling preemptively a set of jobs, each one specified by an amount ofwork, a release date and a deadline, so as to minimize the total energy consumption.In order to measure the energy consumption of a processor, the authors considered thewell-known rule according to which the processor’s power consumption is P(t) = s(t)α ateach time t, where s(t) is the processor’s speed at t and α > 1 is a machine-dependentconstant (usually α ∈ [2, 3]). Here, we study speed scaling problems on a single processor,on homogeneous parallel processors, on heterogeneous environments and on shopenvironments. In most cases, the objective is the minimization of the energy but we alsoaddress problems in which we are interested in capturing the trade-off between energyand performance.We tackle speed scaling problems through different approaches. For non-preemptiveproblems, we explore the idea of transforming optimal preemptive schedules to nonpreemptiveones. Moreover, we exploit the fact that some problems can be formulatedas convex programs and we propose greedy algorithms that produce optimal solutionssatisfying the KKT conditions which are necessary and sufficient for optimality in convexprogramming. In the context of convex programming and KKT conditions, we also studythe design of primal-dual algorithms. Additionally, we solve speed scaling problems byformulating them as convex cost flow or minimum weighted bipartite matching problems.Finally, we elaborate on approximating energy minimization problems that can be formulatedas integer configuration linear programs. We can obtain an approximate solutionfor such a problem by solving the fractional relaxation of an integer configuration linearprogram for it and applying randomized rounding.In this thesis, we solve some new energy aware scheduling problems and we improvethe best-known algorithms for some other problems. For instance, we improve the bestknownapproximation algorithm for the single-processor non-preemptive energy minimizationproblem which is strongly NP-hard. When α = 3, we decrease the approximationratio from 2048 to 20. Furthermore, we propose a faster optimal combinatorial algorithmviiviiifor the preemptive migratory energy minimization problem on power-homogeneous processors,while the best-known algorithm was based on solving linear programs. Last butnot least, we improve the best-known approximation algorithm for the preemptive nonmigratoryenergy minimization problem on power-homogeneous processors for fractionalvalues of α. Our algorithm can be applied even in the more general case where the processorsare heterogeneous and, for αmax = 2.5 (which is the maximum constant α amongall processors), we get an improvement of the approximation ratio from 5 to 3.08.In order to manage the thermal behavior of a computing device, we adopt the approachof Chrobak, Dürr, Hurand and Robert (2011). The main assumption is that some jobsare more CPU intensive than others and more heat is generated during their execution.So, each job is associated with a heat contribution which is the impact of the job on theprocessor’s temperature. In this setting, we study the complexity and the approximabilityof multiprocessor scheduling problems where either there is a constraint on the processors’temperature and our aim is to optimize some performance metric or the temperature isthe optimization goal itself.La gestion de la consommation d’énergie et de la température est devenue un enjeucrucial dans les systèmes informatiques. En effet, un grand centre de données consommeautant d’électricité qu’une ville et les processeurs modernes atteignent des températuresimportantes dégradant ainsi leurs performances et leur fiabilité. Dans cette thèse, nousétudions différents problèmes d’ordonnancement prenant en compte la consommationd’énergie et la température des processeurs en se focalisant sur leur complexité et leurapproximabilité. Pour cela, nous utilisons le modèle de Yao et al. (1995) (modèle devariation de vitesse) pour la gestion d’énergie et le modèle de Chrobak et al. (2008) pourla gestion de la température