Эффективный способ поворота байта внутри регистра AVX

Question

Резюме/tl; dr: Есть ли способ повернуть байт в регистре YMM поразрядным (с использованием AVX), кроме выполнения двух сдвигов и смешивания результатов вместе?

Для каждого 8 байтов в регистре YMM мне нужно повернуть 7 байтов влево. Каждый байт должен быть повернут на несколько бит слева, чем первый. Таким образом, 1 байт должен быть повернут на 0 бит, а седьмой должен быть повернут на 6 бит.

В настоящее время я выполнил реализацию, которая делает это с помощью [я использую 1-битный поворот в качестве примера здесь], сдвигая регистр 1 бит влево и 7 вправо по отдельности. Затем я использую операцию смешивания (внутренняя операция _mm256_blend_epi16), чтобы выбрать правильные биты из первого и второго временных результатов, чтобы получить мой окончательный повернутый байт.
Это всего 2 операции смены и 1 операция смешивания на каждый байт, а 6 байтов необходимо повернуть, таким образом, 18 операций на байт (сдвиг и смешение имеют примерно такую ​​же производительность).

Должен быть более быстрый способ сделать это, чем использовать 18 операций для вращения одного байта!

Кроме того, мне нужно собрать все байты впоследствии в новом регистре. Я делаю это, загружая 7 масок командой «set» в регистры, поэтому я могу извлечь правильный байт из каждого регистра. I И эти маски с регистрами извлекают из них правильный байт. Впоследствии я XOR однобайтовые регистры вместе, чтобы получить новый регистр со всеми байтами. Это занимает в общей сложности 7 + 7 + 6 операций, поэтому еще 20 операций (за регистр).

Я мог бы использовать извлечение intrinsic (_mm256_extract_epi8), чтобы получить одиночные байты, а затем использовать _mm256_set_epi8 для сборки новых регистров, но пока не знаю, будет ли это быстрее. (В руководстве по встроению Intel нет указанной производительности, поэтому, возможно, я что-то не понимаю.)

Это дает в общей сложности 38 операций на регистр, что кажется менее оптимальным для вращения 6 байтов по-разному внутри регистр.

Надеюсь, что кто-то, более опытный в AVX/SIMD, может направить меня сюда - будь то я ошибаюсь - как я чувствую, что сейчас могу делать именно это.

Answer 1

XOP instruction set Предоставляет _mm_rot_epi8() (что НЕ относится к Microsoft, оно также доступно в GCC с 4.4 или более ранней версии и должно быть доступно также в недавнем clang). Его можно использовать для выполнения требуемой задачи в 128-битных единицах. К сожалению, у меня нет процессора с поддержкой XOP, поэтому я не могу это проверить.

На AVX2, разделяющем 256-битный регистр на две половины, один из которых содержит четные байты, а другие нечетные байты смещены вправо 8 бит, позволяет умножить 16-разрядный вектор на трюк. Указанные константы (с использованием GCC, 64-битный компонент формата массива)

static const __m256i epi16_highbyte = { 0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL }; 
static const __m256i epi16_lowbyte = { 0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL }; 
static const __m256i epi16_oddmuls = { 0x4040101004040101ULL, 
             0x4040101004040101ULL, 
             0x4040101004040101ULL, 
             0x4040101004040101ULL }; 
static const __m256i epi16_evenmuls = { 0x8080202008080202ULL, 
             0x8080202008080202ULL, 
             0x8080202008080202ULL, 
             0x8080202008080202ULL }; 

операция вращения может быть записана в виде

__m256i byteshift(__m256i value) 
{ 
    return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_lowbyte), epi16_oddmuls), 8), 
          _mm256_and_si256(_mm256_mullo_epi16(_mm256_and_si256(_mm256_srai_epi16(value, 8), epi16_lowbyte), epi16_evenmuls), epi16_highbyte)); 
} 

Это было проверено, чтобы получить правильные результаты на Intel Core i5-4200U с помощью GCC- 4.8.4. В качестве примера, входной вектор (в виде одного 256-битного шестнадцатеричного числа)

88 87 86 85 84 83 82 81 38 37 36 35 34 33 32 31 28 27 26 25 24 23 22 21 FF FE FD FC FB FA F9 F8 

получает поворачивается в

44 E1 D0 58 24 0E 05 81 1C CD C6 53 A1 CC 64 31 14 C9 C4 52 21 8C 44 21 FF BF BF CF DF EB F3 F8 

, где крайний левый октет поворачивается влево на 7 битов, следующие 6 битов, и скоро; седьмой октет не изменяется, восьмой октет вращается на 7 бит и т. д. для всех 32 октетов.

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

Так как вы, вероятно, не нравится выше краткий формат для функции, здесь она в процедурной, расширенная форма:

static __m256i byteshift(__m256i value) 
{ 
    __m256i low, high; 
    high = _mm256_srai_epi16(value, 8); 
    low = _mm256_and_si256(value, epi16_lowbyte); 
    high = _mm256_and_si256(high, epi16_lowbyte); 
    low = _mm256_mullo_epi16(low, epi16_lowmuls); 
    high = _mm256_mullo_epi16(high, epi16_highmuls); 
    low = _mm256_srli_epi16(low, 8); 
    high = _mm256_and_si256(high, epi16_highbyte); 
    return _mm256_or_si256(low, high); 
} 

---

В комментарии, Peter Cordes предложил заменить srai + and с srli, и, возможно, окончательный and + or с blendv. Первое имеет большой смысл, поскольку это чисто оптимизация, но последнее может не быть (хотя и на современных процессорах Intel!) На самом деле быстрее.

Я попробовал несколько микрофункции, но не смог получить надежные результаты. Обычно я использую TSC на x86-64 и принимаю медиану нескольких сотен тысяч тестов с использованием входов и выходов, хранящихся в массиве.

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

Я также согласен с его предложением использовать odd и even вместо high и low, но учтите, что, поскольку первый элемент в векторе нумеруются элемент 0, то первый элемент даже, второй нечетные, и так далее.

#include <immintrin.h> 

static const __m256i epi16_oddmask = { 0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL, 
             0xFF00FF00FF00FF00ULL }; 
static const __m256i epi16_evenmask = { 0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL, 
             0x00FF00FF00FF00FFULL }; 
static const __m256i epi16_evenmuls = { 0x4040101004040101ULL, 
             0x4040101004040101ULL, 
             0x4040101004040101ULL, 
             0x4040101004040101ULL }; 
static const __m256i epi16_oddmuls = { 0x8080202008080202ULL, 
             0x8080202008080202ULL, 
             0x8080202008080202ULL, 
             0x8080202008080202ULL }; 

/* Original version suggested by Nominal Animal. */ 
__m256i original(__m256i value) 
{ 
    return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_evenmask), epi16_evenmuls), 8), 
          _mm256_and_si256(_mm256_mullo_epi16(_mm256_and_si256(_mm256_srai_epi16(value, 8), epi16_evenmask), epi16_oddmuls), epi16_oddmask)); 
} 

/* Optimized as suggested by Peter Cordes, without blendv */ 
__m256i no_blendv(__m256i value) 
{ 
    return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_evenmask), epi16_evenmuls), 8), 
          _mm256_and_si256(_mm256_mullo_epi16(_mm256_srli_epi16(value, 8), epi16_oddmuls), epi16_oddmask)); 
} 

/* Optimized as suggested by Peter Cordes, with blendv. 
* This is the recommended version. */ 
__m256i optimized(__m256i value) 
{ 
    return _mm256_blendv_epi8(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_evenmask), epi16_evenmuls), 8), 
           _mm256_mullo_epi16(_mm256_srli_epi16(value, 8), epi16_oddmuls), epi16_oddmask); 
} 

Здесь вы найдете те же функции, что и отдельные операции. Хотя он вообще не влияет на компиляторы, я пометил параметр функции и каждое временное значение const, так что очевидно, как вы можете вставить каждый в последующее выражение, чтобы упростить функции до их более сжатых форм.

__m256i original_verbose(const __m256i value) 
{ 
    const __m256i odd1 = _mm256_srai_epi16(value, 8); 
    const __m256i even1 = _mm256_and_si256(value, epi16_evenmask); 
    const __m256i odd2 = _mm256_and_si256(odd1, epi16_evenmask); 
    const __m256i even2 = _mm256_mullo_epi16(even1, epi16_evenmuls); 
    const __m256i odd3 = _mm256_mullo_epi16(odd3, epi16_oddmuls); 
    const __m256i even3 = _mm256_srli_epi16(even3, 8); 
    const __m256i odd4 = _mm256_and_si256(odd3, epi16_oddmask); 
    return _mm256_or_si256(even3, odd4); 
} 

__m256i no_blendv_verbose(const __m256i value) 
{ 
    const __m256i even1 = _mm256_and_si256(value, epi16_evenmask); 
    const __m256i odd1 = _mm256_srli_epi16(value, 8); 
    const __m256i even2 = _mm256_mullo_epi16(even1, epi16_evenmuls); 
    const __m256i odd2 = _mm256_mullo_epi16(odd1, epi16_oddmuls); 
    const __m256i even3 = _mm256_srli_epi16(even2, 8); 
    const __m256i odd3 = _mm256_and_si256(odd2, epi16_oddmask); 
    return _mm256_or_si256(even3, odd3); 
} 

__m256i optimized_verbose(const __m256i value) 
{ 
    const __m256i even1 = _mm256_and_si256(value, epi16_evenmask); 
    const __m256i odd1 = _mm256_srli_epi16(value, 8); 
    const __m256i even2 = _mm256_mullo_epi16(even1, epi16_evenmuls); 
    const __m256i odd2 = _mm256_mullo_epi16(odd1, epi16_oddmuls); 
    const __m256i even3 = _mm256_srli_epi16(even2, 8); 
    return _mm256_blendv_epi8(even3, odd2, epi16_oddmask); 
} 

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

Answer 2

[Основываясь на первом комментарии и некоторых изменениях, получившееся решение немного отличается. Я представлю это сначала, а затем оставьте первоначальную мысль ниже]

Основная идея здесь заключается в использовании умножения на степеней 2 для выполнения сдвига, поскольку эти константы могут меняться в зависимости от вектора. @harold указала на следующую идею, которая заключается в том, что умножение двух дублированных байтов автоматически приведет к «вращению» сдвинутых битов обратно в младшие биты.

1. Распаковка и дублирующие байты в 16-разрядные значения [... d c b a] -> [... dd cc bb aa]
2. Генерировать 16-разрядную константу [128 64 32 16 8 4 2 1]
3. Multiply
4. байт вы хотите верхние восемь бит каждого 16-битного значения, так правая смена и переупаковка

Предполагая источник __m128i (у вас всего 8 байт, не так ли?):

__m128i duped = _mm_unpacklo_epi8(src, src); 
__m128i res = _mm_mullo_epi16(duped, power_of_two_vector); 
__m128i repacked = _mm_packus_epi16(_mm_srli_epi16(res, 8), __mm_setzero_si128()); 

---

[Сохранив эту оригинальную идею для сравнения]

Что об этом: Используйте умножение степеней 2, чтобы выполнить сдвиги, используя 16-разрядные продукты. Затем ИЛИ верхнюю и нижнюю половинки продукта, чтобы выполнить поворот.

1. Распакуйте байты в 16-битные слова.
2. Генерировать 16-бит [128 64 32 16 8 4 2 1]
3. умножают 16-битовых слов
4. Re-Pack 16-бит на два восемь-битных векторов, вектор высокого байта и низкобайтовый вектор
5. OR эти два вектора для выполнения поворота.

Я немного расплывчатый по доступным опциям умножения и ограничению набора инструкций, но идеальным было бы 8-битное умножение на 8 бит, которое производит 16-разрядные продукты. Насколько я знаю, этого не существует, поэтому я предлагаю распаковать сначала, но я видел другие аккуратные алгоритмы для этого.