Difficulté avec un code sans algo

**panda31** · 06/04/2006, 15h30

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 !!!

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

**gangsoleil** · 06/04/2006, 17h40

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.

**Jean-Marc.Bourguet** · 06/04/2006, 17h50

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.

**panda31** · 06/04/2006, 18h01

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

mat.M · 06/04/2006, 18h25

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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..

**Matthieu Brucher** · 06/04/2006, 18h48

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.

**panda31** · 06/04/2006, 19h43

si en plus le modo lit mes messages... LOL
Ben oui mais je savais pas par quoi commencer...
DSL

**panda31** · 06/04/2006, 19h48

j'ai une chtite question : que choisir comme profiler ? Merci d'avance

**Matthieu Brucher** · 06/04/2006, 19h54

Quelle plateforme ?

**panda31** · 06/04/2006, 19h56

Solaris, Linux et Windows 2000/XP

**panda31** · 07/04/2006, 09h43

Envoyé par mat.M

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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..

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 !

Difficulté avec un code sans algo

Algorithmes et structures de données

Discussions similaires

Partager

Partager