Ressources infor­ma­ti­ques : encore une his­toire de temps !

L’objec­tif de cette pré­sen­ta­tion est de s’inter­ro­ger sur la notion de res­source en Informatique, et en par­ti­cu­lier sur la res­source « temps ». Cette dis­cus­sion sera l’occa­sion de pré­sen­ter les appro­ches clas-siques pour la réso­lu­tion de pro­blè­mes à l’aide d’ordi­na­teurs. Comment opti­mi­ser les res­sour­ces dont on dis­pose pour effec­tuer un calcul ? Ces res­sour­ces sont le temps (néces­saire pour faire le calcul) et l’espace (mesuré par la quan­tité de mémoire également néces­saire pour mener à bien le calcul). Une des pro­blé­ma­ti­ques fon­da­men­ta­les de l’Informatique réside dans la façon d’uti­li­ser ces res­sour­ces, à savoir d’une part mini­mi­ser l’espace néces­saire pour sto­cker et mani­pu­ler les don­nées, et d’autre part accé­lé­rer le temps d’exé­cu­tion des algo­rith­mes. La res­source « temps » est sou­vent la plus cri­ti­que, au sens où l’espace (mémoire) coûte peu cher en Informatique. On connaît des pro­blè­mes pour les­quels on ne par­vient pas à conce­voir des algo­rith-mes rapi­des, sans pour autant être capa­bles de démon­trer for­mel­le­ment qu’il n’en existe pas ! Pire, cer­tains pro­blè­mes ne pos­sè­dent pas de solu­tions sous forme algo­rith­mi­que. Outre le temps passé à résou­dre un pro­blème, et l’espace mémoire (ou le maté­riel) uti­lisé, le bon usage des res­sour­ces est aussi mesuré par d’autres objec­tifs comme la consom­ma­tion énergétique. L’algo­rithme doit alors effec­tuer des com­pro­mis puis­que ces objec­tifs sont contra­dic­toi­res. Enfin, on peut uti­li­ser des res­sour­ces mul­ti­ples (i.e., plu­sieurs ordi­na­teurs) pour accé­lé­rer la réso­lu­tion des pro­blè­mes. Ceci pose de nou­veaux défis liés à la dis­tri­bu­tion des unités de calcul et à leurs inte­rac-tions. Les domai­nes du paral­lé­lisme et du calcul réparti font ainsi appa­raî­tre une dua­lité entre l’es-pace uti­lisé sur un seul ordi­na­teur, et le temps obtenu dans le cas où l’on dis­pose de plu­sieurs pro-ces­seurs. Dans ce cas, nous mon­tre­rons sur des exem­ples qu’il n’est pas tou­jours judi­cieux d’uti­li­ser davan­tage de res­sour­ces, même si celles-ci sont gra­tui­tes et dis­po­ni­bles !

Computing resources : yet another matter of time !

The goal of this paper is to pre­sent the notion of resource in Computer Science and, in par­ti­cu­lar, to dis­cuss the resource « time ». This dis­cus­sion pre­sents the stan­dard approa­ches for the solu­tion of pro­blems by means of com­pu­ters. How can one opti­mize resour­ces avai­la­ble when per­for­ming some com­pu­ta­tion ? These resour­ces are « time » (needed for this com­pu­ta­tion) and space (mea­su­red as the quan­tity of memory needed for it). One of the fun­da­men­tal issues in Computer Science lies in the way of using these resour­ces. Good usage mainly consists, on the one hand, of mini­mi­zing space neces­sary for sto­ring and pro­cess-ing data and, on the other hand, of acce­le­ra­ting conver­gence time of algo­rithms. Very often « time » is more cri­ti­cal, in the sense that « space » (memory) is very cheap nowa­days. It is well-known that there exist pro­blems for which we do not know how to devise fast algo­rithms, with-out howe­ver being able to for­mally prove that such algo­rithms do not exist ! Much worse : there exist pro­blems that cannot be solved by algo­rithms. In addi­tion to the time spent for sol­ving a pro­blem and the space used, good usage of resour­ces is also mea­su­red by means of other cri­te­ria, such as energy consump­tion. An algo­rithm must then per-form seve­ral trade-offs bet­ween time (and space), and energy consump­tion, since these issues are very fre­quently anta­go­nis­tic. Furthermore, one can use mul­ti­ple resour­ces (for exam­ple, seve­ral com­pu­ters). Here, new chal­len­ges arise concer­ning the dis­tri­bu­tion of com­pu­ta­tion units and their inte­rac­tions. The fields of paral­le­lism and of dis­tri­bu­ted com­pu­ting exhi­bit a kind of dua­lity bet­ween the space used on a single com­pu­ter, and the time needed when using many pro­ces­sors (com­pu­ters). In this case, we will give exam­ples sho­wing that it is not always sound to use more resour­ces, even if they are freely avai­la­ble !