ядро cuda для игры жизни Конвея

Я пытаюсь вычислить количество переходов, которые будут сделаны при запуске GOL Конвея для матрицы pxq для n итераций. Например, дана 1 итерация с начальным состоянием 1 мигалкой (как показано ниже). будет 5 переходов (2 рождения, 1 выживание, 2 смерти от малонаселенности). У меня это уже работает, но я хотел бы преобразовать эту логику для работы с использованием CUDA. Ниже я хочу портировать на CUDA.

Код alt text:

    static void gol() // call this iterations x's
    {
        int[] tempGrid = new int[rows * cols]; // grid holds init conditions
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                tempGrid[i * cols + j] = grid[i * cols + j];
            }
        }

        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                int numNeighbors = neighbors(i, j); // finds # of neighbors

                if (grid[i * cols + j] == 1 && numNeighbors > 3)
                {
                    tempGrid[i * cols + j] = 0;
                    overcrowding++;
                }
                else if (grid[i * cols + j] == 1 && numNeighbors < 2)
                {
                    tempGrid[i * cols + j] = 0;
                    underpopulation++;
                }
                else if (grid[i * cols + j] == 1 && numNeighbors > 1)
                {
                    tempGrid[i * cols + j] = 1;
                    survival++;
                }
                else if (grid[i * cols + j] == 0 && numNeighbors == 3)
                {
                    tempGrid[i * cols + j] = 1;
                    birth++;
                }
            }
        }

        grid = tempGrid;
    }

person dnbwise    schedule 14.12.2010    source источник
comment
В чем конкретно вам нужна помощь - идеи, как распараллеливать, хранить, собственно программирование CUDA и т. Д.?   -  person Rup    schedule 14.12.2010
comment
Извините, как мне подойти к параллелизму?   -  person dnbwise    schedule 14.12.2010


Ответы (2)


Ваше основное замедление будет связано с доступом к основной памяти. Поэтому я бы посоветовал вам выбрать большой размер блока резьбы в зависимости от имеющегося у вас оборудования. 256 (16x16) - хороший выбор для кросс-аппаратной совместимости. Каждый из этих блоков потоков будет вычислять результаты для немного меньшей секции платы - если вы использовали 16x16, они будут вычислять результаты для секции 14x14 платы, поскольку есть граница из одного элемента. (Причина использования блока 16x16 для вычисления фрагмента 14x14 вместо фрагмента 16x16 заключается в объединении операций чтения из памяти.)

Разделите доску на части (скажем) 14x14; это ваша сетка (организованная так, как вы считаете нужным, но, скорее всего, что-то вроде board_width / 14, board_height / 14.

Внутри ядра пусть каждый поток загружает свой элемент в общую память. Тогда syncthreads. Затем попросите средние элементы 14x14 вычислить новое значение (используя значения, хранящиеся в общей памяти) и записать его обратно в глобальную память. Использование общей памяти помогает минимизировать глобальные операции чтения и записи. Это также причина, по которой размер блока вашего потока должен быть как можно большим - края и углы являются «потраченными впустую» обращениями к глобальной памяти, поскольку значения, полученные оттуда, используются только 1 или 3 раза, а не 9 раз.

person Josh Bleecher Snyder    schedule 14.12.2010

Вот один из возможных вариантов:

  1. Каждый поток выполняет вычисление для 1 элемента сетки.
  2. Каждый поток сначала загружает один элемент из основной сетки в общую память.
  3. Нити на краю блока резьбы также должны загружать граничные элементы.
  4. Затем каждый поток может произвести вычисление выживаемости на основе содержимого общей памяти.
  5. Затем каждый поток записывает свой результат обратно в основную память.
person Edric    schedule 14.12.2010