Programmation parallele - sommes

Bonjour,

J'ai actuellement dans un programme une boucle qui prend pas mal de temps qui ressemble á :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

for(i = 1; i< 256; i++) { data = M/i % 256; h = HammingWeight(data); sum1[i] += h; sum2[i] += h*h;   for(k=0; k<1000; k++) sum3[i][k] += h* tab[k]; } // M et tab sont définis avant la boucle.

---

J'aimerai accelerer ce code en le passant en parallele avec Parallel.For mais je n'arrive pas á m'en sortir a cause des sommes auxquelles on accede en meme temps.

Avec :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Parralel.For(1, 256, tst => { i = tst; data = M/i % 256; h = HammingWeight(data);   lock(this) { sum1[i] += h; sum2[i] += h*h;   for(k=0; k<1000; k++) sum3[i][k] += h* tab[k]; } });

---

Je ne gagne pas de temps car le lock l'empeche mais je ne comprend pas comment passer en 3 fonctions, comme je l'ai souvent vu sur le net.
Je voudrais faire qqch qui ressemble á :

Code:

---

1 2 3 4 5 6

int sum = 0; Parallel.For(0, 100, () => 0, (i,state)=> { if (isPrime(i)) state.ThreadLocalState += i; }, partialSum => Interlocked.Add(ref sum, partialSum));

---

Mais qui garde toutes mes sommes et mon tableau de sommes

Est-ce que l'un d'entre vous pourrait m'aider ?

Cordialement.


RQ : J'ai essayer avec un paralle.Invoke et des sommes locales mais je n'y arrive pas non plus.

Bonjour,

Prenons le cas d'un parcours de somme tous bete, comme tu l'as remarqué, si tu fais un simple lock tu ne gagne pas de temps. La technique pour gagner du temps c'est de faire des sommes partielles puis de locker pour la somme des sommes partielles.

Example (tirer du site de Ben Albahari)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

object locker = new object(); double grandTotal = 0;   Parallel.For (1, 10000000,   () => 0.0, // Initialize the local value.   (i, state, localTotal) => // Body delegate. Notice that it localTotal + Math.Sqrt (i), // returns the new local total.   localTotal => // Add the local value { lock (locker) grandTotal += localTotal; } // to the master value. );

---

Comme tu stockes tes sommes en fonction de l'indice i. Il te faut un tableau temporaire de stockage. Et comme tu veux faire plusieurs somme d'un coup une structure pour stocker tes 3 tableaux temporaires me parait bien.


EDIT:

Voici une ebauche de la chose:

Code:

---

1 2 3 4 5 6 7

public class SumsTmp { public double[] simple; public double[] carre; public List<double[]> complex; }

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Parallel.For(1, 256, () => new SumsTmp(), (i, state, localSum) => { double data = M/i%256; double h = HammingWeight(data); localSum.simple[i] += h; localSum.carre[i] += h*h;   for (int k = 0; k < 1000; ++k) localSum.complex[i][k] += h*tab[k]; return localSum; }, localSum => { lock (_locker) { for (int i = 1; i < 256; ++i) { final.simple[i] += localSum.simple[i]; final.carre[i] += localSum.carre[i];   for (int k = 0; k < 1000; ++k) final.complex[i][k] += localSum.complex[i][k]; } } } );

---

Mais l’agrégation des sommes prendras pas mal de temps, le parcours de "tab" est un réel probleme

EDIT2:
J'avais oublier le retour du corps, du coup j'ai passé la struct en class

Bonjour,

Merci de me répondre,
Je vais essayer de créer une structure pour les resultats, je n'y avais pas pensé. Par contre, comment je crée ma fonction finale

Code:

---

1 2 3

localTotal => { lock (locker) grandTotal += localTotal; }

---

alors que j'ai une autre boucle pour "les sous sommes" (la boucle en k) ? Mon tableau résultat dépend de l'indice i, existe-t-il encore á ce moment lá ?

Non ton indice n'existe plus à ce moment là.

Comme je le disais dans mon edit, la boucle en k est un réel problème.
Si la méthode "HammingWeight" est relativement courte, on peut essaye en ne parallélisant que la boucle sur k

Bonjour,

Merci pour la réponse, je n'avais pas vu l'edit.

Ce qui me prend du temps c'est la division M/i (car M est un bigInteger) et la boucle k, c'est pourquoi je voulais faire mon parallel.for sur la boucle en i. Je vais essayer votre proposition, si je ne gagne pas de temps j'essaierai seulement sur la boucle k.

Merci beaucoup en tous cas.

Cordialement

Bonjour,

Bon alors, voilá j'ai tenté de passer mon localSum comme il avait été proposé mais je me retrouve avec le meme probleme que lorsque j'essaie de faire ma somme pas en local et sans lock : lors de la boucle k : k vaut 1000 et i 256 et j'ai une exception index out of range bien sur.

Je ne comprend pas pourquoi ma condition <1000 et 256 n'est pas vérifiée, auriez vous une idée ?

Cordialement

Comment initialises tu tes tableaux?

Bonjour,

J'ai fais un constructeur qui prend en parametre nb1 et nb2 (ici 256 et 1000) et j'ai declaré :

Code:

---

1 2 3 4 5 6 7 8 9

public Sums(int nb1, int nb2) { locH = new double[nb1] locHcarre = new double[nb1] locCoprod = new doule[nb1][] for(i=0; i<nb2; i++) locCoprod[i] = new double[nb2] }

---

Euh, j'ai mis un tableau a 2 dimensions au lieu d'une liste car je suis plus á l'aise avec un tableau, est-ce un probleme ?

Du coup il y a un petit problème avec "i", il doit varier entre 0 et 255 pour accéder correctement au tableau.

Code:

---

Parallel.For(0, 256,

---

Code:

---

for (int i = 0; i < 256; ++i)

---

et du coup il ne faut faire attention a la division

Code:

---

M/(i+1)%256;

---

Par rapport à ton constructeur, non les tableaux ne sont pas un problème tant qu'ils restent de dimension 1.
Par contre ça devrait pas être

Code:

---

1 2 3

for(i=0; i<nb1; i++) locCoprod[i] = new double[nb2]; }

---

Sinon peux tu indiqué plus précisément ou à lieu l'exception, et quels sont les états des variables "i" et "k"?

Bonjour,

Je ne comprend pas pourquoi il y a un probleme avec le i, je veux bien le faire varier de 1 á 255. (par contre pour la suite de mon programme je l'utilise parfois de 0 a 255 auquel cas je mets une boucle de 0 a 255)

Oui bien sur c'est

Code:

---

1 2 3

for(i=0; i<nb1; i++) locCoprod[i] = new double[nb2];

---

mauvaise recopie de mon code :oops:

Sinon mon erreur apparait comme ceci :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Parallel.For(1, 256, () => new SumsTmp(), (i, state, localSum) => { double data = M/i%256; double h = HammingWeight(data); localSum.simple[i] += h; localSum.carre[i] += h*h; for (int k = 0; k < 1000; ++k) localSum.complex[i][k] += h*tab[k]; return localSum; }, localSum => { lock (_locker) { for (int i = 1; i < 256; ++i) { final.simple[i] += localSum.simple[i]; final.carre[i] += localSum.carre[i]; for (int k = 0; k < 1000; ++k) final.complex[i][k] += localSum.complex[i][k]; } } } );

---

avec IndexOutOfRangeException, i = 256 et k = 1000.

Je ne comprend pas comment i et k peuvent prendre ces valeurs. J'ai essayé de débuguer mais le mode parallele rend ca trop compliqué (du moins pour moi).

"i" ne peux pas valoir 256.
"k" ne peux pas valoir 1000.
Es-tu sur que "tab" est correctement initialisé? Es tu sur de ne pas avoir déclarer "i" ou "k" a l'exterieur de lambda expression.

J'ai fais un test chez moi, et tous est bon. :aie:

En effet j'avais déjá déclaré i et k avant ma boucle (je n'avais pas compris qu'ils devaient etre locaux :oops: )

Par contre maintenant les resultats des sommes sont faux :cry:

Ceci dit ca prend beaucoup plus de temps qu'avant donc je pense que je vais laisser tomber l'idée.

Je prend quand meme les conseils si qqn sait pourquoi les resultats sont faux.

Merci antoine.debyser pour ta patience !

Je n'ai aucune idée de la performance du truc. Mais voici les conditions de mon test.
M = factoriel(125)
La valeurs d'une case de "tab" est égale à son index.
Sur un quad-core à 2.6Ghz (Q8400 pour être précis), le temps de calcul total est de 8 ms.
Les résultats semblent correct à première vu.

Pardon je me suis mal fait comprendre :
les resultats des sommes sont faux, je ne trouve plus les meme choses qu'avec la boucle for classique.

Par rapport aux performances, je vois bien que mes 8 coeurs sont utilisés contrairement á précédemment mais le temps est multiplié par 4... J'aurais espéré gagner un peu de temps mais bon je vais chercher une autre solution.