Какое значение имеет _mm256_shuffle_epi8 в этой реализации Game of Life? - PullRequest
Новая
       39

Какое значение имеет _mm256_shuffle_epi8 в этой реализации Game of Life?

0 голосов
/ 06 февраля 2019

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

Эта реализация сначала вычисляет количество живых соседей для каждой продажи и сохраняет результат в массиве counts, поэтому массив продаж (world) равен states.Я действительно не могу понять, как newstate генерируется здесь.Я понимаю, как работает сдвиг влево, как работает побитовое ИЛИ, но я не могу понять, почему они используются так, почему shufmask так и как работает тасование.Также не могу понять, почему _mm256_slli_epi16 используется, если тип элементов массива uint8_t.Так что мой вопрос все об этой строке

__m256i newstate = _mm256_shuffle_epi8(shufmask, _mm256_or_si256(c, _mm256_slli_epi16(oldstate, 3)));

Не могли бы вы объяснить, фиктивный мальчик, если это возможно максимально подробно, как это работает. 

void gameoflife8vec(uint8_t *counts, uint8_t *states, size_t width, size_t height) {
assert(width % (sizeof(__m256i)) == 0);
size_t awidth = width + 2;
computecounts8vec(counts, states, width, height);
__m256i shufmask =
    _mm256_set_epi8(
        0, 0, 0, 0, 0, 1, 1, 0,
        0, 0, 0, 0, 0, 1, 0, 0,
        0, 0, 0, 0, 0, 1, 1, 0,
        0, 0, 0, 0, 0, 1, 0, 0
    );
for (size_t i = 0; i < height; i++) {
    for (size_t j = 0; j < width; j += sizeof(__m256i)) {
        __m256i c = _mm256_lddqu_si256(
            (const __m256i *)(counts + (i + 1) * awidth + j + 1));
        c = _mm256_subs_epu8(
            c, _mm256_set1_epi8(
                1)); // max was 8 = 0b1000, make it 7, 1 becomes 0, 0 remains 0

        __m256i oldstate = _mm256_lddqu_si256(
            (const __m256i *)(states + (i + 1) * awidth + j + 1));
        __m256i newstate = _mm256_shuffle_epi8(
            shufmask, _mm256_or_si256(c, _mm256_slli_epi16(oldstate, 3)));
        _mm256_storeu_si256((__m256i *)(states + (i + 1) * awidth + (j + 1)),
            newstate);
    }
}
}

Память для массива распределяется таким образом 

uint8_t *states = (uint8_t *)malloc((N + 2) * (N + 2) * sizeof(uint8_t));
uint8_t *counts = (uint8_t *)malloc((N + 2) * (N + 2) * sizeof(uint8_t));

Также здесь можно найти исходный код https://github.com/lemire/SIMDgameoflife

1 Ответ

0 голосов
/ 06 февраля 2019

shuffle_epi8 используется здесь как параллельный поиск в таблице с постоянным первым операндом и переменным вторым операндом.

Код Даниеля выполняет некоторые вычисления, которые выдают 4-битное целое число для каждого байта ввектор, затем использует _mm256_shuffle_epi8, чтобы отобразить эти целые числа в 0/1 новых живых или мертвых новых состояний.

Обратите внимание, что нижние и верхние полосы shufmask идентичны: это та же самая таблица поиска дляобе полосы движения(Это не случайный переход, это 32 параллельных поиска из 2-х 16-байтовых таблиц, использующих младшие 4 бита в каждом элементе. И старший бит для его обнуления.)

shufmask плохой выбор имени переменной.Это , а не вектор тасования.alivetable может быть лучшим выбором.

Использование [v]pshufb для реализации LUT с 16 записями является (довольно) хорошо известным методом. Это один из способов реализацииpopcnt для больших массивов, который быстрее скалярного, разбивает байты на клочки low / high и просматривает 4-битные результаты popcnt.См. Подсчет 1 бита (подсчет населения) для больших данных с использованием AVX-512 или AVX-2 , в частности https://github.com/WojciechMula/sse-popcount/blob/master/popcnt-avx2-lookup.cpp

...