Преобразование из исходных индексов в целевые индексы
Я использую инструкции AVX2 в некотором C-коде.
Инструкция VPERMD принимает два 8-целых вектора a а также idx и генерирует третий, dstпереставляя a основанный на idx, Это похоже на dst[i] = a[idx[i]] for i in 0..7, Я называю этот источник на основе, потому что движение индексируется на основе источника.
Тем не менее, у меня есть мои рассчитанные индексы в форме на основе назначения. Это естественно для установки массива и эквивалентно dst[idx[i]] = a[i] for i in 0..7,
Как я могу преобразовать из исходной формы в форму назначения? Пример теста:
{2 1 0 5 3 4 6 7} source-based form.
{2 1 0 4 5 3 6 7} destination-based equivalent
Для этого преобразования я остаюсь в регистрах ymm, так что это означает, что решения на основе назначения не работают. Даже если бы я вставил каждый из них отдельно, так как он работает только с постоянными индексами, вы не можете просто установить их.
3 ответа
Я предполагаю, что вы неявно говорите, что вы не можете изменить свой код для вычисления исходных индексов? Я не могу придумать ничего, что вы можете сделать с x86 SIMD, кроме инструкций разброса AVX512, которые принимают индексы на основе dst.
Хранение в памяти, инвертирование и перезагрузка вектора могут быть действительно лучшими. (Или передача в целочисленные регистры напрямую, а не через память, возможно, после vextracti128 / packusdw, поэтому вам нужно всего лишь два 64-битных переноса из векторных в целочисленные регистры: movq и pextrq).
Но в любом случае, затем используйте их в качестве индексов для хранения счетчика в массиве в памяти и перезагрузите его как вектор. Это все еще медленно и безобразно, и включает в себя задержку сбоя при пересылке магазина. Так что, вероятно, стоит потратить время на то, чтобы изменить код, генерирующий индексы, для генерации случайных векторов на основе исходного кода.
Чтобы протестировать решение, я изменил код из своего другого ответа, чтобы сравнить производительность инструкции разброса (определено) с сохранением и последовательной перестановкой (не определено). Мне пришлось скопировать результат обратно в шаблон перестановки
permчтобы компилятор не оптимизировал тело цикла:
#ifdef TEST_SCATTER
#define REPEATS 1000000001
#define USE_SCATTER
__m512i ident = _mm512_set_epi32(15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0);
__m512i perm = _mm512_set_epi32(7,9,3,0,5,8,13,11,4,2,15,1,12,6,10,14);
uint32_t outA[16] __attribute__ ((aligned(64)));
uint32_t id[16], in[16];
_mm512_storeu_si512(id, ident);
for (int i = 0; i < 16; i++) printf("%2d ", id[i]); puts("");
_mm512_storeu_si512(in, perm);
for (int i = 0; i < 16; i++) printf("%2d ", in[i]); puts("");
#ifdef USE_SCATTER
puts("scatter");
for (long t = 0; t < REPEATS; t++) {
_mm512_i32scatter_epi32(outA, perm, ident, 4);
perm = _mm512_load_si512(outA);
}
#else
puts("store & permute");
uint32_t permA[16] __attribute__ ((aligned(64)));
for (long t = 0; t < REPEATS; t++) {
_mm512_store_si512(permA, perm);
for (int i = 0; i < 16; i++) outA[permA[i]] = i;
perm = _mm512_load_si512(outA);
}
#endif
for (int i = 0; i < 16; i++) printf("%2d ", outA[i]); puts("");
#endif
Вот вывод для двух случаев (с использованием встроенного
timeкоманда
tcsh,
uвывод - время в пространстве пользователя в секундах):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 10 6 12 1 15 2 4 11 13 8 5 0 3 9 7
store & permute
12 4 6 13 7 11 2 15 10 14 1 8 3 9 0 5
10.765u 0.001s 0:11.22 95.9% 0+0k 0+0io 0pf+0w
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 10 6 12 1 15 2 4 11 13 8 5 0 3 9 7
scatter
12 4 6 13 7 11 2 15 10 14 1 8 3 9 0 5
10.740u 0.000s 0:11.19 95.9% 0+0k 40+0io 0pf+0w
Время работы примерно такое же (процессор Intel(R) Xeon(R) W-2125 с тактовой частотой 4,00 ГГц, clang++-6.0,
-O3 -funroll-loops -march=native). Я проверил сгенерированный код сборки. С
USE_SCATTERопределены, компилятор генерирует
vpscatterddинструкции, без него генерируется сложный код с использованием
vpextrd,
vpextrq, а также
vpextracti32x4.
Редактировать: я беспокоился, что компилятор мог найти конкретное решение для фиксированного шаблона перестановки, который я использовал. Поэтому я заменил его случайно сгенерированным шаблоном из
std::random_shuffe(), но измерения времени примерно одинаковы.
Редактировать: после комментария Питера Кордеса я написал модифицированный тест, который, надеюсь, измеряет что-то вроде пропускной способности:
#define REPEATS 1000000
#define ARRAYSIZE 1000
#define USE_SCATTER
std::srand(unsigned(std::time(0)));
// build array with random permutations
uint32_t permA[ARRAYSIZE][16] __attribute__ ((aligned(64)));
for (int i = 0; i < ARRAYSIZE; i++)
_mm512_store_si512(permA[i], randPermZMM());
// vector register
__m512i perm;
#ifdef USE_SCATTER
puts("scatter");
__m512i ident = _mm512_set_epi32(15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0);
for (long t = 0; t < REPEATS; t++)
for (long i = 0; i < ARRAYSIZE; i++) {
perm = _mm512_load_si512(permA[i]);
_mm512_i32scatter_epi32(permA[i], perm, ident, 4);
}
#else
uint32_t permAsingle[16] __attribute__ ((aligned(64)));
puts("store & permute");
for (long t = 0; t < REPEATS; t++)
for (long i = 0; i < ARRAYSIZE; i++) {
perm = _mm512_load_si512(permA[i]);
_mm512_store_si512(permAsingle, perm);
uint32_t *permAVec = permA[i];
for (int e = 0; e < 16; e++)
permAVec[permAsingle[e]] = e;
}
#endif
FILE *f = fopen("testperm.dat", "w");
fwrite(permA, ARRAYSIZE, 64, f);
fclose(f);
Я использую массив шаблонов перестановок, которые изменяются последовательно без зависимостей.
Вот результаты:
scatter
4.241u 0.002s 0:04.26 99.5% 0+0k 80+128io 0pf+0w
store & permute
5.956u 0.002s 0:05.97 99.6% 0+0k 80+128io 0pf+0w
Таким образом, пропускная способность лучше при использовании команды разброса.
У меня была та же проблема, но в противоположном направлении: индексы назначения было легко вычислить, но исходные индексы требовались для применения инструкций перестановки SIMD. Вот решение для AVX-512 с использованием инструкции разброса, предложенной Питером Кордесом; это также должно применяться к противоположному направлению:
__m512i ident = _mm512_set_epi32(15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0);
__m512i perm = _mm512_set_epi32(7,9,3,0,5,8,13,11,4,2,15,1,12,6,10,14);
uint32_t id[16], in[16], out[16];
_mm512_storeu_si512(id, ident);
for (int i = 0; i < 16; i++) printf("%2d ", id[i]); puts("");
_mm512_storeu_si512(in, perm);
for (int i = 0; i < 16; i++) printf("%2d ", in[i]); puts("");
_mm512_i32scatter_epi32(out, perm, ident, 4);
for (int i = 0; i < 16; i++) printf("%2d ", out[i]); puts("");
Отображение личности
identраспределяется по массиву в соответствии с шаблоном индекса
perm. Идея в основном такая же, как описанная для инвертирования перестановки . Вот результат:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 10 6 12 1 15 2 4 11 13 8 5 0 3 9 7
12 4 6 13 7 11 2 15 10 14 1 8 3 9 0 5
Обратите внимание, что у меня есть перестановки в математическом смысле (без дубликатов). С дубликатами,
outstore необходимо инициализировать, так как некоторые элементы могут остаться незаписанными.
Я также не вижу простого способа сделать это в регистрах. Я подумал о циклическом выполнении заданной перестановки путем многократного применения инструкции перестановки. Как только шаблон идентичности достигнут, предыдущий является обратной перестановкой (это восходит к идее EOF в операциях распаковки ). Однако циклы могут быть длинными. Максимальное количество циклов, которое может потребоваться, определяется функцией Ландау, которая для 16 элементов равна 140, см. Эту таблицу .. Я мог бы показать, что это число можно сократить до 16, если отдельные подциклы перестановок замораживаются, как только они совпадают с элементами идентичности. Это сокращает в среднем с 28 до 9 команд перестановки для теста на случайные шаблоны перестановки. Тем не менее, это все еще не эффективное решение (намного медленнее, чем инструкция разброса в тесте пропускной способности, описанном в моем другом ответе).