Optimisation du cache du code C++

Question

Cela peut sembler un peu ouvert, mais j'ai du mal à optimiser un morceau de code C++ pour plusieurs processeurs et le cache.

Plus important que plusieurs processeurs est le cache: J'Enumérer les 2 boucles imbriquées

for(int i=0; i<n; i++){ 
    //do a little something here with a single array 
    for(int j=0; j<whoaAnotherArray[n].size(); j++){ 
    * access array[i][j] and otherArray[i][j] and store in a variable 
     - an example is: "int x = array[i][j] + otherArray[i][j]" 
    * compare variable to some other array[index calculated from i and j] 
     - an example is: "if (x < yetAnotherArray[i*n+j]){ //do something to yetAnotherArray }" 
    } 
} 

Mes tableaux (array et otherArray) sont de très grande taille . n est leur taille.

Y at-il un moyen de rendre ce cache plus convivial? Je suis déjà passé de l'utilisation de listes liées, qui sont terribles pour le cache. J'ai lu quelque part que mon ordre d'accès [i] [j] est également efficace dans le cache. FWIW, ceci fait partie d'un algorithme de détection de cycle de poids négatif.

Je pensais que peut-être puisque mes tableaux sont si énormes (ce sont des tableaux d'entiers btw), serait-il préférable de les décomposer un peu afin qu'ils s'intègrent mieux dans le cache? Mais je ne suis pas sûr si c'est vrai ou si c'est le cas, comment s'y prendre.

J'ai également commencé à utiliser openmp. La seule chose que je fais ajoute

#pragma omp parallel for 

avant le droit pour les boucles, et j'obtenir une utilisation correcte. Je voudrais apprendre comment mieux utiliser le parallélisme mais au-delà des boucles dans mon code je ne suis pas sûr de ce que je peux faire. Et tout le temps: j'essaie d'être amical en cache.

Answer 1

Une possibilité d'amélioration de l'utilisation du cache consiste à modifier votre modèle d'accès à array et otherArray. Lorsque vous lisez array[i][j] votre machine va, bien sûr, déplacer une «ligne» de mémoire dans le cache. Lorsque vous lisez otherArray[i][j] votre machine va, bien sûr, déplacer une «ligne» de mémoire dans le cache. Il est possible que pour lire la deuxième ligne, la première doit être vidée du cache dans la RAM. Et puis vous rendez la situation encore pire (potentiellement) en lisant une valeur de yetAnotherArray. Ce qui se passe réellement dépend beaucoup de ce qui se passe en même temps, de ce qui est en cache et de toutes les autres opérations effectuées. Cela peut être très difficile à comprendre. Si votre modèle (dominant) d'accès au tableau doit exiger element[i][j] des deux (ou des trois) tableaux en même temps, alors vous voulez arranger les choses telles qu'elles se trouvent dans la même 'ligne' de mémoire qui est lue . Une façon de le faire est de fusionner les 3 tableaux en un seul tableau m*n*3, dans lequel superArray[i][j][1] est à côté de superArray[i][j][2] qui est à côté de superArray[i][j][3] et dans lequel les 3 plans du tableau représentent chacun l'un des tableaux d'origine. Bien sûr, cela ne fonctionne que si l'index est correct, alors donnez-lui plus de réflexion que j'ai.

Enfin:

1. cela peut transformer votre programme élégant dans un mess spaghetti - mais qui est un petit prix à payer pour amélioration de la vitesse! Je veux dire quel que soit le bloc votre plate-forme se charge de la RAM vers cache en une seule fois.

2. Google autour de la boucle carrelage et bande minière. Les compilateurs sont pas très bon à cela encore et toute aide que vous pouvez fournir devrait être récompensé dans l'exécution améliorée vitesse.

Answer 2

Il existe un programme appelé Cachegrind (un plugin Valgrind) qui peut vous aider à définir la manière dont votre code s'exécute sur un cache virtuel. Je travaillerais avec cela pour voir comment votre code fait contre le cache de votre CPU. (Cela fait un moment que je l'ai utilisé, donc je ne me souviens pas s'il peut détecter automatiquement les attributs de cache de votre CPU Vous devrez peut-être lui donner les paramètres de cache exact pour votre CPU.)

Vous pourriez aussi essayez quelques optimisations qui, idéalement, votre compilateur est ou devrait faire:

1) Remplacer cette ligne:

for(int j=0; j<whoaAnotherArray[n].size(); j++){ 

avec:

2) Créer des pointeurs dans les tableaux dans votre boucle extérieure:

int* pArray = array[i] - 1; 
int* pOtherArray = pOtherArray[j] - 1; 

et utilisation préincrémentation sur le premier accès de pointeur dans la boucle:

int x = *(++pArray) + *(++pOtherArray); 

(Oui, je sais qui est laid. Je sais le compilateur devrait le faire pour vous. Mais il n'y a pas trop de mois, j'ai trouvé que cela faisait une différence avec gcc 4.3 (?) Sur linux. YMMV.)

3) S'il y a un moyen de restructurer le code de sorte que vous traversiez array en une seule passe, puis bouclez otherArray dans un second passage, puis essayez de le faire. Cela semble peu probable dans votre cas, mais je ne sais pas. Le point est, vous voulez garder les accès mémoire aussi concentrés que possible à un tableau à la fois.

Bonne chance.

Answer 3

Lire ces 2 articles par Herb Sutter en particulier le premier

http://www.ddj.com/go-parallel/article/showArticle.jhtml?articleID=217500206

http://ddj.com/architect/208200273