Настройка алгоритма подсчета битов Массачусетского технологического института для параллельного подсчета слов?

Я хочу использовать версию хорошо известного алгоритма MIT bitcount для подсчета соседей в жизненной игре Конвея с использованием инструкций 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, делаю то же самое для слова 1 XMM0 и т. д. с использованием разных срезов и масок, чтобы каждое слово в XMM0 и XMM1 содержало соседей для другого пикселя.

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

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

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


optimization simd sse sse2 conways-game-of-life
person Johan    schedule 21.06.2011    source источник
comment
Просто чтобы уточнить - вы хотите, чтобы popcnt для каждого из 8 x 16-битных слов в 128-битном векторе? Например. вход = {0, 1, 2, 3, 4, 5, 6, 7}, выход = {0, 1, 1, 2, 1, 2, 2, 3}. Это верно ?   -  person Paul R    schedule 22.06.2011
comment
Мне любопытны ваши результаты - метод SSE2 быстрее? И как это соотносится с реализацией с использованием инструкции сборки POPCNT (представленной в SSE4, который, кстати, доступен в Delphi)? Также это может быть интересно: wm.ite.pl/articles/sse-popcount.html < / а>   -  person PhiS    schedule 28.06.2011
comment
@phiS, еще не тестировал его полностью, поиск пока выглядит быстрее, потому что кеш всегда горячий из-за небольшого набора тестов. Если кеш-промахи начинают, факторинг в SSE должен выиграть. Проблема в том, что поиск генерирует вывод за один раз, и SSE требуется некоторый перевод для создания вывода. В SSE3 есть инструкция pshufb, которая может выполнять поиск по 4 битам + переполнение = 4,5 бит. Это могло быть победителем.   -  person Johan    schedule 29.06.2011
comment
Для «Игры жизни» Конвея вам не нужен алгоритм подсчета битов. Вы хотите реализовать весь алгоритм, используя чистую двоичную логику, а затем реализовать его для 64 ячеек параллельно, используя беззнаковые 64-битные целые числа (или 128 или 256 бит параллельно с использованием векторных регистров).   -  person gnasher729    schedule 29.04.2014

Ответы (1)


arrow_upward
3
arrow_downward

Алгоритм MIT будет сложно реализовать в SSE2, поскольку нет инструкции целочисленного модуля, которую можно было бы использовать для окончательного выражения ... % 255. Из различных существующих методов popcnt тот, который наиболее легко и эффективно поддается SSE, вероятно, является первым в главе 5 " Hackers Delight "Генри С. Уоррена, который я реализовал здесь на 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 такта на точку.

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

person Paul R    schedule 22.06.2011
comment
Спасибо, Пол, это похоже на жесткий подход. Я тоже интересовался mod. - person Johan; 22.06.2011
comment
Также есть хорошая сравнительная таблица для нескольких алгоритмов на strchr.com/crc32_popcnt (оба размещены здесь и включены как хорошо). - person FrankH.; 30.08.2011