Bonjour à tous    
 
Je souhaiterais avoir quelques conseils sur l'optimisation des boucles pour le calcul de quatres somme imbriquées telles que :
 
Ni    Nj   Nk   Nl
∑    ∑    ∑     ∑ ( F[i][j]*G[k][l]*H[i][k])  
i=0 j=0  k=0  l=0
 
C'est une version désossée de mon calcul afin de mettre en évidence le fait que j'ai une fonction F qui dépend de (i,j) multipliée par une fonction G dépendant de (k,l) et d'une troisième fonction H dépendant de (i,k). Le problème est que le nombre d'itérations pour chaque boucle est énorme :
Ni~Nk~5000
Nj=Nl~1 000 000
Donc au total, j'ai 5000²*1000000²=25e+18   !!!! J'en ai pour des semaines de calcul (voir des mois ?!). Si je n'avais pas la fonction H(i,k), je pourrais séparer les sommes telles que :
 Ni    Nj               Nk    Nl
(∑    ∑  F[i][j]) *( ∑      ∑  G[k][l])
  i=0 j=0              k=0  l=0
 
Je n'aurais alors que 2*5000*1000000=1e+10 et c'est déjà énorme   !  Mais de toute façon, la fonction H dépend de i et de k, donc je ne peux séparer les sommes sur (i,j) et (k,l).
 
Y aurait-il des algorithmes d'optimisation me permettant de réduire les quantités de calcul   ? Je suis en thèse de doctorat donc ce travail est primordial pour moi   , je vous serais donc très reconnaissante si vous pouviez m'aider.  

La première idée qui me viens reste quand même la simplification de ta méga somme.
 
Voire si c'est vraiment impossible de tourner le problème autrement, trouver un encadrement calculable plus facilement qui te permette d'avoir un résultat assez précis pour tes besoins.

deja :

- utiliser une bonne méthode pr stocker tes données : stockage NRC : http://forum.hardware.fr/hfr/Progr [...] m#t1654178
- faire du tiling de boucle : http://forum.hardware.fr/hfr/Progr [...] m#t1654178
- faire du déroulaeg de boucle de l'ordre de rgandeur de la taille du pipeline du processeur
- faire du SIMD avec SSE2 (intel) ou Altivec(PowerPC) : cdf ma signature

En gros, faut essayer d'implanter cette somme de manière la plus "mrmory firendly" en evitant de merder partout.

Factoriasation (en notant ∑i(Xi) la somme des Xi):

Dans la dernière formule, on voit que les termes ∑j(F[i][j]) et ∑l(G[k][l]) peuvent n'être calculés qu'une seule fois pour chaque couple (i,k).
L'ordre de grandeur du nombre d'itérations deviens: i*k*(j+l) ~ 5000²*(2000000) ~ 5*10^13 ~ 2^40
Tu y gagne quelques siècles, mais c'est encore trop long je pense... Pour raccourcir encore, il faut essayer de développer les fonctions F,G,H et les factoriser de la même manière, si c'est possible.

merci à vous deux de m'avoir répondu aussi rapidement   .
Kyntriad, j'ai effectivement réussi à réorganiser mes boucles et les blocs d'instructions à l'intérieur, je suis passée de 25e+18 itérations à 25e+12   itérations. Maintenant, je vais prendre en compte les idées de Joel : je comprends bien ce qu'est le déroulage de boucle, donc je vais essayer d l'appliquer correctement. Le tiling, ce n'est pas tout à fait clair pour moi   , donc je vais faire un peu de recherche biblio pour m'informer de ces techniques.
Merci à vous deux   , je relancerais un message si après tout cela, je n'y arrive toujours pas.
 

oui, effectivement, j'en suis aussi arrivée à cette conclusion en remaniant mes sommes, d'ailleurs j'ai encore gagné un facteur 2 en sortant ∑j(F[i][j]) de la somme sur k. Mais je suis d'accord avec toi, c'est encore beaucoup trop long! Mais comme je l'ai dit à Joel, je vais suivre ses idées, on verra si j'y arrive    
 
Merci beaucoup
 

As-tu beaucoup de zéros dans tes valeurs ? Si c'est le cas, tu peux gagner énormément de temps en évitant beaucoup de calculs. Car, comme tu le sais sans doute : zéro fois tout-ce-que-tu-veux égale toujours zéro. Et si le zéro doit multiplié au résultat du calcul d'une grosse boucle... c'est toute la grosse boucle qui peut être court-circuitée !

Autre piste d'optimisation : la parallélisation du calcul. Ce genre de calcul est très facile à paralléliser massivement, et si ta machine dispose de plusieurs (voire de nombreux) processeurs, tu gagneras un facteur substantiel en exploitant l'ensemble des ressources processeur de ta machine au lieu de n'utiliser qu'un seul processeur (voire une partie d'un seul processeur).

avant de passer en multi thread, optimisez le monothread me parait bien
Et rien qu'en utilisant des trucs simples, tu as des gains de l'ordre de 6 à 10

Question bete. Les compilo actuels ont-ils vraiment besoin qu'on leur déroule les boulces a la main?

si les bornes ne sont pas des constantes et qu'il y des strcutures de controels dedans : Oui
Et dérouler ne suffit pas toujours, reduction, rotation de registre etc

Joel F> Ca dépend lesquels, et ça dépend des langages. En C/C++, c'est le cas, mais uniquement parce qu'on travaille assez près de la machine. Dans d'autres langages ou d'autres environnement d'exécution, on ne s'amuse pas à cela, et on laisse faire le compilateur à l'exécution s'occuper de ça (les machines virtuelles Java et OCaml sont réputées précisément pour cela)

ouasi mais perso, je fait pas de HIGH PERFORMANCES computign en JAVA :[, ca me parait assez antinomique

Détrompe-toi, ça ne l'est plus du tout depuis 2 ou 3 ans. Pour ma part, j'observe de plus en plus souvent des programmes Java qui tournent plus vite que leurs équivalents C++...

Hmm. Même si je trouve aussi que ça s'est amélioré dernièrement, j'ai du mal à croire qu'à qualité de code égale, un programme Java soit plus performant que le même en C++.

EN HPC ?? j'y crois pas un dixieme de cycle

Au temps pour moi, Joel F : à ma connaissance, Java n'est pas utilisé en calcul très intensif dans le monde des superordinateurs massivement parallèles. Dans ce secteur-là (comme dans d'autres), l'inertie des habitudes et des préjugés est encore lourde, et on utilise surtout C (voire FORTRAN !) pour programmer. J'insiste au passage sur le fait que ce sont surtout les habitudes (et les a priori) qui font que l'on utilise toujours ces langages. Alors même que leur puissance de modélisation est pitoyable, et que leur supériorité de performance n'est pas vraiment démontrée (en tout cas, sur des machines dites "classiques", c'est le contraire qui l'est).
 
Mais l'immense majorité des gens qui font du calcul intensif ne dispose pas de ce genre de matériel, seulement de PC ou de stations/serveurs UNIX un peu gonflés (voire d'une grappe de telles machines quand ils sont un peu plus fortunés). Et là, Java est facilement disponible, et il a déjà prouvé qu'il tenait tout à fait tête.

on parle bien de JAVA, ce langage qui s'exécute en s'INTERPRETANT dans une MACHINE VIRTUELLE ... Deja comparait au système d'accés, d'allocation méméoir et de réutilisation des registres et du cache, FORTRAN (voire même C) à encore 150 ans d'avance.
 
Tu prends LINPACK et tu fais le test en JAVA, et on en reparle :E
Les épiphénoménes dus à des incompetents notoires en C++/C/FORTRAN mis à part (paske moi aussi je peut coder du JAVA de merde si il faut vraiment biaisé les tests)
 
Le seul endroit ou ej vois du JAVA dans le HPC, c'est pour des applis types grilles ou de toute manière passer 10 jours ou 15 sur 10K machines, ils s'en foutent.
 

troll

OK file moi UN papier ou on comapre une vrai appli HPC java à la même appli en C et on en reparle

je parle pas pour toi joel, mais pour BifaceMcLeOD qui compare Java et C, alors qu'il est évident qu'il n'y connait apparemment pas grand chose: il avoue lui même n'être pas capable de modéliser un programme en C.

 
OK faut que j'arrive à lire avec 0g de caféine dans le système sanguion      

Apparemment, c'est toi qui ne connais pas grand chose à Java et aux langages autres que C et FORTRAN. En tout cas, tu sembles être la parfaite illustration de ce que j'avançais concernant les habitudes et les a priori sur les différents langages de programmation et environnements d'exécution.
 
Les machines virtuelles Java actuelles compilent nativement, à la volée, le bytecode lorsqu'il est utilisé de manière récurrente : elles ne l'interprètent pas bêtement. Une fois compilé, ce code est aussi rapide voire légèrement plus rapide qu'un code C équivalent (c'est ce que les mesures montrent). Ces mêmes machines virtuelles sont écrites pour allouer les registres de manière optimisée par la machine sur laquelle elles tournent (le compilateur C sait le faire, alors pourquoi une machine virtuelle qui compile du code nativement ne saurait-elle pas le faire ?).
 
Mais contrairement au compilateur C, une VM possède des informations sur le flot d'exécution dont ne pourra jamais disposer le compilateur C (il faudrait qu'il exécute le programme pour cela). Cela permet à la VM Java d'effectuer des optimisations globales totalement impossibles à réaliser en C parce que le compilateur ne peut pas deviner ce qu'il y a derrière des pointeurs (c'est ça, entre autres, qui rend le code Java compilé nativement plus rapide que le code C équivalent).
 
Par ailleurs, les mesures montrent que la gestion mémoire directe par pointeur et désallocation explicite n'est pas la méthode la plus efficace pour gérer la mémoire : les ramasse-miettes générationnels d'aujourd'hui savent éviter bien mieux la fragmentation inévitable de la mémoire lorsque les allocations sont nombreuses. Sur le long terme, la mémoire bien moins fragmentée rend le programme toujours aussi rapide qu'au premier jour (ce n'est pas pour rien qu'on privilégie Java pour implémenter des serveurs qui doivent répondre aux requêtes simultanées venant de dizaines de milliers de clients, avec un temps de panne ou d'arrêt annuel inférieur à la journée voire à quelques heures...).
Et quand les études montrent que dans l'industrie (pourtant, il n'y a pas que des brêles dans l'industrie...), 70% des bugs sont des bugs mémoire (accès à des blocs mémoire déjà désalloués ou partiellement initialisés, pointeurs ballants menant à des fuites mémoire), un système qui élimine ces bugs par construction (le ramasse-miettes) est plutôt le bienvenu.
 
Enfin, tu as déformé mes propos sur la modélisation : je n'ai pas dit que j'étais incapable de "modéliser un programme en C". J'ai dit que C (ou pire encore, FORTRAN) sont des langages dont la puissance d'expression est pauvre en terme de modélisation. Ce n'est pas pour rien que pour toutes les problématiques complexes dans le monde du logiciel, on utilise systématiquement l'objet depuis près de 10 ans (dans l'industrie de manière généralisée, j'entends, parce qu'en fait, l'objet existe et est utilisé depuis les années 70 : le langage objet ancêtre, c'est Simula, créé en 1960, 9 ans avant le langage C). Parce que l'objet a prouvé sa grande supériorité en matière de modélisation statique et dynamique d'objets ou d'entités du monde réel, par rapport aux outils procéduraux (comme le langage C) voire simplement structurés (comme le langage FORTRAN). A tel point que même FORTRAN a été transformé pour en faire un langage objet, au début des années 2000. Sauf que les compilateurs optimisants que tu évoques travaillent avec FORTRAN 77, donc pas avec les extensions objets, qu'ils ne savent pas optimiser (de toute façon les bibliothèques n'exploitent pas vraiment ces extensions).

bon ben montre alors

Alors là, tu les surestime malheureusement

Et comme j'aime pas passer pour un frustré borné :
 
http://www.idiom.com/~zilla/Comput [...] hmark.html
 
Alors je concede quelque points :
 
1/ le JIT compilation : Un truc qui a tellement bien était marketer que les non spécialistes de JAVA n'en ont guère entendu parler alors que ça à l'air sexy :[
2/ L'amélioration de VM et de leur implantation depuis 1995
 
Par contre :
3/ Dire que le GC garantit la localité pour le cache etc .. ok. Un programme C bien écris (tuilage,deroulage etc) le fait aussi :[
4/ Aller sortir des benchs de C++ qui date de 199x est d'une mechanceté crasse : les compilos était à chier, l'implant de std aussi.
5/ Toujours pour C++, le coup de 'ca coute cher de renvoyer un objet" est à ranger - et la on st d'accord - dans la même boite qu emon "Java c'ets lent". Les références c'est pas fait pour les clébards comme les idomes de lazy evaluation
6/ Compiler avec gcc quand on veut de la performance est une abérration : ICC c'est pas fait pour les chiots ouzbéques.
 
Par contre je réitére. Quid d'un bench style LINPACK ou DARPA en JAVA ?

La lecture et l'étude de l'algorithme de GC montre que, plus la condition de déclenchement du ramasse miette est complexe, plus l'allocation mémoire est lente. Sans cette condition, l'algo GC devient l'algo d'allocation dynamique. Ensuite toute politique d'allocation (pools, pointeurs comptés, v-listes, ...) peut aussi bien être appliquée aux deux méthodes.
 
Supposons que l'on ait les fonctions alloc()/dealloc() qui allouent/désallouent de la mémoire en un temps T avec la meilleure politique possible, et qui maintienne une variable globale "memoire_libre":

 
oilà, ya une ligne en plus... qui sert non pas à aller plus vite, mais à s'assurer qu'il n'y ai pas de fuite mémoire.
 
Le GC, c'est un peu comme une couche culotte: c'est pas pratique pour courrir, mais ça évite les fuites.

Avec un bon compilateur, 2-3 directive OpenMP bien placé ca peut le faire.

 
oui si ICC ou autre bon compilo de disponible

J'ai réfléchi vite fait donc il y a peut-être un truc qui m'échappe, mais tu as plein de trucs indépendants dans ta somme. En factorisant, au final, il faut calculer (Si veut dire somme sur i) :
 
Si( Sj( Fij * Sk( Hik * Sl(Gkl) ) ) )
 
Tu commences par calculer un vecteur A de Nk éléments : Ak = Sl(Gkl). Ca prend (Nl - 1) aditions. Il te reste à calculer Si( Sj( Fij * Sk( Hik * Ak ) ) ).
 
Tu calcules un vecteur B de Ni éléments : Bi = Sk( Hik * Ak ). Ca prens Nk multiplications et (Nk - 1) additions. Il te reste à calculer Si( Sj( Fij * Bi ) ), qui s'écrit aussi Si( Bi * Sj(Fij) ). Tu peux libérer A.
 
Tu calcules un vecteur C de Ni éléments : Cj = Sj(Fij). Ca prend (Nj - 1) additions. Il te reste à calculer Si( Bi * Ci ).
 
Tu calcules ta valeur finale V = Si( Bi * Ci ). Ca prend Ni multiplications et (Ni - 1) additions. Tu peux libérer B et C.
 
Au final ça n'a pris que (Nl + Nk + Nj + Ni - 4) aditions et (Nk + Ni) multiplications, pour un total de 2,020,000 opérations. J'ai ratté quelque chose ?

Rien que cette phrase montre le peu de connaissances et d'expérience que tu as du sujet. Et ton pseudo-algo qui suit est tellement simpliste qu'il en est ridicule : un GC ne fonctionne pas tout seul, il fait systématiquement partie d'un gestionnaire de mémoire qui possède des structures de données élaborées pour modéliser l'usage de la mémoire, les zones libres et occupées, etc..
 
Par ailleurs, il n'y a pas un, mais des algorithmes de GC, qui suivent chacun une stratégie de gestion mémoire particulière. Il n'y a pas de stratégie de GC universelle : certaines stratégies de GC ont plus appropriées pour certains types de programmes, d'autres stratégies pour d'autres types de programmes. Tout dépend de la manière dont le programme alloue de la mémoire (par exemple, beaucoup de petits blocs et peu de gros blocs, ou le contraire ; beaucoup de blocs alloués pour un court laps de temps et peu pour de longues périodes, ou le contraire ; etc). Par ailleurs, certains GC se "déclenchent" comme tu dis, ralentissant le reste du programme pendant un laps de temps (qu'on essaie être le plus court possible), le temps de libérer de la mémoire ; mais tant qu'il reste de la mémoire libre, il n'y a aucune raison que les allocations soient ralenties (puisque le gestionnaire mémoire sait en permanence où il y a de la mémoire libre). Par ailleurs, d'autres GC fonctionnent en parallèle, en permanence ; et là encore, les allocations ne sont pas ralenties au fur et à mesure de la consommation mémoire, puisque de la mémoire est libérée en permanence. Enfin, certains GC sont hybrides, par exemple en libérant la mémoire au fil de l'eau pour les blocs à courte durée de vie, et en se reposant sur un Mar&Sweep plus classique pour ceux à longue durée de vie.
 
Tout cela sachant que le GC devient particulièrement intéressant (parce que plus du tout pénalisant) dès que la machine possède plusieurs processeurs (ou coeurs ou pseudo-coeurs), puisqu'il pourra alors fonctionner sur un autre processeur que le programme principal.

 
Hello tout le monde,
 
Je me permets d'intervenir dans cette discussion que je trouve très intéressante même si il ne s'agit pas de mon domaine.  
 
Joel F > Je me suis inspiré de tes remarques sur le topic que tu as mis en lien, et j'ai du mal à mettre en avant la supériorité du stockage NRC avec des benchmarks de mon cru (d'où le problème ) !  
 
Le source est disponible ici : http://evadream.free.fr/files/sources/array.cpp  
 
J'ai uniquement testé avec gcc. Ça doit se compiler avec g++ array.cpp -W -Wall -O3 -lboost_program_options
 
En gros, je prépare un tableau 2d en utilisant le stockage NRC (je ne suis pas certain de la terminologie à employer) que je remplis avec des valeurs aléatoires. Je parcours intégralement le tableau plusieurs fois de suite en utlisant l'accès NSR, puis en utilisant un accès naïf (mutliplication + addition). Jusqu'à présent, je n'ai obtenu que des résultats équivalents. Si tu as des benchmarks qui établissent une différence, je suis preneur afin d'essayer de comprendre ce qui ne va pas dans mon code
 
A+

@Eva: je te cherche ça. De toute manière, l'avantage du NRC reste dans la facilité à écrire les accès (pense au tableau à N>2) et dans le fait que le code ainsi écrit est trivialement vectorisable à la main et - avec certains compilos auto-vectorisant - plus facile à autovectoriser par le compilateur que le même code écris en notation i+h*j. En terme d eperf, on est équivalent, et des fois (des fois = taille+probleme+compilo), on est meilleur. Sous gcc, tu n'auras guère de gain en 2D.

Autre avantage, tu peut gérer trivialement des tableaux avec des index de départ quelconque, les remapper avec un coup nul et écrire des fonctions qui traite des sous tableaux de manière triviale.

En gros, le gain est dans la facilité d'écriture, la facilité de vectorisation et le fait que tu puisse écrire plus simplement pas mal de truc casse pied. C'était pas dans la discu original, mais par exemple tu peut ajouter un support pr du padding, du stride voire des tableaux non-dense en gardant une interface d'accès unique.

Quand je rentre, je t'envoie mon truc de tests.

Addedum :
Je viens de compiler ton test. Pour que ça soit probant, essaye un truc du genre Tableau1 = Tableau2*Tableau3+Tableau4.
Avec cette config, où tu as des plus d'accès que de calcul contrairement à res+=array[i][j], j'obtiens des différences de l'ordre de 5%.

Addendum 2 : Il se peut aussi que j'ai louper un wagon sur les dernières versions des compilos et que c'est derniers génèrent proprement des accès directs et non indirects avec les deux méthodes. L'avantage restant est alors d'ordre pratique.

Un grand merci pour ta réponse. Je n'avais pas du tout pensé à l'aspect "pratique" des choses pour l'utilisateur et le compilateur, surtout avec des dimensions supérieurs à 2.  
 
Je prends note de tes remarques. Ne t'embête pas trop longtemps à chercher des exemples, je pense que j'ai assez de matière maintenant pour avancer

 
Bah ca va pas m'embetais, je sais qu'ils sont quelque part. Juste à trouver le quelque part
Ca m'interesse aussi de savori dans quoi tu travail (en MP si tu veux)

 
Sauf que personnellement, je préfère quand tous mes core participent au calcul

Dites donc vous en pensez quoi de mon post ? Parce que c'est bien beau de s'étripper sur des questions d'optimisation de compilation, de parallélisation et de stockage de données, mais s'il n'y a effectivement que 2 millons d'opérations on s'en fout un peu.

j'ai vu :E mais bon je peut pas répondre à la place du PO

 
MP

Un site de benchs intéressant : http://shootout.alioth.debian.org/ [...] lang2=java