Векторизация косвенного доступа с помощью инструкций AVX
Недавно я познакомился с Vector Instructions (теоретически) и очень рад тому, как я могу использовать их для ускорения своих приложений.
Одна область, которую я хотел бы улучшить, это очень горячий цикл:
__declspec(noinline) void pleaseVectorize(int* arr, int* someGlobalArray, int* output)
{
for (int i = 0; i < 16; ++i)
{
auto someIndex = arr[i];
output[i] = someGlobalArray[someIndex];
}
for (int i = 0; i < 16; ++i)
{
if (output[i] == 1)
{
return i;
}
}
return -1;
}
Но, конечно, все 3 основных компилятора (msvc, gcc, clang) отказываются векторизовать это. Я могу понять почему, но я хотел получить подтверждение.
Если бы мне пришлось векторизовать это вручную, это было бы:
(1) VectorLoad «arr», это вводит 16 4-байтовых целых чисел, скажем, в zmm0
(2) 16 памяти загружаются с адреса, на который указывает zmm0 [0..3], в zmm1 [0..3], загрузка с адреса, на который указывает zmm0 [4..7], в zmm1 [4..7], так и так далее
(3) сравнить zmm0 и zmm1
(4) вектор popcnt в выходной файл, чтобы определить самый значимый бит и, по сути, разделить его на 8, чтобы получить соответствующий индекс
Прежде всего, могут ли векторные инструкции делать эти вещи? Как они могут выполнить эту операцию «сбора», то есть выполнить загрузку с адреса, указывающего на zmm0?
Вот что генерирует Clang:
0000000000400530 <_Z5superPiS_S_>:
400530: 48 63 07 movslq (%rdi),%rax
400533: 8b 04 86 mov (%rsi,%rax,4),%eax
400536: 89 02 mov %eax,(%rdx)
400538: 48 63 47 04 movslq 0x4(%rdi),%rax
40053c: 8b 04 86 mov (%rsi,%rax,4),%eax
40053f: 89 42 04 mov %eax,0x4(%rdx)
400542: 48 63 47 08 movslq 0x8(%rdi),%rax
400546: 8b 04 86 mov (%rsi,%rax,4),%eax
400549: 89 42 08 mov %eax,0x8(%rdx)
40054c: 48 63 47 0c movslq 0xc(%rdi),%rax
400550: 8b 04 86 mov (%rsi,%rax,4),%eax
400553: 89 42 0c mov %eax,0xc(%rdx)
400556: 48 63 47 10 movslq 0x10(%rdi),%rax
40055a: 8b 04 86 mov (%rsi,%rax,4),%eax
40055d: 89 42 10 mov %eax,0x10(%rdx)
400560: 48 63 47 14 movslq 0x14(%rdi),%rax
400564: 8b 04 86 mov (%rsi,%rax,4),%eax
400567: 89 42 14 mov %eax,0x14(%rdx)
40056a: 48 63 47 18 movslq 0x18(%rdi),%rax
40056e: 8b 04 86 mov (%rsi,%rax,4),%eax
400571: 89 42 18 mov %eax,0x18(%rdx)
400574: 48 63 47 1c movslq 0x1c(%rdi),%rax
400578: 8b 04 86 mov (%rsi,%rax,4),%eax
40057b: 89 42 1c mov %eax,0x1c(%rdx)
40057e: 48 63 47 20 movslq 0x20(%rdi),%rax
400582: 8b 04 86 mov (%rsi,%rax,4),%eax
400585: 89 42 20 mov %eax,0x20(%rdx)
400588: 48 63 47 24 movslq 0x24(%rdi),%rax
40058c: 8b 04 86 mov (%rsi,%rax,4),%eax
40058f: 89 42 24 mov %eax,0x24(%rdx)
400592: 48 63 47 28 movslq 0x28(%rdi),%rax
400596: 8b 04 86 mov (%rsi,%rax,4),%eax
400599: 89 42 28 mov %eax,0x28(%rdx)
40059c: 48 63 47 2c movslq 0x2c(%rdi),%rax
4005a0: 8b 04 86 mov (%rsi,%rax,4),%eax
4005a3: 89 42 2c mov %eax,0x2c(%rdx)
4005a6: 48 63 47 30 movslq 0x30(%rdi),%rax
4005aa: 8b 04 86 mov (%rsi,%rax,4),%eax
4005ad: 89 42 30 mov %eax,0x30(%rdx)
4005b0: 48 63 47 34 movslq 0x34(%rdi),%rax
4005b4: 8b 04 86 mov (%rsi,%rax,4),%eax
4005b7: 89 42 34 mov %eax,0x34(%rdx)
4005ba: 48 63 47 38 movslq 0x38(%rdi),%rax
4005be: 8b 04 86 mov (%rsi,%rax,4),%eax
4005c1: 89 42 38 mov %eax,0x38(%rdx)
4005c4: 48 63 47 3c movslq 0x3c(%rdi),%rax
4005c8: 8b 04 86 mov (%rsi,%rax,4),%eax
4005cb: 89 42 3c mov %eax,0x3c(%rdx)
4005ce: c3 retq
4005cf: 90 nop
Решение
Ваша идея о том, как это может работать, близка, за исключением того, что вы хотите bit-scan / find-first-set-bit (x86 BSF или TZCNT) растрового изображения сравнения, а не численности населения (число биты установлены).
AVX2 / AVX512 есть vpgatherdd который использует вектор 32-битных масштабированных индексов со знаком. Едва ли стоит использовать на Haswell, улучшен на Broadwell и очень хорош на Skylake. (http://agner.org/optimize/, и увидеть другие ссылки в тег x86 вики, например, руководство по оптимизации Intel, в котором есть раздел о повышении производительности). SIMD сравнение и битовое сканирование очень дешевы по сравнению; один моп и полностью конвейерный.
gcc8.1 может автоматически векторизовать ваш сбор, если это может доказать, что ваши входы не перекрывают ваши output функция арг. Иногда возможно после встраивания, но для не встроенной версии вы можете пообещать это с int * __restrict output, Или если вы делаете output локальный временный вместо функции arg. (Общее правило: хранение через не_restrict указатель часто запрещает автоматическую векторизацию, особенно если это char* который может иметь псевдоним что угодно.)
gcc и clang никогда не векторизируют поисковые циклы; только циклы, где счетчик поездок может быть рассчитан до входа в цикл. Но ICC может; он собирает скаляр и сохраняет результат (даже если output[] местный, так что не иметь чтобы сделать это как побочный эффект от запуска функции), затем используется SIMD Packaged-Compare + Bit-Scan.
Выход компилятора для __restrict версия. Обратите внимание, что gcc8.1 и ICC по умолчанию избегают 512-битных векторов при настройке Skylake-AVX512. 512-битные векторы могут ограничивать максимальное турбо и всегда отключать вектор ALU на порту 1, пока они находятся в конвейере, поэтому имеет смысл использовать AVX512 или AVX2 с 256-битными векторами, если эта функция только небольшая часть большой программы. (Компиляторы не знают, что эта функция в вашей программе перегрета.)
Если output[] Это локальная, лучше стратегия генерации кода, вероятно, будет сравнивать при сборе, поэтому раннее попадание пропускает остальные нагрузки. Компиляторы, которые работают полностью скалярно (clang и MSVC), оба пропускают эту оптимизацию. Фактически, они даже сохраняются в локальном массиве, хотя clang в основном не перечитывает его (сохраняя результаты в регистрах). Запись исходного кода со сравнением внутри первого цикла будет работать для получения лучшего скалярного кода. (В зависимости от пропусков в кеше из-за ошибок сбора и ветвления при поиске без SIMD, скаляр может быть хорошей стратегией. Особенно, если попадания в первые несколько элементов являются общими. В настоящее время оборудование сбора не может использовать преимущества нескольких элементов, поступающих из та же строка кэша, поэтому жесткий предел по-прежнему составляет 2 элемента, загружаемых за такт.
Но использование широкой векторной нагрузки для индексов для подачи набора значительно снижает нагрузку на порт / кэш-нагрузку, если ваши данные в основном были горячими в кеше.)
Компилятор мог автоматически векторизовать __restrict версия вашего кода примерно так. (gcc управляет частью сбора, ICC управляет частью сравнения SIMD)
;; Windows x64 calling convention: rcx,rdx, r8,r9
; but of course you'd actually inline this
; only uses ZMM16..31, so vzeroupper not required
vmovdqu32 zmm16, [rcx/arr] ; You def. want to reach an alignment boundary if you can for ZMM loads, vmovdqa32 will enforce that
kxnorw k1, k0,k0 ; k1 = -1. k0 false dep is likely not a problem.
; optional: vpxord xmm17, xmm17, xmm17 ; break merge-masking false dep
vpgatherdd zmm17{k1}, [rdx + zmm16 * 4] ; GlobalArray + scaled-vector-index
; sets k1 = 0 when done
vmovdqu32 [r8/output], zmm17
vpcmpd k1, zmm17, zmm31, 0 ; 0->EQ. Outside the loop, do zmm31=set1_epi32(1)
; k1 = compare bitmap
kortestw k1, k1
jz .not_found ; early check for not-found
kmovw edx, k1
; tzcnt doesn't have a false dep on the output on Skylake
; so no AVX512 CPUs need to worry about that HSW/BDW issue
tzcnt eax, edx ; bit-scan for the first (lowest-address) set element
; input=0 produces output=32
; or avoid the branch and let 32 be the not-found return value.
; or do a branchless kortestw / cmov if -1 is directly useful without branching
ret
.not_found:
mov eax, -1
ret
Вы можете сделать это самостоятельно с помощью встроенных функций:
Справочное руководство по набору инструкций Intel (выдержка HTML в http://felixcloutier.com/x86/index.html) включает в себя собственные имена C / C ++ для каждой инструкции или ищет их в https://software.intel.com/sites/landingpage/IntrinsicsGuide/
Я изменил output введите в __m512i, Вы можете изменить его обратно на массив, если вы не векторизуете вызывающего вручную. Вы определенно хочу эту функцию встроить.
#include <immintrin.h>
//__declspec(noinline) // I *hope* this was just to see the stand-alone asm version
// but it means the output array can't optimize away at all
//static inline
int find_first_1(const int *__restrict arr, const int *__restrict someGlobalArray, __m512i *__restrict output)
{
__m512i vindex = _mm512_load_si512(arr);
__m512i gather = _mm512_i32gather_epi32(vindex, someGlobalArray, 4); // indexing by 4-byte int
*output = gather;
__mmask16 cmp = _mm512_cmpeq_epi32_mask(gather, _mm512_set1_epi32(1));
// Intrinsics make masks freely convert to integer
// even though it costs a `kmov` instruction either way.
int onepos = _tzcnt_u32(cmp);
if (onepos >= 16){
return -1;
}
return onepos;
}
Все 4 x86 компилятора выдают схожий ассемблер с тем, что я предложил (увидеть это в проводнике компилятора Godbolt), но, конечно, они должны на самом деле материализовать set1_epi32(1) векторную константу или используйте (широковещательный) операнд памяти. Clang на самом деле использует {1to16} широковещательная нагрузка от константы для сравнения: vpcmpeqd k0, zmm1, dword ptr [rip + .LCPI0_0]{1to16}, (Конечно, они сделают разные варианты, когда будут встроены в цикл.) Другие используют mov eax,1 / vpbroadcastd zmm0, eax,
gcc8.1 -O3 -march = skylake-avx512 имеет два избыточных mov eax, -1 инструкции: один, чтобы накормить kmov для сбора, другой для материала возвращаемого значения. Глупый компилятор должен хранить его и использовать другой регистр для 1,
Все они используют zmm0..15 и поэтому не могут избежать vzeroupper, (xmm16.31 не доступны с legacy-SSE, поэтому проблема штрафа перехода SSE / AVX, которая vzeroupper решает не существует, если используются только широкие векторные регистры y / zmm16..31). Все еще могут быть крошечные возможные преимущества vzeroupper, такие как более дешевые контекстные переключатели, когда известно, что верхние половины регистров ymm или zmm равны нулю (Полезно ли использовать VZEROUPPER, если ваша программа + библиотеки не содержат инструкций SSE?). Если вы все равно собираетесь его использовать, нет причин избегать xmm0..15.
Да, и в соглашении о вызовах Windows xmm6..15 сохраняется при вызове. (Не ymm / zmm, только младшие 128 бит), поэтому zmm16..31 — хороший выбор, если у вас закончились регистры xmm0..5.
Другие решения
Других решений пока нет …