Wersje SIMD instrukcji SHLD/SHRD

Question

Instrukcje SHLD/SHRD to instrukcje montażu służące do wprowadzania przesunięć wieloetapowych.

Rozważmy następujący problem:

uint64_t array[4] = {/*something*/}; 
left_shift(array, 172); 
right_shift(array, 172); 

Co jest najbardziej wydajnym sposobem wdrożenia left_shift i right_shift, dwie funkcje, które działa w oparciu o przesunięcie na tablicy czterech 64-bitowych bez znaku liczby całkowitej, jakby to była wielka 256 bitów bez znaku liczby całkowitej?

Czy jest to najskuteczniejszy sposób na wykonanie instrukcji SHLD/SHRD lub czy istnieją lepsze (jak wersje SIMD) instrukcje dotyczące nowoczesnej architektury?

Answer 1

W tej odpowiedzi zamierzam mówić tylko o x64.
x86 jest przestarzały od 15 lat, jeśli kodujesz w 2016 r., Nie ma sensu utknąć w 2000 r.
Wszystkie czasy są zgodne z Agner Fog's instruction tables.

Intel Skylake przykładowe czasy *
W shld/shrd instrukcje są raczej powolne na x64.
Nawet na skylake Intela mają opóźnienie 4 cykli i używają 4 upy, co oznacza, że ​​zużywa dużo jednostek wykonawczych, na starszych procesorach jest jeszcze wolniejszy.
zamierzam zakładać chcesz przesunąć o zmiennej wysokości, co oznacza

SHLD RAX,RDX,cl  4 uops, 4 cycle latency. -> 1/16 per bit 

Korzystanie 2 zmiany + dodaj można to zrobić szybciej wolniej.

@Init: 
MOV R15,-1 
SHR R15,cl //mask for later use.  
@Work: 
SHL RAX,cl  3 uops, 2 cycle latency 
ROL RDX,cl  3 uops, 2 cycle latency 
AND RDX,R15  1 uops, 0.25 latency 
OR RAX,RDX  1 uops, 0.25 latency  
//Still needs unrolling to achieve least amount of slowness. 

Należy zauważyć, że przesuwa to tylko 64 bity, ponieważ nie ma wpływu na RDX.
Próbujesz pokonać 4 cykle na 64 bity.

//4*64 bits parallel shift. 
//Shifts in zeros. 
VPSLLVQ YMM2, YMM2, YMM3 1uop, 0.5 cycle latency. 

Jednak jeśli chcesz to zrobić dokładnie to, co robi SHLD musisz używać dodatkowego VPSLRVQ oraz lub, aby połączyć te dwa wyniki.

VPSLLVQ YMM1, YMM2, YMM3 1uop, 0.5 cycle latency. 
VPSRLVQ YMM5, YMM2, YMM4 1uop, 0.5 cycle latency. 
VPOR YMM1, YMM1, YMM5 1uop, 0.33 cycle latency. 

Będziesz musiał przeplatać 4 zestawy tych kosztujących cię (3 * 4) + 2 = 14 YMM rejestrów.
W ten sposób wątpię, że będziesz czerpał korzyści z niskiego opóźnienia VPADDQ wynoszącego 0,33, więc zamiast tego przyjmę 0,5 opóźnienia.
To powoduje, że 3uops, 1,5 cykl opóźnienia dla 256 bitów = 1/171 na bit = 0,37 cyklu na QWord = 10x szybciej, nie jest zły. Jeśli jesteś w stanie uzyskać 1,33 cyklu na 256 bitów = 1/192 na bit = 0,33 cyklu na QWord = 12x szybciej.

'It’s the Memory, Stupid!'
Oczywiście nie dodaliśmy narzut w pętli i obciążenia/sklepy z/do pamięci.
Obwód pętli jest niewielki, biorąc pod uwagę prawidłowe wyrównanie celów skoku, ale dostęp do pamięci będzie z łatwością największym spowolnieniem.
Pojedynczy brak pamięci podręcznej do pamięci głównej w Skylake może kosztować more than 250 cycles¹.
To w sprytnym zarządzaniu pamięcią osiąga się duże zyski.
12-krotność przyspieszenia przy użyciu AVX256 to małe ziemniaki w porównaniu.

Nie liczę ustawień licznika zmian w CL/(YMM3/YMM4) ponieważ zakładam, że będziesz używał tej wartości przez wiele iteracji.

Nie zamierzasz tego robić z instrukcjami AVX512, ponieważ procesory klasy konsumenckiej z instrukcjami AVX512 nie są jeszcze dostępne.
Jedynym obecnie obsługiwanym obecnie procesorem jest Knights Landing.

*) Wszystkie te wartości są najlepszymi wartościami i powinny być traktowane jako wskazania, a nie jako wartości twarde.
) Koszt pominięcia pamięci podręcznej w Skylake: 42 cykle + 52ns = 42 + (52 * 4,6 GHz) = 281 cykli.