Ниже приведена альтернатива LUT или pdep
инструкциям, которые могут быть более эффективными:
ymm
и байты 16. .19 того же регистра. Вы можете использовать временный массив и _mm256_load_si256
. Или вы можете перенести одиночную копию 32-битной маски на нижние байты некоторого регистра ymm
, затем транслировать ее с помощью VPBROADCASTD (_mm_broadcastd_epi32)
или других команд широковещания / тасования. VPSHUFB (_mm256_shuffle_epi8)
с регистром управления, содержащим «0» в младших 8 байтах, «1» в следующих 8 байтах и т. д. VPOR (_mm256_or_si256)
или VPAND (_mm256_and_si256)
. VPCMPEQB (_mm256_cmpeq_epi8)
. Сравните каждый байт с 0xFF
. Если вы хотите, чтобы каждый бит маски переключился, используйте VPAND
на предыдущем шаге и сравните с нулем. Дополнительная гибкость этого подхода заключается в том, что вы можете выбрать другой регистр управления для шага №2 и другую маску для шага № 3 для перетасовки битов вашей битовой маски (например, вы можете скопировать эту маску в регистр ymm
в обратном порядке).
Вот еще одна реализация, которая может работать на AVX2, поскольку у вас есть этот тег на ваш вопрос (он непроверен, так как у меня нет машины Haswell). Это похоже на ответ Евгения Клюева, но может потребоваться меньше инструкций. Однако для этого требуются две постоянные маски __m256i
. Если вы делаете это много раз в цикле, то накладные расходы на настройку этих констант один раз досрочно могут быть незначительными.
ymm
, используя _mm_broadcastd_epi32()
. __m256i
, удерживая 8 32-битных целых чисел со значениями [0, 1, 2, 3, 4, 5, 6, 7]
(от наименее значимого до наиболее значимого элемента). 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-битным LUT: выполнить поиск по 4 x 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);
Я реализовал вышеупомянутые три подхода на машине Хасуэлла. Подход Евгения Клюева является самым быстрым (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;
}
Мой первоначальный подход к этому был похож на @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))
Чтобы получить вектор с наивысшим битом каждого double word установлено в соответствии с маской:
/* 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;
}
Другие инструкции аналогичны.