Настраивает алгоритм MIT для подсчета битов для параллельного подсчета слов? - PullRequest
Новая
       100

Настраивает алгоритм MIT для подсчета битов для параллельного подсчета слов?

3 голосов
/ 22 июня 2011

Я хочу использовать версию хорошо известного алгоритма подсчета битов MIT для подсчета соседей в игре жизни Конвея с использованием инструкций SSE2.

Вот битрейт MIT в c, расширенный для подсчета битрейтов> 63 бит. 

int bitCount(unsigned long long n)
{
unsigned long long uCount;

uCount = n – ((n >> 1) & 0×7777777777777777)
           - ((n >> 2) & 0×3333333333333333)
           - ((n >> 3) & 0×1111111111111111);
return ((uCount + (uCount >> 4))
& 0x0F0F0F0F0F0F0F0F) % 255;
}

Вот версия на Паскале 

function bitcount(n: uint64): cardinal;
var ucount: uint64;
begin
  ucount:= n - ((n shr 1) and $7777777777777777)
             - ((n shr 2) and $3333333333333333) 
             - ((n shr 3) and $1111111111111111);
  Result:= ((ucount + (count shr 4)) 
           and $0F0F0F0F0F0F0F0F) mod 255;
end;

Я рассчитываю подсчитывать биты в этой структуре параллельно. 

  32-bit word where the pixels are laid out as follows.
  lo-byte         lo-byte neighbor
  0 4 8 C  048C   0 4 8 C 
   +---------------+
  1|5 9 D  159D   1|5 9 D 
   |               |
  2|6 A E  26AE   2|6 A E  
   +---------------+
  3 7 B F  37BF   3 7 B F 
 |-------------|            << slice A
   |---------------|        << slice B
     |---------------|      << slice C

Обратите внимание, как эта структура имеет16 бит в середине, которые нужно посмотреть вверх.Я хочу вычислить число соседей для каждого из 16 битов в середине, используя SSE2.Для этого я помещаю срез A в XMM0 с низким мечом, срез B в XXM0-dword1 и т. Д.
Я копирую XMM0 в XMM1 и маскирую биты 012-456-89A для бита 5 в младшем слове XMM0сделайте то же самое для word1 в XMM0 и т. д., используя разные срезы и маски, чтобы убедиться, что каждое слово в XMM0 и XMM1 содержит соседей для другого пикселя.

Вопрос
Какмне настроить бит-счет MIT, чтобы в каждом слове XMM получалось количество бит на слово / пиксель?

Примечания
Я не хочу использовать таблицу поиска, потому чтоУ меня уже есть такой подход, и я хочу проверить, ускорит ли SSE2 процесс, не требуя обращения к памяти для таблицы поиска.

Ответ с использованием сборки SSE будет оптимальным, потому что я программирую этов Delphi, и поэтому я использую код сборки x86 + SSE2.

1 Ответ

3 голосов
/ 22 июня 2011

Алгоритм MIT было бы сложно реализовать в SSE2, так как не существует инструкции целочисленного модуля, которую можно было бы использовать для конечного выражения ... % 255. Из различных методов popcnt, тот, который наиболее легко и эффективно поддается SSE, является, вероятно, первым в главе 5 «Хакерского наслаждения» Генри С. Уоррена , которую я реализовал здесь C с использованием встроенных функций SSE: 

#include <stdio.h>
#include <emmintrin.h>

__m128i _mm_popcnt_epi16(__m128i v)
{
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x5555)), _mm_and_si128(_mm_srli_epi16(v, 1), _mm_set1_epi16(0x5555)));
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x3333)), _mm_and_si128(_mm_srli_epi16(v, 2), _mm_set1_epi16(0x3333)));
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x0f0f)), _mm_and_si128(_mm_srli_epi16(v, 4), _mm_set1_epi16(0x0f0f)));
    v = _mm_add_epi16(_mm_and_si128(v, _mm_set1_epi16(0x00ff)), _mm_and_si128(_mm_srli_epi16(v, 8), _mm_set1_epi16(0x00ff)));
    return v;
}

int main(void)
{
    __m128i v0 = _mm_set_epi16(7, 6, 5, 4, 3, 2, 1, 0);
    __m128i v1;

    v1 = _mm_popcnt_epi16(v0);

    printf("v0 = %vhd\n", v0);
    printf("v1 = %vhd\n", v1);

    return 0;
}

Скомпилируйте и протестируйте следующим образом: 

$ gcc -Wall -msse2 _mm_popcnt_epi16.c -o _mm_popcnt_epi16
$ ./_mm_popcnt_epi16 
v0 = 0 1 2 3 4 5 6 7
v1 = 0 1 1 2 1 2 2 3
$

Похоже, около 16 арифметических / логических инструкций, поэтому он должен работать примерно на 16/8 = 2 такта на точку.

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

...