ENS de Lyon.
Vangelis Th. PaschosUniversité Paris-Dauphine
Michel RaynalUniversité de Rennes 1.
Yves RobertENS de Lyon
Denis TrystramGrenoble INP.
L’objectif de cette présentation est de s’interroger sur la notion de ressource en Informatique, et en particulier sur la ressource « temps ». Cette discussion sera l’occasion de présenter les approches clas-siques pour la résolution de problèmes à l’aide d’ordinateurs. Comment optimiser les ressources dont on dispose pour effectuer un calcul ? Ces ressources sont le temps (nécessaire pour faire le calcul) et l’espace (mesuré par la quantité de mémoire également nécessaire pour mener à bien le calcul). Une des problématiques fondamentales de l’Informatique réside dans la façon d’utiliser ces ressources, à savoir d’une part minimiser l’espace nécessaire pour stocker et manipuler les données, et d’autre part accélérer le temps d’exécution des algorithmes. La ressource « temps » est souvent la plus critique, au sens où l’espace (mémoire) coûte peu cher en Informatique. On connaît des problèmes pour lesquels on ne parvient pas à concevoir des algorith-mes rapides, sans pour autant être capables de démontrer formellement qu’il n’en existe pas ! Pire, certains problèmes ne possèdent pas de solutions sous forme algorithmique. Outre le temps passé à résoudre un problème, et l’espace mémoire (ou le matériel) utilisé, le bon usage des ressources est aussi mesuré par d’autres objectifs comme la consommation énergétique. L’algorithme doit alors effectuer des compromis puisque ces objectifs sont contradictoires. Enfin, on peut utiliser des ressources multiples (i.e., plusieurs ordinateurs) pour accélérer la résolution des problèmes. Ceci pose de nouveaux défis liés à la distribution des unités de calcul et à leurs interac-tions. Les domaines du parallélisme et du calcul réparti font ainsi apparaître une dualité entre l’es-pace utilisé sur un seul ordinateur, et le temps obtenu dans le cas où l’on dispose de plusieurs pro-cesseurs. Dans ce cas, nous montrerons sur des exemples qu’il n’est pas toujours judicieux d’utiliser davantage de ressources, même si celles-ci sont gratuites et disponibles !
The goal of this paper is to present the notion of resource in Computer Science and, in particular, to discuss the resource « time ». This discussion presents the standard approaches for the solution of problems by means of computers. How can one optimize resources available when performing some computation ? These resources are « time » (needed for this computation) and space (measured as the quantity of memory needed for it). One of the fundamental issues in Computer Science lies in the way of using these resources. Good usage mainly consists, on the one hand, of minimizing space necessary for storing and process-ing data and, on the other hand, of accelerating convergence time of algorithms. Very often « time » is more critical, in the sense that « space » (memory) is very cheap nowadays. It is well-known that there exist problems for which we do not know how to devise fast algorithms, with-out however being able to formally prove that such algorithms do not exist ! Much worse : there exist problems that cannot be solved by algorithms. In addition to the time spent for solving a problem and the space used, good usage of resources is also measured by means of other criteria, such as energy consumption. An algorithm must then per-form several trade-offs between time (and space), and energy consumption, since these issues are very frequently antagonistic. Furthermore, one can use multiple resources (for example, several computers). Here, new challenges arise concerning the distribution of computation units and their interactions. The fields of parallelism and of distributed computing exhibit a kind of duality between the space used on a single computer, and the time needed when using many processors (computers). In this case, we will give examples showing that it is not always sound to use more resources, even if they are freely available !