Может ли использование AVX2 реализовать более быструю обработку LZCNT для массива слов? - PullRequest
Новая
       92

Может ли использование AVX2 реализовать более быструю обработку LZCNT для массива слов?

5 голосов
/ 15 мая 2019

Мне нужно выполнить битовое сканирование в обратном порядке с помощью LZCNT массива слов: 16 битов.

Пропускная способность LZCNT составляет 1 выполнение в такт на процессорах Intel последнего поколения.Пропускная способность на AMD Ryzen, кажется, составляет 4.

Я пытаюсь найти алгоритм, использующий набор команд AVX2, чтобы быть быстрее.

Я знаю, что AVX-512 имеет VPLZCNTD для 32-битных элементов, поэтому, если бы у меня был AVX512CD, я мог бы распаковать и использовать его.

С помощью всего лишь набора инструкций AVX2 можно кодировать алгоритм быстрее, чем с помощью инструкции x86 asm LZCNT?

1 Ответ

6 голосов
/ 16 мая 2019 
#include <immintrin.h>

__m256i avx2_lzcnt_epi16(__m256i v) {
    const __m256i lut_lo = _mm256_set_epi8(
        4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 16,
        4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 16
    );
    const __m256i lut_hi = _mm256_set_epi8(
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 16,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 16
    );
    const __m256i nibble_mask = _mm256_set1_epi8(0x0F);
    const __m256i byte_offset = _mm256_set1_epi16(0x0008);
    __m256i t;

    t = _mm256_and_si256(nibble_mask, v);
    v = _mm256_and_si256(_mm256_srli_epi16(v, 4), nibble_mask);
    t = _mm256_shuffle_epi8(lut_lo, t);
    v = _mm256_shuffle_epi8(lut_hi, v);
    v = _mm256_min_epu8(v, t);

    t = _mm256_srli_epi16(v, 8);
    v = _mm256_or_si256(v, byte_offset);
    v = _mm256_min_epu8(v, t);

    return v;
}

// 16 - lzcnt_u16(subwords)
__m256i avx2_ms1b_epi16(__m256i v) {
    const __m256i lut_lo = _mm256_set_epi8(
        12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 10, 10, 9, 0,
        12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 10, 10, 9, 0
    );
    const __m256i lut_hi = _mm256_set_epi8(
        16, 16, 16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 14, 14, 13, 0,
        16, 16, 16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 14, 14, 13, 0
    );
    const __m256i nibble_mask = _mm256_set1_epi8(0x0F);
    const __m256i adj = _mm256_set1_epi16(0x1F08);
    __m256i t;

    t = _mm256_and_si256(nibble_mask, v);
    v = _mm256_and_si256(_mm256_srli_epi16(v, 4), nibble_mask);
    t = _mm256_shuffle_epi8(lut_lo, t);
    v = _mm256_shuffle_epi8(lut_hi, v);
    v = _mm256_max_epu8(v, t);

    t = _mm256_srli_epi16(v, 8);
    v = _mm256_sub_epi8(v, adj);
    v = _mm256_max_epi8(v, t);

    return v;
}

Для результатов, упакованных в uint8, используйте _mm256_packs_epi16().Для получения упакованных результатов в правильном порядке также используйте _mm256_permute4x64_epi64().

Solution от r / SIMD .Это решение также было описано в комментариях здесь.

...