Vettorizzazione con buffer non allineati: utilizzando VMASKMOVPS: generazione di una maschera da un conteggio disallineamento? O non usare affatto quell’Inn

gcc 5.3 con -O3 -mavx -mtune=haswell per x86-64 rende il codice sorprendentemente ingombrante per gestire input potenzialmente disallineati per codice come:

 // convenient simple example of compiler input // I'm not actually interested in this for any real program void floatmul(float *a) { for (int i=0; i<1024 ; i++) a[i] *= 2; } 

clang utilizza istruzioni carico / archivio non allineate, ma gcc fa un’introduzione scalare / outro e un loop vettoriale allineato: rimuove le prime iterazioni non allineate fino a 7, srotolandolo completamente in una sequenza di

  vmovss xmm0, DWORD PTR [rdi] vaddss xmm0, xmm0, xmm0 ; multiply by two vmovss DWORD PTR [rdi], xmm0 cmp eax, 1 je .L13 vmovss xmm0, DWORD PTR [rdi+4] vaddss xmm0, xmm0, xmm0 vmovss DWORD PTR [rdi+4], xmm0 cmp eax, 2 je .L14 ... 

Questo sembra abbastanza terribile, esp. per CPU con una cache uop. Ho segnalato un bug di gcc su questo, con un suggerimento per il codice più piccolo / migliore che gcc poteva usare quando si rimuovevano le iterazioni non allineate. Probabilmente non è ancora ottimale, però.

Questa domanda riguarda ciò che effettivamente sarebbe ottimale con AVX . Sto chiedendo soluzioni generiche che gcc e altri compilatori potrebbero / dovrebbero usare. (Non ho trovato nessuna mailing list gcc con discussioni a riguardo, ma non ho speso molto tempo.)


Probabilmente ci saranno risposte multiple, poiché ciò che è ottimale per -mtune=haswell sarà probabilmente diverso da quello ottimale per -mtune=bdver3 ( -mtune=bdver3 ). E poi c’è la domanda su cosa sia ottimale quando si consente l’estensione di set di istruzioni (ad es. AVX2 per materiale intero da 256b, BMI1 per trasformare un conteggio in una maschera di bit con meno istruzioni).

Sono a conoscenza della guida di Optimization Assembly di Agner Fog, Sezione 13.5 Accesso ai dati non allineati e ai vettori parziali . Suggerisce di utilizzare accessi non allineati, eseguire una scrittura sovrapposta all’inizio e / o alla fine o mischiare i dati dagli accessi allineati (ma PALIGNR richiede solo un conteggio imm8, quindi 2x pshufb / por ). VMASKMOVPS che VMASKMOVPS non sia utile, probabilmente a causa di come funziona male su AMD. Sospetto che se si sintonizzi per Intel, vale la pena considerare. Non è ovvio come generare la maschera corretta, da qui il titolo della domanda.


Potrebbe risultare che sia meglio usare semplicemente accessi non allineati, come fa clang. Per i buffer brevi, il sovraccarico dell’allineamento potrebbe annullare qualsiasi vantaggio derivante dall’evitare le suddivisioni della cacheline per il ciclo principale. Per i buffer grandi, la memoria principale o L3 come collo di bottiglia può hide la penalità per le suddivisioni in cacheline. Se qualcuno ha dati sperimentali per eseguire il backup di questo per qualsiasi codice reale che hanno messo a punto, sono utili anche queste informazioni.


VMASKMOVPS sembra utilizzabile per obiettivi Intel. (La versione SSE è orribile, con un suggerimento implicito non temporale, ma la versione AVX non ha questo. C’è anche un nuovo intrinseco per essere sicuro di non ottenere la versione SSE per gli operandi 128b: _mm128_maskstore_ps ) La versione AVX è solo un po ‘lento su Haswell :

  • 3 upput / 4c latenza / 1-per-2c throughput come carico.
  • 4 throughput uop / 14c / 1-per-2c come archivio 256b.
  • 4 throughput / 13c latenza / 1-per-1c come archivio 128b.

La forma del negozio è ancora insolitamente lenta sulle CPU AMD, sia Jaguar (1 per 22c tput) che Bulldozer: 1 per 16c su Steamroller (simile a Bulldozer), o 1 per ~ 180c su Piledriver.

Ma se vogliamo usare VMASKMOVPS , abbiamo bisogno di un vettore con il bit più alto impostato in ogni elemento che dovrebbe essere effettivamente caricato / memorizzato. PALIGNR e PSRLDQ (per l’uso su un vettore di tutti i tipi) richiedono solo conteggi costanti in tempo di compilazione.

Si noti che gli altri bit non contano: non devono essere tutti, quindi spargere alcuni bit di impostazione sui bit alti degli elementi è una possibilità.

Carica una maschera per VMOVMASKPS da una finestra in una tabella. AVX2 o AVX1 con alcune istruzioni aggiuntive o una tabella più grande.

La maschera può anche essere utilizzata per ANDPS nei registri in una riduzione che deve contare ogni elemento esattamente una volta. Come sottolinea Stephen Canon nei commenti sull’OP, i carichi di pipeline possono consentire la sovrapposizione di archivi non allineati per funzionare anche per una funzione di riscrittura sul posto come nell’esempio che ho scelto, quindi VMASKMOVPS NON è la scelta migliore qui.


Questo dovrebbe essere buono su CPU Intel, esp. Haswell e più tardi per AVX2.

Il metodo Agner Fog per ottenere una maschera pshufb ha effettivamente fornito un’idea molto efficiente: fare un carico non allineato prendendo una finestra di dati da una tabella. Invece di una gigantesca tabella di maschere, utilizzare un indice come metodo per eseguire uno spostamento di byte sui dati in memoria.


Maschere nell’ordine del primo byte LSB (dato che sono memorizzate), non la solita notazione per gli elementi {X3,X2,X1,X0} in un vettore. Come scritto, si allineano con una finestra allineata che include l’inizio / la fine della matrice di input in memoria.

  • avvia conteggio errato = 0: mask = all-ones (caso allineato)
  • avvia il conteggio errato = 1: maschera = {0,-1,-1,-1,-1,-1,-1,-1} (salta uno nel primo 32B)
  • avvia conteggio errato = 7: maschera = {0, 0, 0, 0, 0, 0, 0,-1} (salta tutti tranne uno nel primo 32B)

  • fine disallineamento = 0: nessun elemento finale. mask = all-ones (caso allineato).
    questo è il caso strano, non simile a count = 1 . Un paio di istruzioni in più per questo caso speciale vale la pena di evitare un’ulteriore iterazione del ciclo e una pulizia con una maschera di tutti zero.

  • fine conteggio errato = 1: un elemento finale. mask = {-1, 0, 0, 0, 0, 0, 0, 0}
  • end misalign count = 7: seven elemme finali. mask = {-1,-1,-1,-1,-1,-1,-1, 0}

Codice non testato, supponiamo che ci siano errori

 section .data align 32 ; preferably no cache-line boundaries inside the table ; byte elements, to be loaded with pmovsx. all-ones sign-extends DB 0, 0, 0, 0, 0, 0, 0, 0 masktable_intro: ; index with 0..-7 DB -1, -1, -1, -1, -1, -1, -1, -1 masktable_outro: ; index with -8(aligned), or -1..-7 DB 0, 0, 0, 0, 0, 0, 0, 0 ; the very first and last 0 bytes are not needed, since we avoid an all-zero mask. section .text global floatmul ; (float *rdi) floatmul: mov eax, edi and eax, 0x1c ; 0x1c = 7 << 2 = 0b11100 lea rdx, [rdi + 4096 - 32] ; one full vector less than the end address (calculated *before* masking for alignment). ;; replace 4096 with rsi*4 if rsi has the count (in floats, not bytes) and rdi, ~0x1c ; Leave the low 2 bits alone, so this still works on misaligned floats. shr eax, 2 ; misalignment-count, in the range [0..7] neg rax vpmovsxbd ymm0, [masktable_intro + rax] ; Won't link on OS X: Need a separate LEA for RIP-relative vmaskmovps ymm1, ymm0, [rdi] vaddps ymm1, ymm1, ymm1 ; *= 2.0 vmaskmovps [rdi], ymm0, ymm1 ;;; also prepare the cleanup mask while the table is still hot in L1 cache ; if the loop count known to be a multiple of the vector width, ; the alignment of the end will be the same as the alignment of the start ; so we could just invert the mask ; vpxor xmm1, xmm1, xmm1 ; doesn't need an execution unit ; vpcmpeqd ymm0, ymm1, ymm0 ; In the more general case: just re-generate the mask from the one-past-the-end addr mov eax, edx xor ecx, ecx ; prep for setcc and eax, 0x1c ; sets ZF when aligned setz cl ; rcx=1 in the aligned special-case, else 0 shr eax, 2 lea eax, [rax + rcx*8] ; 1..7, or 8 in the aligned case neg rax vpmovsxbd ymm0, [masktable_outro + rax] .loop: add rdi, 32 vmovups ymm1, [rdi] ; Or vmovaps if you want to fault if the address isn't 4B-aligned vaddps ymm1, ymm1, ymm1 ; *= 2.0 vmovups [rdi], ymm1 cmp rdi, rdx ; while( (p+=8) < (start+1024-8) ) jb .loop ; 5 fused-domain uops, yuck. ; use the outro mask that we generated before the loop for insn scheduling / cache locality reasons. vmaskmov ymm1, ymm0, [rdi] vaddps ymm1, ymm1, ymm1 ; *= 2.0 vmaskmovps [rdi], ymm0, ymm1 ret ; vpcmpeqd ymm1, ymm1, ymm1 ; worse way to invert the mask: dep-chain breaker but still needs an execution unit to make all-ones instead of all-zeros. ; vpxor ymm0, ymm0, ymm1 

Ciò richiede un carico da una tabella, che può mancare nella cache L1 e 15B dei dati della tabella. (O 24B se anche il conteggio dei cicli è variabile, e dobbiamo generare separatamente la maschera finale).

In ogni caso, dopo le 4 istruzioni per generare il conteggio dei disallineamenti e l'indirizzo iniziale allineato, ottenere la maschera richiede solo una singola istruzione vpmosvsxbd. (La ymm, la forma mem non può micro-fondersi, quindi è 2 uops). Ciò richiede AVX2.


Senza AVX2:

  • 2x vpmovsxbd in due registri da 128b ( [masktable_intro + rax] e [masktable_intro + rax + 4] )
  • vinsertf128

Oppure: (più insns e più pressione shuffle-port, ma meno pressione port-load)

  • vpmovsxbw in un registro 128b
  • vpunpcklwd / vpunpckhwd in due regs xmm (src1 = src2 per entrambi)
  • vinsertf128

O:

  • vmovdqu da una tabella 60B di DWORDs ( DD ) anziché Byte ( DB ). Questo in realtà salverebbe un insn relativo a AVX2: l' address & 0x1c è l'indice, senza che sia necessario uno spostamento verso destra di due. L'intera tabella si inserisce ancora in una linea di cache, ma senza spazio per altre costanti che l'algo potrebbe utilizzare.

Overhead:

  • Oper intero: 5 uop all'inizio per ottenere un indice e allineare il puntatore iniziale. 7 uop per ottenere l'indice per la maschera finale. Il totale di 12 UPO di registro GP oltre il semplice utilizzo non allineato, se il numero di elementi del ciclo è un multiplo della larghezza del vettore.

  • AVX2: Due inss vettoriali a dominio con due fusibili per passare dall'indice [0..7] in un registro GP a una maschera in un registro YMM. (Uno per la maschera iniziale, uno per la maschera finale). Utilizza una tabella 24B, accessibile in una finestra 8B con granularità di byte.

  • AVX: sei inss vettoriali con dominio a 1 fusibile-uop (tre all'inizio e tre alla fine). Con l'indirizzamento relativo al RIP per la tabella, quattro di quelle istruzioni saranno [base+index] e non saranno micro-fuse, quindi potrebbe essere meglio un extra di due interi integer.

Il codice all'interno del ciclo viene replicato 3 volte.


TODO: scrivi un'altra risposta generando la maschera al volo, magari come byte in un reg 64b, quindi decomprimilo in 256b. Forse con un cambio di bit o BZHI del BMI2 (-1, conteggio)?

Solo AVX: accessi non allineati all’inizio / fine, pipeline i carichi per evitare problemi durante la riscrittura sul posto.

Grazie a @StephenCanon per aver sottolineato che questo è migliore di VMASKMOVPS per tutto ciò che VMASKMOVPS potrebbe fare per aiutare il loop su buffer non allineati.

Forse è un po ‘troppo aspettarsi che un compilatore faccia una trasformazione del ciclo, esp. poiché il modo ovvio può rendere infelice Valgrind (vedi sotto).

 section .text global floatmul ; (float *rdi) floatmul: lea rdx, [rdi + 4096 - 32] ; one full vector less than the end address (calculated *before* masking for alignment). ;; replace 4096 with rsi*4 if rsi has the count (in floats, not bytes) vmovups ymm0, [rdi] vaddps ymm0, ymm0, ymm0 ; *= 2.0 ; don't store yet lea rax, [rdi+32] and rax, ~0x1c ; 0x1c = 7 << 2 = 0b11100 vmovups ymm1, [rax] ; first aligned vector, for use by first loop iteration vmovups [rdi], ymm0 ; store the first unaligned vector vmovups ymm0, [rdx] ; load the *last* unaligned vector .loop: ;; on entry: [rax] is already loaded into ymm1 vaddps ymm1, ymm1, ymm1 ; *= 2.0 vmovups [rax] ; vmovaps would fault if p%4 != 0 add rax, 32 vmovups ymm1, [rax] cmp rax, rdx ; while( (p+=8) < (endp-8) ); jb .loop ; discard ymm1. It includes data from beyond the end of the array (aligned case: same as ymm0) vaddss ymm0, ymm0, ymm0 ; the last 32B, which we loaded before the loop vmovups [rdx], ymm0 ret ; End alignment: ; a[] = XXXX XXXX ABCD E___ _ = garbage past the end ; ^rdx ; ^rax ^rax ^rax ^rax(loop exit) ; ymm0 = BCDE ; ymm1 loops over ..., XXXX, ABCD, E___ ; The last load off the end of the array includes garbage ; because we pipeline the load for the next iteration 

Fare un carico dalla fine dell'array all'inizio del loop sembra un po 'strano, ma si spera che non confonda i prefetcher dell'hardware, o rallentare il stream dell'array dalla memoria.

Overhead:

  • 2 integer extra in totale (per impostare l'avvio allineato). Stiamo già utilizzando il puntatore finale per la normale struttura del ciclo, quindi è gratuito.

  • 2 copie extra del corpo del loop (carico / calc / store). (Prima e ultima iterazione sbucciata).


I compilatori probabilmente non saranno contenti di emettere codice come questo, quando si auto-vettorizzano. Valgrind segnalerà gli accessi al di fuori dei limiti dell'array , e lo fa con istruzioni di stepping singolo e decodifica per vedere a cosa stanno accedendo. Quindi rimanere semplicemente all'interno della stessa pagina (e linea della cache) come ultimo elemento dell'array non è sufficiente. Si noti inoltre che se il puntatore di input non è allineato 4B, possiamo potenzialmente leggere in un'altra pagina e segfault.

Per mantenere felice Valgrind, potremmo interrompere anticipatamente il loop di due larghezze vettoriali, per eseguire il caricamento del caso speciale dell'ultima larghezza vettoriale non allineata dell'array. Ciò richiederebbe la duplicazione del corpo del loop per un tempo extra (non significativo in questo esempio, ma è banale di proposito). O forse evitare il pipelining facendo saltare il codice introduttivo nel mezzo del loop. (Potrebbe non essere ottimale per la cache di uop, tuttavia: (parti di) il corpo del ciclo potrebbe finire due volte nella cache di uop).

TODO: scrivi una versione che salta nel loop a metà strada.