Cette thèse se focalise sur des algorithmes efficaces en énergie pour des problèmes d'ordonnancement de tâches sur des processeurs pouvant varier la vitesse d'exécution ainsi que sur des processeurs fonctionnant sous un mécanisme de réchauffement-refroidissement, où pour un budget d'énergie donné ou un seuil thermique, l'objectif consiste à optimiser un critère de Qualité de Service. Une partie de notre recherche concerne des problèmes d'ordonnancement de tâches apparaissant dans des environnements de traitement de grandes données. Dans ce contexte, nous nous focalisons sur le paradigme MapReduce en considérant des problèmes d'ordonnancement efficaces en énergie sur un ensemble de processeurs, ainsi que pour la version classique.Premièrement, nous proposons des résultats de complexité, des algorithmes optimaux et approchés pour différentes variantes du problème de la minimisation du retard maximal d'un ensemble de tâches sur un processeur pouvant varier la vitesse d'exécution. Ensuite, nous considérons le problème d'ordonnancement MapReduce dans les versions énergétique et classique sur des processeurs non-reliés où le but est de minimiser le temps d'achèvement pondéré. Nous étudions deux cas spéciaux et les généralisations de ces deux problèmes en proposant des algorithmes d'approximation constante. Enfin, nous étudions le problème d'ordonnancement dans lequel la température du processeur est en-dessous un seuil donné où chaque tâche contribue au réchauffement et le but est de maximiser le nombre de tâches exécutées. Nous considérons le cas où les tâches ont des durées unitaires et ayant la même date d'échéance et nous étudions le rapport d'approximation de ce problème. / This thesis is focused on energy-efficient algorithms for job scheduling problems on speed-scalable processors, as well as on processors operating under a thermal and cooling mechanism, where, for a given budget of energy or a thermal threshold, the goal is to optimize a Quality of Service criterion. A part of our research concerns scheduling problems arising in large-data processing environments. In this context, we focus on the MapReduce paradigm and we consider problems of energy-efficient scheduling on multiple speed-scalable processors as well as classical scheduling on a set of unrelated processors.First, we propose complexity results, optimal and constant competitive algorithms for different energy-aware variants of the problem of minimizing the maximum lateness of a set of jobs on a single speed-scalable processor. Then, we consider energy-aware MapReduce scheduling as well as classical MapReduce scheduling (where energy is not our concern) on unrelated processors, where the goal is to minimize the total weighted completion time of a set of MapReduce jobs. We study special cases and generalizations of both problems and propose constant approximation algorithms. Finally, we study temperature-aware scheduling on a single processor that operates under a strict thermal threshold, where each job has its own heat contribution and the goal is to maximize the schedule's throughput. We consider the case of unit-length jobs with a common deadline and we study the approximability of the problem.

L’algorithme EM (Dempster et al., 1977) permet de construire une séquence d’estimateurs qui converge vers l’estimateur de vraisemblance maximale pour des modèles à données manquantes pour lesquels l’estimateur du maximum de vraisemblance n’est pas calculable. Cet algorithme est remarquable compte tenu de ses nombreuses applications en apprentissage statistique. Toutefois, il peut avoir un lourd coût computationnel. Les auteurs Cappé et Moulines (2009) ont proposé une version en ligne de cet algorithme pour les modèles appartenant à la famille exponentielle qui permet de faire des gains d’efficacité computationnelle importants en présence de grands jeux de données. Cependant, le calcul de l’espérance a posteriori de la statistique exhaustive, qui est nécessaire dans la version de Cappé et Moulines (2009), est rarement possible pour des modèles complexes et/ou lorsque la dimension des données manquantes est grande. On doit alors la remplacer par un estimateur. Plusieurs questions se présentent naturellement : les résultats de convergence de l’algorithme initial restent-ils valides lorsqu’on remplace l’espérance par un estimateur ? En particulier, que dire de la normalité asymptotique de la séquence des estimateurs ainsi créés, de la variance asymptotique et de la vitesse de convergence ? Comment la variance de l’estimateur de l’espérance se reflète-t-elle sur la variance asymptotique de l’estimateur EM? Peut-on travailler avec des estimateurs de type Monte-Carlo ou MCMC? Peut-on emprunter des outils populaires de réduction de variance comme les variables de contrôle ? Ces questions seront étudiées à l’aide d’exemples de modèles à variables latentes. Les contributions principales de ce mémoire sont une présentation unifiée des algorithmes EM d’approximation stochastique, une illustration de l’impact au niveau de la variance lorsque l’espérance a posteriori est estimée dans les algorithmes EM en ligne et l’introduction d’algorithmes EM en ligne permettant de réduire la variance supplémentaire occasionnée par l’estimation de l’espérance a posteriori. / The EM algorithm Dempster et al. (1977) yields a sequence of estimators that converges to the maximum likelihood estimator for missing data models whose maximum likelihood estimator is not directly tractable. The EM algorithm is remarkable given its numerous applications in statistical learning. However, it may suffer from its computational cost. Cappé and Moulines (2009) proposed an online version of the algorithm in models whose likelihood belongs to the exponential family that provides an upgrade in computational efficiency in large data sets. However, the conditional expected value of the sufficient statistic is often intractable for complex models and/or when the missing data is of a high dimension. In those cases, it is replaced by an estimator. Many questions then arise naturally: do the convergence results pertaining to the initial estimator hold when the expected value is substituted by an estimator? In particular, does the asymptotic normality property remain in this case? How does the variance of the estimator of the expected value affect the asymptotic variance of the EM estimator? Are Monte-Carlo and MCMC estimators suitable in this situation? Could variance reduction tools such as control variates provide variance relief? These questions will be tackled by the means of examples containing latent data models. This master’s thesis’ main contributions are the presentation of a unified framework for stochastic approximation EM algorithms, an illustration of the impact that the estimation of the conditional expected value has on the variance and the introduction of online EM algorithms which reduce the additional variance stemming from the estimation of the conditional expected value.

Les réseaux de capteurs sans fil sont constitués de noeuds capteurs, capables de récolter des données, de les analyser et de les transmettre. Ces réseaux ont plusieurs applications, en fonction de la zone où ils sont déployés. Application militaire ou de sauvetage dans des zones pouvant être inaccessibles aux humains ; application sanitaire avec des capteurs déployés sur et dans le corps humain ; application de surveillance avec des capteurs sur les voitures d'un ville, ou les arbres d'une forêt. Les noeuds sont autonomes en énergie et il est primordial d'assurer leur longévité sans retarder la récolte des données. La tache principale réalisée par les réseaux de capteurs sans fils consiste à effectuer des mesures et à envoyer ces données jusqu'à un noeud coordinateur. Cette tache d'agrégation est effectuée régulièrement, ce qui en fait la plus consommatrice d'énergie. L'étude approfondie de la consommation d'énergie des capteurs, qui au centre de ma thèse, peut se traduire de différentes manières. Premièrement, nous avons étudié la complexité du problème de l'agrégation de données en utilisant un modèle simplifié pour représenter un réseau de capteurs sans fils. Secondement, nous nous sommes concentrés sur l'estimation de cette durée de vie. Nous présentons WiSeBat, un modèle de batterie et de consommation d'énergie optimisé pour les réseaux de capteurs, implémenté dans le simulateur WSNET. Après validation, nous l'utilisons pour comparer les performances des algorithmes de broadcast efficaces en énergie. / A wireless sensor network is an ad-hoc network connecting small devices equipped with sensors. Such networks are self-organized and independent of any infrastructure. The deployment of a WSN is possible in areas inaccessible to humans, or for applications with a long lifetime requirement. Indeed, devices in a wireless sensor network are usually battery-powered, tolerate failure, and may use their own communication protocols, allowing them to optimize the energy consumption. The main application of WSNs it to sense the environment at different locations and aggregate all the data to a specific node that logs it and can send alerts if necessary. This task of data aggregation is performed regularly, making it the most energy consuming. As reducing the energy consumed by sensor is the leading challenge to ensure sustainable applications, we tackle in this thesis the problem of aggregating efficiently the data of the network. Then, we study lifetime evaluation techniques and apply it to benchmark existing energy-centric protocols.