SIMD ne vale la pena? C'è un'opzione migliore?

Question

Ho un codice che funziona abbastanza bene, ma mi piacerebbe farlo funzionare meglio. Il problema principale che ho con esso è che ha bisogno di avere un ciclo annidato. Quella esterna è per le iterazioni (che devono avvenire in serie), e quella interna per ogni particella punto in esame. So che non c'è molto che possa fare quello esterno, ma mi chiedo se c'è un modo di ottimizzare qualcosa di simile:

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; 
      } 
    }/*}}}*/ 

Ho guardato SIMD, anche se non riesco a trovare molto su esso, e non sono del tutto sicuro che l'elaborazione richiesta per estrarre e impacchettare correttamente i dati varrebbe la pena di fare la metà delle istruzioni, dal momento che apparentemente solo due doppi possono essere usati contemporaneamente.

Ho provato a suddividerlo in più thread con shm e pthread_barrier (per sincronizzare le diverse fasi, di cui il codice precedente è uno), ma lo ha reso più lento.

Il mio codice attuale è abbastanza veloce; è nell'ordine di un secondo per 10M di iterazioni di particelle * e da quello che posso dire da gprof, il 30% del mio tempo viene speso solo in quella funzione (5000 chiamate; PART_COUNT = 8192 particelle impiegano 1,8 secondi). Non sono preoccupato per le piccole cose a tempo costante, sono solo 512K particelle * 50.000 iterazioni * 1000 esperimenti hanno impiegato più di una settimana l'ultima volta.

Credo che la mia domanda sia se esiste un modo per gestire questi lunghi vettori che è più efficiente del semplice scorrere su di essi. Mi sento come dovrebbe essere, ma non riesco a trovarlo.

Answer 1

Non sono sicuro di quanto trarrebbe vantaggio SIMD; il ciclo interno è piuttosto piccolo e semplice, quindi suppongo (solo osservando) che tu sia probabilmente più legato alla memoria di qualsiasi altra cosa. Con questo in mente, mi piacerebbe provare a riscrivere la parte principale del ciclo di non toccare la matrice particelle più necessario:

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; 

Questo ha il piccolo potenziale effetto collaterale di non fare l'aggiunta extra alla fine.

---

altro potenziale accelerazione sarebbe usare __restrict sull'array particella, in modo che il compilatore può ottimizzare meglio le scritture le velocità. Inoltre, se Wxx, ecc. Sono variabili globali, potrebbero dover essere ricaricate ogni volta attraverso il ciclo invece di essere eventualmente memorizzate nei registri; usando __restrict sarebbe di aiuto anche con quello.

---

Dal momento che si sta accedendo le particelle in ordine, si può provare prefetching (ad esempio __builtin_prefetch su GCC) poche particelle avanti per ridurre la cache miss. Il precaricamento sulle scatole è un po 'più difficile dal momento che le stai accedendo in un ordine imprevedibile; si potrebbe provare qualcosa di simile

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

---

Un ultimo uno che ho appena notato - se la casella :: rotDir è sempre +/- 1.0, quindi è possibile eliminare il confronto e filiale nel ciclo interno in questo modo:

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; 

---

Naturalmente, valgono i soliti avvertimenti di profilazione prima e dopo. Ma penso che tutto ciò possa aiutare e può essere fatto indipendentemente dal fatto che tu passi o meno a SIMD.

Answer 2

Avete un profilo sufficiente per dirvi dove è trascorso il tempo all'interno di tale funzione?

Ad esempio, sei sicuro che non sono i tuoi div e mod nel calcolo del boxnum in cui viene speso il tempo? A volte i compilatori non riescono a individuare possibili alternative a MAIUSC/AND, anche se un essere umano (o almeno uno che conosceva BOX_SIZE e BWIDTH/BHEIGHT, che non conosco) potrebbe essere in grado di farlo.

Sarebbe un peccato spendere un sacco di tempo sul SIMDifying il bit sbagliata del codice ...

L'altra cosa che potrebbe essere merita di essere esaminata è se il lavoro può essere costretto in qualcosa che potrebbe funzionare con una libreria come IPP, che prenderà decisioni ben informate sul modo migliore di utilizzare il processore.

Answer 3

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

Questo è costoso se sX è un int (non si sa). Tronca boxShiftX/Y a un int prima di entrare nel ciclo.

Answer 4

Solo per la cronaca, c'è anche libSIMDx86!

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

(On compilazione si può anche provare: gcc -O3 -msse2 o simili).

Answer 5

L'algoritmo contiene troppe istruzioni di memoria, intero e diramazione per disporre di un numero di flop indipendenti sufficiente a trarre vantaggio da SIMD. Il gasdotto sarà costantemente in stallo.

Trovare un modo più efficace di randomizzare sarebbe in cima alla lista. Quindi, prova a lavorare in float o in int, ma non in entrambi. Ripeti i condizionali come aritmetici, o almeno come operazione di selezione. Solo allora SIMD diventa una proposta realistica