Est-ce que SIMD le mérite? Y a-t-il une meilleure option?

Question

J'ai du code qui fonctionne assez bien, mais je voudrais le faire fonctionner mieux. Le problème majeur que j'ai avec cela est qu'il doit avoir une boucle imbriquée. L'externe est pour les itérations (qui doivent arriver en série), et l'interne est pour chaque particule de point considérée. Je sais qu'il n'y a pas beaucoup je peux faire l'externe, mais je me demande s'il y a un moyen d'optimiser quelque chose comme:

void collide(particle particles[], box boxes[], 
     double boxShiftX, double boxShiftY) {/*{{{*/ 
      int i; 
      double nX; 
      double nY; 
      int boxnum; 
      for(i=0;i<PART_COUNT;i++) { 
        boxnum = ((((int)(particles[i].sX+boxShiftX))/BOX_SIZE)%BWIDTH+ 
         BWIDTH*((((int)(particles[i].sY+boxShiftY))/BOX_SIZE)%BHEIGHT)); 
         //copied and pasted the macro which is why it's kinda odd looking 

        particles[i].vX -= boxes[boxnum].mX; 
        particles[i].vY -= boxes[boxnum].mY; 
        if(boxes[boxnum].rotDir == 1) { 
          nX = particles[i].vX*Wxx+particles[i].vY*Wxy; 
          nY = particles[i].vX*Wyx+particles[i].vY*Wyy; 
        } else { //to make it randomly pick a rot. direction 
          nX = particles[i].vX*Wxx-particles[i].vY*Wxy; 
          nY = -particles[i].vX*Wyx+particles[i].vY*Wyy; 
        } 
        particles[i].vX = nX + boxes[boxnum].mX; 
        particles[i].vY = nY + boxes[boxnum].mY; 
      } 
    }/*}}}*/ 

Je l'ai regardé SIMD, même si je ne trouve pas beaucoup au sujet de et je ne suis pas tout à fait sûr que le traitement nécessaire pour extraire et emballer correctement les données vaudrait la peine de faire la moitié des instructions, car apparemment, seulement deux doubles peuvent être utilisés à la fois.

J'ai essayé de le diviser en plusieurs threads avec shm et pthread_barrier (pour synchroniser les différentes étapes, dont le code ci-dessus est un), mais cela l'a simplement ralenti.

Mon code actuel va assez vite; il est de l'ordre d'une seconde par itérations de particules * 10M, et d'après ce que je peux dire de gprof, 30% de mon temps est consacré à cette seule fonction (5000 appels, PART_COUNT = 8192 particules ont pris 1,8 secondes). Je ne suis pas inquiet pour les petites choses à temps constant, c'est juste que 512K particules * 50K itérations * 1000 expériences ont pris plus d'une semaine la dernière fois. Je suppose que ma question est de savoir s'il est possible de traiter ces longs vecteurs de manière plus efficace que de simplement les parcourir. Je me sens comme il devrait y avoir, mais je ne peux pas le trouver.

Answer 1

Je ne suis pas sûr de combien SIMD bénéficierait; la boucle interne est assez petite et simple, donc je devine (juste en regardant) que vous êtes probablement plus lié à la mémoire qu'autre chose. Dans cet esprit, je vais essayer de réécrire la partie principale de la boucle de ne pas toucher le tableau particules plus que nécessaire:

const double temp_vX = particles[i].vX - boxes[boxnum].mX; 
const double temp_vY = particles[i].vY - boxes[boxnum].mY; 

if(boxes[boxnum].rotDir == 1) 
{ 
    nX = temp_vX*Wxx+temp_vY*Wxy; 
    nY = temp_vX*Wyx+temp_vY*Wyy; 
} 
else 
{ 
    //to make it randomly pick a rot. direction 
    nX = temp_vX*Wxx-temp_vY*Wxy; 
    nY = -temp_vX*Wyx+temp_vY*Wyy; 
} 
particles[i].vX = nX; 
particles[i].vY = nY; 

Cela a peu d'effet secondaire potentiel de ne pas faire l'addition supplémentaire à la fin.

---

Un autre potentiel speedup serait d'utiliser __restrict sur la matrice de particules, de sorte que le compilateur peut mieux optimiser les écritures aux vitesses. De même, si Wxx etc. sont des variables globales, elles peuvent devoir être rechargées à chaque fois dans la boucle au lieu d'être éventuellement stockées dans des registres; en utilisant __restrict aiderait avec ça aussi.

---

Puisque vous accédez aux particules dans l'ordre, vous pouvez essayer de préchargement (par exemple __builtin_prefetch sur GCC) quelques particules avant de réduire misses du cache. La préextraction sur les boîtes est un peu plus difficile puisque vous y accédez dans un ordre imprévisible; vous pouvez essayer quelque chose comme

int nextBoxnum = ((((int)(particles[i+1].sX+boxShiftX) /// etc... 
// prefetch boxes[nextBoxnum] 

---

Un dernier que je viens de remarquer - si la case :: rotDir est toujours +/- 1.0, vous pouvez éliminer la comparaison et la branche dans la boucle interne comme celui-ci:

const double rot = boxes[boxnum].rotDir; // always +/- 1.0 
nX =  particles[i].vX*Wxx + rot*particles[i].vY*Wxy; 
nY = rot*particles[i].vX*Wyx +  particles[i].vY*Wyy; 

---

Bien entendu, les mises en garde habituelles de profilage avant et après application. Mais je pense que tout cela peut aider, et peut être fait, que vous passiez ou non au SIMD. Pour l'enregistrement, il y a aussi libSIMDx86!

Answer 2

Avez-vous un profilage suffisant pour vous dire où le temps est passé dans cette fonction? Par exemple, êtes-vous sûr que ce ne sont pas vos divs et mods dans le calcul boxnum où le temps est passé? Parfois, les compilateurs ne parviennent pas à repérer d'éventuelles alternatives shift/AND, même si un humain (ou du moins, un homme qui connaissait BOX_SIZE et BWIDTH/BHEIGHT, ce que je ne connais pas) pourrait le faire.

Il serait dommage de passer beaucoup de temps sur SIMDifying le mauvais bit du code ...

L'autre chose qui pourrait être intéressant de regarder en est si le travail peut être contraint quelque chose qui pourrait fonctionner avec une bibliothèque comme IPP, qui prendra des décisions bien informées sur la meilleure façon d'utiliser le processeur.

Answer 3

((int)(particles[i].sX+boxShiftX))/BOX_SIZE 

C'est cher si sX est un int (ne peut pas dire). Tronquer boxShiftX/Y à un int avant d'entrer dans la boucle.

Answer 4

http://simdx86.sourceforge.net/Modules.html

(Sur compilation, vous pouvez aussi essayer: gcc -O3 -msse2 ou similaire).

Answer 5

Votre algorithme a trop d'instructions de mémoire, d'entier et de branche pour avoir suffisamment de flops indépendants pour bénéficier de SIMD. Le pipeline sera constamment bloqué. Trouver un moyen plus efficace de randomiser serait le haut de la liste. Ensuite, essayez de travailler dans float ou int, mais pas les deux. Refonte des conditionnels comme arithmétique, ou au moins comme une opération de sélection. Seulement alors SIMD devient une proposition réaliste