Parallélisation d’une sum de préfixes (Openmp)

J’ai deux vecteurs, a [n] et b [n], où n est un grand nombre.

a[0] = b[0]; for (i = 1; i < size; i++) { a[i] = a[i-1] + b[i]; } 

Avec ce code, nous essayons de réaliser que a [i] contient la sum de tous les nombres de b [] jusqu’à b [i]. Je dois paralléliser cette boucle en utilisant openmp.

Le problème principal est qu’un [i] dépend d’un [i-1]. Le seul moyen direct qui me vient à l’esprit serait donc d’attendre que chaque numéro [i-1] soit prêt, ce qui prend beaucoup de temps. et n’a aucun sens. Y at-il une approche dans openmp pour résoudre ce problème?

Vous êtes Carl Friedrich Gauss au 18ème siècle et votre professeur d’école primaire a décidé de punir la classe d’un problème de devoirs nécessitant un calcul arithmétique répétitif. Au cours de la semaine précédente, votre professeur vous avait demandé d’additionner les 100 premiers nombres et, comme vous êtes malin, vous avez trouvé une solution rapide . Votre professeur n’a pas aimé cela. Il a donc proposé un nouveau problème qui, selon lui, ne peut être optimisé. Dans votre propre notation, vous réécrivez le problème comme ceci

 a[0] = b[0]; for (int i = 1; i < size; i++) a[i] = a[i-1] + b[i]; 

alors vous réalisez que

 a0 = b[0] a1 = (b[0]) + b[1]; a2 = ((b[0]) + b[1]) + b[2] a_n = b[0] + b[1] + b[2] + ... b[n] 

en utilisant votre notation à nouveau, vous réécrivez le problème

 int sum = 0; for (int i = 0; i < size; i++) sum += b[i], a[i] = sum; 

Comment optimiser cela? D'abord, vous définissez

 int sum(n0, n) { int sum = 0; for (int i = n0; i < n; i++) sum += b[i], a[i] = sum; return sum; } 

Puis tu te rends compte que

 a_n+1 = sum(0, n) + sum(n, n+1) a_n+2 = sum(0, n) + sum(n, n+2) a_n+m = sum(0, n) + sum(n, n+m) a_n+m+k = sum(0, n) + sum(n, n+m) + sum(n+m, n+m+k) 

Alors maintenant, vous savez quoi faire. Trouvez des camarades de classe. Demandez à chacun de travailler sur un sous-ensemble des nombres. Pour restr simple, vous choisissez la size est 100 et quatre camarades de classe t0, t1, t2, t3 puis chacun fait

  t0 t1 t2 t3 s0 = sum(0,25) s1 = sum(25,50) s2 = sum(50,75) s3 = sum(75,100) 

en même temps. Puis définir

 fix(int n0, int n, int offset) { for(int i=n0; i 

et puis chaque camarades de classe revient sur leur sous-ensemble en même temps à nouveau comme ça

 t0 t1 t2 t3 fix(0, 25, 0) fix(25, 50, s0) fix(50, 75, s0+s1) fix(75, 100, s0+s1+s2) 

Vous vous rendez compte qu'avec un camarade de classe prenant environ K secondes à faire l'arithmétique, vous pouvez terminer le travail en 2*K*size/t secondes, alors qu'une personne prendrait K*size . Il est clair que vous aurez besoin d'au moins deux camarades de classe pour atteindre le seuil de rentabilité. Donc, avec quatre camarades de classe, ils devraient finir dans la moitié du temps en tant que camarade de classe.

Maintenant, écrivez votre algorithme dans votre propre notation

 int *suma; // array of partial results from each classmate #pragma omp parallel { int ithread = omp_get_thread_num(); //label of classmate int nthreads = omp_get_num_threads(); //number of classmates #pragma omp single suma = malloc(sizeof *suma * (nthreads+1)), suma[0] = 0; //now have each classmate calculate their partial result s = sum(n0, n) int s = 0; #pragma omp for schedule(static) nowait for (int i=0; i 

Vous réalisez que vous pouvez optimiser la partie dans laquelle chaque camarade de classe doit append le résultat du camarade de classe précédent, mais depuis la size >> t vous ne pensez pas que cela en vaut la peine.

Votre solution n’est pas aussi rapide que votre solution en ajoutant les chiffres de comptage, mais néanmoins votre enseignant n’est pas heureux que plusieurs de ses élèves aient terminé beaucoup plus tôt que les autres. Alors, il décide maintenant qu’un élève doit lire lentement le tableau b à la classe et, lorsque vous rapportez le résultat, il doit également être fait lentement. Vous appelez cela être lié à la bande passante en lecture / écriture. Cela limite considérablement l'efficacité de votre algorithme. Qu'allez-vous faire maintenant?

La seule chose à laquelle vous pouvez penser est de faire en sorte que plusieurs camarades de classe lisent et enregistrent différents sous-ensembles de nombres dans la classe en même temps .