Discussion :

[Heimdall]

re-salut,

Bon j'espère avoir une explication rationnelle à mes tests :

après quelque recherches, je suis tombé sur ceci http://developer.intel.com/Assets/PDF/manual/248966.pdf


Je cite quelques passages (3-71):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
struct 
{	
/* 1600 bytes */ 
int	a, c, e;
char b, d; 
} array_of_struct [100];
 
struct 
{	
/* 1400 bytes */ 
int	a[100], c[100], e[100]; 
char b[100], d[100];
} struct_of_array;

The efficiency of such optimizations depends on usage patterns. If the elements of the structure are all accessed together but the access pattern of the array is random, then ARRAY_OF_STRUCT avoids unnecessary prefetch even though it wastes memory.

However, if the access pattern of the array exhibits locality (for example, if the array index is being swept through) then processors with hardware prefetchers will prefetch data from STRUCT_OF_ARRAY, even if the elements of the structure are accessed together.

When the elements of the structure are not accessed with equal frequency, such as when element A is accessed ten times more often than the other entries, then STRUCT_OF_ARRAY not only saves memory, but it also prevents fetching unneces- sary data items B, C, D, and E.
Using STRUCT_OF_ARRAY also enables the use of the SIMD data types by the programmer and the compiler.

quelques sélections entre la page 4-23 et 4-26

For certain algorithms, like 3D transformations and lighting, there are two basic ways to arrange vertex data. The traditional method is the array of structures (AoS) arrangement, with a structure for each vertex (Example 4-13). However this method does not take full advantage of SIMD technology capabilities.

Code :

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

1
2
3
4
5
6
7
 
typedef struct
{ 
float x,y,z;
int a,b,c;
} Vertex;
Vertex Vertices[NumOfVertices];

The best processing method for code using SIMD technology is to arrange the data in an array for each coordinate (Example 4-14). This data arrangement is called struc- ture of arrays (SoA).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
typedef struct
{ 
float x[NumOfVertices]; 
float y[NumOfVertices]; 
float z[NumOfVertices]; 
int a[NumOfVertices]; 
int b[NumOfVertices];
 int c[NumOfVertices]; 
} VerticesList; 
 
VerticesList Vertices;

Use of the SoA format for data structures can lead to more efficient use of caches and bandwidth. When the elements of the structure are not accessed with equal frequency, such as when element x, y, z are accessed ten times more often than the other entries, then SoA saves memory and prevents fetching unnecessary data items a, b, and c.

[souviron34]

re-salut,

Bon j'espère avoir une explication rationnelle à mes tests :

oui, intéressant, mais c'est un peu ce que j'avais dit plus haut :

Par contre, suivant le problème :

si il peut arriver que l'on modifie g ou h tout en gardant f constant (ou h modifé et f et g constants, ou toute autre combinaison), alors la 2ième solution est mieux..

C'est effectivement l'intensité d'usage de telle ou telle partie qui va le garder en mémoire vive..

Mais donc il faudrait connaître réellement le problème considéré pour pouvoir aider plus..

Il n'y a pas de réponse absolue...

Après ça dépend du problème bien entendu..

Mais à ce compte-là, si on n'utilise réellement qu'une partie de la structure, pourquoi s'emmerder à stocker le reste ?

Et d'ailleurs ça revient à poser la question : pourquoi se servir d'une structure, et pas simplement de 5 tableaux ...



Enfin je maintiens quand même qu'une optimisation en vitesse se fera quand même de manière prépondérante par l'utilisation au maximum des pointeurs directs, doublée d'une optimisation des boucles et factorisation des calculs (pour éviter les multiples opérations similaires), et que la fraction pénalisante due au cache ne l'est réellement que quand on n'a pas utilisé un bon algorithme :

par exemple utiliser un "pivot" et référencer simultanément des début et fin de matrices..


Mais dans la plupart des (bons) calculs, même si les matrices sont gigantesques, on ne se sert que du voisinage d'une cellule (ce qui par exemple sert pour le grid-computing ou le parallèlisme), et là le cache n'est utlisé que pour "mover" des blocs entiers... Donc il n'y a que (n*n)/M transferts, ces transferts dépendants bien entendu de la taille du cache, mais la plupart du temps non pénalisants si les calculs sont effectivement faits autour du voisnage d'une cellule....

[Heimdall]

Hum, si tu le disais depuis le début, désolé je n'avais pas vraiment compris tout ce que tu disais

Pour ce qui est de l'algorithme.... il n'y en a pas 50... je fais du calcul sur des grilles contenant plusieurs quantités physiques reliées entre elles par des équations.... soit je fais plein de tableaux et je fais fonctions qui les prennent tous en paramètre... soit j'encapsule les données dans des structures.

Se pose alors un choix : est-ce que je fais une structure par point du maillage ou plutôt une structure pour toute la grille avec à l'intérieur un tableau par quantité physique...

du point de vue du "sens physique" des choses... c'est un peu pareil... maintenant du point de vue rapidité, c'était ma question...

Mais comme il a été dit ici plus haut, je ne cherche pas la rapidité "à tout prix"... je veux un code lisible et maintenable également...

[souviron34]

Pour ce qui est de l'algorithme.... il n'y en a pas 50... je fais du calcul sur des grilles contenant plusieurs quantités physiques reliées entre elles par des équations.... soit je fais plein de tableaux et je fais fonctions qui les prennent tous en paramètre... soit j'encapsule les données dans des structures.

Se pose alors un choix : est-ce que je fais une structure par point du maillage ou plutôt une structure pour toute la grille avec à l'intérieur un tableau par quantité physique...

Rhaaaa


D'où ce dont j'avais parlé plus haut...



Je t'ai dit que il y avait BEAUCOUP plus efficace si on savait que les points n'étaient pas aléatoires...

Moins lisible certes (quoique) mais beaucoup plus efficaces...

Voilà ce que j'ai fait pour des modèles numériques de météo (donc avec beaucoup de points sur un maillage et beaucoup de mesures par points) :

• Au lieu de stocker les points comme x,y,z (valeurs réelles) tu stockes les VALEURS prises par les x, y , ou z dans des tableaux unidimenionnels.
  
  
• Puis tu crées une structure "endroit" ou "position" contenant les pointeurs vers ces valeurs, et un tableau de pointeurs
  
  
• Puis tu crées les données en leur ajoutant un pointeur sur l'endroit.

Admettons une grille de 100*100*100.

Au lieu de stocker 10^6 doubles, tu stockes 300 doubles et 10^6 pointeurs : économie environ 10^6 * 32 bits (sur une machine 32 bits).


C'est pour ça que je demandais si les particules étaient aléatoires ou non.. Si il y a au moins une dimension qui ne l'est pas, il est (très nettement) plus avantageux de faire ça...

Et plutôt que d'aller se poser la question du cache, ça c'est beaucoup plus important.. Ce que je dis depuis le début..

Car si tu réduis la mémoire, tu réduis les problèmes liés au cache..



Et si les x,y,z ne sont pas des valeurs réelles mais n'existent pas en tant que tels (références uniquement sur la position dans la matrice) (que ce soit un indice ou rien du tout) alors effectivement de ce côté-là il n'y a pas grand chose à tirer, sauf à n'utiliser que des pointeurs et économiser la place en calculant à chaque fois la position en utilisant les pointeurs..

[Heimdall]

En fait, je vais t'en dire plus

J'utilise un code "particle-mesh"... j'ai donc deux types d'opérations typiques dans le code :

1/ un calcul eulérien, donc parcours de grille toujours régulier.

2/ un calcul lagrangien, où je pousse les particules...


Mais il y a un couplage : les forces ressenties par les particules proviennent de la grille...

et les champs mis à jours sur la grille proviennent de la distribution locale de particules...


donc on passe notre temps a aller du tableau de particules vers le tableau de champs.. provoquant au bout d'un certain temps des acces non ordonnées dans certaines phases.


ta méthode semble intéressante, je vais regarder ça ...

[souviron34]

Dans ce cas-là 2 questions :

1. Les coordonnées des points sont-elles des valeurs réelles (voir plus haut) ou uniquement la position dans la grille (en i,j,k) ?
   
   
2. Est-ce un problème à N corps, c'est à dire que TOUTE la grillle est influencée par un point , et réciproquement, ou bien un phénomène local, c'est à dire que bouger un point influence les voisins dans la grille mais pas l'ensemble de la grille ?
   
   Si c'est un problème à N corps (style modélisation de galaxies où la champ de gravité influe sur chaque particule et chaque particle influe sur le champ de gravité) alors il n'y a rien à faire pour diminuer la cmplexité. Dans le cas contraire, la subdivision en sous-matrices est la direction dans laquelle il faut que tu cherches : il y a tout un tas d'algos spécialisés là-dedans.

[Heimdall]

Dans ce cas-là 2 questions :


Les coordonnées des points sont-elles des valeurs réelles (voir plus haut) ou uniquement la position dans la grille (en i,j,k) ?

Chaque point de la grille correspond à un indice (i,j,k) et aussi à une valeur "physique" (donc réelle, au sens mathématique) obtenue de la façon suivante i*dx, j*dy, z*dz., et dx, dy, dz sont constants.

Est-ce un problème à N corps, c'est à dire que TOUTE la grillle est influencée par un point , et réciproquement, ou bien un phénomène local, c'est à dire que bouger un point influence les voisins dans la grille mais pas l'ensemble de la grille ?

Si c'est un problème à N corps (style modélisation de galaxies où la champ de gravité influe sur chaque particule et chaque particle influe sur le champ de gravité) alors il n'y a rien à faire pour diminuer la cmplexité. Dans le cas contraire, la subdivision en sous-matrices est la direction dans laquelle il faut que tu cherches : il y a tout un tas d'algos spécialisés là-dedans.

Chaque point de la grille est influence par les particules dans les cellules (entre 4 points en 2D) autour.

Une particule est influencée par les quantités physique des 4 coins de la cellue dans laquelle elle se trouve (en 2D);

Admettons une grille de 100*100*100.

Au lieu de stocker 10^6 doubles, tu stockes 300 doubles et 10^6 pointeurs : économie environ 10^6 * 32 bits (sur une machine 32 bits).

Bon j'ai pas tout pigé...
de ce que je comprends, tu stockes la valeur des quantités physique dans des tableaux 1D, et ta "grille physique" de position n'est qu'un tableau de pointeurs, pointant vers la case des tableaux 1D de données physiques.

Mais au final... tes données, dans tes tableaux 1D, ça représente bien 10^6 doubles tout de même ? Je vois pas comment tu fais l'économie de 10^6 valeurs...

Prenons un exemple, puisque tu parles de météo : tu as un cube maillé régulièrement de 100*100*100 points où tu stockes la densité de gaz et la température du gaz, deux double donc 2*1e6*sizeof(double) octets.

Où est-ce que tu mets les valeurs de la densité et de la température ?

[souviron34]

Chaque point de la grille correspond à un indice (i,j,k) et aussi à une valeur "physique" (donc réelle, au sens mathématique) obtenue de la façon suivante i*dx, j*dy, z*dz., et dx, dy, dz sont constants.

Ok, mais donc tu ne les stockes pas (les "i*dx), tu les calcules quand tu en as besoin, c'est bien ça ?

Chaque point de la grille est influence par les particules dans les cellules (entre 4 points en 2D) autour.

Une particule est influencée par les quantités physique des 4 coins de la cellue dans laquelle elle se trouve (en 2D);

Ok, on est donc bien dans le cas où la sub-division en sous-matrices sera très nettement avantageux...

Regarde de ce côté (tu as des posts sur ce sujet dans le forum Algorithmes et/ou sa sous-partie mathématiques) et aussi sr le net sous "grid computing" et "parallellism matrix data".

Bon j'ai pas tout pigé...
de ce que je comprends, tu stockes la valeur des quantités physique dans des tableaux 1D, et ta "grille physique" de position n'est qu'un tableau de pointeurs, pointant vers la case des tableaux 1D de données physiques.

Mais au final... tes données, dans tes tableaux 1D, ça représente bien 10^6 doubles tout de même ? Je vois pas comment tu fais l'économie de 10^6 valeurs...

Prenons un exemple, puisque tu parles de météo : tu as un cube maillé régulièrement de 100*100*100 points où tu stockes la densité de gaz et la température du gaz, deux double donc 2*1e6*sizeof(double) octets.

Où est-ce que tu mets les valeurs de la densité et de la température ?

les valeurs des données sont (simplement) incompressibles : il y a des algos et des stockages permettant de réduire drastiquement (voir par exemple le format GRIB : stockage du style mpeg : on stocke une valeur double, un expostant, puis des différences sur x bits : réduction de 95% du volume de données) mais ce n'est en général utilisé que pour le stockage sur disque (trop de calculs pour le faire au vol).

Je parlais plutôt au niveau de la position , si par exemple on a une grille géo-référencée (lat,lon, alt), plutôt que de stocker par point l'alltitude par exemple, on stocke l'altitude comme un nombre dans un tableau 1D et les points contiennent juste un pointeur vers cette valeur, donc pour un plan à une certaine altitude au lieu de Dx*Dy*1 double, on a Dx*Dy*1 pointeur + 1 double


Maintenant on peut s'inspirer du format GRIB et réduire de Dx*Dy*Dz doubles * Dx*Dy*Dz int en stockant à part par exemple la valeur médiane et facteur en double, plus un exposant permettant d'atteindre la précision requise.. et ceci est valable quelle que soit la donnée..


Mais pour ton problème c'est bien du côté de la sub-division de matrice que tu auras ta solution (et tu n'auras pas de problèmes liés au cache)

[Heimdall]

salut,


Ok si je comprends bien, tu me dis de faire de la décomposition de domaines pour faire du calcul parallèle ?

Si c'est la cas, c'est déjà ce que je fais

[souviron34]

salut,


Ok si je comprends bien, tu me dis de faire de la décomposition de domaines pour faire du calcul parallèle ?

Si c'est la cas, c'est déjà ce que je fais

D'une part tu nous fais perdre notre temps en ne donnat pas les infos qu'il faut pour qu'on puisse t'aider : il faut qu'on soutire les infos et ça arrive au compte-gouttes... Il n'est nulle par ailleurs fait mention du fait que tu fais du parallèlisme..


D'autre part je ne sais pas si ça s'appelle "décomposition de domaines", mais quand je vois "matrix division" je vois des Eigen values et autres méthodes...

Par conséquent, si tu as toujours des problèmes de taille, c'est que tu l'utilises mal, c'est tout...

C'est fait pour ne pas en avoir...


ou que le problème est mal posé..


Par exemple, justement j'ai eu le cas en météo : tous les algos de "contouring" ou de "détections de cellules" fonctionnaient sur des grilles. Avec les données que j'avais (résolution au mètre), et le domaine que je couvrais (amérique du Nord), impossible de faire de telles matrices (5000000 * 5000000), qui plus est en 3 exemplaires (ce dont j'avais besoin). Je me suis donc tourné vers des algos prenant juste des points... Et j'ai gagné un facteur 800000 (la plupart des "cellules" auraient été vides)..

Je maintiens qu'avec les machines modernes il est absurde de "tuner" un algo ou des structures par rapport au cache...

[Heimdall]

D'une part tu nous fais perdre notre temps en ne donnat pas les infos qu'il faut pour qu'on puisse t'aider : il faut qu'on soutire les infos et ça arrive au compte-gouttes...

Je suis pas sûr de savoir comment le prendre, tu t'énerves là c'est ça ? Ma question initiale portait sur l'utilisation des structures de tableaux ou tableaux de structures. C'était une question claire et précise, illustrée un peu plus tard par un code qui compile.

Si au fil de la discussion, j'ai été ammené à comprendre que cette question n'était pas forcément la bonne (pour moi, car ça reste une question intéressante en tant que telle) je l'ignorais au départ, je pense donc pas avoir dissimulé explicitement des informations.

Sur le fait que je te fasse perdre ton temps.. effectivement je pose des questions, et tu es celui qui à le plus répondu et je t'en remercie, mais il n'y a pas obligation de répondre après tout... merci de l'avoir fait en tout cas.

Il n'est nulle par ailleurs fait mention du fait que tu fais du parallèlisme..

pour ça, je réponds en citant mon message du 2 avril dernier :

http://http://www.developpez.net/forums/d1060599/c-cpp/c/performance-structure-tableaux-tableau-structures/#post5885802

dont voici un extrait :

Mais en fait j'ai quand même à me soucier de la performance... je m'explique : Je fais du calcul scientifique assez intensif (des programmes qui peuvent durer plusieurs semaines sur calculateur parallèle avec quelques dizaines de processeurs) et donc un gain de temps d'un facteur 6 sur des boucles ça m'intéresse

D'autre part je ne sais pas si ça s'appelle "décomposition de domaines", mais quand je vois "matrix division" je vois des Eigen values et autres méthodes...

Ok tu vois ça... moi je ne vois rien car je ne connais pas le terme "matrix division". Tu me dis de chercher des divistion de tableaux, et "parallelism" sur le net, moi ça me fait penser à de la décomposition de domaine... d'ailleurs je n'ai jamais parlé de calcul matriciel.

Tu vois quand tu dis quelque chose, l'autre ne comprends pas forcément clairement ce que tu voulais dire.. c'est en partie une question de vocabulaire, pas la peine de s'énerver pour ça...

Par conséquent, si tu as toujours des problèmes de taille, c'est que tu l'utilises mal, c'est tout...

C'est fait pour ne pas en avoir...


ou que le problème est mal posé..

j'ai un peu l'impression que tout le monde autour de moi fait comme ce que je fais... donc on est tous un peu super crétins avec nos structures de tableaux ou tableaux de structures... ou alors je dis des bétises, ou alors on s'est mal compris. J'ai tout de même cité une doc de biblio scientifique qui précisait qu'elle avait implémenté des structures de tableaux car plus efficaces que le reste vis à vis des simulations qu'on fait. Ils se gourent peut-être ceci dit et n'ont peut être tout simplement pas utilisé le bon algo par ailleurs.

J'ai également lu des articles scientifiques essayant précisément de régler les problèmes de cache dans les simulations particle-mesh, c'est bien qu'il y en a, et encore une fois je suis pas sûr qu'il existe des méthodes alternatives.

exemple de problème de cache dans mon type de simulation :

http://http://www.google.fr/url?sa=t&source=web&cd=1&ved=0CCIQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.115.1362%26rep%3Drep1%26type%3Dpdf&rct=j&q=accelerating%20a%20particle%20in%20cell%20simulation%20using%20a%20hybrid%20counting%20sort&ei=z4ScTcm7B8uXhQe_-PjPBg&usg=AFQjCNGyLRHOU7NW28_MpFMm6QSZPBQUlw&sig2=cK94c5OBcohSbWUN4wQAVA&cad=rja

Par exemple, justement j'ai eu le cas en météo : tous les algos de "contouring" ou de "détections de cellules" fonctionnaient sur des grilles. Avec les données que j'avais (résolution au mètre), et le domaine que je couvrais (amérique du Nord), impossible de faire de telles matrices (5000000 * 5000000), qui plus est en 3 exemplaires (ce dont j'avais besoin). Je me suis donc tourné vers des algos prenant juste des points... Et j'ai gagné un facteur 800000 (la plupart des "cellules" auraient été vides)..

Je maintiens qu'avec les machines modernes il est absurde de "tuner" un algo ou des structures par rapport au cache...

je prends note, même si je comprends toujours pas vraiment quelle serait l'alternative a ce que je fais... En tout cas je te remercie encore de tes réponses.

[souviron34]

bon c'est vrai je me suis énervé...

Mais on ne parle pas tout à fait de la même chose (je crois)

D'après ce que je lis, la décomposition de domaines n'est pas tout à fait ce que j'avais en tête, mais plutôt le Block-computing..

Solution of Large Scale Matrix Inversion on Cluster and Grid


Sinon, plus dans ton "sujet" :

Partition-Based Optimizing Algorithm for Dense Matrix Computation
under Multicore Environment

Je ne suis pas spécialiste, mais j'ai déjà vu utiliser beaucoup (et effleuré en lecture) le block-partitioning..

Je pense que puisque tes données et leur influence sont "locales", tu devrais t'orienter vers ça..


Si maintenant tu es dans la recherche là-dedans, je pense que tu auras plus de succès dans les cercles de recherche (inria, mit, et autres)