“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 157 — #167
i
i
i
i
i
i
i
i
3.6 L’efficacité en temps et en espace
157
La méthode du banquier compte des crédits, où un « crédit » représente une unité
de temps d’exécution ou d’espace de mémoire. Chaque opération met de côté des
crédits. Une opération chère est autorisée quand il y a assez de crédits disponibles
pour payer son exécution.
La méthode du physicien est basée sur la découverte d’une fonction de potentiel.
On peut la considérer comme une sorte d’altitude par rapport au niveau de la mer.
Chaque opération change le potentiel, c’est-à-dire qu’elle monte ou descend un peu.
Le coût de chaque opération est son changement en potentiel : de combien elle monte
ou descend. La complexité totale est une fonction de la différence entre le potentiel
initial et final. Si elle reste petite, de grandes variations seront autorisées entre les
deux.
Pour plus d’informations sur ces méthodes et beaucoup d’exemples de leur utilisation avec des algorithmes déclaratifs, nous recommandons le livre de Okasaki [72].
3.6.4 Des considérations sur la performance
Depuis le début de l’ère de l’ordinateur dans les années 1940, les coûts du temps
et de l’espace ont diminué à un taux exponentiel : un facteur multiplicatif d’amélioration chaque année. Ils sont actuellement très bon marché, en termes absolus et
en perception : un ordinateur personnel actuel a au moins 512 Mo de mémoire vive,
120 Go de mémoire persistante sur disque dur et une fréquence d’horloge de 3 GHz.
Il a une performance maximale soutenue d’environ un milliard d’instructions par
seconde, où chaque instruction peut faire une opération complète de 64 bits, y compris
en virgule flottante. Il est nettement plus rapide qu’un super-ordinateur Cray-1,
l’ordinateur le plus rapide au monde en 1975. Un super-ordinateur est défini
comme un des ordinateurs les plus rapides à un moment donné. Le premier Cray-1
avait une fréquence d’horloge de 80 MHz et pouvait exécuter par cycle plusieurs
opérations à virgule flottante de 64 bits [83]. À prix constant, la performance d’un
ordinateur personnel s’améliore à un taux exponentiel (doublant environ tous les deux
ans), et on peut prévoir que cela continuera au moins pendant dix ans. C’est une
conséquence de la loi de Moore sur la densité des transistors.
La loi de Moore
La loi de Moore dit que la densité des circuits intégrés double environ tous les 18
mois. Ce phénomène a été observé pour la première fois par Gordon Moore vers 1965
et se vérifie jusqu’à ce jour. Les experts pensent que la loi peut ralentir mais qu’elle
se maintiendra substantiellement pendant encore au moins 10 ans. Une interprétation
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.6 L’efficacité en temps et en espace
157
La méthode du banquier compte des crédits, où un « crédit » représente une unité
de temps d’exécution ou d’espace de mémoire. Chaque opération met de côté des
crédits. Une opération chère est autorisée quand il y a assez de crédits disponibles
pour payer son exécution.
La méthode du physicien est basée sur la découverte d’une fonction de potentiel.
On peut la considérer comme une sorte d’altitude par rapport au niveau de la mer.
Chaque opération change le potentiel, c’est-à-dire qu’elle monte ou descend un peu.
Le coût de chaque opération est son changement en potentiel : de combien elle monte
ou descend. La complexité totale est une fonction de la différence entre le potentiel
initial et final. Si elle reste petite, de grandes variations seront autorisées entre les
deux.
Pour plus d’informations sur ces méthodes et beaucoup d’exemples de leur utilisation avec des algorithmes déclaratifs, nous recommandons le livre de Okasaki [72].
3.6.4 Des considérations sur la performance
Depuis le début de l’ère de l’ordinateur dans les années 1940, les coûts du temps
et de l’espace ont diminué à un taux exponentiel : un facteur multiplicatif d’amélioration chaque année. Ils sont actuellement très bon marché, en termes absolus et
en perception : un ordinateur personnel actuel a au moins 512 Mo de mémoire vive,
120 Go de mémoire persistante sur disque dur et une fréquence d’horloge de 3 GHz.
Il a une performance maximale soutenue d’environ un milliard d’instructions par
seconde, où chaque instruction peut faire une opération complète de 64 bits, y compris
en virgule flottante. Il est nettement plus rapide qu’un super-ordinateur Cray-1,
l’ordinateur le plus rapide au monde en 1975. Un super-ordinateur est défini
comme un des ordinateurs les plus rapides à un moment donné. Le premier Cray-1
avait une fréquence d’horloge de 80 MHz et pouvait exécuter par cycle plusieurs
opérations à virgule flottante de 64 bits [83]. À prix constant, la performance d’un
ordinateur personnel s’améliore à un taux exponentiel (doublant environ tous les deux
ans), et on peut prévoir que cela continuera au moins pendant dix ans. C’est une
conséquence de la loi de Moore sur la densité des transistors.
La loi de Moore
La loi de Moore dit que la densité des circuits intégrés double environ tous les 18
mois. Ce phénomène a été observé pour la première fois par Gordon Moore vers 1965
et se vérifie jusqu’à ce jour. Les experts pensent que la loi peut ralentir mais qu’elle
se maintiendra substantiellement pendant encore au moins 10 ans. Une interprétation
© Dunod – La photocopie non autorisée est un délit