SIMD zero vector test

Question

Существует ли быстрый способ проверить, является ли SIMD-вектор нулевым вектором (все компоненты равны + -zero). В настоящее время я использую алгоритм с использованием сдвигов, который выполняется в log2 (N) времени, где N - размерность вектора. Существует ли что-нибудь быстрее? Обратите внимание, что мой вопрос более широк (теги), чем предлагаемый ответ, и он относится к векторам всех типов (integer, float, double, ...).

Answer 1

Как насчет этого простого кода avx? Я думаю, что это O (N) и не знаю, как вы могли бы сделать лучше, не делая предположений о входных данных - вы должны действительно читать каждое значение, чтобы знать, является ли его 0, поэтому он должен делать столько, сколько возможно за цикл ,

Вы должны иметь возможность массировать код в соответствии с вашими потребностями. Следует рассматривать как +0, так и -0 как ноль. Будет работать для неадминистративных адресов памяти, но выравнивание по 32-байтным адресам сделает загрузку быстрее. Вы можете добавить что-то, чтобы иметь дело с оставшимися байт, если размер не кратен 8.

uint64_t num_non_zero_floats(float *mem_address, int size) { 
    uint64_t num_non_zero = 0; 
    __m256 zeros _mm256_setzero_ps(); 
    for(i = 0; i != size; i+=8) { 
     __m256 vec _mm256_loadu_ps (mem_addr + i); 
     __m256 comparison_out _mm256_cmp_ps (zeros, vec, _CMP_EQ_OQ); //3 cycles latency, throughput 1 
     uint64_t bits_non_zero = _mm256_movemask_ps(comparison_out); //2-3 cycles latency 
     num_non_zero += __builtin_popcountll(bits_non_zero); 
    } 
    return num_non_zero; 
} 

Answer 2

Если вы хотите проверить, поплавки для +/- 0,0, то вы можете проверить все биты, равным нулю , за исключением знакового бита. Любые биты в любом месте, кроме знакового бита, означают, что поплавок отличен от нуля. (http://www.h-schmidt.net/FloatConverter/IEEE754.html)

---

Agner Туман-х asm optimization guide указывает на то, что вы можете проверить поплавок или дважды за ноль с помощью инструкции целочисленных:

; Example 17.4b 
mov eax, [rsi] 
add eax, eax ; shift out the sign bit 
jz IsZero 

Для векторов, хотя, используя ptest с знаком-битной маски лучше, чем использование paddd, чтобы избавиться от бита знака. На самом деле, test [rsi], $0x7fffffff может быть более эффективным, чем последовательность загрузки/добавления Agner Fog, но 32-битное мгновенно, вероятно, останавливает нагрузку от микро-плавки на Intel и, возможно, имеет больший размер кода.

---

x86 PTEST (SSE4.1) делает побитовое И и устанавливает флаги на основании результата.

movdqa xmm0, [mask] 
.loop: 
ptest xmm0, [rsi+rcx] 
jnz nonzero 
add rcx, 16 # count up towards zero 
jl  .loop # with rsi pointing to past the end of the array 
... 
nonzero: 

Или cmov может быть полезно потреблять флаги, установленные ptest.

IDK, если можно было бы использовать инструкцию loop-counter, которая не устанавливала флаг нуля, поэтому вы могли бы выполнить оба теста с помощью одной команды перехода или чего-то еще. Возможно нет. И дополнительный uop для объединения флагов (или срыв частичных флагов на более ранние процессоры) сэкономит преимущество.

@Iwillnotexist Idonotexist: повторите один из комментариев к OP: вы не можете просто movemask, не делая сначала pcmpeq, или cmpps. Необязательный бит может быть не в бит! Вы, наверное, знали об этом, но один из ваших комментариев, похоже, оставил его.

Мне нравится идея объединить несколько значений перед фактическим тестированием. Вы правы, что знаковые биты будут ИЛИ с другими знаками, а затем вы игнорируете их так же, как если бы вы тестировали один за раз. Цикл, который POR s 4 или 8 векторов перед каждым PTEST, вероятно, будет быстрее. (PTEST - это 2 устройства и не может использовать макро-предохранитель с jcc.)