Оригинал https://blog.devel.faith/posts/cellular-automata-on-gpu-julia/

В этом посте мы узнаем об основах программирования GPU и Джулии, кодируя игру Conway’s Game of Life. Вы можете попробовать поискать «Игра жизни Конвея» в Google ;).

Что такое жизнь? Версия Tl;dr

Для каждой итерации

  • Недостаточное население: любая ячейка с менее чем двумя соседями умирает
  • Перенаселение: любая клетка с более чем 3 соседями умирает
  • Размножение: любая клетка с точно 3 соседями становится живой

Выполнение

Базовый

Написание кода для этих правил довольно тривиально. Для каждой ячейки проверьте ее соседей, а затем сделайте что-нибудь. Однако в этом уроке мы хотим перенести всю логику на GPU. Многие операции с матрицами можно эффективно выполнять параллельно в графическом процессоре. Таким образом, вместо того, чтобы писать простую симуляцию на низкоуровневом CUDA или OpenCL, мы можем просто использовать код более высокого уровня, думая с точки зрения линейной алгебры.

свертка

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

Как это делает нашу симуляцию быстрее?

Эта операция доступна для использования в большинстве библиотек линейной алгебры. Нам просто нужно найти библиотеку графического процессора, поддерживающую 2D-свертку, и ядро, вычисляющее количество соседей вокруг ячейки.

Если вы не знаете

Полиномиальное умножение в старших классах требует около n² операций (для каждого члена умножить на все члены другого полинома). Можем ли мы сделать это лучше? На самом деле вам просто нужно около n log n операций с fft. Недавно проведенное исследование показало, что мы можем выполнять целочисленное умножение и за O(n log n). Вкратце: свертка, скорее всего, будет быстрее, чем обычные циклы for.

Код

using ArrayFire
using LinearAlgebra
let
    kernel = convert(Array{Float32}, [1 1 1; 1 0 1; 1 1 1]) |> AFArray
    state = rand(Bool, 30, 30) .+ Float32(.0) |> AFArray
    step = 30
    for i = 1:step
        nb = convolve2(state, kernel, UInt32(0), UInt32(0))
        a = (nb == 2)
        b = (nb == 3)
        state = ((state .* a .+ b) > 0) + Float32(0)
        save_image(string(i, ".tiff"), state)
    end
end

На гифку: convert -scale 2000% -delay 20 -loop 0 *.tiff image.gif