оператор if / else в встроенных функциях SSE - PullRequest
Новая
       114

оператор if / else в встроенных функциях SSE

6 голосов
/ 09 июня 2011

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

Мой оригинальный код:

unsigned long c;
unsigned long constant = 0x12345678;
unsigned long table[256];
int n, k;

for( n = 0; n < 256; n++ )
{
  c = n;
  for( k = 0; k < 8; k++ )
    {
      if( c & 1 ) c = constant ^ (c >> 1);
      else c >>= 1;
    }
  table[n] = c;
}

Цель этого кода - вычислить таблицу crc (константа может быть любым полиномом, здесь она не играет роли),

Полагаю, мой оптимизированный кодбыть примерно таким: 

__m128 x;
__m128 y;
__m128 *table;

x = _mm_set_ps(3, 2, 1, 0);
y = _mm_set_ps(3, 2, 1, 0);
//offset for incrementation
offset = _mm_set1_ps(4);

for( n = 0; n < 64; n++ )
{
    y = x;
    for( k = 0; k < 8; k++ )
    {
        //if do something with y
        //else do something with y
    }
    table[n] = y;
    x = _mm_add_epi32 (x, offset);
}

Я не знаю, как пройти через оператор if-else, но я подозреваю, что есть хитрый трюк.У кого-нибудь есть идеи о том, как это сделать?

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

Ответы [ 3 ]

12 голосов
/ 09 июня 2011

Вы можете полностью избавиться от if / else. В те времена, когда я создавал код сборки MMX, это было обычное программирование. Позвольте мне начать с серии преобразований «ложного» утверждения: 

c >>= 1;

c = c >> 1;

c = 0 ^ (c >> 1);

Почему я ввел эксклюзив или? Поскольку исключающее-или также находится в «истинном» утверждении: 

c = constant ^ (c >> 1);

Обратите внимание на сходство? В «истинной» части мы xor с константой, а в ложной части мы xor с нулем.

Теперь я собираюсь показать вам серию преобразований всего оператора if / else: 

if (c & 1)
    c = constant ^ (c >> 1);          // same as before
else
    c =        0 ^ (c >> 1);          // just different layout

if (c & 1)
    c =  constant      ^ (c >> 1);
else
    c = (constant & 0) ^ (c >> 1);    // 0 == x & 0

if (c & 1)
    c = (constant & -1) ^ (c >> 1);   // x == x & -1
else
    c = (constant &  0) ^ (c >> 1);

Теперь две ветви отличаются только вторым аргументом двоичного-и, который можно вычислить тривиально из самого условия, что позволяет нам избавиться от if / else: 

c = (constant & -(c & 1)) ^ (c >> 1);

Отказ от ответственности: Это решение работает только на архитектуре дополнения до двух , где -1 означает «все биты установлены».

2 голосов
/ 09 июня 2011

Идея в SSE состоит в том, чтобы построить оба результата и затем смешать результаты вместе.

Например: 

__m128i mask = ...; // some way to build mask[n] = 0x1
__m128i constant = ...;

__m128i tmp_c = _mm_xor_si128( _mm_srli_epis32( c, 1 ), constant );
__m128i tmp_c2 = _mm_srli_epis32( c, 1 );

__m128i v = _mm_cmpeq_epi32( c, mask );
tmp_c = _mm_and_epi32( tmp_c, mask );
tmp_c2 = _mm_andnot_si128( mask, tmp_c2 );
c = _mm_or_si128( tmp_c, tmp_c2 );
// or in sse4_1
c = _mm_blendv_epi8( tmp_c, tmp_c2, mask );

Обратите внимание, что это не полный код, только для демонстрации принципа.

1 голос
/ 09 июня 2011

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

...