Самый быстрый способ хранения индексированных массивов в AVX512?

У меня есть операция вида:

for (I=0;I<31;I++)
{
 dst[index1[I]]=src1[I];
 dst[index2[I]]=src2[I];
}

Все массивы данных имеют 128b элементов. [отредактировано]

Я не уверен, как лучше всего реализовать это в AVX512. Я могу загрузить исходники в регистры zmm, но лучшее, что я могу сделать после этого, это использовать извлечения и 128-битные хранилища. Какие-либо предложения?


x86 avx avx512
person its    schedule 29.09.2020    source источник
comment
Подождите, все массивы имеют 128b элементов, даже индекс? x86-64 имеет только 64-битные указатели, так какой в ​​этом смысл? Или вы имели в виду только dst и 2 источника? Если index1/2 равен unsigned __int128, вы хотите просто обрезать их ширину указателя при индексировании массивов? Это единственное, что действительно имеет смысл. В своем ответе я предположил, что индексы, вероятно, будут 32-битными для экономии места.   -  person Peter Cordes    schedule 29.09.2020
comment
Я должен исправить это. Элементы индексного массива имеют длину 32 бита.   -  person its    schedule 29.09.2020

Ответы (1)


arrow_upward
2
arrow_downward

На современных процессорах разбросанные инструкции AVX-512 не очень быстрые, менее одного 64-битного элемента за такт на Skylake-X и чуть более 1 qword/такт на Ice Lake1. Ручной разброс должен быть лучше, чем эмуляция 128-битного разброса с точки зрения 64-разрядной инструкции разброса, но вы можете сравнить оба способа, если вам интересно.

Особенно, если индексы могут перекрываться (конфликтовать) между index1 и index2, 4 отдельных 128-битных хранилища почти наверняка лучше, чем проверка на коллизии между парами векторов индексов. Обратите внимание, что рассеяние 4x элементов из src1, а затем Элементы 4x из src2 дадут другой конечный результат, если idx1[1] == idx2[0]. В исходном порядке этот элемент dst получил бы src1[1], но если вы не будете осторожны, он получит src2[0].

Со 128-битными элементами, вероятно, просто сделать 512-битные загрузки и вручную разбросать с vmovdqu xmm (через _mm512_castsi512_si128/_mm_storeu_si128) и 3x _mm512_extracti64x2_epi64 (VEXTRACTI64x2) хранилищ.

Или 256-битные загрузки и vmovdqu xmm + vextracti128 сохранения. Но если вы используете 512-битные векторы в окружающем коде, вы можете использовать их и здесь; вы уже платите за частоту процессора и затраты на отключение порта выполнения.

Было бы хорошо, если бы вы могли заставить компилятор выполнять 64-битные загрузки индексных данных и разделять 32-битные половины с помощью mov eax, edx/shr rdx, 32, чтобы сэкономить на портах загрузки/сохранения памяти. Это возможно с GNU C typedef uint64_t aliasing_u64 __attribute((may_alias,aligned(4)));.

Сноска 1: например. vpscatterdq zmm на Skylake-X в лучшем случае имеет пропускную способность один на 11 циклов. Или на Ледяном озере, по одному на 7 циклов. https://uops.info/

Итак, это 4x 128-битных хранилища за 11 циклов. Ручной 128-битный разброс, вероятно, может выполнять как минимум 1x 128-битное сохранение за 2 цикла, возможно, даже 1 за такт. Или, может быть, даже быстрее на Ice Lake с двумя портами для хранения и двумя портами для загрузки и более широким внешним интерфейсом.

Scatter-инструкций также много для интерфейса: 26 или 19 на SKX или ICL соответственно.

Но ради интереса, эмулируя 128-битный скаттер:

Мы можем эмулировать разброс 128-битных элементов, используя разброс 64-битных элементов, например _mm512_i32scatter_epi64 (VPSCATTERDQ). Или _mm512_i64scatter_epi64 (VPSCATTERQQ), если ваши индексы должны быть 64-битными, в противном случае экономьте пропускную способность памяти для загрузки индексов.

Сгенерируйте индексный вектор, который хранит последовательные пары элементов qword в index1[I]*2 и index1[I]*2 + 1.

Масштабный коэффициент в разбросе может быть только 1,2,4 или 8, как и в режимах индексированной адресации x86. Если вы можете хранить свой индекс как смещения байтов вместо смещений элементов, это может быть полезно для повышения эффективности. В противном случае вам придется начать с удвоения каждого входного вектора индексов (добавляя его к себе).

Затем чередуйте его с увеличенной копией, возможно, с vpermt2d

void scatter(char *dst, __m512i data_lo, __m512i data_hi, __m256i idx)
{
    idx = _mm256_add_epi32(idx,idx);
    __m256i idx1 = _mm256_sub_epi32(idx, _mm256_set1_epi32(-1));

    const __m256i interleave_lo = _mm256_set_epi32(11,3, 10,2, 9,1,  8,0);
    const __m256i interleave_hi = _mm256_set_epi32(15,7, 14,6, 13,5, 12,4);
    __m256i idx_lo = _mm256_permutex2var_epi32(idx, interleave_lo, idx1);  // vpermt2d
    __m256i idx_hi = _mm256_permutex2var_epi32(idx, interleave_hi, idx1);

    _mm512_i32scatter_epi64(dst, idx_lo, data_lo, 8);
    _mm512_i32scatter_epi64(dst, idx_hi, data_hi, 8);
}

https://godbolt.org/z/TxzjWz показывает, как он компилируется в цикле. (clang полностью разворачивает его по умолчанию.)

person Peter Cordes    schedule 29.09.2020