SIMD 버전의 SHLD/SHRD 명령어

Question

SHLD/SHRD 명령어는 다중 값 쉬프트를 구현하는 어셈블리 명령어입니다.

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

left_shift 및 right_shift, 그것은 큰 것처럼 네 개의 64 비트 부호없는 정수의 배열에 변화를 운영하는 두 가지 기능을 구현하는 가장 효율적인 방법은 무엇입니까 :

는 다음과 같은 문제를 고려 256 비트 부호없는 정수?

SHLD/SHRD 명령어를 사용하는 것이 가장 효율적인 방법입니까, 아니면 현대 건축에 대한 (SIMD 버전과 같은) 지침이 있습니까?

Answer 1

이 대답에서 나는 x64에 대해서만 이야기 할 것입니다.
x86은 2016 년에 코딩하면 15 년 동안 구식이되었습니다. 2000 년에 걸림돌이되는 것이 거의 없습니다.
모든 시간은 Agner Fog's instruction tables에 따라 결정됩니다.

인텔 스카이 레이크 예 타이밍 *이
shld/shrd 지침 64에 다소 느리다.
Intel skylake에서도 4 사이클의 대기 시간을 가지며 많은 실행 단위를 사용한다는 것을 의미하는 4 uops를 사용합니다. 구형 프로세서에서는 훨씬 느립니다.
나는 당신이 빠른 느리게 할 수있는 추가 + 2 개 교대를 사용하여

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

을 의미 변수 양에 의해 이동한다고 가정하겠습니다. RDX 영향을받지 않기 때문에

@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. 

참고 이것은 64 비트 시프트있다.
그래서 64 비트 당 4 사이클을이기려고합니다.

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

그러나 당신은 SHLD 당신이이 개 결과를 결합하는 추가 VPSLRVQ와 OR를 사용해야합니다 않습니다 정확히 수행하려는 경우.

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. 

귀하는 (3 * 4) + 2 = 14 YMM 레지스터를 4 세트 씩 인터리브해야합니다.
VPADDQ의 0.33 대기 시간 때문에 이익을 얻을 수 있을지 의심 스럽습니다. 대신 0.5 대기 시간을 가정합니다.
이렇게하면 3 비트가되며 256 비트의 경우 1.5 사이클 대기 시간 = 비트 당 1/171 = QWord 당 0.37 사이클 = 10 배 빠르며 나쁘지 않습니다.
256 비트 당 1.33 사이클을 얻을 수 있다면 비트 당 1/192 = QWord 당 0.33 사이클 = 12 배 빨라집니다.

'It’s the Memory, Stupid!'
는 분명 내가 루프 오버 헤드 및 부하/저장에/메모리에서 추가되지했습니다.
루프 오버 헤드는 점프 대상의 적절한 정렬을 고려할 때 매우 작지만 액세스가 가장 큰 속도 저하가 될 수있는 메모리는
입니다.
Skylake의 주 메모리에 대한 단일 캐시 누락으로 인해 more than 250 cycles¹이 발생할 수 있습니다.
메모리를 현명하게 관리하여 큰 이익을 얻습니다.
AVX256을 사용하여 12 배의 속도 향상이 가능한 작은 감자입니다.

시프트 카운터의 설정은 CL/(YMM3/YMM4)입니다. 많은 반복을 통해이 값을 재사용한다고 가정하기 때문에 저는 시프트 카운터를 세지 않았습니다.

AVX512 명령어가있는 일반 소비자 용 CPU는 아직 제공되지 않기 때문에 AVX512 명령어로이 문제를 해결할 수는 없습니다.
현재 지원하는 유일한 프로세서는 Knights Landing입니다.

*) 이러한 모든 타이밍은 최상의 경우 값이며 하드 값이 아닌 표시로 사용해야합니다.
) Skylake의 캐시 미스 비용 : 42 사이클 + 52ns = 42 + (52 * 4.6Ghz) = 281 사이클.