Je pense aussi que les algos iteratifs sont inapates pour etre bien parallelise, mais je pense que le probleme vient plus de l'algo en lui meme que du probleme a resoudre. Je m'explique :
Tu veux calculer a(i,j) et pour calculer a(i,j) il faut avoir deja calcule a(i-1, j) et a(i, j-1). C'est valable aussi pour des differences finis and co.
On peut faire un algo iteratif:
pour i de 1 a n
pour j de 1 a n
calculer a(i,j)
Il sera pas bien parallelisable (remarquons aussi qu'il ne sera pas bien efficace car limite par la bande passante memoire si n est plus grand que le cache !).
On peut faire des blocs pour acceler tous ca, ou mieux faire des blocs recursifs. On obtient alors des algorithmes cache-oblivious (cf google) qui sont efficaces (quel que soit la hierarchie memoire) et efficacement parallelisable (meme sur des clusters avec des reseaux ordinaires). Bref, je pense qu'il y a pas mal de boulot a faire du cote des algos, et brulons les algos iteratifs.
[^] # Re: Supercalculateurs : pour qui ? quel usage ?
Posté par Alberto . En réponse à la dépêche Supercalculateurs : scalaires ou vectoriels ?. Évalué à 5.
Tu veux calculer a(i,j) et pour calculer a(i,j) il faut avoir deja calcule a(i-1, j) et a(i, j-1). C'est valable aussi pour des differences finis and co.
On peut faire un algo iteratif:
pour i de 1 a n
pour j de 1 a n
calculer a(i,j)
Il sera pas bien parallelisable (remarquons aussi qu'il ne sera pas bien efficace car limite par la bande passante memoire si n est plus grand que le cache !).
On peut faire des blocs pour acceler tous ca, ou mieux faire des blocs recursifs. On obtient alors des algorithmes cache-oblivious (cf google) qui sont efficaces (quel que soit la hierarchie memoire) et efficacement parallelisable (meme sur des clusters avec des reseaux ordinaires). Bref, je pense qu'il y a pas mal de boulot a faire du cote des algos, et brulons les algos iteratifs.