Résumé :
L'analyse d'un algorithme consiste à prévoir les ressources qu'il utilise lors de son exécution. Dans le passé, les ressources principalement étudiées furent le temps et l'espace mémoire. La généralisation des appareils portables comportant une unité de calcul pour laquelle l'énergie est une ressource critique implique qu'il est désormais essentiel de concevoir et d'analyser les algorithmes en fonction de l'énergie qu'ils utilisent.
Nous présenterons donc des travaux visant à définir une mesure de complexité liée à l'énergie qui soit aussi indépendante que possible du modèle de calcul utilisé. Les modèles de calcul fournissent une abstraction des fonctionnalités, et des coûts liés à l'utilisation d'une technologie ; et la méthode permettant la prise en compte du facteur énergie doit induire si possible peu de modifications.
Par exemple, la machine RAM (Random Access Memory) est une abstraction d'un processeur générique, ce modèle estime la performance d'un algorithme selon le nombre d'opérations effectuées, celles-ci ayant toutes le même coût. Pour de nombreuses raisons, ce modèle n'est pas approprié lorsque l'on estime l'énergie consommée ; par exemple des données empiriques montrent que les accès mémoire consomment quatre fois plus d'énergie que les autres instructions. Un autre défaut de ce modèle est l'hypothèse d'une mémoire d'un seul tenant. En effet la plupart des calculateurs modernes utilisent des caches afin d'exploiter la localité temporelle et spatiale des données. Ainsi le coût énergétique dépend tout autant du nombre de références à la mémoire cache, que du nombre d'accès mémoire. Ainsi l'analyse du comportement de la mémoire cache est essentielle afin d'obtenir une estimation réaliste de la consommation d'énergie.
La consommation d'énergie n'est pas seulement dépendante des opérations effectuées mais aussi de paramètres du processeur tels que le voltage, la capacité, la fréquence, la précision des calculs. Diverses techniques d'optimisation peuvent être appliquées afin de contrôler ces paramètres au cours de l'algorithme (réglage en ligne du voltage, de la précision arithmétique). Bien que les processeurs actuels permettent l'utilisation de ces techniques, il n'existe pas de modèle de calcul intégrant une telle flexibilité.
Dans cet exposé nous introduirons une notion de complexité
mesurant l'energie consommée qui s'adapte à la fois au modèle
de la machine RAM et à des modèles plus complexes. En introduisant
un invariant de la complexité énergétique en tant
que fonction du temps, de l'espace et des communications, nous pouvons
adjoindre une mesure de la consommation à la plupart des modèles
de calcul. Nous parlerons des classes de complexité LOW-ENERGY and
HIGH-ENERGY qui distinguent les algorithmes selon que leur consommation
d'énergie est faible ou importante. Enfin nous présenterons
les nombreuses direction de recherche ouvertes et liées à
la prise en compte de la consommation d´énergie en algorithmique.
Abstract:
Analysis of an algorithm implies predicting the resources required when it is executed on real machines. Resources like time and memory have been of primary concern for designers in the past. Portable, battery operated devices have become increasingly popular. Energy is a precious resource for the new generation of high speed processors whose performance is limited by thermal constraints of the chip. In this scenario, it has become essential to design and analyze algorithms with energy as an optimization metric.
We will present a very preliminary research on defining energy as a complexity measure as independent as possible of the model of computation. Models of computation are necessary for algorithm development as they provide a high level abstraction of the characteristics, costs and functionality of the implementation technology. Our energy framework should work over any model of computation with as few as possible modifications. The RAM (random access machine) model, for instance, has been widely used in abstracting a generic uniprocessor system for performance analysis. It predicts the performance of an algorithm as a function of operation counts which are assumed to have an uniform costs; this model is not appropriate for energy analysis of algorithms for many reasons. Practical data shows that memory access consumes nearly four times more energy as compared to other instructions. Another drawback of the RAM model is the assumption about a flat memory. Most modern machines utilize a cache to exploit spatial and temporal locality of references to a data. Thus energy complexity is as much a function of the cache reference pattern as they are of the number of memory access operations. Analysis of the cache behavior is essential to obtain realistic power estimates.
Energy consumption is not only a function of the number of operations but also of architecture parameters such as capacitance, voltage, frequency, precision. Several optimization techniques can be implemented by control of these parameters through specifications in the algorithm such as voltage-frequency scaling and precision management. Architecture support for implementation of these techniques is being provided in the state-of-the-art processors. However, there is no computational model which provides an abstraction of such architecture malleability.
In this talk, we introduce energy as a complexity measure which works for both the simple inadequate RAM model as well as for more sophisticated models. By introducing an invariant of the energy complexity as function of time, space and communication complexities we can exploit most of models of computation. We will talk about complexity classes such as LOW-ENERGY and HIGH-ENERGY for algorithms which are low or high energy consumption and point out the many unexplored research directions related to energy as an algorithm resource.