mikeash.com: just this guy, you know?

next up previous contents
Next: Extension de lancer de Up: Parallélisme Previous: Parallélisme   Contents

Extension de fluide en parallèle

Pour paralléliser la simulation de fluide, on coupe le cube en plusieurs morceaux et on fait le calcul de chaque morceau sur son propre noeud.

Pour minimiser les communications entre les noeuds, il faut que chaque morceau ait le moins de surface possible. L'optimale est alors de couper le cube en sous cubes qui sont répartis sur les noeuds de simulation. Cette distribution pose un problème sur le nombre de noeuds de simulation. Il y a toujours un nombre cube de sous cubes, alors cette distribution ne marche bien qu'avec un nombre cube de noeuds. Sur une grappe de PC, cela nous limite à $1$, $8$, et peut-être $27$ noeuds de simulation. Il est possible de distribuer plusieurs sous cubes sur chaque noeud de simulation, mais il y a toujours des problèmes de répartition de charges. En plus, les communications de chaque noeud sont difficiles à gérer car il y a six voisins pour chaque noeud.

Une autre possibilité est de couper le cube en tranches et distribuer chaque tranche sur un noeud de simulation. Cette distribution n'est pas optimale au niveau de communications mais elle marche avec un nombre de noeuds quelconque et les communications sont beaucoup moins difficiles à gérer avec seulement deux voisins pour chaque noeud.

Ces deux approches sont illustrés par la figure 14.

Figure: À gauche, le cube divisé en sous cubes. À droite, le cube divisé en tranches.

On a décidé alors de couper le cube en tranches sur l'axe Z. On a choisi l'axe Z à cause de l'organisation de nos données volumiques : remonter les données d'un cube est une simple concaténation des données de chaque tranche.

Pour la communication, on crée une couche de ghosts (fantômes). Les ghosts sont des cellules du voisin qui sont copiées sur un noeud. Ces copies doivent être mises à jour après chaque sous étape de calcul qui les modifie. Les deux noeuds au bord ont des ghosts sur seulement une face, et les autres noeuds ont des ghosts sur deux faces. (Voir Figure 15.)

Figure: La simulation de fluide sur quatre noeuds. Les cellules en gris sont les ghosts qui sont communiqué après chaque sous-étape.

Il est à noter qu'il y a 4 couches de ghosts pour la densité et les trois composantes de la vitesse.

On échange les ghosts après chaque itération de lin_solve, après chaque advect, et au milieu et après chaque project. En total, on échange les ghosts 38 fois par étape de simulation.

La taille de la couche de ghosts est déterminante pour l'efficacité de notre parallélisation. Dans l'étape de advect, une cellule avec une grande vitesse peut modifier une cellule non voisine. Une cellule avec une vitesse de $x$ peut modifier une autre cellule de distance $x$. Mais il n'est pas possible de modifier les cellules de l'autre côté des ghosts. Si une simulation contient des vitesses qui sont supérieures à l'épaisseur de sa couche de ghosts, elle risque de ne pas être fidèle (Voir Figure 16). Normalement les vélocités sont inférieures à $1$, alors une épaisseur d'une cellule est suffisante.

Figure: Une trop grande vitesse ne peut pas traverser la frontière entre deux noeuds.

Si N est la taille du cube, la couche de ghosts a alors $N^2$ cellules. Si chaque cellule contient une valeur de 4 octets, la quantité totale des données envoyées et reçues par un noeud interne est:


\begin{displaymath}
donn\acute{e}es = 2 \times 38N^2 \times 4o
\end{displaymath}

Le facteur deux est dû au fait que chaque noeud interne à une couche de ghosts sur deux faces. Pour un cube de 32x32x32, il faut alors transférer 304ko par étape. Pour un cube de 64x64x64, il faut transférer plus de 1.18Mo, et pour un cube de 128x128x128, 4.75Mo. D'où l'importance des communications qui peuvent constituer un goulot d'étranglement pour notre simulation.


next up previous contents
Next: Extension de lancer de Up: Parallélisme Previous: Parallélisme   Contents
Michael Ash 2005-09-21

Hosted at DigitalOcean.