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 устарел в течение 15 лет, если вы кодируете в 2016 году, вряд ли имеет смысл застревать в 2000 году.
Все времена соответствуют Agner Fog's instruction tables.

Intel Skylake пример тайминги *
В shld/shrd инструкции довольно медленно на x64.
Даже на Intel skylake у них есть латентность в 4 цикла и используется 4 uops, что означает, что он использует множество исполнительных блоков, а на более старых процессорах они еще медленнее.
Я предполагаю, что вы хотите перейти на переменную сумму, что означает

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

Используя 2 смены + добавить Вы можете сделать это быстрее медленнее.

@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 бит, потому что RDX не влияет.
Итак, вы пытаетесь бить 4 такта на 64 бит.

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

Вам необходимо будет чередовать 4 комплекта этих расходов, которые вы стоите (3 * 4) + 2 = 14 YMM-регистров.
В результате я сомневаюсь, что вы выиграете от низкой 0,33 латентности VPADDQ, поэтому я возьму на себя 0,5 латентности.
Это делает 3uops, 1,5-секундную задержку для 256 бит = 1/171 за бит = 0,37 цикла за QWord = 10 раз быстрее, неплохо.
Если вы можете получить 1,33 цикла на 256 бит = 1/192 на бит = 0,33 цикла на QWord = 12 раз быстрее.

'It’s the Memory, Stupid!'
Очевидно, я не добавил в накладных петель и нагрузки/сохраняет в/из памяти.
Накладные расходы на петле крошечные, учитывая правильное выравнивание целей перехода, но память
доступ будет легко быть самым большим замедлением.
Одиночный кеш-промах в основной памяти на Skylake может стоить вам more than 250 cycles¹.
Это умное управление памятью, что основные выгоды будут сделаны.
12-кратное ускорение с использованием AVX256 - это небольшой картофель для сравнения.

Я не рассчитываю настройку счетчика сдвига в CL/(YMM3/YMM4), потому что предполагаю, что вы будете использовать это значение для многих итераций.

Вы не будете бить это с помощью инструкций AVX512, потому что процессоры потребительского класса с инструкциями AVX512 пока недоступны.
Единственный текущий процессор, который поддерживает в настоящее время, - Knights Landing.

*) Все эти тайминги являются лучшими значениями для случая и должны восприниматься как показания, а не как жесткие значения.
) Стоимость пропусков кэш-памяти в Skylake: 42 цикла + 52ns = 42 + (52 * 4.6Ghz) = 281 цикл.