Сотовый автомат
Сотовый автомат можно рассматривать как массив битов плюс таблицу вычислений, которая требует, чтобы биты постоянно обновлялись как функция от их соседей.Например,
111 -> 0
110 -> 0
101 -> 0
100 -> 1
011 -> 1
010 -> 1
001 -> 1
000 -> 0
Эта таблица требует, чтобы всякий раз, когда массив содержал последовательность 110, средний бит должен был переворачиваться.Это повторяется снова и снова в глобальном масштабе, заставляя массив развиваться интересными способами.Такое вычисление может быть эффективно выполнено на графических процессорах, поскольку можно легко предварительно загружать фрагменты в общую память потокового мультипроцессора.
Сотовый автомат со вставками и удалениями
Теперь предположим, что у нас есть другой вид автоматов, где размер массива может динамически изменяться.изменить, и по каким определенным правилам вводится новый бит.Например:
111 -> 0
110 -> 00
101 ->
100 -> 1
011 -> 00
010 ->
001 -> 1
000 -> 0
Это похоже на предыдущее вычисление, за исключением того, что теперь, когда в массиве есть последовательность 110, должен переключаться не только средний бит, но и новый бит,0, должен быть вставлен прямо рядом с ним.Более того, когда у нас есть последовательность 101, средний бит должен быть удален.
Очевидно, что реализация этой новой задачи с использованием той же структуры данных, массива, была бы запретительной, поскольку вставка бита в середину массива требует сдвига всех задних элементов на 1 индекс вправо, что было бы чрезвычайно дорого.
Вопрос
Существует ли какая-нибудь умная структура данных или общий подход, позволяющий эффективно выполнять эти вычисления на графическом процессоре?