Убедитесь, что по крайней мере 1 элемент истинен в каждом из нескольких векторов результатов сравнения - горизонтальное ИЛИ, а затем И

Question

Я ищу SSE побитовое ИЛИ между компонентами одного и того же вектора. (Примечание редактора: это потенциально проблема XY, реальная логика сравнения приведена ниже.)

Я портирую некоторую SIMD-логику от встроенных функций SPU. Есть инструкция

spu_orx(a)

Который в соответствии с документами

spu_orx: ИЛИ слово через d = spu_orx(a) Четыре элемента слова вектора a логически выделены. Результат возвращается в элементе слова 0 вектора d. Всем остальным элементам (1,2,3) из d присваивается значение ноль.

Как я могу сделать это с SSE 2 - 4, включающей минимальное обучение? _mm_or_ps это то, что я получил здесь

ОБНОВИТЬ:

Вот сценарий из кода на основе SPU:

qword res =  spu_orx(spu_or(spu_fcgt(x, y), spu_fcgt(z, w)))

Таким образом, сначала ИЛИ два "больших" сравнения, а затем ИЛИ его результат. Более поздние пары этих результатов используются для получения окончательного значения сравнения.

Это эффективно делает (A||B||C||D||E||F||G||H) && (I||J||K||L||M||N||O||P) && ... где A..D - 4x 32-битные элементы fcgt(x,y) и так далее.

Очевидно вертикальный _mm_or_ps из _mm_cmp_ps Результаты - это хороший способ уменьшить до 1 вектора, но что тогда? Shuffle + ИЛИ или что-то еще?

ОБНОВЛЕНИЕ 1

Что касается "но тогда что?" Я выполняю

     qword res =  spu_orx(spu_or(spu_fcgt(x, y), spu_fcgt(z, w)))

На SPU это выглядит так:

 qword aRes  = si_and(res, res1);
 qword aRes1 = si_and(aRes, res2);
 qword aRes2 = si_and(aRes1 , res3);
 return si_to_uint(aRes2 );

несколько раз на разных входах, а затем И все в один результат, который в итоге приводится к целому числу 0 или 1 (тест false/true)

Answer 1

SSE4.1 PTEST bool any_nonzero = !_mm_testz_si128(v,v);

Это было бы хорошим способом горизонтального ИЛИ + логического преобразования вектора в целое число 0/1. Он скомпилируется с несколькими инструкциями и ptest same,same является 2 мопами самостоятельно. Но как только вы получите результат в виде скалярного целого числа, скаляр AND даже дешевле, чем любая векторная инструкция, и вы можете переходить к результату напрямую, потому что он устанавливает целочисленные флаги.

#include <immintrin.h>
bool any_nonzero_bit(__m128i v) {
    return !_mm_testz_si128(v,v);
}

На Годболте с gcc9.1 -O3 -march= Нехалем:

any_nonzero(long long __vector(2)):
    ptest   xmm0, xmm0                        # 2 uops
    setne   al                                # 1 uop with false dep on old value of RAX
    ret

Это всего 3 мопа на Intel для горизонтального ИЛИ в один бит в целочисленном регистре. AMD Ryzen ptest только 1 моп, так что это даже лучше.

Единственный риск здесь заключается в том, что gcc или clang создает ложные зависимости, не обнуляя нулю eax прежде чем делать setcc в AL. Обычно gcc довольно фанатично тратит лишние мопы, чтобы сломать ложные зависимости, поэтому я не знаю, почему этого не происходит. (Я проверил с -march=skylake а также -mtune=generic в случае, если он полагался на переименование частичного регистра Nehalem для -march=nehalem, Четный -march=znver1 не получил xor-zero EAX перед тестированием.)

Было бы хорошо, если бы мы могли избежать _mm_or_ps и пусть PTEST сделает всю работу. Но даже если мы рассмотрим инверсию сравнений, поведение вертикального И / горизонтального ИЛИ не позволяет нам проверять что-либо обо всех 8 элементах 2 векторов или о любом из этих 8 элементов.

Например, можно ли использовать PTEST для проверки того, что оба регистра равны нулю, или какое-то другое условие?

  // NOT USEFUL
 // 1 if all the vertical pairs AND to zero.
 // but 0 if even one vertical AND result is non-zero
_mm_testz_si128( _mm_castps_si128(_mm_cmpngt_ps(x,y)), 
                 _mm_castps_si128(_mm_cmpngt_ps(z,w)));

Я упоминаю об этом только для того, чтобы исключить это и избавить вас от необходимости рассматривать эту идею оптимизации. (@chtz предложил это в комментариях. Инвертировать сравнение - это хорошая идея, которая может быть полезна для других способов ведения дел.)

---

Без SSE4.1 / задержка горизонтального ИЛИ

Мы могли бы задержать горизонтальное ORing / booleanizing до тех пор, пока не будут объединены некоторые результаты из нескольких векторов. Это делает объединение более дорогим (imul или что-то в этом роде), но сохраняет 2 мопа в векторе -> целочисленная стадия против PTEST.

x86 имеет дешевую векторную маску-> целочисленное растровое изображение с _mm_movemask_ps, Особенно, если вы в конечном итоге хотите получить результат, это может быть хорошей идеей. (Но у x86 нет || инструкция, которая логизирует свои входы, так что вы не можете просто & результаты передвижения маски).

Одна вещь, которую вы можете сделать, это умножение целых чисел movemask Результаты: x * y ненулевой, если оба входа отличны от нуля. в отличие x & y который может быть ложным для 0b0101 & 0b1010 for example. (Our inputs are 4-bit movemask results and unsigned` является 32-битным, поэтому у нас есть место до переполнения). Семейство AMD Bulldozer имеет целочисленное умножение, которое не полностью конвейеризовано, поэтому это может быть узким местом на старых процессорах AMD. Использование только 32-разрядных целых чисел также хорошо для некоторых процессоров с низким энергопотреблением с медленным 64-разрядным умножением.

Это может быть хорошо, если пропускная способность является скорее узким местом, чем задержкой, хотя movmskps может работать только на одном порту.

Я не уверен, существуют ли более дешевые целочисленные операции, которые позволят нам восстановить результат логического И позже. Добавление не работает; результат не равен нулю, даже если только один из входов был ненулевым. Объединение битов вместе (shift + или) также, конечно, похоже на OR, если мы в конечном итоге просто проверяем любой ненулевой бит. Мы не можем просто поразить И потому что 2 & 1 == 0, в отличие 2 && 1,

---

Хранение в векторной области

Горизонтальное ИЛИ из 4 элементов занимает несколько шагов.

Очевидный путь _mm_movehl_ps + ИЛИ, затем еще одна случайность + ИЛИ. (См. Самый быстрый способ сделать горизонтальную векторную сумму с плавающей запятой на x86, но заменить _mm_add_ps с участием _mm_or_ps)

Но так как нам на самом деле не нужно точное побитовое ИЛИ, когда наши входные данные сравнивают результаты, мы просто заботимся, если какой-либо элемент не равен нулю. Мы можем и должны думать о векторах как о целых числах и рассматривать целочисленные инструкции как 64-битный элемент ==, Один 64-битный элемент охватывает / псевдоним двух 32-битных элементов.

__m128i cmp = _mm_castps_si128(cmpps_result);               // reinterpret: zero instructions
                 // SSE4.1 pcmpeqq 64-bit integer elements
__m128i cmp64 = _mm_cmpeq_epi64(cmp, _mm_setzero_si128());  // -1 if both elements were zero, otherwise 0
__m128i swap =  _mm_shuffle_epi32(cmp64, _MM_SHUFFLE(1,0, 3,2));  // copy and swap, no movdqa instruction needed even without AVX
__m128i bothzero = _mm_and_si128(cmp64, swap);              // both halves have the full result

После этой логической инверсии ORing вместе несколько bothzero результаты дадут вам И для нескольких условий, которые вы ищете.

В качестве альтернативы, SSE4.1 _mm_minpos_epu16(cmp64) ( phminposuw ) сообщит нам в 1 моп (но с 5 задержками цикла), если любое из qword равно нулю. Это будет либо 0 или же 0xFFFF в самом низком слове (16 бит) результата в этом случае.

Если бы мы перевернули оригинальное сравнение, мы могли бы использовать phminposuw на что (без pcmpeqq ) чтобы проверить, есть ли ноль. Так что в основном горизонтальное И по всему вектору. (Предполагая, что это элементы 0 / -1). Я думаю, что это полезный результат для инвертированных входов. (И спасает нас от использования _mm_xor_si128 перевернуть биты).

Альтернатива pcmpeqq (_mm_cmpeq_epi64) будет SSE2 psadbw против обнуленного вектора, чтобы получить 0 или ненулевое значение в нижней части каждого 64-битного элемента. Это не будет маска, хотя, это 0xFF * 8, Тем не менее, это всегда тот или 0, так что вы все еще можете и это. И это не инвертировать.