Optimiser un noyau

Bonjour,

Quelqu’un peut m'aider pour optimiser ce noyau avec :
1) Les directives OpenMP pour paralléliser le noyau.
2) Les intrinsics pour écrire/optimiser le code, voir modifiez directement l'assembleur.

Voila le noyau :

Code:

---

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

void kernel (int n, double a[n], double b[n], double c[n]) { int i, j; for (j=0;j<n;j++) { for(i=0;i<n;i++) { c[i]+=b[n-1-i]; if (i<j) { c[i]+=a[j]; } } } }

---

Merci d'avance.



Cordialement.

Je vois ce post-ci...

Puis, je vois ce post-là...

Et, d'un coup, je ne me dis pas du tout qu'en fait, tu veux que l'on fasse tes exercices de cours C à ta place.. ! :roll:

C'est pas ça, en fait j'ai réussi à faire la première partie avec l'aide des membres de forum, maintenant, j'ai besoin d'aides sur la deuxième partie (qui est plus compliquée que l'autre) !!

Deuxième partie de quoi?

Si ce n'est pas ça, c'est quoi ?

Les forums sont là pour fournir de l'aide, mais c'est contre notre philosophie de faire ton travail à ta place. Ta demande est tellement vaste qu'elle s'apparente à "faites mon travail". Montre-nous ce que tu as déjà fait, explique nous sur quels points tu bloques ou tu doutes, et là on pourra t'apporter une aide précise et utile.

J'ai fait des efforts (des recherches bien évidement)

Pour faire la parallélisation il faut en fait que le "n" soit supérieur à 100 miles, et si c'est le cas faut que je fais : pragma OpenMP parallel for sur la première boucle

et sinon pour optimisation final j'ai fais ça :

Code:

---

1 2 3 4 5 6 7

a_cumul=j=0; for (i=n-1;i>0;i--) { a_cumul+=a[i]; c[i]=a_cumul+n*b[j++]; } c[0]=n*b[j];

---

et du coup je passe de N carré à N (coté complexité).

Bonjour,

Il y a la première optimisation de Foetus dans l'autre discussion.

On peut également réécrire le code ainsi :

Code:

---

1 2 3 4 5

pour j de 0 à n-1 // boucle 1 pour i de 0 à n-1 // boucle 1.1 c[i] += b[n-1-i] pour i de 0 à j-1 // boucle 1.2 c[i] += a[j]

---

La boucle 1.1 est exécutée n fois et ne dépend pas de j dans les calculs. On peut donc la sortir de la boucle 1 :

Code:

---

1 2 3 4 5

pour i de 0 à n-1 // boucle 0 c[i] += n * b[n-1-i] pour j de 0 à n-1 // boucle 1 pour i de 0 à j-1 // boucle 1.1 c[i] += a[j]

---

La boucle 0 est facilement paraléllisable. Vois-tu comment réduire les boucles 1 et 1.1 ? combien de fois ajoute-t-on a[j] à tous les c[i] ? Fais quelques essais à la main ...