Распакуйте m128i/m256i в m64 (MMX, SSE2, AVX2)
У меня память организована так:
block1 (m64), block2 (m64), block3 (m64), block4 (m64),....
Теперь я делаю в цикле for эту операцию:
итерация 1.....
x = block1 XOR block2
y = block1 AND block2
block1 = x
block2 = y
итерация 2.....
x = block3 XOR block4
y = block3 AND block4
block3 = x
block4 = y
И так далее...
Я попытался объединить блоки m64 с блоками m128i:
block1_block3 (m128), block2_block4 (m128),....
Теперь я могу использовать 128-битные инструкции SIMD, и цикл for будет составлять только 50% от команд m64.
Но плохо то, что я не могу привести память напрямую к m128i/m256i, потому что значения m64 не находятся в одной строке. Поэтому мне нужно будет собрать и разложить значения следующим образом:
// combine two 128 bit to one 256 bit nummber
__m256i static inline iCombine_128_256(__m128i *a, __m128i *b)
{
__m256i ret = _mm256_castsi128_si256(*a);
return _mm256_inserti128_si256(ret, *b, 1);
}
// combine four 64 bit to one 256 bit nummber
__m256i static inline iCombine_64_256(__m64 *a, __m64 *b, __m64 *c, __m64 *d)
{
__m256i ret = _mm256_castsi128_si256(_mm_set_epi64(*b, *a));
return _mm256_inserti128_si256(ret, _mm_set_epi64(*d, *c), 1);
}
// combine eight 32 bit to one 256 bit nummber
__m256i static inline iCombine_32_256(unsigned int *a, unsigned int *b, unsigned int *c, unsigned int *d, unsigned int *e, unsigned int *f, unsigned int *g, unsigned int *h)
{
__m256i ret = _mm256_castsi128_si256(_mm_set_epi32(*d, *c, *b, *a));
return _mm256_inserti128_si256(ret, _mm_set_epi32(*h, *g, *f, *e), 1);
}
Так что для сборки этих блоков потребуются дополнительные инструкции. Разве нет способа "обмануть" m256i? Допустим, я сообщаю x.m256i_u64[0] указатель первого блока 1, x.m256i_u64[1] второй указатель на block2,... И в сумме он показывает мне собранное значение m256i этих 4 значений m64? Это как-то возможно?
1 ответ
_mm_set_epi64() внутренние не волшебство. Они компилируются в грузы или тасования. Предоставление компилятору нескольких указателей для сортировки обычно является неправильным подходом при ручной векторизации: выясните, какие SSE/AVX можно использовать в случайном порядке после выполнения векторных загрузок.
Для 128b SSE2, (или AVX с -mprefer-avx128 gcc делает разумную работу по автоматической векторизации простой скалярной реализации, если знает, что указатель выровнен как минимум на 16B. (Таким образом, пара блоков, которые должны обрабатываться вместе, будет в одном выровненном блоке 16B). Я не вижу лучшего способа, и он может быть немного быстрее, чем скалярный 64-битный. Странно, но Clang не выполняет векторизацию, если у него нет AVX512 (для vpermt2q).
(С AVX2, gcc слишком тасует. Сообщается как https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82137. См. Ниже мою векторную версию, которая должна быть более чем в 2 раза быстрее, чем скаляр или SSE2 на Haswell.)
Посмотрите весь источник в проводнике компилятора Godbolt, чтобы увидеть, как он векторизован.
// scalar version for compilers to autovectorize
#include <stdint.h>
void foo(uint64_t blocks[]) {
// tell gcc the pointer is 64-byte aligned, to get a simpler auto-vectorization strategy.
blocks = __builtin_assume_aligned(blocks, 64);
for (intptr_t i = 0 ; i<10240 ; i+=2) {
uint64_t x = blocks[i];
uint64_t y = blocks[i+1];
blocks[i] = x^y;
blocks[i+1] = x&y;
}
}
Выровнены ли ваши указатели как минимум до 128b в вашем сценарии использования? Вероятно, вам следует попытаться сделать это, чтобы "пара" не разбивалась по границе строки кэша. Версия SSE2 может использовать выровненные загрузки / хранилища или операнды памяти для инструкций SSE вместо отдельных загрузок.
Есть много разных способов автоматической векторизации чего угодно. Вы могли бы даже рассмотреть возможность выравнивания перекрывающихся нагрузок, чтобы получить второй вектор с blocks[0] а также blocks[2] выстроились в ряд с низкими 64b каждой полосы 128b. (Пропускная способность загрузки, как правило, очень хороша для попаданий в кэш L1 на современных процессорах. Стоит рассмотреть возможность использования невыровненных нагрузок для уменьшения перестановки, но я не думаю, что это лучший вариант в этом случае для AVX2).
Сначала давайте рассмотрим скаляр (или 32-битный код, используя SSE2 для выполнения 64-битной скалярной целочисленной математики). gcc -m32 делает именно это с невыровненными указателями и без AVX или -mprefer-avx128):
mov # load
mov # load
mov # copy a register
and
xor
mov # store
mov # store
на пару 128b: 7 мопов в слитых доменах (все инструкции однопроцессорные). 2xload, 2xstore, 3x ALU (или меньше, если mov не нужен порт). Фронт-энд может выпустить 7 мопов в 1.75c (или меньше на Ryzen). Сохраняйте узкие места пропускной способности по 1 на такт на всех текущих процессорах, поэтому при достаточном развертывании цикла вы можете делать около 1 пары на 2 такта со скалярным x86-64, MMX или скалярным SSE2 даже на старых процессорах, таких как Core2 или Bulldozer.
SSE2
Вот как gcc автоматически векторизует, обрабатывая 2 пары за цикл. Это выглядит хорошо с AVX-128, но с SSE2 ему нужно 3 дополнительных инструкции movdqa, чтобы скопировать регистры, прежде чем уничтожать их как объединенный src/destination. (См. Следующий раздел для ручной версии, которая должна быть лучше).
b0 b1 # load128
b2 b3 # load128
# movdqa copy a reg
b0 b2 # punpcklqdq
b1 b3 # punpckhqdq
# movdqa copy a reg
b0&b1 b2&b3 # pand
b0^b1 b2^b3 # pxor
# movdqa copy a reg
b0^b1 b0&b1 # punpcklqdq
# store 128
b2^b3 b2&b3 # punpckhqdq
# store 128
13 слитков домена. (3.25c внешние циклы на процессорах, отличных от Ryzen). 4x shuffle, 2xload, 2x store, 2x boolean. 3x reg-reg copy, которая либо использует порт исполнения ALU, либо нет, в зависимости от процессора. Но это не имеет значения, 5 ALU мопов в 3,25 циклах не являются узким местом.
gcc -m32 делает интересный выбор - использовать punpckh / l с одним и тем же операндом памяти дважды вместо отдельного movdqa загрузить для 2-го вектора. Это сохраняет UOP с плавким доменом (потому что punpck может микроплавкий предохранитель), но держит порт нагрузки более загруженным. Тем не менее, не узкое место.
Intel Haswell и более поздние узкие места - 1 случайное перемешивание за такт, поэтому они имеют пропускную способность 4c или 2c на пару, аналогично скаляру (но, вероятно, легче приблизиться к этому пределу и может достичь его даже без развертывания цикла).
Процессоры AMD и Intel Core2 для IvyBridge могут выполнять 2 раза по 128 байт в час, так что они просто узкое место во внешнем интерфейсе при нагрузке цикла 3,25 с +, а не на какой-либо конкретный порт. С небольшим количеством накладных расходов это может быть 1.75c на пару. (Или Райзен может делать около 5 мопов за такт, выполняя однопроцессные инструкции, поэтому две пары на ~2,6 такта или 1 пара на ~1,3 такта + накладные расходы).
С AVX-128 и микросинхронными нагрузками это 9 мопов в слитых доменах (2,25c + накладные расходы цикла для выдачи). Все еще 4x тасует, и требует AVX1, но это отлично для Sandybridge и AMD. Около 1.125c + накладные расходы цикла на пару на SnB.
SSE2 / SSE3 ручная векторизация
Самая большая проблема с версией SSE2 выше - все дополнительные инструкции movdqa для копирования регистров перед их уничтожением.
Мы можем воспользоваться преимуществами AND и XOR, чтобы сохранить некоторые инструкции asm. x&x = x, а также x ^ 0 = x,
Эта версия может быть хороша для Haswell, используя 3 загрузки одинаковых данных. Но на других процессорах (в том числе AMD) такое количество загрузок + хранилищ будет узким местом.
x x # movddup load (SSE3)
x x&y # pand [mem]
y 0 # movq load
x^y x&y # pxor ([x x&y], [y 0])
store
5 uops (1.25c front-end), 3 loads + 1 store (1.5c HSW, or 2c AMD/SnB, or 3c NHM)
Или эта версия является хорошим балансом между загрузкой и перемешиванием. На самом деле это действительно хорошо для pre-AVX2.
x y # load
x x # movddup or pshufd to copy+shuffle
x x&y # pand
y 0 # movq load or PSRLDQ by 8 bytes
x^y x&y # pxor
store
6 uops (1.5c front-end + loop overhead)
movq-load version: 2 loads + 1 store (1c HSW, 1.5c AMD/SNB, 2c NHM)
PSRLDQ version: 1 load + 1 store, 2 shuffles, 2 boolean: (2c HSW, 1.33c AMD and Intel NHM/SnB)
Таким образом, передний конец является узким местом для версии с 2 шаффлами, даже на Nehalem, который не может делать 2 загрузки за такт. На процессорах без AVX2 это может быть заметно лучше, чем скалярное:
#include <immintrin.h>
void pair_u64_sse2(uint64_t blocks[]) {
// take advantage of x&x = x
// and x&y ^ 0 = x&y
for (int i = 0 ; i<10240 ; i+=2) {
__m128i v = _mm_loadu_si128((__m128i*)&blocks[i]);
__m128i dup = _mm_shuffle_epi32(v, _MM_SHUFFLE(1,0, 1,0));
__m128i and = _mm_and_si128(v, dup); // x x&y
__m128i y = _mm_srli_si128(v, 8); // y 0
__m128i xor = _mm_xor_si128(and, y); // x^y x&y
_mm_storeu_si128((__m128i*)&blocks[i], xor);
}
}
На ссылке Godbolt, посмотрите на вкладку clang для вывода asm не AVX. gcc использует дополнительные movdqa без причины, но clang преуспевает в том, чтобы не тратить инструкции. При развертывании цикла он должен приближаться к 1 вектору на 1,5 такта (если данные в кеше перегреваются) на процессорах Intel pre-Haswell или некоторых процессорах AMD. На Ryzen, может быть, даже лучше, чем это.
AVX2
Это то, где компиляторы делают ужасную работу, смотрите отчёт об ошибках gcc, который я подал, связанный ранее.
Векторизация вручную для одного вектора 256b за раз с такой схемой перемещения данных должна быть хорошей:
b0 b1 | b2 b3 # load 256b
b1 b0 | b3 b2 # vpshufd
b0^b1 b0^b1 | b2^b3 b2^b3 # vpxor
b0&b1 b0&b1 | b2^b3 b2&b3 # vpand
b0^b1 b0&b1 | b2^b3 b2&b3 # vpblendd
# store 256b
Вот встроенная версия C/C++:
#include <immintrin.h>
void pairs_u64_avx2(uint64_t blocks[]) {
for (int i = 0 ; i<10240 ; i+=4) {
__m256i v = _mm256_loadu_si256((__m256i*)&blocks[i]);
__m256i swapped = _mm256_shuffle_epi32(v, _MM_SHUFFLE(1,0, 3,2));
__m256i and = _mm256_and_si256(v, swapped);
__m256i xor = _mm256_xor_si256(v, swapped);
__m256i blend = _mm256_blend_epi32(xor, and, _MM_SHUFFLE(3,0,3,0));
_mm256_storeu_si256((__m256i*)&blocks[i], blend);
}
}
Это 6 мопов слитых доменов в Intel, и они должны легко работать с 1 итером на 1,5 цикла (+ издержки цикла), без узких мест на любых портах. Узким местом является внешний интерфейс, поэтому развертывание помогает.
Это 0,75 цикла на пару 128b на Haswell, плюс накладные расходы на цикл.
Немедленное смешивание может выполняться на любом порту в HSW+ или p0/p5 в SnB (и хорошая пропускная способность в BD/Ryzen), так что это намного более благоприятно для пропускной способности, чем использование vunpcklqdq для объединения векторов результата AND / XOR.
Другие заброшенные идеи, которые не выглядели многообещающими
b0 b1 load 128
b2 b3 load 128
b0 b1 | b3 b4 vinsertf128 y,y,m,1 (SKL: 2 uops, load + p015 ALU)
b2 b3 | b5 b6 vinsertf128
Нет, легче получить это с
b0 b1 | b2 b3 v = load256 aligned
b4 b5 | b6 b7 v2 = load256 aligned
b0 b1 | b6 b7 vpblendd //vinserti128 (v, v2)
b2 b3 | b4 b5 vperm2i128 (v, v2) (doesn't micro-fuse, unlike vpunpck, so not helpful to use with a memory operand)
Then vpunpck l/h in-lane shuffles, then a AND/XOR,
then 2x VPERMQ + 2x vpunpck?
Or vpunpck and split 128b stores? vmovdqa 128b + vextracti128
b0 b1 # load128
b1 b0 # pshufd (copy+shuffle)
# movdqa copy
b0&b1 b1&b0 # pand
movq # store low half
b0^b1 b1^b0 # pxor
movq # store low half
В принципе нет преимуществ по сравнению со скаляром.
Может быть, можно объединить два вектора вместе и использовать movhps хранить верхнюю половину? Тем не менее, для этого требуется uop со случайным портом, поэтому не так много, чтобы выиграть по сравнению с punpckhqdq или movhlps, чтобы объединить два регистра для 128-битного хранилища.