Phiên bản SIMD của hướng dẫn SHLD/SHRD

Question

Hướng dẫn SHLD/SHRD là hướng dẫn lắp ráp để thực hiện thay đổi đa điểm.

Hãy xem xét những vấn đề sau đây:

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

cách hiệu quả nhất để thực hiện left_shift và right_shift, hai chức năng mà hoạt động này một sự thay đổi trên một mảng bốn số nguyên unsigned 64-bit như thể nó là một lớn là gì 256 bit số nguyên không dấu?

Cách hiệu quả nhất để làm điều đó là sử dụng hướng dẫn SHLD/SHRD hoặc có hướng dẫn tốt hơn (như phiên bản SIMD) về kiến ​​trúc hiện đại không?

Answer 1

Trong câu trả lời này, tôi sẽ chỉ nói về x64.
x86 đã lỗi thời trong 15 năm nay nếu bạn đang viết mã vào năm 2016, khó có thể bị kẹt vào năm 2000.
Tất cả thời gian theo Agner Fog's instruction tables.

Intel Skylake dụ timings *
Các shld/shrd hướng dẫn khá chậm trên x64.
Ngay cả trên Intel skylake họ có độ trễ 4 chu kỳ và sử dụng 4 uops nghĩa là nó sử dụng nhiều đơn vị thực thi, trên các bộ vi xử lý cũ hơn, chúng thậm chí còn chậm hơn.
Tôi sẽ giả sử bạn muốn thay đổi bởi một số lượng biến, có nghĩa là một

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

Sử dụng 2 ca + thêm bạn có thể làm điều này nhanh chậm hơn.

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

Lưu ý rằng điều này chỉ thay đổi 64 bit vì RDX không bị ảnh hưởng.
Vì vậy, bạn đang cố gắng để đánh bại 4 chu kỳ mỗi 64 bit.

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

Tuy nhiên nếu bạn muốn nó thực hiện chính xác SHLD bạn cần sử dụng thêm VPSLRVQ và OR để kết hợp hai kết quả.

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ạn sẽ cần phải xen kẽ 4 bộ chi phí này cho bạn (3 * 4) + 2 = 14 thanh ghi YMM.
Làm như vậy tôi nghi ngờ bạn sẽ thu được lợi nhuận từ độ trễ thấp .33 của VPADDQ vì vậy tôi sẽ giả sử độ trễ 0.5 thay thế.
Điều đó làm cho 3uops, độ trễ chu kỳ 1,5 cho 256 bit = 1/171 mỗi bit = 0,37 chu kỳ mỗi QWord = 10x nhanh hơn, không tệ.
Nếu bạn có thể nhận được 1.33 chu kỳ trên 256 bit = 1/192 mỗi bit = 0,33 chu kỳ mỗi QWord = 12x nhanh hơn.

'It’s the Memory, Stupid!'
Rõ ràng là tôi đã không được thêm vào ở trên không lặp và tải/cửa hàng đến/từ bộ nhớ.
Chi phí vòng lặp rất nhỏ cho việc căn chỉnh các mục tiêu nhảy phù hợp, nhưng việc truy cập bộ nhớ
sẽ dễ dàng là sự sụt giảm lớn nhất.
Một bộ nhớ cache duy nhất bỏ lỡ bộ nhớ chính trên Skylake có thể khiến bạn mất chi phí more than 250 cycles¹.
Đó là trong quản lý thông minh của bộ nhớ rằng lợi ích lớn sẽ được thực hiện.
Tốc độ 12 lần có thể tăng tốc bằng AVX256 là so sánh với khoai tây nhỏ.

Tôi không tính việc thiết lập bộ đếm thay đổi trong CL/(YMM3/YMM4) vì tôi giả sử bạn sẽ sử dụng lại giá trị đó qua nhiều lần lặp lại.

Bạn sẽ không đánh bại điều đó với hướng dẫn AVX512, bởi vì CPU của người tiêu dùng có chỉ dẫn AVX512 chưa có sẵn.
Bộ xử lý hiện tại duy nhất hỗ trợ hiện tại là Knights Landing.

*) Tất cả các thời gian này là giá trị trường hợp tốt nhất và phải được coi là chỉ báo chứ không phải là giá trị cứng.
) Chi phí bỏ lỡ bộ nhớ cache trong Skylake: 42 chu kỳ + 52ns = 42 + (52 * 4,6Ghz) = 281 chu kỳ.