Эффективно собирать отдельные байты, разделенные байтовым шагом 4

Question

Я пытаюсь оптимизировать алгоритм, который будет обрабатывать массивные массивы данных, которые могут сильно выиграть от инструкций AVX SIMD. К сожалению, макет входной памяти не является оптимальным для требуемых вычислений. Информация должна быть заказана, путем сборки __m256i значения из отдельных байтов, которые ровно 4 байта друг от друга:

НАЧАТЬ EDIT

Моя цель процессоры не поддерживают инструкции AVX2, так как @Elalfer и @PeterCordes отметил, Я не могу использовать значения __m256i, код должен быть преобразован для использования значения __m128i вместо)

END EDIT раскладки

DataSet в памяти

---

Byte 0 | Byte 1 | Byte 2 | Byte 3 
Byte 4 | Byte 5 | Byte 6 | Byte 7 
... 
Byte 120 | Byte 121 | Byte 122 | Byte 123 
Byte 124 | Byte 125 | Byte 126 | Byte 127 

Нужные значения в переменной __m256i:

---

| Byte 0 | Byte 4 | Byte 8 |  ...  | Byte 120 | Byte 124 | 

---

Есть ли более эффективный способ, чтобы собрать и изменить другие, чем этот простой код strided данные?

union { __m256i reg; uint8_t bytes[32]; } aux; 
... 
for(int i = 0; i < 32; i++) 
    aux.bytes[i] = data[i * 4]; 

Edit:

Стадию Я пытаюсь оптимизировать немного столбец транспонирования; другими словами, биты определенного столбца (32 возможных столбца бит в моей компоновке данных) должны стать одним значением uint32_t, в то время как остальные биты игнорируются.

Я выполняю транспонирование, переставляя данные, как показано на рисунке, выполняя сдвиг влево, чтобы привести бит столбца в качестве наиболее значимых бит в каждом подбайте, и, наконец, извлечь и собрать биты в одно значение uint32 _t через _mm256_movemask_epi8() внутренний.

Answer 1

Я только что заметил редактирование, которое имеет специальный случай.

Если вам нужно сделать много разных позиций битов по тем же данным, то ваш текущий план хорош.

Если вам нужна только одна позиция бита (особенно наивысшая позиция бита) из 128B памяти, вы можете использовать _mm256_movemask_ps, чтобы получить высокий бит из каждого элемента 32b. Затем объедините четыре 8-битных маски в регистры GP.

Хороший компилятор должен оптимизировать, что:

vmovdqu ymm0, [buf + 0] 
; to select a different bit: 
; vpslld ymm0, ymm0, count ; count can be imm8 or the low byte of an xmm register 
vmovmskps eax, ymm0 

vmovdqu ymm0, [buf + 32] 
vmovmskps ebx, ymm0 

... ecx and edx 

mov  ah, bl 
mov  ch, dl 
shl  ecx, 16 
or  eax, ecx 

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

---

Ответ на первоначальный вопрос:

Подобно идее Elalfer, но использовать устройство воспроизведения в случайном порядке для pack инструкции вместо pshufb. Кроме того, все Иs являются независимыми, поэтому они могут выполняться параллельно. Процессоры Intel могут одновременно делать 3 AND, но только один перетасовка. (Или два перетасовки сразу по предварительному Haswell.)

// without AVX2: you won't really be able to 
// do anything with a __m256i, only __m128i 
// just convert everything to regular _mm_..., and leave out the final permute 

mask = _mm256_set1_epi32(0x000000ff); 

// same mask for all, and the load can fold into the AND 
// You can write the load separately if you like, it'll still fold 
L1 = and(mask, (buf))  // load and zero the bytes we don't want 
L2 = and(mask, (buf+32)) 
L3 = and(mask, (buf+64)) 
L4 = and(mask, (buf+96)) 

// squish dwords from 2 concatenated regs down to words in 1 reg 
pack12 = _mm256_packus_epi32(L1, L2); 
pack34 = _mm256_packus_epi32(L3, L4); 

packed = _mm256_packus_epi16(pack12, pack34); // note the different width: zero-padded-16 -> 8 

Vec = permute(packed) // fix DWORD order in the vector (only needed for 256b version) 

Vec = shift(Vec, bit_wanted) 
bitvec = movemask(Vec) 

    // shift: 
    // I guess word or dword granularity is fine, since byte granularity isn't available. 
    // You only care about the high bit, so it doesn't matter than you're not shifting zeroes into the bottom of each byte. 

    // _mm_slli_epi32(Vec, imm8): 1 uop, 1c latency if your count is a compile-time constant. 
    // _mm_sll_epi32 (Vec, _mm_cvtsi32_si128(count)): 2uop 2c latency if it's variable. 

    // *not* _mm_sllv_epi32(): slower: different shift count for each element. 

Если вы делаете это только с AVX (как вы сказали), то вы не будете иметь 256B целочисленные инструкции доступны. Просто создайте 128b векторов и получите 16b за время данных маски. Вам не понадобится окончательная перестановка в конце.

Объединить маски с целыми инструкциями: (m2<<16) | m1. При желании, даже до 64b данных маски, путем объединения двух 32b масок.

Производительность: Это позволяет избежать необходимости в отдельных инструкциях по загрузке с помощью AVX, так как vpand может micro-fuse a memory operand if used with a one-register addressing mode.

• цикл 1: 3 vpand инструкция. (или только 2, если мы ждали по адресу, так как есть только 2 порта нагрузки.)
• Цикл 2: последний раз один или два vpand, один pack (L1, L2)
• Цикл 3: Следующий pack (L3, L4)
• Цикл 4: конечная pack
• // 256b AVX2: переставляют
• цикл 5: упакованный сдвиг с imm8 count: 1 uop, 1c латентность.
• цикл 6: movemask (3 цикла задержки)

Задержка = 8 (SNB и позже)

Пропускная способность: 3 перетасовки (P5), 4 логические выражения (P015), 1 сдвиг (р0), 1 pmovmsk (p0). 4 загрузки.

• SnB/IvB: 9 ALU uops -> 3c. 4 чтения: 2c.
  Так что, в зависимости от того, что вы делаете с масками, вам потребуется 3 аккумулятора, чтобы поддерживать насыщенные порты исполнения. (ceil (8/3) = 3).

С учетом сдвига в переменной, которая не может быть разрешена для константы времени компиляции при встраивании/разворачивании компилятора: latency = 9. И сдвиг производит другой uop для p1/p5.

С AVX2 для Haswell и позже есть еще 3 дополнительных латентности для vpermd.

Answer 2

Вы можете попробовать развернуть этот цикл, это должно по крайней мере избавиться от одного сравнения (i < 32), одного приращения (i ++) и одного умножения (i * 4) в теле цикла. Также постоянные смещения массива могут работать немного быстрее, чем переменные. Но обратите внимание, что ваш компилятор может генерировать схожий код (или лучше) в любом случае с включенными соответствующими параметрами компиляции.

union { __m256i reg; uint8_t bytes[32]; } aux; 
... 
aux.bytes[0] = data[0]; 
aux.bytes[1] = data[3]; 
... 
aux.bytes[31] = data[124]; 

Answer 3

Один из способов будет - упаковывают байты с _mm256_shuffle_epi8, смешать все _mm256_blend_epi32 результирующие векторы (вам нужно сделать 4 такой нагрузки + перетасовать), и сделать один 32bit переставлять _mm256_permutevar8x32_epi32.

Вот псевдо-код (я надеюсь, что вы можете придумать маски тасовани):

L1 = load32byte(buf) 
L2 = load32byte(buf+32) 
L3 = load32byte(buf+64) 
L4 = load32byte(buf+96) 

// Pack 4 bytes in the corresponding 32bit DWORD in each lane and zero-out other bytes 
L1 = shuffle(L1, mask_for_L1) 
L2 = shuffle(L2, mask_for_L2) 
L3 = shuffle(L3, mask_for_L3) 
L4 = shuffle(L4, mask_for_L4) 

// Vec = blend(blend(L1,L2),blend(L3,L4)) 
Vec = or(or(or(L1,L2),L3),L4) 
Vec = permute(Vec) // fix DWORD order in the vector 

Update: Забыл почему я сказал «обнуление остальных байт» - таким образом, вы можете заменить blend с or

Update: Снижение задержки один цикл перестановкой or операций на комментарий Петра ниже.

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