Bonjour,
 
J'ai un petit souci, je ne sais pas comment optimiser cette fonction en C :
 
void  
baseline ( 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 ];
                           }
                 }
       }
}
 
En fait, je me suis renseigné, en gros il faut remonter le "if" parce qu'il coûte cher, voir pour une optimisation idéale l'éliminer (le code doit toujours rester équivalent à celui de début).
 
 
Merci pour votre aide.
 
Bonne journée.

Déjà, ta fonction, elle est censée faire quoi ? Parce qu'elle a pas un poil de commentaire, les noms des variables ne sont pas explicites sur leur contenu, et t'utilises même pas la balise code
 
Le if dépendant de la 2ème boucle, je vois pas comment le sortir.
 
Si tu dois optimiser ce code, je commencerais par donner des noms de variables compréhensibles et j'ajouterais du commentaire. Ca n’accéléra pas le temps d'exécution, mais ça accéléra celui de sa compréhension

Remplace a l'intérieur du deuxième for par:
 

 
T'aura déjà un léger gain d'opti avec le += qui sera pas affecté deux fois dans le cas i < j.
 
 
Comme dit rufo sans plus d'info tu pourras pas plus optimiser sans autre information...

Merci pour vos reponses.
 
En fait, dans un compte rendu, le prof nous demande seulement d'étudier et d'optimiser la fonction, et de justifier chaque modification du code (le code doit à la fin d'optimisation être le même que le code principal).
 
Il nous demande en fait d'optimiser la fonction, et de vérifier avec  gcc -O2 si le temps d’exécution s'améliore ou pas pour chaque optimisation de la fonction.  
 
 
Cordialement.  

Ben, tu pourrais mettre une partie du code en ASM

Oui, c'est une solution ( code assembleur ), mais sur le compte rendu on me demande sans assembleur !

Bonjour,
 
Je trouve des difficultés sur un travail "Optimisation en C".
Voila ce qu'il faut faire en gros :  
 
Il ya un code à optimiser, que nous appellerons "noyau".  
Il faut étuider les performances en L1, en L2, en L3 et en RAM.
 
Partie I
========
1) Ecrivez un driver permettant de mesurer la performance du noyau
2) Compilez le noyau avec gcc -O2
3) Mesurez la performance du noyau
4) Recommencez avec gcc -O3, gcc -O3 -march=native, icc -O2, icc -O3 et  
icc -O3 -xHost.
 
Partie II
=========
Pour cette partie,vous compilerez avec gcc -O2.
1) Mesurez la performance du noyau
2) Identifiez le goulet d'étranglement (ce qui limite les performances)
3) Proposez une optimisation (au niveau source)
4) Recommencez (rebouclez à l'étape 1) tant que vous arrivez à améliorer  
les performances. Vous pouvez soit repartir du noyau non optimisé, soit  
d'un noyau précédemment optimisé.
 
Partie III
==========
1) Utilisez des directives OpenMP pour paralléliser votre noyau.
2) Utilisez des intrinsics pour écrire/optimiser le code, voir modifiez directement l'assembleur.
 
 
 
J'ai réussi la partie I, mais je bloque sur la partie II et III (Optimisation du noyau)
 
voila le noyau :

 
Merci pour vos aides.
 
 
Bien cordialement.

Les sujets suivant ont été fusionnés à ce sujet par Gilou

• optimisation fonction "c"

"Ecrivez un driver permettant de mesurer la performance du noyau "  
 
Purée, c'est déjà du sacré niveau. C'est en quel cours qu'on te demande ça et dans quelle école ?

Salut,

Il faut chercher au niveau de la complexité algorithmique de ta fonction :
Ici la complexité de ta fonction et de N² et le plus simple pour l'optimiser et de passer ça complexité à Log(N).

Pour cela il faut supprimer/modifier le second "for" car c'est celui-ci qui pose problème dans la complexité.

Je te laisse chercher un peux avant de donné une réponse toute faire.

Bon courage

Re,
 
en fait j'ai fait ca :
 
1)  
dans un premier temps :

 
 
Cette fonction ajoute à chaque case de C son miroir dans b, n fois. Donc, déjà en une boucle je peux faire toute une partie des opérations :

 
 
Cela, nous donne le code suivant :

 
 
Soit donc en boucle intérieure "pour  j  entre 0 et  n  et  j  supérieur à  i faire,
Donc " pour j entre i (exclus) et n ".
 

 
 
Finalement, on tout du long on manipule le meme c[ i ], on peut passer par un registre temporaire :
 

 
 
mais je sais pas si c'est la meilleur optimisation.
 
Merci

Salut,

C'est l'optimisation la plus simple en tout cas.
En cherchant rapidement je suis tomber sur quasiment la même chose.

Tu ai bien en complexité log(N) car tu ne parcours plus deux fois ton tableau.

Par contre je comprends pas ton :

Tu n'a pas besoin de changer ce calcul ( il est imposer ).

Tu peux encore optimiser ta boucle en faisant du récursif mais c'est toujours un petit peu risquer ( risque de passer en overflow quelques part dans ton programme ).

PS : Cherche du coté des algorithmes de recherche ou de trie. Cela pourras te donner des pistes.

Re,
 
Franchement je ne peux pas aller plus loin que cette optimisation, par contre, m'est avis que l'ajout du a peut-être fait autrement, avec une seule boucle! En parcourant le tableau en sens inverse!  
 
J'explique  
 
j=0   rien  
j=1  
c[0]+=a[1]  
j=2  
c[0]+=a[2]  
c[1]+=a[2]  
j=3  
c[0]+=a[3]  
c[1]+=a[3]  
c[2]+=a[3]  
etc.  
 
En gros, je pense qu'il faut partir de la fin  
et puis tout mettre dans une seule boucle.
   

 
 
Là j'ai une seule boucle, de quoi laisser le compilo faire sa sauce pour le prefetch.
 
Quelque vous pensez ?
 
Mercii

ça à l'air cohérent.
 
Si lorsque tu trace tu obtient toujours le même résultat ( entre ton algo et celui de base ) tu es passé à une complexité de N.
 
Donc tu ne pourra pas faire mieux.
 
Bravo