Velkommen til conf
SIMD liveprogrammering!
Jeg skal snakke om SIMD.
Single
Instruction
Multiple
Data
SIMD står for Single Instruction Multiple Data.
SIMD lar oss gjøre operasjoner flere operasjoner med en CPU-instruksjon. Dette vil gå betraktelig raskere. En SIMD-instruksjon tar ca. like lang tid som en tilsvarende "skalar"-instruksjon.
for (int i = 0; i < n; ++i) {
a[i] = a[i] + b[i];
}
Så la oss ta en kikk på denne koden. Her summerer vi tallene i to arrays og lagrer resultatet i en av dem.
for (int i = 0; i < n; ++i) {
a[i] = a[i] + b[i];
}
a[0] = a[0] + b[0] // add ax, bx
a[1] = a[1] + b[1]
...
I vanlig skalarkode plusser vi sammen element for element.
for (int i = 0; i < n; ++i) {
a[i] = a[i] + b[i];
}
a[0] = a[0] + b[0] // add ax, bx
a[1] = a[1] + b[1]
...
Erstattes med
a[0..8] = a[0..8] + b[0..8] // vadd ymm, ymm
a[8..16] = a[8..16] + b[8..16]
Dette er jo kjempegøy og veldig bra hvis du vil plusse sammen store arrays med tall. Og av og til vil du det, men veldig mye programmering gjør andre ting.
Dette var omtrent alt de første versjonene av SIMD kunne gjøre. Så jeg har alltid gledet meg til å kunne få bruk for det, men er stort sett aldri i en situasjon der det faktisk er nødvendig.
for (int i = 0; i < n; ++i) {
if (in[i] < 0) {
re[i] = 0;
im[i] = sqrt(abs(in[i]));
} else {
re[i] = sqrt(in[i]);
im[i] = 0;
}
}
For eksempel, la oss ta kvadratroten av alle tall i en array. Input er reelle tall, output er komplekse tall. Med skalare verdier er det enkelt, men med SIMD har vi et problem siden vi har en branch her.
Vel... det viser seg at SIMD har kommet et stykke siden begynnelsen.
Den viktige konseptet vi trenger for å løse dette problemet er "execution mask".
// input = { 0, -9, -1, 36, ... }
execution mask = in[0..8] < 0
// resultat 0, 1, 1, 0, ...
(masked) re[0..8] = 0
(masked) im[0..8] = sqrt(abs(in[0..8]));
execution mask = ~execution mask
// resultat 1, 0, 0, 1, ...
(masked) re[0..8] = sqrt(in[0..8]);
(masked) im[0..8] = 0
Her er pseudo-kode for hvordan dette foregår med SIMD. Vi sammenligner 4 og 4 element i arrayen og stapper resultatet i et register. Så går vi igjennom begge branchene, men instruksjonene blir bare eksekvert der execution bits er 1.
Når vi går over til den andre branchen gjør vi bare en bitwise NOT.
Hva blir dette i assembly-kode?
Register:
xmm 128 bits (4 floats)
ymm 256 bits (8 floats)
zmm 512 bits (16 floats)
Register:
xmm [ 128 ]
ymm [ 128 | xmm ]
zmm [ 256 | ymm ]
in[0..8] < 0
^
Gamledager:
xor ax, ax
ax = ax xor ax
0 xor 0 == 0
1 xor 1 == 0
I gamledager brukte vi dette trikset. Det setter ax til xor av.
in[0..8] < 0
^
Nye dager:
vxorps xmm1, xmm1, xmm1
xmm1 = xmm1 xor xmm1
Her setter vi xmm1 til 0.
vxorps xmm1, xmm1, xmm1
^
Vector extension
Først og fremst gjør dette at vi har separert resultatet fra operandene.
Dette er også de eneste intruksjonene som gir tilgang til 256-bits registre og oppover.
vxorps xmm1, xmm1, xmm1
^^^
xor
vxorps xmm1, xmm1, xmm1
^^
Packed Single Precision Float (32 bits)
Packed. Ingen løse bits mellom flyttallene her, nei!
Vi opererer på 32 bits flyttall (ikke at det har så mye å si akkurat for xor).
vxorps xmm1, xmm1, xmm1
resultat:
xmm1 = 0
ymm1 = 0
Dette har også effekten å sette de høye bitene i ymm1 til 0, så i effekt har vi satt ymm1 = 0.
in[0..8] < 0
^
Da har vi nullen i boks. La oss se på sammenligningen.
in[0..8] < 0
blir til
in[0..8] < ymm1
!( in[0..8] >= ymm1 )
!( ymm1 <= in[0..8] )
!( ymm1 <= in[0..8])
vcmpnleps ymm0, ymm1, ymmword ptr [rdi]
^ ^^
v og ps kjenner vi:
Vector extension og packed single precision float
!( ymm1 <= in[0..8])
vcmpnleps ymm0, ymm1, ymmword ptr [rdi]
^^^
cmp for compare.
!( ymm1 <= in[0..8])
vcmpnleps ymm0, ymm1, ymmword ptr [rdi]
^^^
Not less than or equal.
Grunnen til at vi snur om på rekkefølgen er at vi vil kun kan bruke minneoppslag som siste operand.
Samme med ymm1: Vi kan ikke bruke en immediate, altså en null, i denne posisjonen.
!( ymm1 <= in[0..8])
vcmpnleps ymm0, ymm1, ymmword ptr [rdi]
^^^^
For hver float:
Hvis sant: 0xFFFFFFFF
Hvis usant: 0
Resultat i ymm0.
// input = { 0, -9, -1, 36, ... }
execution mask = in[0..8] < 0
// resultat 0, 1, 1, 0, ...
(masked) re[0..8] = 0
(masked) im[0..8] = sqrt(abs(in[0..8]));
execution mask = ~execution mask
// resultat 1, 0, 0, 1, ...
(masked) re[0..8] = sqrt(in[0..8]);
(masked) im[0..8] = 0
Da har vi execution mask fra pseudokoden. Neste blir å faktisk gjøre operasjonene.
re[0..8] = 0
vmaskmovps ymmword ptr [rsi], ymm0, ymm1
^^^^^^^ ^^^^
Vi bruker masken som vi har i ymm0. Den ser her om den høyeste bitten er satt.
re[0..8] = 0
vmaskmovps ymmword ptr [rsi], ymm0, ymm1
^^^^^^^^^^^^^^^^^ ^^^^
re[0..8] 0
For alle bits som er satt i ymm0, gjør den moven.
vxorps xmm1, xmm1, xmm1
vcmpnleps ymm0, ymm1, ymmword ptr [rdi]
vmaskmovps ymmword ptr [rsi], ymm0, ymm1
Så da har vi altså:
- Null ut
ymm1 - Er verdiene mindre enn
0 - For de som er det, sett
re=0
Dette kan være opp til 8 ganger så raskt som å gjøre det sekvensielt.
En annen fin bonus her er at det ikke er noen brancher. Brancher kan virkelig sakke ned hastigheten på programmet. Denne fordelen kan man få med conditional move på vanlige register også.
for (int i = 0; i < n; ++i) {
if (in[i] < 0) {
re[i] = 0;
im[i] = sqrt(abs(in[i]));
} else {
re[i] = sqrt(in[i]);
im[i] = 0;
}
}
Ja, da har vi kommet et godt stykke på veien! Og vi har vel sett det meste av opkoder.
La oss se hvor mye vi har igjen: IntrinsicsGuide
Ok, det var jo en god del. Er det mulig å kode SIMD uten å lære seg alle disse?
Før vi går vi kan jeg nevne at vi har en opkode for kvadratrot (vsqrtps). For de som kjenner til "fast inverse square", kan det nok være på tide å huske den som "slow inverse square".
Et alternativ
Det finnes en del alternativ.
- Noen kompilatorer tilbyr pragma's for å gi hint
- Språk som OpenMP gir også hint
Vanskelig å si om hintene blir fulgt opp.
Vi vil ha et språk som er like "gjennomsiktig" som C. Vil har lyst å skjønne hvilken kode som blir generert.
ISPC
Et alternativ vi skal se på er ISPC, eller...
Intel
SPMD
Program
Compiler
Der SPMD står for...
Intel
Single Program Multiple Data
Program
Compiler
Evt...
Intel -> Single -> Program -> Compiler
| ^
+---+ +--+
v |
Multiple -> Data
for de som liker tilstandsmaskiner
Intel
Single Program Multiple Data
Program
Compiler
Av dette kan vi skjønne at det er laget av intel og at det er en programkompilator. (I motsetning til andre kompilatorer)
SPMD synes jeg er en litt forvirrende beskrivelse, men den prøver altså å si at du skriver ett program, og den går igjennom det på samme måte som vi har sett tidligere, med potensielt flere data om gangen.
for (int i = 0; i < n; ++i) {
if (in[i] < 0) {
re[i] = 0;
im[i] = sqrt(abs(in[i]));
} else {
re[i] = sqrt(in[i]);
im[i] = 0;
}
}
Jeg har visst lovet litt livekoding, så la oss prøve å kode om den tidligere C-koden vår til ISPC.
(livecoding)
Structs
(livecoding)
Structs
re im re im re im ...
Struct of array (SOA)
struct Complex {
float re[4];
float im[4];
};
re re re re im im im im
Array of struct of array (AOSOA)
struct Complex {
float re[4];
float im[4];
};
typedef Complex[100] ComplexArray;
re re re re im im im im re re re ...
ISPC
struct Complex {
float re;
float im;
};
typedef soa<4> Complex[100] ComplexArray;
re re re re im im im im re re re ...
Konvertering av programmer.
Gjør alt om til batch-operasjoner på arrays.
For å konvertere eksisterende program, gjelder det å gjøre alt om til arrays. Ofte kan dette være nok til at kompilatoren skjønner hvordan den kan "autovektorisere". Hvis ikke kan du legge skrive det i ISPC.
Konvertering av programmer.
OOP er ikke noe særlig.
Objekt-orientert programmering vil ofte jobbe mot dette målet. Like data må ligge ved siden av hverandre.
Dette er betyr mye jobb, hvis alt er veldig OOP.
Til slutt...
Det er drager her.
Frekvensreduksjon
SIMD går raskere, men prosessorer vil ofte redusere frekvensen ("gigahertz") med rundt 10% i flere millisekund etter en 512-bits instruksjon har blitt kjørt. Det er papers på hvordan man kan komme unna dette, men det gjør det hele mer komplisert.
SIMD-intrinsics er på vei til WebLisp
SIMD-intrinsics er på vei til WASM
JSON parsing med SIMD
https://github.com/lemire/simdjson
2.2 GB/s JSON-parsing
(RapidJSON på 0.51 GB/s og
fastjson på 0.26 GB/s)
Spørsmål?