Difficulté avec un code sans algo

Version imprimable

Bonjour à tous.
Je travaille actuellement pour mon stage en labo sur un code déjà écrit à mon arrivée. Malheureusement, ce code a été écrit par des physiciens qui n'ont pas pensé utile de faire un algorithme général ou même détaillé du programme ou encore d'utiliser des noms explicites pour les variables... :?
Donc, mon boulot est d'"optimiser" tout cela... En fait, le code est tel que tout le temps d'execution est dépendant d'une seule fonction essentiellement composée de boucles imbriquées, la fonction étant elle-même ancrée dans des boucles deux POUR imbriqués !!! :evil: Un truc horrible quoi... En effet, j'ai mesuré le temps d'execution pour un fonctionnement minimum =>~30 minutes !!!

Le programme en cause est un programme de calcul scientifique. Il calcule grâce à des matrices (d'où les boucles imbriquées) la modification de l'orientation des atomes d'une molecule suite à une déformation. L'exemple sur lequel on tourne est une petite molécule de 46 atomes et cela dure 30 minutes ! On voudrait pouvoir calculer les modifications atomiques de protéines de plusieurs centaines d'atomes !!!

C'est pourquoi je vous écris. Ce problème de manipulation de matrices me fait penser à une modification d'une image selon un filtre.

Voici l'appel de ma fonction LinMode en question dans le programme en C :
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 /*APPEL DE LinMode => Indicateurs de temps CallLinMode1 et CallLinMode2 */ CallLinMode1 = time(NULL); /*MODIFIE LE 05/04/06*/ printf("CallLinMode1 = %lf\n",CallLinMode1); k = 0; for (j = 0; j < Natomes; j++){ for (i = 0; i <= 2 ;i++) { if (CMOD[j][i] == 1) {/*par defaut on traite tous les modes, plus tard on pourra choisir */ LinMode(Natomes, j, i, k, nj, nk, En, err, dx, nl, gg, D, M); kk[j][i] = k; k = k+1; } } } CallLinMode2 = time(NULL); /*MODIFIE LE 05/04/06*/ printf("CallLinMode2 = %lf\n",CallLinMode2); TEMPS_BOUCLE_LINMODE = difftime(CallLinMode2,CallLinMode1) ; /*MODIFIE LE 05/04/06*/ printf("******************************************\n\n"); printf("temps en s = %lf\n", TEMPS_BOUCLE_LINMODE); printf("temps en min = %lf\n", TEMPS_BOUCLE_LINMODE/60) ; printf("\n\n******************************************\n\n");
et la fonction elle-même :
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 void LinMode(int Natomes, int N, int in, int k, int nj, int nk, double En, double err, double *dx,int *nl, int *gg, double **D, double **M) { time_t LM_BEGIN=time(NULL), LM_END ; double eps, *ddx , LM_Duree ; int i, j, n, nn, ii, it; ddx=vec(3 * Natomes); puts("LinMode\n"); eps = 10. * err; it = 3 * Natomes - 6; for (i = 0; i < 3 * Natomes; i++) { dx[i] = 0.; } ii = 3 * nl[N] + in; if (ii == it) { ii = it - 1; } printf("ii=%d\n",ii); dx[ii] = 1.; while (eps > err) { for (i = 0; i < it ; i++) { ddx[i] = dx[i]; if (i != ii) { for (j = 0; j < it ; j++) { if (i != j) { dx[i] += D[i][j] * dx[j]; } } dx[i] = -dx[i] / D[i][i]; } ddx[i] -= dx[i]; } eps = Norme(ddx,it); /* normalisation de ddx pas nécessaire !*/ } En = Energie(Natomes, dx, D); printf("Energie = %f\n",En); for (n = 0; n < Natomes - 3; n++) { nn = 3 * n; ii = gg[n] * 3; M[ii][k] = dx[nn]; M[ii + 1][k] = dx[nn + 1]; M[ii + 2][k] = dx[nn + 2]; } nn = 3 * Natomes - 9; M[3 * nk][k] = dx[nn]; M[3 * nk + 1][k] = dx[nn + 1]; M[3 * nj][k] = dx[nn + 2]; M[3 * Natomes][k] = En; M[3 * Natomes + 1][k] = 3 * N + in; LM_END=time(NULL) ; LM_Duree=difftime(LM_END,LM_BEGIN) ; printf(" Duree (en secondes) d'execution pour cet appel = %lf\n", LM_Duree) ; }
Comme vous le voyez, le nommage des variables est loin d'être explicite. Nous travaillons sur des machines Sun SunBlade 1500 ou sur PC actuellement mais nous souhaitons passer sur architecture parallèle prochainement. Mais avant cela, il est clair qu'un réarrangement de l'algorithme est nécessaire.
J'aimerais en effet décomposer mes boucles POUR et PENDANT QUE en sous-blocs de quelques lignes mais j'avoue mon impuissance... J'ai modifié LinMode afin de virer le PENDANT QUE eps > err FAIRE ... par un appel récursif dépendant de la variable eps... Mais cela ne compile pas... Outre le problème de compilation (mineur), une refonte de l'algo de LinMode est donc inévitable mais je coince un pue beaucoup... Avez-vous une idée SVP ?

06/04/2006, 17h40
gangsoleil

Bonjour,

Effectivement, le code est crade, ce qui n'aide pas à la compréhension de l'algo.

Je pense que si tu ré-écrivais ce code de façcon propre, cela te permettrait de bien mieux comprendre le code, et où se situent les pertes de temps.

Ensuite, tu parles de parallélisation. Saches que le fait d'optimiser un algorithme peut le rendre plus complexe à paralléliser.
Les optimisations de parallélisation ou de gain vitesse sur un mono-processeur ne sont pas les mêmes, et tu vas donc passer pas mal de temps à optimiser cet algo pour le refaire d'une autre manière derrière...

Dans tous les cas, pour optimiser un algo, il est nécessaire de l'avoir bien compris, et de comprendre pourquoi tel endroit prends du temps, et ensuite seulement chercher comment l'améliorer.

Peut-être que l'utilisation d'un profiler de code t'aiderait à mieux voir dans quelle partie de l'algo le temps se perd.
06/04/2006, 17h50
Jean-Marc.Bourguet

Petite note, c'est pas bien de poster foncierement le meme message dans deux forums differents avec des titres differents (ici et sur le forum sur le C).

Pour la proprete du code, tu verras pire.

Quelques remarques visibles a la premiere lecture:

ddx est alloue et jamais libere. Je sortirais l'allocation de la boucle si on veut des perf...

Je mettrais dx[i] dans une variable temporaire pour le sortir de la boucle for (j...)

C'est apparemment un code qui fonctionne en integrant des derivees partielles, je chercherais dans les algo d'analyse numerique quelque chose qui converge plus rapidement que cette variante de l'algo d'Euler.
06/04/2006, 18h01
panda31

Ben en fait, je l'ai d'abord mis en Algo le modo l'a viré et alors j'ai posté en C... On m'a dit c Algorithmique...

Ok pour les algo d'analyse numérique. Merci je v tenté ! :d
06/04/2006, 18h25
mat.M
Code:

1 2 3 void LinMode(int Natomes, int N, int in, int k, int nj, int nk, double En, double err, double *dx,int *nl, int *gg, double **D, double **M) {
on évite de programmer comme cela; au lieu de passer 30 paramêtres à une fonction on passe plutot une structure ou un pointeur de structure
Code:

1 2 3 4 struct{ int Natomes;.....} TAtome; void LinMode(TAtome *pAtome) {
Si c'est sous UNIX il faut obligatoirement avoir recours aux processus avec fork(), pid() et compagnie.. :wink:
06/04/2006, 18h48
Matthieu Brucher

Citation:

Envoyé par panda31

Ben en fait, je l'ai d'abord mis en Algo le modo l'a viré et alors j'ai posté en C... On m'a dit c Algorithmique...

Ok pour les algo d'analyse numérique. Merci je v tenté ! :d

Précision : tu l'as posté dans algo et dans C, mais tu voulais du C au début, donc j'ai ôté le premier message. Je t'ai invité à remettre un message ici si le problème n'était plus le C, mais à condition de mieux expliciter ton problème, sans recopier ton post dans l'autre forum.
06/04/2006, 19h43
panda31

si en plus le modo lit mes messages... LOL
Ben oui mais je savais pas par quoi commencer...
DSL
06/04/2006, 19h48
panda31

j'ai une chtite question : que choisir comme profiler ? Merci d'avance
06/04/2006, 19h54
Matthieu Brucher

Quelle plateforme ?
06/04/2006, 19h56
panda31

Solaris, Linux et Windows 2000/XP
07/04/2006, 09h43
panda31
Citation:
Envoyé par mat.M

Code:

1 2 3 void LinMode(int Natomes, int N, int in, int k, int nj, int nk, double En, double err, double *dx,int *nl, int *gg, double **D, double **M) {

on évite de programmer comme cela; au lieu de passer 30 paramêtres à une fonction on passe plutot une structure ou un pointeur de structure

Code:

1 2 3 4 struct{ int Natomes;.....} TAtome; void LinMode(TAtome *pAtome) {

Si c'est sous UNIX il faut obligatoirement avoir recours aux processus avec fork(), pid() et compagnie.. :wink:
Merci bcp, je vais me renseigner pour fork et pid (et exec() aussi je crois, non ?)
Je vais de ce pas modifier ma fonction avec une structure !