Как выполнить инверсию _mm256_movemask_epi8 (VPMOVMSKB)?

Question

Внутреннее:

int mask = _mm256_movemask_epi8(__m256i s1)

создает маску, с ее 32 биты, соответствующие старшему значащему биту каждого байта s1, После манипуляции маской с помощью битовых операций (BMI2 например) Я хотел бы выполнить обратное _mm256_movemask_epi8создать __m256i вектор с самым старшим битом каждого байта, содержащим соответствующий бит uint32_t mask,

Каков наилучший способ сделать это?

Редактировать: мне нужно выполнить обратное, потому что внутренний _mm256_blendv_epi8 принимает только __m256i введите маску вместо uint32_t, Таким образом, в результате __m256i маска, я могу игнорировать биты, отличные от MSB каждого байта.

Answer 1

Вот альтернатива LUT или pdep инструкции, которые могут быть более эффективными:

1. Скопируйте свою 32-битную маску в оба младших байта некоторых ymm регистр и байты 16..19 того же регистра. Вы можете использовать временный массив и _mm256_load_si256, Или вы можете переместить одну копию 32-битной маски в младшие байты некоторых ymm зарегистрироваться, затем транслировать VPBROADCASTD (_mm_broadcastd_epi32) или другие инструкции трансляции / случайного воспроизведения.
2. Переставьте байты регистра таким образом, чтобы младшие 8 байтов (каждый) содержали младшие 8 бит вашей маски, следующие 8 байтов - следующие 8 бит и т. Д. Это можно сделать с помощью VPSHUFB (_mm256_shuffle_epi8) с управляющим регистром, содержащим "0" в младших 8 байтах, "1" в следующих 8 байтах и ​​т. д.
3. Выберите правильный бит для каждого байта с помощью VPOR (_mm256_or_si256) или же VPAND (_mm256_and_si256),
4. Установите MSB соответствующих байтов с помощью VPCMPEQB (_mm256_cmpeq_epi8), Сравните каждый байт с 0xFF, Если вы хотите, чтобы каждый бит маски был переключен, используйте VPAND на предыдущем шаге и сравните с нулем.

Дополнительная гибкость этого подхода заключается в том, что вы можете выбрать другой регистр управления для шага № 2 и другую маску для шага № 3, чтобы перетасовать биты вашей битовой маски (например, вы можете скопировать эту маску в ymm зарегистрироваться в обратном порядке).

Answer 2

Я реализовал вышеупомянутые три подхода на машине Haswell. Подход Евгения Клюева - самый быстрый (1,07 с), за которым следуют Джейсон Р (1,97 с) и Пол Р. (2,44 с). Приведенный ниже код был скомпилирован с флагами оптимизации -march=core-avx2 -O3.

#include <immintrin.h>
#include <boost/date_time/posix_time/posix_time.hpp>

//t_icc = 1.07 s
//t_g++ = 1.09 s
__m256i get_mask3(const uint32_t mask) {
  __m256i vmask(_mm256_set1_epi32(mask));
  const __m256i shuffle(_mm256_setr_epi64x(0x0000000000000000,
      0x0101010101010101, 0x0202020202020202, 0x0303030303030303));
  vmask = _mm256_shuffle_epi8(vmask, shuffle);
  const __m256i bit_mask(_mm256_set1_epi64x(0x7fbfdfeff7fbfdfe));
  vmask = _mm256_or_si256(vmask, bit_mask);
  return _mm256_cmpeq_epi8(vmask, _mm256_set1_epi64x(-1));
}

//t_icc = 1.97 s
//t_g++ = 1.97 s
__m256i get_mask2(const uint32_t mask) {
  __m256i vmask(_mm256_set1_epi32(mask));
  const __m256i shift(_mm256_set_epi32(7, 6, 5, 4, 3, 2, 1, 0));
  vmask = _mm256_sllv_epi32(vmask, shift);
  const __m256i shuffle(_mm256_setr_epi64x(0x0105090d0004080c,
      0x03070b0f02060a0e, 0x0105090d0004080c, 0x03070b0f02060a0e));
  vmask = _mm256_shuffle_epi8(vmask, shuffle);
  const __m256i perm(_mm256_setr_epi64x(0x0000000000000004, 0x0000000100000005,
      0x0000000200000006, 0x0000000300000007));
  return _mm256_permutevar8x32_epi32(vmask, perm);
}

//t_icc = 2.44 s
//t_g++ = 2.45 s
__m256i get_mask1(uint32_t mask) {
  const uint64_t pmask = 0x8080808080808080ULL; // bit unpacking mask for PDEP
  uint64_t amask0, amask1, amask2, amask3; 
  amask0 = _pdep_u64(mask, pmask);
  mask >>= 8;
  amask1 = _pdep_u64(mask, pmask);
  mask >>= 8;
  amask2 = _pdep_u64(mask, pmask);
  mask >>= 8;
  amask3 = _pdep_u64(mask, pmask);
  return _mm256_set_epi64x(amask3, amask2, amask1, amask0);
}

int main() {
  __m256i mask;
  boost::posix_time::ptime start(
      boost::posix_time::microsec_clock::universal_time()); 
  for(unsigned i(0); i != 1000000000; ++i)
    { 
      mask = _mm256_xor_si256(mask, get_mask3(i));
    }
  boost::posix_time::ptime end(
      boost::posix_time::microsec_clock::universal_time());
  std::cout << "duration:" << (end-start) << 
    " mask:" << _mm256_movemask_epi8(mask) << std::endl;
  return 0;
}

Answer 3

Мой первоначальный подход к этому был похож на @Jason R, потому что именно так работают "нормальные" операции, но большинство этих операций заботятся только о старшем бите - игнорируя все остальные биты. Как только я понял это, _mm*_maskz_broadcast*_epi*(mask,__m128i) ряд функций имеет смысл. Вам нужно будет включить -mavx512vl и -mavx512bw (gcc)

Чтобы получить вектор с самым старшим битом каждого байта, установленного в соответствии с маской:

/* convert 16 bit mask to __m128i control byte mask */
_mm_maskz_broadcastb_epi8((__mmask16)mask,_mm_set1_epi32(~0))
/* convert 32 bit mask to __m256i control byte mask */
_mm256_maskz_broadcastb_epi8((__mmask32)mask,_mm_set1_epi32(~0))
/* convert 64 bit mask to __m512i control byte mask */
_mm512_maskz_broadcastb_epi8((__mmask64)mask,_mm_set1_epi32(~0))

Чтобы получить вектор с старшим битом каждого слова, установленным в соответствии с маской:

/* convert 8 bit mask to __m128i control word mask */
_mm_maskz_broadcastw_epi16((__mmask8)mask,_mm_set1_epi32(~0))
/* convert 16 bit mask to __m256i control word mask */
_mm256_maskz_broadcastw_epi16((__mmask16)mask,_mm_set1_epi32(~0))
/* convert 32 bit mask to __m512i control word mask */
_mm512_maskz_broadcastw_epi16((__mmask32)mask,_mm_set1_epi32(~0))

Чтобы получить вектор с старшим битом каждого двойного слова, установленного в соответствии с маской:

/* convert 8 bit mask to __m256i control mask */
_mm256_maskz_broadcastd_epi32((__mmask8)mask,_mm_set1_epi32(~0))
/* convert 16 bit mask to __m512i control mask */
_mm512_maskz_broadcastd_epi32((__mmask16)mask,_mm_set1_epi32(~0))

Чтобы получить вектор с старшим битом каждого четырехугольного слова, установленного в соответствии с маской:

/* convert 8 bit mask to __m512i control mask */
_mm512_maskz_broadcastq_epi64((__mmask8)mask,_mm_set1_epi32(~0))

Один конкретный для этого вопроса: _mm256_maskz_broadcastb_epi8((__mmask32)mask,_mm_set1_epi32(~0)) но я включаю другие для справки / сравнения.

Обратите внимание, что каждый байт / слово /... будет либо всеми единицами, либо всеми нулями в соответствии с маской (а не только старшим битом). Это также может быть полезно для выполнения векторизованных битовых операций (например, с другим вектором для обнуления нежелательных байтов / слов).

Еще одно примечание: каждый _mm_set1_epi32(~0) может / должен быть преобразован в константу (либо вручную, либо компилятором), поэтому он должен компилироваться всего за одну довольно быструю операцию, хотя это может быть немного быстрее при тестировании, чем в реальной жизни, поскольку константа, скорее всего, останется в регистре. Затем они преобразуются в инструкции VPMOVM2{b,w,d,q}

Изменить: Если ваш компилятор не поддерживает AVX512, версия встроенной сборки должна выглядеть следующим образом:

inline __m256i dmask2epi8(__mmask32 mask){
  __m256i ret;
  __asm("vpmovm2b   %1, %0":"=x"(ret):"k"(mask):);
  return ret;
}

Другие инструкции похожи.

Answer 4

Вот еще одна реализация, которая может работать на AVX2, поскольку у вас есть этот тег в вашем вопросе (он не проверен, так как у меня нет машины Haswell). Это похоже на ответ Евгения Клюева, но может потребовать меньше инструкций. Требуется два постоянных __m256i хотя маски. Если вы делаете это много раз в цикле, то издержки на установку этих констант один раз заранее могут быть незначительными.

• Возьмите свою 32-битную маску и транслируйте ее на все 8 слотов ymm зарегистрироваться с помощью _mm_broadcastd_epi32(),

• Создать __m256i содержит 8 32-разрядных целых чисел со значениями [0, 1, 2, 3, 4, 5, 6, 7] (от наименее значимого до наиболее значимого элемента).

• Используйте эту постоянную маску для поворота каждого из 32-битных целых чисел в вашем ymm зарегистрируйтесь на другую сумму, используя _mm256_sllv_epi32(),

• Теперь, если мы посмотрим на ymm зарегистрируйтесь как содержащие 8-битные целые числа и посмотрите на их MSB, тогда регистр теперь содержит MSB для байтовых индексов [7, 15, 23, 31, 6, 14, 22, 30, 5, 13, 21, 29, 4, 12, 20, 28, 3, 11, 19, 27, 2, 10, 18, 26, 1, 9, 17, 25, 0, 8, 16, 24] (от наименее значимого до наиболее значимого элемента).

• Используйте побитовое И против постоянной маски [0x80, 0x80, 0x80, ...] выделить MSB из каждого байта.

• Используйте последовательность перемешиваний и / или перестановок, чтобы вернуть элементы в нужном вам порядке. К сожалению, для 8-битных целых чисел не существует произвольных перестановок, как для значений с плавающей точкой в ​​AVX2.

Answer 5

Единственный разумно эффективный способ, о котором я могу подумать, - это 8-битное LUT: выполнить 4 х 8-битный поиск, а затем загрузить результаты в вектор, например

static const uint64_t LUT[256] = { 0x0000000000000000ULL,
                                   ...
                                   0xffffffffffffffffULL };

uint64_t amask[4] __attribute__ ((aligned(32)));

uint32_t mask;
__m256i vmask;

amask[0] = LUT[mask & 0xff];
amask[1] = LUT[(mask >> 8) & 0xff];
amask[2] = LUT[(mask >> 16) & 0xff];
amask[3] = LUT[mask >> 24];
vmask = _mm256_load_si256((__m256i *)amask);

В качестве альтернативы вы можете использовать регистры вместо временного массива и посмотреть, может ли ваш компилятор сделать что-то более эффективное, не требующее прохождения через память:

static const uint64_t LUT[256] = { 0x0000000000000000ULL,
                                   ...
                                   0xffffffffffffffffULL };

uint64_t amask0, amask1, amask2, amask3;

uint32_t mask;
__m256i vmask;

amask0 = LUT[mask & 0xff];
amask1 = LUT[(mask >> 8) & 0xff];
amask2 = LUT[(mask >> 16) & 0xff];
amask3 = LUT[mask >> 24];
vmask = _mm256_set_epi64x(amask3, amask2, amask1, amask0);

Запоздалая мысль: интересной задачей может быть использование, например, инструкций Haswell BMI для выполнения эквивалента операции 8 -> 64-битного LUT и, таким образом, избавления от LUT. Похоже, вы могли бы использовать PDEP для этого, например

const uint64_t pmask = 0x8080808080808080ULL; // bit unpacking mask for PDEP

uint64_t amask0, amask1, amask2, amask3;

uint32_t mask;
__m256i vmask;

amask0 = _pdep_u64(mask, pmask); mask >>= 8;
amask1 = _pdep_u64(mask, pmask); mask >>= 8;
amask2 = _pdep_u64(mask, pmask); mask >>= 8;
amask3 = _pdep_u64(mask, pmask);
vmask = _mm256_set_epi64x(amask3, amask2, amask1, amask0);