Caclulating min of 8 long ints с использованием AVX2

Question

Я пытался попытаться найти минимум 8 long ints, используя AVX2. Я зелёный для программирования SIMD, и я понятия не имею, с чего начать. Я не видел никаких сообщений/примеров, которые объясняют, как провести min и max в AVX2. Я знаю, что я не могу превышать 4 long ints из-за предела 256 bit, но я могу решить свою проблему, используя три шага. Также я не могу понять, как загрузить данные уже существующего нормального long int array в vectors для avx2.

Я знаю идею за процессом, это то, что я пытаюсь достичь

long int nums = {1 , 2, 3 , 4 , 5 , 6 , 7, 8} 
a = min(1,2) ; b = min(3,4) ; c = min(5,6) ; d = min(7,8) 
x = min(a,b) ; y = min(c,d) 
answer = min(x,y) 

Может кто-то помочь мне о том, как получить эту работу. Также последние min - это одна операция, лучше ли это делать на CPU? Должен ли я использовать что-то другое, кроме AVX2? (Я нахожусь в системе)

Answer 1

Для оптимизации x86 и т. Д. См. Ссылки на https://stackoverflow.com/tags/x86/info. Особенно Руководство по интуиции Intel и материалы Agner Fog.

Если у вас всегда имеется ровно 8 элементов (64 байта), это упрощает многое. Одной из основных проблем, возникающих при векторизации небольших файлов, является не добавление слишком большого количества загрузочных/очистных накладных расходов, которые обрабатывают оставшиеся элементы, которые не заполняют целый вектор.

AVX2 не имеет инструкций min/max для упакованных 64-битных цепей. Только 8, 16 и 32. Это означает, что вам нужно эмулировать его с помощью сравнения, которое генерирует маску (all-0s для элементов, где условие является false, all-1s, где true, поэтому вы можете И эта маска обнулить элементы в других векторах.) Чтобы сэкономить на выполнении операций AND/ANDN и OR для комбинирования объектов с маской, существуют инструкции по смешиванию.

AVX-512 будет принести большую скорость для этой операции. (поддержка входит (только для xeon) Skylake). Он имеет _mm_min_epi64. Для этой операции есть также функция библиотеки: __int64 _mm512_reduce_min_epi64 (__m512i a). Я предполагаю, что это внутреннее будет испускать последовательность команд vpminsq. Intel перечисляет его в своем встроенном поисковом устройстве, но это только функция библиотеки Intel, не машинная инструкция.

Вот реализация AVX2, которая должна работать. Я не тестировал его, но скомпилированный вывод выглядит как правильная последовательность команд. Возможно, я где-то сравнил сравнение, поэтому проверьте это.

Принцип работы: получить элементный минимум двух векторов 256b. Разделите это на два 128b вектора и получите по порядку минус. Затем верните этот вектор из двух значений 64b обратно в регистры GP и выполните окончательный мин. Макс выполняется одновременно, чередуясь с мин.

(К сожалению, вы упомянули min/max в своем вопросе, но теперь я вижу, что вы на самом деле просто хотели мин. Удаление ненужных частей тривиально, и вы можете изменить его на возвращаемое значение вместо сохранения результатов через указатели/ссылки скалярное версия может быть быстрее;.. лучше тест в контексте, где ваше приложение использует эту операцию (а не автономный microbenchmark))

#include <stdint.h> 
#include <immintrin.h> 

int64_t input[8] = { 1, 2, 3, }; 

#define min(a,b) \ 
    ({ __typeof__ (a) _a = (a); __typeof__ (b) _b = (b); \ 
    _a < _b ? _a : _b; }) 

#define max(a,b) \ 
    ({ __typeof__ (a) _a = (a); \ 
     __typeof__ (b) _b = (b); \ 
    _a > _b ? _a : _b; }) 

// put this where it can get inlined. You don't want to actually store the results to RAM 
// or have the compiler-generated VZEROUPPER at the end for every use. 
void minmax64(int64_t input[8], int64_t *minret, int64_t *maxret) 
{ 
    __m256i *in_vec = (__m256i*)input; 
    __m256i v0 = in_vec[0], v1=in_vec[1]; // _mm256_loadu_si256 is optional for AVX 

    __m256i gt = _mm256_cmpgt_epi64(v0, v1); // 0xff.. for elements where v0 > v1. 0 elsewhere 
    __m256i minv = _mm256_blendv_epi8(v0, v1, gt); // take bytes from v1 where gt=0xff (i.e. where v0>v1) 
    __m256i maxv = _mm256_blendv_epi8(v1, v0, gt); // input order reversed 

    /* for 8, 16, or 32b: cmp/blend isn't needed 
     minv = _mm256_min_epi32(v0,v1); 
     maxv = _mm256_min_epi32(v0,v1); // one insn shorter, but much faster (esp. latency) 
     And at the stage of having a 128b vectors holding the min and max candidates, 
     you'd shuffle and repeat to get the low 64, and optionally again for the low 32, 
     before extracting to GP regs to finish the comparisons. 
    */ 

    __m128i min0 = _mm256_castsi256_si128(minv); // stupid gcc 4.9.2 compiles this to a vmovdqa 
    __m128i min1 = _mm256_extracti128_si256(minv, 1); // extracti128(x, 0) should optimize away to nothing. 

    __m128i max0 = _mm256_castsi256_si128(maxv); 
    __m128i max1 = _mm256_extracti128_si256(maxv, 1); 

    __m128i gtmin = _mm_cmpgt_epi64(min0, min1); 
    __m128i gtmax = _mm_cmpgt_epi64(max0, max1); 
    min0 = _mm_blendv_epi8(min0, min1, gtmin); 
    max0 = _mm_blendv_epi8(max1, max0, gtmax); 

    int64_t tmp0 = _mm_cvtsi128_si64(min0); // tmp0 = max0.m128i_i64[0]; // MSVC only 
    int64_t tmp1 = _mm_extract_epi64(min0, 1); 
    *minret = min(tmp0, tmp1); // compiles to a quick cmp/cmovg of 64bit GP registers 

    tmp0 = _mm_cvtsi128_si64(max0); 
    tmp1 = _mm_extract_epi64(max0, 1); 
    *maxret = min(tmp0, tmp1); 
} 

Это может или не может быть быстрее, чем делать все это в регистрах GP, так как 64-разрядная загрузка равна одному uop, cmp - один uop, а cmovcc - всего 2 устройства (на Intel).Хасуэлл может выдавать 4 часа за каждый цикл. Пока вы не дойдете до дна дерева сравнения, есть много самостоятельной работы, и даже так, cmp - это 1 задержка цикла, а cmov - 2. Если вы чередуете работу на минуту и ​​макс при том же времени есть две отдельные цепи зависимостей (или деревья в этом случае).

У векторной версии гораздо более высокая латентность, чем пропускная способность. Если вам нужна эта операция для нескольких независимых наборов из 8 значений, векторная версия, вероятно, будет преуспевать. В противном случае будет зависеть 5-тикратная латентность pcmpgt* и 2-часовая латентность blendv. Если есть другая независимая работа, которая может происходить параллельно, тогда это нормально.

Если у вас были меньшие целые числа, pmin* (подписанный или неподписанный, 8, 16 или 32b) - это 1 задержка цикла, 2 на пропускную способность каждого цикла. Только для 16-битных элементов без знака существует даже минимальная инструкция по горизонтали, которая дает вам элемент min из 8 в одном векторе, как прокомментировал пользователь-номер пользователя. Это сокращает весь процесс сужения сплит/мин, который необходим после того, как минимальные кандидаты попадают в один вектор.