Il y a des limites théoriques à l'optimisation algorithmique. A moins qu'on démontre P=NP, dans le cadre de machine de turing (ou équivalente), je ne vois pas vraiment comment on pourrait faire un grand pas dans ce domaine.
Au contraire, je pense qu'il y a beaucoup a gagner a reflechir au niveau algorithmique. L'algorithmique classique est basee sur le modele RAM qui considere que chaque acces a la memoire est uniforme, or de plus en plus les architectures materielles sont basees sur des hierarchies memoires (registre, caches L1, L2, L3, disque...). Il y a ainsi un fossee entre l'algorithmique classique et le developpement d'application efficace tirant parti du materiel. Certains algorithmes sont mauvais en pratique a cause de ca. !
Juste un exemple pour bien comprendre. Si l'on realise un produit de matrice (C = A x B) avec un algorithme classique (calcul de c_{i,j}) alors pour calculer une ligne de la matrice C, il va falloir acceder a toute la matrice B (qui peut ne pas tenir en L2, ni meme en memoire). On peut alors faire ce produit par bloc mais dans ce cas on ne tire parti que d'un seul niveau de "cache" (souvent le plus petit). Un produit de matrice recursif (il tire partie efficacement de tous le niveaux de cache) est plus adapte, il permet ainsi de realiser efficacement le produit de plusieurs matrices qui ne tiennent pas en memoire central !
(ps: Le produit de matrices est un exemple, il existe des algorihtmes theoriques mieux qu'en o(n^3), la complexite du produit de matrice est meme un pb ouvert ! mais on peut reflechir a des algorithmes pour d'autres problemes)
Pour ce qui est de l'optimisation de code a proprement parler, les compilateurs optimisants pour des architectures actuelles (pas c merde de x86 donc ;-) font mieux que les humains...
Les compilos sont en general bons pour ce qui est de l'optimisation local (au niveau du bloc d'instructions) par contre au niveau global c'est moins fun. Certains arrivent a faire quelques trucs au niveau des boucles pour "vectoriser" un peu le code mais c'est a peu pret tout.
Pour moi, il y a donc de la place en recherche entre la theorie pure et dure (P=NP?) et l'architecture des processeurs. Par contre, il faut bien garder en vue que developper des processeurs rapides permet de gagner sur toutes les applications (sans rien couter au niveau developpement logiciel) alors qu'optimiser un algorithme/ une application est local a l'application donc plus cher. Il convient donc de developper des techniques algorithmiques applicables a un spectre large d'applications.
[^] # Re: remarque.
Posté par Alberto . En réponse à la dépêche Article sur le POWER4 d'IBM. Évalué à 10.
Au contraire, je pense qu'il y a beaucoup a gagner a reflechir au niveau algorithmique. L'algorithmique classique est basee sur le modele RAM qui considere que chaque acces a la memoire est uniforme, or de plus en plus les architectures materielles sont basees sur des hierarchies memoires (registre, caches L1, L2, L3, disque...). Il y a ainsi un fossee entre l'algorithmique classique et le developpement d'application efficace tirant parti du materiel. Certains algorithmes sont mauvais en pratique a cause de ca. !
Juste un exemple pour bien comprendre. Si l'on realise un produit de matrice (C = A x B) avec un algorithme classique (calcul de c_{i,j}) alors pour calculer une ligne de la matrice C, il va falloir acceder a toute la matrice B (qui peut ne pas tenir en L2, ni meme en memoire). On peut alors faire ce produit par bloc mais dans ce cas on ne tire parti que d'un seul niveau de "cache" (souvent le plus petit). Un produit de matrice recursif (il tire partie efficacement de tous le niveaux de cache) est plus adapte, il permet ainsi de realiser efficacement le produit de plusieurs matrices qui ne tiennent pas en memoire central !
(ps: Le produit de matrices est un exemple, il existe des algorihtmes theoriques mieux qu'en o(n^3), la complexite du produit de matrice est meme un pb ouvert ! mais on peut reflechir a des algorithmes pour d'autres problemes)
Pour ce qui est de l'optimisation de code a proprement parler, les compilateurs optimisants pour des architectures actuelles (pas c merde de x86 donc ;-) font mieux que les humains...
Les compilos sont en general bons pour ce qui est de l'optimisation local (au niveau du bloc d'instructions) par contre au niveau global c'est moins fun. Certains arrivent a faire quelques trucs au niveau des boucles pour "vectoriser" un peu le code mais c'est a peu pret tout.
Pour moi, il y a donc de la place en recherche entre la theorie pure et dure (P=NP?) et l'architecture des processeurs. Par contre, il faut bien garder en vue que developper des processeurs rapides permet de gagner sur toutes les applications (sans rien couter au niveau developpement logiciel) alors qu'optimiser un algorithme/ une application est local a l'application donc plus cher. Il convient donc de developper des techniques algorithmiques applicables a un spectre large d'applications.