C'est d'optimisation de code que tu parles pas d'algorithmique. L'optimisation de code consiste à adapter un algorithme pour un architecture particulière.
Non ce dont je parle est a la frontiere entre algorithmique et optimisation. Je ne souhaite pas adapter un algorithme a une architecture particuliere (pex: tunner pour une taille de cache donnee), mais construire des algorithmes efficaces pour une famille large d'architectures (les architectures hierarchiques). Il y a un bon article sur les articles cache oblivious (tirant parti efficacement d'un cache quelque soit sa taille) dans FOCS99.
Il est évident que certains algorithmes marche mieux sur certaines achitectures mais il est plus intéressant de trouver un algorithme qui marche mieux quelque soit l'architecture. Ce qui correspond à un abaissement de la complexité.
Je suis d'accord avec toi ! sauf sur la derniere phrase. Certains algorithmes de meme complexite (o(n^3)) sont efficaces alors que d'autres ne le sont pas. Relit l'exemple du produit de matrice, l'algorithme classique de produit de matrice fait des mauvais acces a la memoire.
Lorsque tu parles de complexite en o(x) tu supposes en general implicitement un modele de type ram (random access memory) et tu supposes implicitement egalement que les temps d'acces memoire sont identiques. Ces hypotheses sont insuffisantes pour avoir une corollation forte entre complexite et efficacite.
>la complexite du produit de matrice est meme un pb ouvert
Ca m'étonnerai beaucoup qu'on fasse mieux que le nombre d'éléments de la matrice à calculer (n2) à moins de pouvoir tout faire en parallèle (turing vs ...).
Oui cette borne inferieure du produit de matrice est triviale, mais malheureusement aucun n'algorithme de produit de matrice en o(n^2) n'a ete trouve ! Il existe par contre des algos en o(n^k) avec 2<k<3. Je repete la complexite du produit de matrice est un probleme ouvert.
Au niveau des optimisations des compilos je corrige un peu ce que j'ai dit il y a beaucoup d'optimisations au niveau de la fonction (j'avais dit bloc d'instructions) c'est quand meme assez local et j'ai dit que les compilos etaient bons au niveau local (les optimisations classiques dont tu parles sont surtout locales). Qaunt'aux optimisations sur les boucles (autres que l'unrolling mais plutot recherche de localite dans les boucles tilling & co), c'est toujours un sujet de recherche actif.
[^] # Re: remarque.
Posté par Alberto . En réponse à la dépêche Article sur le POWER4 d'IBM. Évalué à 2.
Non ce dont je parle est a la frontiere entre algorithmique et optimisation. Je ne souhaite pas adapter un algorithme a une architecture particuliere (pex: tunner pour une taille de cache donnee), mais construire des algorithmes efficaces pour une famille large d'architectures (les architectures hierarchiques). Il y a un bon article sur les articles cache oblivious (tirant parti efficacement d'un cache quelque soit sa taille) dans FOCS99.
Il est évident que certains algorithmes marche mieux sur certaines achitectures mais il est plus intéressant de trouver un algorithme qui marche mieux quelque soit l'architecture. Ce qui correspond à un abaissement de la complexité.
Je suis d'accord avec toi ! sauf sur la derniere phrase. Certains algorithmes de meme complexite (o(n^3)) sont efficaces alors que d'autres ne le sont pas. Relit l'exemple du produit de matrice, l'algorithme classique de produit de matrice fait des mauvais acces a la memoire.
Lorsque tu parles de complexite en o(x) tu supposes en general implicitement un modele de type ram (random access memory) et tu supposes implicitement egalement que les temps d'acces memoire sont identiques. Ces hypotheses sont insuffisantes pour avoir une corollation forte entre complexite et efficacite.
>la complexite du produit de matrice est meme un pb ouvert
Ca m'étonnerai beaucoup qu'on fasse mieux que le nombre d'éléments de la matrice à calculer (n2) à moins de pouvoir tout faire en parallèle (turing vs ...).
Oui cette borne inferieure du produit de matrice est triviale, mais malheureusement aucun n'algorithme de produit de matrice en o(n^2) n'a ete trouve ! Il existe par contre des algos en o(n^k) avec 2<k<3. Je repete la complexite du produit de matrice est un probleme ouvert.
Au niveau des optimisations des compilos je corrige un peu ce que j'ai dit il y a beaucoup d'optimisations au niveau de la fonction (j'avais dit bloc d'instructions) c'est quand meme assez local et j'ai dit que les compilos etaient bons au niveau local (les optimisations classiques dont tu parles sont surtout locales). Qaunt'aux optimisations sur les boucles (autres que l'unrolling mais plutot recherche de localite dans les boucles tilling & co), c'est toujours un sujet de recherche actif.