Вычислите абсолютную разницу между целыми числами без знака, используя SSE

Есть несколько способов сделать это, я упомяну только один:

SSE4

• Используйте PMINUD и PMAXUD, чтобы разделить большее значение в регистре №1 и меньшее значение в регистре №2.
• Вычтите их.

MMX/SSE2

• Переверните бит знака двух значений, потому что следующая инструкция принимает только сравнение целых чисел со знаком.
• PCMPGTD. Используйте этот результат в качестве маски.
• Вычислить результаты как (a-b), так и (b-a)
• Используйте POR ( PAND ( mask, a-b ), PANDN ( mask, b-a ) ), чтобы выбрать правильное значение абсолютной разницы.

На сайте tommesani.com одним из решений этой проблемы является двукратное использование насыщающего беззнакового вычитания.

Поскольку вычитание насыщения никогда не опускается ниже 0, вы вычисляете: r1 = (a-b).saturating r2 = (b-a).saturating

Если a больше b, то r1 будет содержать ответ, а r2 будет равно 0, и наоборот, если b>a. Объединение двух частичных результатов по операции ИЛИ даст желаемый результат.

Согласно руководство пользователя VTUNE, PSUBUSB/PSUBUSW доступны для 128-битных регистров, поэтому таким образом вы сможете получить тонну распараллеливания.

max(i,j) - min(i,j)
(i>j)*(i-j) + (j>i)*(j-i)

вы, конечно, можете использовать регистры SSE, но компилятор все равно может сделать это за вас

SSE2:

Кажется, примерно такая же скорость, как и у второй функции Ферноста. Иногда GCC планирует выполнение полного цикла быстрее, иногда немного медленнее.

__m128i big = _mm_set_epi32( INT_MIN, INT_MIN, INT_MIN, INT_MIN );

a = _mm_add_epi32( a, big ); // re-center the variables: send 0 to INT_MIN,
b = _mm_add_epi32( b, big ); // INT_MAX to -1, etc.
__m128i diff = _mm_sub_epi32( a, b ); // get signed difference
__m128i mask = _mm_cmpgt_epi32( b, a ); // mask: need to negate difference?
mask = _mm_andnot_si128( big, mask ); // mask = 0x7ffff... if negating
diff = _mm_xor_si128( diff, mask ); // 1's complement except MSB
diff = _mm_sub_epi32( diff, mask ); // add 1 and restore MSB

SSSE3:

Всегда немного быстрее, чем предыдущий. Существует множество вариаций в зависимости от того, как объявляются вещи вне цикла. (Например, преобразование a и b в volatile ускорит работу! Похоже, что это случайный эффект при планировании.) Но это постоянно ускоряет цикл или около того.

__m128i big = _mm_set_epi32( INT_MIN, INT_MIN, INT_MIN, INT_MIN );

a = _mm_add_epi32( a, big ); // re-center the variables: send 0 to INT_MIN,
b = _mm_add_epi32( b, big ); // INT_MAX to -1, etc.
__m128i diff = _mm_sub_epi32( b, a ); // get reverse signed difference
__m128i mask = _mm_cmpgt_epi32( b, a ); // mask: need to negate difference?
mask = _mm_xor_si128( mask, big ); // mask cannot be 0 for PSIGND insn
diff = _mm_sign_epi32( diff, mask ); // negate diff if needed

SSE4 (спасибо, Рвонг):

Не могу проверить это.

__m128i diff = _mm_sub_epi32( _mm_max_epu32( a, b ), _mm_min_epu32( a, b ) );

вычислить разницу и вернуть абсолютное значение

__m128i diff = _mm_sub_epi32(a, b);  
__m128i mask = _mm_xor_si128(diff, a);
mask = _mm_xor_si128(mask, b);
mask = _mm_srai_epi32(mask, 31);
diff = _mm_xor_si128(diff, mask);  
mask = _mm_srli_epi32(mask, 31);  
diff = _mm_add_epi32(diff, mask);  

Это требует на одну операцию меньше, чем при использовании операции сравнения со знаком, и создает меньшее давление на регистр.

То же количество регистров, что и раньше, еще 2 операции, улучшенное ветвление и слияние цепочек зависимостей, объединение инструкций для декодирования мопов и использование отдельных единиц. Хотя для этого требуется загрузка, которая может быть вне кеша. У меня нет идей после этого.

__m128i mask, diff;
diff = _mm_set1_epi32(-1<<31); // dependency branch after
a = _mm_add_epi32(a, diff); // arithmetic sign flip
b = _mm_xor_si128(b, diff); // bitwise sign flip parallel with 'add' unit
diff = _mm_xor_si128(a, b); // reduce uops, instruction already decoded
mask = _mm_cmpgt_epi32(b, a); // parallel with xor
mask = _mm_and_si128(mask, diff); // dependency merge, branch after
a = _mm_xor_si128(a, mask); // if 2 'bit' units in CPU, parallel with next
b = _mm_xor_si128(b, mask); // reduce uops, instruction already decoded
diff = _mm_sub_epi32(a, b); // result

После хронометража каждой версии с 2 миллионами итераций на Core2Duo различия неизмеримы. Так что выбирайте то, что легче понять.

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

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

unsigned udiff( unsigned a, unsigned b )
{
      unsigned result = a-b;   // ok if a<b;
      if(a <b ) result = -result; 
      return result;
}
unsigned udiff( unsigned a, unsigned b )
{
      unsigned n =(a<b)? (unsigned)-1 : 0u;
      unsigned result = a-b;
      return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF
}


unsigned udiff( unsigned a, unsigned b )
{
      unsigned axb = a^b;
      if( a < b )  axb = 0;
      return (axb^b) - (axb^a);  // a-b, or b-a
}

Это будет работать на x86_64 (или где-либо, где 64-битные временные файлы в основном бесплатны)

unsigned udiff( unsigned a, unsigned b )
{
      unsigned n= (unsigned)( 
         (long long)((unsigned long long)a - (unsigned long long)b)>>32 
                      ); // same n as 2nd example
      unsigned result = a-b;
      return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF
}

Попробуйте это (предполагается 2-е дополнение, что нормально, судя по тому факту, что вы запрашиваете SSE):

int d = a-b;
int ad = ((d >> 30) | 1) * d;

Объяснение: знаковый бит (бит 31) распространяется вниз до 1-го бита. | 1 часть гарантирует, что множитель равен 1 или -1. Умножения выполняются быстро на современных процессорах.

Эм... это довольно легко...

int diff = abs( a - b );

Легко векторизуемый (с использованием SSE3 как):

__m128i sseDiff = _mm_abs_epi32( _mm_sub_epi32( a, b ) );

a и b — целые числа без знака. Рассмотрим a=0 и b=0xffffffff. Правильная абсолютная разница — 0xffffffff, но ваше решение даст 1.