mikeash.com: just this guy, you know?

next up previous contents
Next: Résultats Up: Les accès mémoire Previous: Les accès mémoire   Contents

Ordre de boucles

Dans le cas d'une simulation de fluide ou de beaucoup d'autres algorithmes, on travaille avec des données multidimensionnelles, mais l'organisation des données en mémoire, pour la plupart des ordinateurs, est monodimensionnelle. Pour les données à deux dimensions, par exemple une matrice, les données sont traditionnellement rangées par ligne (on peut parfois trouver une organisation selon les colonnes comme en Fortran par exemple). Avec cet ordre de données, dans une grille de $X$ par $Y$, $X$ le nombre de colonnes et $Y$ le nombre de lignes, l'indice de la cellule $(x, y)$ est alors $y \times X + x$. Pour trois dimensions on garde cet ordre pour chaque plan, et les plans sont stockés consécutivement.

L'ordre d'accès mémoire dépend de quelle variable est incrémentée le plus souvent. Pour des données 2D, il y a deux façons pour itérer toutes les données en deux boucles. Si $x$ est incrémenté par la boucle à l'extérieur et $y$ est incrémenté par la boucle à l'intérieur, $y$ changera le plus souvent. Les boucles parcouront les cellules $(0, 0)$, $(0, 1)$, $(0, 2)$, $(0, 3)$, ..., $(1, 0)$, $(1, 1)$, $(1, 2)$, $(1, 3)$, .... Ces cellules correspondent aux adresses $0$, $X$, $2X$, $3X$, ..., $1$, $X + 1$, $2X + 1$, $3X + 1$, ...(Voir Figure 9). Inverser les boucles et mettre $y$ à l'intérieur touche les adresses $0$, $1$, $2$, $3$, ..., $X$, $X + 1$, $X + 2$, ..., une séquence qui est beaucoup plus conforme au matériel (Voir Figure 8).

Figure: Quand x est à l'intérieur de la boucle, on charge le contenu de la mémoire dans l'ordre respectant le mode de stockage.

Figure: Quand x est à l'extérieur de la boucle, on charge le contenu de la mémoire d'une façon qui ne convient pas au système de mémoire.

Pour les données à trois dimensions, on doit faire la même chose. On préfère itérer selon $x$ puis $y$, et finalement selon $z$.

Alors, il est très important de mettre les boucles dans le bon ordre. 

for(x = 0; x < N; x++) {
    for(y = 0; y < N; y++) {
        for(z = 0; z < N; z++) {

Il faut changer l'ordre pour mettre $x$ dans la boucle intérieur : 

for(z = 0; z < N; z++) {
    for(y = 0; y < N; y++) {
        for(x = 0; x < N; x++) {

Cet ordre chargera les données d'une façon linéaire dans la mémoire ce qui optimisera les accès.

next up previous contents
Next: Résultats Up: Les accès mémoire Previous: Les accès mémoire   Contents
Michael Ash 2005-09-21

Code syntax highlighting thanks to Pygments.
Hosted at DigitalOcean.