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

[Charlemagne]

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

Alors a priori pas besoin d'optimiser la gestion de la mémoire cache.
Mais peut-être les temps d'accès:
-chargement de mémoire contigüe
-prefetch

gnéé???

Les instructions SIMD sont de loin la meilleure façon d'optimiser les caculs numériques. SSE1,SSE2,SSE3 sont les successeurs de MMX.
Je vais donc être un brin sévère ici: mais on ne peut pas parler d'optimisation, tant qu'on n'utilise pas les instructions de calcul parallèles.

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

Je parle des registres, pas de la mémoire. Le truc consiste ici à limiter les accès à la mémoire (goulot d'étranglement pour le processeur).

Au fait, si tu veux des fonctions mathématiques (trigonométrique et autres) très optimisées, il existe la bibliothèque gratuite d'Intel "Approximate Math Library".

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

Et alors, aucun problème. On ne connait quasiment jamais l'intervalle lors de la compilation. Tu peux t'inspirer du "Duff's device".

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

Je me doute bien qu'on met pas des sauts conditionnels pour le plaisir. Y'a quand même des trucs:
-mettre le code le plus vraissemblablement exécuté dans la partie du "then"
-switch
-_min & _max au lieu de min & max
...

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

Très sérieusement!!
J'étais moi aussi surpris à l'époque (Y'a déjà 5-6 ans, mais c'est toujours d'actualité)
J'ai comparé les codes compilés là où les différences de vitesse étaient sensibles, et je suis pas loin de penser que Visual et GCC sont de la m...
Je comprends pourquoi certaines personnes programment encore des bouts de codes en assembleur avec de tels compilos.

Il faut dire que mes calculs numériques sont très optimisés (SSE...), donc pour un programme en C "classique" (avec tout plein de goulots d'étranglement), les différences de vitesses ne sont probablement pas aussi sensibles.

[themadmax]

Petite idée, quand je lis je decoupe ma pile en deux: Tu peut pas crée different thread, qui pourrai booster ton prog sur une machine multiprocesseur.

[jobherzt]

et be, c'est bizzare, j'avais parcour 2 3 tutos, et notamment le "epingle : de la rapidité du code" ci dessus, mais jamais entendu parler de tout ca...

c'est quoi la difference entre min et _min ?

tu aurais des tutos sur les concepts dont tu parles ?

pour les fonctions mathématiques tres optimisées, en fait je n'utilise pas directement des types c++, donc j'ai defini moi meme pas mal d'operation de bases, mais a priori je n'utilise rien d'autre que les 4 operations elementaires.

merci bien, en tout cas !! c'est toujours bon a prendre, meme si je pense que le calcul distribué va quand meme etre un passage obligé !

[edit]
themadmax> c'etait justement l'idee premiere, repartir le travail sur plusieurs ordi qui se "passerait" des bouts de pile suivant la charge qu'ils auraient, genre "j'ai fini avant toi, passe moi 2 3 trucs a faire :-)"... mais je n'ai pas de multiprocesseur sous la main, par contre j'ai les ordi de tout un labo :-)

[Charlemagne]

et be, c'est bizzare, j'avais parcour 2 3 tutos, et notamment le "epingle : de la rapidité du code" ci dessus, mais jamais entendu parler de tout ca...

Je l'ai dit, peu de gens savent réellement optimiser les calculs.
Mais tout le monde croit savoir...

c'est quoi la difference entre min et _min ?

- 'min' c'est la version habituelle avec un 'if' ou éventuellement un '?:' => saut conditionnel mal prédit une fois sur deux => pipeline du processeur brisé
- '_min' est défini quelque par dans les entêtes de Visual: même calcul mais sans saut.
Il est possible de suprimer des sauts conditionnels pour plusieurs calculs de base, notamment avec MMX/SSE

Entre parenthèses, les futures nouveaux Intel Core Duo doublent (théoriquement) la vitesses des instructions SSE. Le gain ne sera sürement pas aussi important pour les calculs sur des scalaires. Le fossé se creuse encore plus.

tu aurais des tutos sur les concepts dont tu parles ?

La doc dont je donne le lien plus haut est pas mal, après il faut chercher...

[jobherzt]

ok, je vais regarder !!

je garde quand meme l'idee du calcul distribué sous le coude, vu que j'ai un paquet d'ordi a ma disposition, ca serait dommage de ne pas optimiser leur utilisation !!

[NewbiZ]

Je ne prétends pas être un spécialiste (loin de là), mais si je peux rajouter ma petite pierre à l'édifice :

+ Même si tu n'utilise pas beaucoup de mémoire, des accès récurrents et répétés peuvent ralentir énormément le programe. La solution la plus simple dans ce cas est un "placement new".
Le principe est simple, tu alloue préalablement un espace mémoire sur la heap, et ensuite tu te sers de cet espace pour y allouer tes variables.

Code :

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

1
2
3
char * memoryBuffer = new char [1000];
int* a = new (memoryBuffer) int; // placement new
int* b = new int; // new classique

+ Vérifies systématiquement les adresses de tes allocations. Stoques tes word sur des adresses %2, tes double-word sur des adresses %4, tes double-word sur des adresses %8... Comme cela a été dit plus haut, la mémoire est le principal goulot d'étranglement pour le processeur, il faut accélérer à tout prix ses accès.

+ Dès que possible utilise des const Ref&.

+ La pile est une zone mémoire, y accéder est donc lent, stoques tes arguments dans un registre.

+ Utilise des heuristiques pour connaitre les calculs qui seront lents, et ceux qui seront plus rapides.

+ Mets toutes les fonctions triviales en inline.

+ Ne dénigre pas les const pour tes getters.

+ Favorise la transmission des données par référence plutot que par valeur. Pars du principe que toute duplication de donnée en mémoire peut être effectuée par un passage de référence.

+ Utilise les instructions SIMD au maximum de leurs capacités.

[loufoque]

- 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 :-)

Voir du côté de MPI peut-être.
Ou OpenMP.

[jobherzt]

loufoque> ouaip, c'est aussi ce que j'avais trouvé, mais je ne comprends pas tout a fait la difference d'usage entre les 2. sinon, il y a clusterknoppix, basée sur openmosix... mais faire du calcul scientifique sur un liveCD ca me laisse reveur !

Je ne prétends pas être un spécialiste (loin de là), mais si je peux rajouter ma petite pierre à l'édifice :

+ Même si tu n'utilise pas beaucoup de mémoire, des accès récurrents et répétés peuvent ralentir énormément le programe. La solution la plus simple dans ce cas est un "placement new".
Le principe est simple, tu alloue préalablement un espace mémoire sur la heap, et ensuite tu te sers de cet espace pour y allouer tes variables.

Code :

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

1
2
3
char * memoryBuffer = new char [1000];
int* a = new (memoryBuffer) int; // placement new
int* b = new int; // new classique

je ne connaissais pas, mais je n'utilises pas de pointeur, ni de tableau dynamique.. je tourne uniquement avec des vecteurs.. d'ailleurs, un profiling me fait apparaitre l'operateur vector[] en tete du temps de calcul

+ Vérifies systématiquement les adresses de tes allocations. Stoques tes word sur des adresses %2, tes double-word sur des adresses %4, tes double-word sur des adresses %8... Comme cela a été dit plus haut, la mémoire est le principal goulot d'étranglement pour le processeur, il faut accélérer à tout prix ses accès.

je crois que je vois l'idée.. mais comme je le disais, je traite les cas un par un, et chaque traitement n'ajoute rien en memoire. a part la pile de recursion, il n'y a pas de changement de taille.

+ Dès que possible utilise des const Ref&.

ca j'essaie :-)

+ La pile est une zone mémoire, y accéder est donc lent, stoques tes arguments dans un registre.

je vais chercher ce qu'est un reistre, j'ai deja vu ca, mais je ne sais pas encore en quoi ca ameliore le schmilblick

+ Utilise des heuristiques pour connaitre les calculs qui seront lents, et ceux qui seront plus rapides.

j'ai utilisé gcc avec l'option qui vont bien pour faire du profiling.. c'est la meme idée ? comme de bien entendu, j'ai une fonction qui prend 70% du temps de calcul, un truc qui optimise les données avant chaque traitement, un peu comme la 2-opt dans un algo genetique.

+ Mets toutes les fonctions triviales en inline.

ouaip

+ Ne dénigre pas les const pour tes getters.

+ Favorise la transmission des données par référence plutot que par valeur. Pars du principe que toute duplication de donnée en mémoire peut être effectuée par un passage de référence.

j'essaie aussi. mais a priori, le passage par reference s'oppose justement a la notion de duplication ?? en tout cas, c'est le but d'eviter la copie..

+ Utilise les instructions SIMD au maximum de leurs capacités.

ca je decouvre, je vais voir ce que ca donne...

merci !

[Luc Hermitte]

Tu es allé voir sur le fil au sujet des performances du C++ ?

a) Même si tu n'utilises pas beaucoup de mémoire, des accès récurrents et répétés peuvent ralentir énormément le programe. La solution la plus simple dans ce cas est un "placement new".
Le principe est simple, tu alloue préalablement un espace mémoire sur la heap, et ensuite tu te sers de cet espace pour y allouer tes variables.

Code :

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

1
2
3
char * memoryBuffer = new char [1000];
int* a = new (memoryBuffer) int; // placement new
int* b = new int; // new classique

b) Vérifies systématiquement les adresses de tes allocations. Stoques tes word sur des adresses %2, tes double-word sur des adresses %4, tes double-word sur des adresses %8... Comme cela a été dit plus haut, la mémoire est le principal goulot d'étranglement pour le processeur, il faut accélérer à tout prix ses accès.

c) Utilise des heuristiques pour connaitre les calculs qui seront lents, et ceux qui seront plus rapides.

a) L'intérêt de ceci pour les types POD m'échappe. Pas parce qu'il n'y aucun intérêt à n'allouer qu'un seul int (car tu n'as donné qu'un exemple), mais parce que le new de placement ne va strictement rien faire pour des types POD -- IIRC. Pour des objets, c'est autre chose.

Et si après c'est pour écrire notre gestionnaire de mémoire qui va tenter de se souvenir où sont les emplacements dispos, ... C'est compliqué. Je passerai d'abord par des resizes de vecteurs -- dans le cas de vecteurs de données POD s'il doit manipuler des ensembles de données de même type. Puis je lorgnerai du côté de pools de données/buffers.

b) En C++, une allocation est censée renvoyer une exception. Il n'y a pas de test à faire -- autre qu'un catch de haut niveau, dans la pile d'appel

c) Nous n'avons pas la même définition d'heuristique
Chez moi, c'est une fonction pifométrique qui est censée nous aider à améliorer, voire carrément écrire, nos algos au prix d'une perte de précision. -> "Heuristique de l'algo A*", "Heuristique d'évaluation d'un individu dans une population dans un algo génétique", ...

d'ailleurs, un profiling me fait apparaitre l'operateur vector[] en tete du temps de calcul

En mode release avec l'inlining activé, l'opérateur [] des vecteurs est censé n'avoir aucun surcoût.

d) pour les fonctions mathématiques tres optimisées, en fait je n'utilise pas directement des types c++, donc j'ai defini moi meme pas mal d'operation de bases, mais a priori je n'utilise rien d'autre que les 4 operations elementaires.

e) je pense que le calcul distribué va quand meme etre un passage obligé !

d) Il existe quantité de bibliothèques de calcul numérique hautes performances pour le C++. Surtout dans le domain matriciel. Dans les divers apports, il y a :
- meilleure utilisation du pipiline
- meilleure utilisation de la mémoire cache
- apport d'une écriture de haut niveau
- support de la programmation répartie
Chaque bibliothèque existante va aller plus ou moins loin dans chacune de ces directions.

e) Quand au calcul distribué, attention de ne pas échanger plus de données que nécessaire. Il serait dommage de saturer les perfs parce que tu ferais trop d'échanges entre la machine principale qui distribue les calculs avec celles qui calculent. Même genre de problème si l'élement dimensionnant n'est pas le processeur, mais le disque partagé entre toutes les machines -- ce qui peut arriver plus vite pour une compilation répartie que pour des calculs répartis.

[millie]

c'etait justement l'idee premiere, repartir le travail sur plusieurs ordi qui se "passerait" des bouts de pile suivant la charge qu'ils auraient, genre "j'ai fini avant toi, passe moi 2 3 trucs a faire :-)"... mais je n'ai pas de multiprocesseur sous la main, par contre j'ai les ordi de tout un labo :

Tes ordinateurs ne sont il pas en réseau ? Car il y a sûrement moyen de faire ça dans ce cas. Il peut y avoir des requêtes dans une file d'attente commune, pour ne pas perdre en efficacité, les ordinateurs peuvent regarder la file toutes les 30 sec par exemple (ou plus, à toi de voir). (quoique, ça ne doit pas trop changer)

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