Если вы собираетесь перебирать маски, выделенные одним битом, по одной, генерировать их по одной эффективно;см. ответ @ harold.
Но если вам действительно нужны все маски, x86 с AVX512F может с пользой распараллелить это. (По крайней мере, потенциально полезно в зависимости от окружающего кодаСкорее всего, это просто забавное упражнение по применению AVX512 и бесполезно для большинства случаев использования.
Ключевой строительный блок: AVX512F vpcompressd: с учетом маски (например, изSIMD сравнение) будет перетасовывать выбранные элементы dword в смежные элементы в нижней части вектора.
Вектор AVX512 ZMM / __m512i содержит 16x 32-разрядных целых числа, поэтому нам нужно только 2 вектора для хранениякаждая возможная однобитовая маска. Наш входной номер равен маске, которая выбирает, какой из этих элементов должен быть частью вывода. (Нет необходимости транслировать его в вектор и vptestmd или что-то в этом роде; мыможете просто kmov записать его в регистр маски и использовать его напрямую.)
См. также мой ответ AVX512 о AVX2, какой самый эффективный способ упаковать левый на основе маски?
#include <stdint.h>
#include <immintrin.h>
// suggest 64-byte alignment for out_array
// returns count of set bits = length stored
unsigned bit_isolate_avx512(uint32_t out_array[32], uint32_t x)
{
const __m512i bitmasks_lo = _mm512_set_epi32(
1UL << 15, 1UL << 14, 1UL << 13, 1UL << 12,
1UL << 11, 1UL << 10, 1UL << 9, 1UL << 8,
1UL << 7, 1UL << 6, 1UL << 5, 1UL << 4,
1UL << 3, 1UL << 2, 1UL << 1, 1UL << 0
);
const __m512i bitmasks_hi = _mm512_slli_epi32(bitmasks_lo, 16); // compilers actually do constprop and load another 64-byte constant, but this is more readable in the source.
__mmask16 set_lo = x;
__mmask16 set_hi = x>>16;
int count_lo = _mm_popcnt_u32(set_lo); // doesn't actually cost a kmov, __mask16 is really just uint16_t
_mm512_mask_compressstoreu_epi32(out_array, set_lo, bitmasks_lo);
_mm512_mask_compressstoreu_epi32(out_array+count_lo, set_hi, bitmasks_hi);
return _mm_popcnt_u32(x);
}
Прекрасно компилируется с помощью clang на Godbolt и с помощью gcc, кроме пары второстепенных неоптимальных выборов с помощью mov, movzx и popcnt, и делаяуказатель кадра без причины. (Также может компилироваться с -march=knl; это не зависит от AVX512BW или DQ.)
# clang9.0 -O3 -march=skylake-avx512
bit_isolate_avx512(unsigned int*, unsigned int):
movzx ecx, si
popcnt eax, esi
shr esi, 16
popcnt edx, ecx
kmovd k1, ecx
vmovdqa64 zmm0, zmmword ptr [rip + .LCPI0_0] # zmm0 = [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768]
vpcompressd zmmword ptr [rdi] {k1}, zmm0
kmovd k1, esi
vmovdqa64 zmm0, zmmword ptr [rip + .LCPI0_1] # zmm0 = [65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648]
vpcompressd zmmword ptr [rdi + 4*rdx] {k1}, zmm0
vzeroupper
ret
На Skylake-AVX512, vpcompressd zmm{k1}, zmm - это 2 моп для порта 5Задержка от входного вектора -> выходной - 3 цикла, но задержка от входной маски -> выходной - 6 циклов. (https://www.uops.info/table.html / https://www.uops.info/html-instr/VPCOMPRESSD_ZMM_K_ZMM.html). Целевая версия памяти - 4 мопа : 2p5 + обычные моп-адреса хранилища и данных хранилища, которые не могут микросинхронизироваться, когда частьболее крупная инструкция.
Может быть, лучше сжать в регистр ZMM и затем сохранить, по крайней мере, для первого сжатия, чтобы сохранить общее количество мопов. Второе, вероятно, должно по-прежнему использовать преимущество маскированного хранилищаvpcompressd [mem]{k1} чтобы выходной массив не нуждался в заполнении для включения. IDK, если это помогает с разбиением строк кэша, т. Е. Может ли маскирование избежать повторного воспроизведения Store Uop для части с нулевой маской во 2-м кешеline.
В KNL vpcompressd zmm{k1} - это всего лишь один моп. Agner Fog не проверял его с назначением памяти (https://agner.org/optimize/).
Это 14 fused-domainмоп для внешнего интерфейса на Skylake-X для реальной работы (например, после встраивания в цикл по множеству значений x, чтобы мы могли поднять нагрузки vmovdqa64 из цикла. В противном случае это еще 2 мопа). внешнее узкое место = 14/ 4 = 3,5 цикла.
Давление на внутреннем порте: 6 моп для порта 5 (2x kmov (1) + 2x vpcompressd (2)): 1 итерация на 6 циклов . (Даже на IceLake ( instlatx64 ), пропускная способность vpcompressd по-прежнему составляет 2c, к сожалению, поэтому, очевидно, дополнительный порт shuffle ICL не обрабатывает ни один из этих мопов. И kmovw k, r32 по-прежнему равен 1 / такт,предположительно, все еще порт 5.)
(Другие порты в порядке: popcnt работает на порту 1, и вектор ALU этого порта отключается, когда 512-битные мопы находятся в полете. Но не его скалярное ALU,только тот, который обрабатывает 3-тактные инструкции с целочисленной задержкой. movzx dword, word не может быть удален, это может сделать только movzx dword, byte, но он работает на любом порту.)
Latency: целочисленный результат - только одинpopcnt (3 цикла). Первая часть результата памяти сохраняется примерно через 7 циклов после того, как маска готова. (kmov -> vpcompressd). Источник вектора для vpcompressd является константой, поэтому OoO exec может подготовить его заранее, если он не попадет в кеш.
Сжатие константы 1<<0..15 было бы возможно, но, вероятно, не стоило бы, построив ее со сдвигом. например, загрузка 16-байтового _mm_setr_epi8(0..15) с vpmovzxbd, затем использование этого с vpsllvd на векторе set1 (1) (который вы можете получить из трансляции или сгенерировать на лету с помощью vpternlogd + shift). Но это, вероятно, не стоит того, даже если вы пишете вручную в asm (так что это ваш выбор вместо компилятора), так как здесь уже используется много случайных комбинаций, а генерация констант займет не менее 3 или 4 инструкций (каждая издлиной не менее 6 байт; только для одного префикса EVEX - 4 байта).
Я бы сгенерировал часть hi со смещением от lo, вместо того, чтобы загружать ее отдельно. Если окружающий код не является узким местом на порте 0, UU ALU не хуже, чем UOP загрузки. Одна 64-байтовая константа заполняет всю строку кэша.
Вы можете сжать константу lo с нагрузкой vpmovzxwd: каждый элемент умещается в 16 бит. Стоит подумать, можете ли вы поднять это вне цикла, чтобы это не стоило дополнительной перестановки за операцию.
Если вы хотите получить результат в виде вектора SIMD вместо того, чтобы сохранять его в памяти, вы могли бы 2xvpcompressd в регистры и, возможно, используйте count_lo, чтобы найти вектор управления перемешиванием для vpermt2d. Возможно из скользящего окна на массиве вместо 16x 64-байтовых векторов? Но результат не гарантированно помещается в один вектор, если вы не знаете, что на вашем входе установлено 16 или менее битов.
С 64-битными целыми числами дела обстоят намного хуже 8x 64-битные элементы означают, что нам нужно 8 векторов. Так что, может быть, это не стоит того, чтобы сравнивать со скаляром, если только на ваших входах не установлено много битов.
Вы можете сделать это в цикле, используя vpslld на 8 для перемещения битов в векторных элементах. Вы могли бы подумать, что kshiftrq было бы хорошо, но с задержкой в 4 цикла это длинная цепочка депонирования. И вам все равно нужен скалярный popcnt каждого 8-битного блока для настройки указателя. Таким образом, ваш цикл должен использовать shr / kmov и movzx / popcnt. (Использование счетчиков + = 8 и bzhi для подачи popcnt будет стоить больше мопов).
Зависимости, переносимые циклом, все короткие (и цикл выполняет только 8 итераций для покрытиямаска 64 бита), поэтому exec-of-order exec должен иметь возможность красиво перекрывать работу для нескольких итераций. Особенно, если мы развернем на 2, чтобы зависимости вектора и маски могли опередить обновление указателя.
- vector:
vpslld немедленный, начиная с константы вектора - mask:
shr r64, 8 начиная с x. (Может прекратить зацикливание, когда оно становится равным 0 после смещения всех битов. Эта цепочка развертывания с 1 циклом является достаточно короткой, чтобы OoO exec мог пронзить ее и скрыть большую часть штрафа за неверный прогноз, когда это произошло.) - указатель:
lea rdi, [rdi + rax*4] где RAX содержит результат popcnt.
Остальная часть работы не зависит от итераций. В зависимости от окружающего кода, мы, вероятно, являемся узким местом на порту 5 с vpcompressd shuffles и kmov