Оригинал 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