Discussion :

[jobherzt]

bonjour a tous, un probleme un peu vague aujourd'hui :-)

je developpe en collaboration avec une equipe de chimiste un petit programme qui fait du calcul assez voire tres violent.. ca fait quelques mois que je suis dessus, je ne suis pas un programmeur "pro" (je suis etudiant en maths) mais je pense avoir pas mal epuisé les possibilités d'optimisation de l'algo (environ 20 fois plus rapide qu'au debut, notamment en "specialisant" l'algo par rapport a des particularité des données traitées.)

seulement voila, on attaque la classe au dessus au niveau difficulté, et du coup ca commence a ne plus suffir. en fait, ils ont mobilisé 5/6 ordis qu'ils font tourner au maximum, et jusqu'ici ca allait bien, les calculs prenait entre 10 minutes et 4 jours...

seulement maintenant, au bout de 5/6 jours on n'obtient rien, et comme il est tres difficile de prevoir le temps que ca va prendre, on ne veut pas monopoliser des ordis pour rien.. donc a priori, il faut augmenter la puissance de calcul..

les questions, donc :
- est ce que quelqu'un a une idée miracle pour booster tout ca ? (ca coute rien de demander )

- dans la negative, je pense que le meixu est de commencer a regarder du cote du calcul distribué : au lieu de faire tourner 5 ordis sur 5 jeux de données differentes, on les fait tourner tous les 5 sur un seul, mais du coup on pourra au moins voir si les calculs qu'on veut faire sont du domaine du possible :-)

donc est ce quelqu'un aurait un lien vers un bon tuto qui parle de ca, une librairie qui fait ca bien (compatible linux/windows)...

en gros, l'algo est plus ou moins recursif binaire.. et comme rien n'est simple, on ne peut pas tellement couper le probleme au depart et donner un bout a chaque ordi ! puisque certaine "branche" peut etre terminée beaucoup plus vite que d'autre, il faudrait que chaque ordi puisse redemander dynamiquement du travail, cad soulager un autre ordi en lui prenant une partie de ce qu'il "projetait" de faire...

voila, ca n'est pas tres clair, (pour moi non plus :-) ), mais je vous remerci d'avance pour votre aide !

[joellel]

Si tu as un problème de temps de calcul, la récursivité coûte cher!
Je ne connais pas ton problème, mais si tu as le moyen de passer en itératif, tu gagneras du temps.

[jobherzt]

en fait, c'est deja en iteratif, meme si "l'esprit" est recursif.. fais-ce vraiment une grosse difference ???

pour simplifier, disons que j'ai un algo de la forme :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Soit A l'element de depart
soit P une pile
empiler A dans P
 
tant que P n'est pas vide
 
B<- depiler P
 
Tester B par rapport au probleme, traitement.. 
 
si le test n'a pas permis de conclure, couper B en B1 et B2
empiler B1 et B2
fin tant que

donc c'est bien de l'iteratif, mais on a bien le schema "diviser pour resoudre".

la solution a laquelle je pensais etais de mettre en place un systeme qui permettrais a un ordi qui a fini son taf de prendre une partie de la pile d'un autre ordi ( meme si ca n'est pas si simple)..

[Charlemagne]

Si, comme je le suppose, tu fais des calculs numériques, alors avant de distribuer le calcul, il vaut mieux utiliser les recettes de l'optimisation, (que finallement peu de gens connaissent).
Une liste non exhaustive:
-meilleure gestion de la mémoire cache (oui c'est possible)
-calcul vectoriel SIMD (SSE/SSE2/SSE3 pour les Pentiums)
-garder les valeurs importantes dans les registres, ça évite d'accéder continuellement à la pile
-développer les boucles (pas trop quand même)
-éviter les sauts conditionnels mal prédits qui brisent le pipeline
-inliner les fonctions => moins de saut, moins d'instructions exécutées, plus d'optimisations possibles
-utiliser un bon compilo: je pense à Intel C++ compiler (Windows ICL,Linux ICC) => exécutable plus rapide qu'avec GCC ou Visual. Pour mes programmes optimisés avec SSE, ICL est environ 2 fois plus rapide que visual ou GCC.
...

PS: Voici un document Intel qui traite de l'optimisation. Ca vaut à mon avis pas la peine de faire du calcul distribué, avant d'en avoir épuiser les idées (qui sont valables dans leur grande majotité pour d'autres architectures).
ftp://download.intel.com/design/Pent...s/24896612.pdf

[jobherzt]

merci bien, j'avais lu pas mal de trucs sur l'optimisation du code, mais rien de tout ce que tu cites (ou presque..)

-meilleure gestion de la mémoire cache (oui c'est possible)

je ne sais pas si on parle de la meme chose, mais mon prog est assez peu gourmand en memoire..

-calcul vectoriel SIMD (SSE/SSE2/SSE3 pour les Pentiums)

gnéé???

-garder les valeurs importantes dans les registres, ça évite d'accéder continuellement à la pile

a priori, je stocke des valeurs trigo, je precalcule ce qui intervient plusieurs fois.. c'est compris dans mon vitesse x20 cité ci dessus :-)

-développer les boucles (pas trop quand même)

j'ai essayé de limiter le nombre de boucle en regroupant.. mais a priori je n'ai aucune boucle dont je connaisse la borne sup a l'avance

-éviter les saut conditionnels mal prédits qui brisent le pipeline

ca, j'en ai entendu parler mais en pratique.. si je mets des conditions, c'est que j'en ai besoin :-)

-inliner les fonctions => moins de saut, moins d'instructions exécutées, plus d'optimisations possibles

ca je fais !

-utiliser un bon compilo: je pense à Intel C++ compiler (Windows ICL,Linux ICC) => exécutable plus rapide qu'avec GCC ou Visual. Pour mes programmes optimisés avec SSE, ICL est environ 2 fois plus rapide que visual ou GCC.
...

serieusement ?? je pensais que g++ se gavait pas mal... avec un -03, je pensais que ca donnerait deja un truc pas mal.. qu'est ce qui le rend si rapide ??

merci des tuyaux !

[poukill]

merci bien, j'avais lu pas mal de trucs sur l'optimisation du code, mais rien de tout ce que tu cites (ou presque..)


je ne sais pas si on parle de la meme chose, mais mon prog est assez peu gourmand en memoire..

gnéé???

a priori, je stocke des valeurs trigo, je precalcule ce qui intervient plusieurs fois.. c'est compris dans mon vitesse x20 cité ci dessus :-)

j'ai essayé de limiter le nombre de boucle en regroupant.. mais a priori je n'ai aucune boucle dont je connaisse la borne sup a l'avance

ca, j'en ai entendu parler mais en pratique.. si je mets des conditions, c'est que j'en ai besoin :-)

ca je fais !


serieusement ?? je pensais que g++ se gavait pas mal... avec un -03, je pensais que ca donnerait deja un truc pas mal.. qu'est ce qui le rend si rapide ??

merci des tuyaux !

SIMD = Single Instruction Multiple Data... C'est une architecture de données....

[10_GOTO_10]

- est ce que quelqu'un a une idée miracle pour booster tout ca ? (ca coute rien de demander )

Déjà, une idée toute bête consiste à dire au système de consacrer plus de temps au programme. Sous Windows ça se fait avec SetThreadPriority, et je pense qu'il y a l'équivalent sous Linux. Rien que ça divise le temps de calcul par deux.

[Médinoc]

Mais ça n'a pas vraiment d'effet si rien d'autre ne tourne, par contre...

[10_GOTO_10]

Il y a toujours un tas de trucs qui tourne sur un ordinateur: les services, le système lui-même. Et même quand il n'y a rien, il y a toujours un processus inactif dont la fonction... est de ne rien faire.
Quand je dis qu'on divise le temps de calcul par deux, je parle par expérience, sur un ordinateur qui ne faisait qu'une seule tâche (calculs sur des nombres premiers).

[jobherzt]

oui, effectivement, mais c'est assez heteroclite, on a 2 3 ordis entierement dispo ( mais sous windows, que voulez vous... donc obligé de se taper l'interface graphique et toutes les salo*** qui tournent en fond..), et d'autres ordi qui sont utilisé pendant la journée. donc on fout la priorité pas trop haut, comme ca ca gene personne, et la nuit ca repart a fond...

10_GOTO_10 > en fait, ca n'est pas si simple ! ce dont tu parles autorise le processus a prendre des ressources aux autres programmes. disons qu'il est prioritaire ( comme le nom l'indique).. mais a priori, s'il n'y a rien qui tourne, de toute facon il prendra toutes les ressources disponibles ! donc je ne suis pas sur qu'on gagane beaucoup...

millie> si, ca serait l'idée.. et en effet, il faut qu'ils partagent la pile de recursion

Luc Hermitte> oui, bien sur, j'avais jete un oeil..
c) je suis d'accord, j'ai la meme definition que toi !
d) est ce que jaurais un gain sur les operations elementaires ?? (notamment la division, c'est elle qui bouffe.)
e) oui, bien sur, sauf qu'une des optimisations TRES consequente de mon programme repose sur la connaissance permanente du resultat courant.. mais je pense, vu la longueur des calculs, qu'en l'echangeant toutes les minutes ca ira bien ! mais ca me semble quand meme compliqué... ca n'est pas vraiment mon rayon !! mais je vais essayer...

[Luc Hermitte]

d) C'est fort probable. C'est une bonne partie le principe des BLAS : fournir des calculs d'algèbre linéaire optimisés. Parce que le pipeline aura été utilisé à fond, parce que les spécificités de ta machine auront été exploitées, ...
Et si tu veux faire des inversions matricielle, alors il ne faut surtout pas hésiter. Il est courant que la programmation naïve introduise des biais dans les calculs, en plus de ne pas toujours être très efficaces.

e) "toutes les minutes" ?
N'est pas plutôt à ton "orchestreur" de transférer le dernier état des lieux aux machines qui ont terminé leur traitement et qui sont prêtes à passer à la suite ?
Ou peut-être qu'en bourrinant comme des sauvages pour que chaque machine diffuse via UDP les résultats de ses calculs. Seuleument si il n'y a pas besoin de grosse synchronisation.
Tu as de quoi t'amuser.