Autres possibilités

Si une donnée doit être utilisée plusieurs fois dans un programme, il vaut mieux utiliser cette donnée successivement avec le moins de temps possible entre chaque utilisation pour avoir plus de chance de la trouver toujours dans le cache. Par exemple, la boucle notée 2 dans le code suivant serait beaucoup plus rapide sur une grande quantité de données que la boucle notée 1 :

// 1
for(n = 0; n < 3; n++)
    for(i = 0; i < size; i++)
        A[i] = f(B[i]);

// 2
for(i = 0; i < size; i++)
    for(n = 0; n < 3; n++)
        A[i] = f(B[i]);

On peut imaginer le calcul dans un tableau où chaque calcul dépend de la valeur précédente dans le tableau, et on veut faire ce calcul trois fois. Alors, l'algorithme le plus simple serait de répéter cette boucle trois fois :

for(n = 0; n < 3; n++)
    for(i = 1; i < size; i++)
        A[i] = f(A[i-1], A[i], A[i+1]);

Cet algorithme parcourt le tableau linéairement trois fois. Si le tableau est plus grand que le cache, l'ordinateur doit charger le tableau de la mémoire trois fois.

On peut changer notre algorithme pour faire les calculs d'une manière qui optimise les accès à la mémoire. On va calculer seulement ce dont on a besoin pour faire le calcul complet pour chaque adresse dans le tableau :

A[1] = f(A[0], A[1], A[2]); // 1

A[2] = f(A[1], A[2], A[3]); // 2
A[1] = f(A[0], A[1], A[2]);

for(i = 1; i < size - 2; i++) // 3
    for(n = 2; n >= 0; n--)
        A[i+n] = f(A[i+n-1], A[i+n], A[i+n+1]);

A[size-2] = f(A[size-3], A[size-2], A[size-1]); // 4
A[size-1] = f(A[size-2], A[size-1], A[size]);

A[size-1] = f(A[size-2], A[size-1], A[size]); // 5

Cet algorithme devient plus compliqué à cause du début et de la fin du tableau. Pour démarrer, il faut d'abord faire le premier calcul de la première adresse dans le tableau (1). Après, il faut calculer les valeurs intermédiaires des deux premières adresses (2). Quand la boucle termine, il faut faire la même chose pour les deux dernières adresses (4 et 5).

La boucle même est la partie intéressante de cet exemple (3). On fait le calcul à l'envers pour avoir assez de valeurs intermédiaires pour calculer la valeur finale pour chaque adresse. On accède la mémoire dans cet ordre : , , , , , , , .... Les adresses sont proches et les accès suivants viennent rapidement, alors il est fortement probable que chaque donnée restera dans le cache jusqu'à la fin des trois calculs sur cette donnée.

La fonction lin_solve dans la simulation de fluide est similaire, sauf en trois dimensions. Pour le solveur Gauss-Seidel, le calcul de chaque cellule dans le fluide dépend du calcul des trois voisins (Voir figure 10).

Pour deux ou trois dimensions, on peut utiliser la même technique. Pour démarrer la boucle on fait le calcul dans un triangle ou une pyramide, ensuite on calcule les valeurs pour toute une ligne, et puis on peut continuer à faire le calcul sur un nombre de lignes égal au nombre d'itérations qu'on fait (Voir Figure 11).

Pour un solveur 3D, il faut faire le calcul sur plusieurs lignes en même temps. Si est le nombre d'itérations, il faut faire le calcul sur lignes. Pour et un cube de 64 cellules contenant chacun une valeur flottante de 4 octets, la quantité des données est :

Cette quantité de données est inférieure à la capacité du cache de niveau 1 d'un processeur typique, qui est souvent de 32ko. Par contre, pour faire le calcul sur tout le cube, on doit toucher 1Mo de données à chaque fois, ce qui est beaucoup plus grand pour le cache de niveau 1, et éventuellement trop grand pour le cache de niveau 2.