Какова эффективная реализация Conway Game of Life для использования с низким объемом памяти?

Question

Я ищу быстрый и эффективный способ памяти для реализации игры жизни Конвея.

Ограничения: плата 96x128, оперативная память около 2 КБ и процессор 52 МГц (см. Технические характеристики здесь: http://www.getinpulse.com/features).

Мое текущее простое решение, которое представляет каждую ячейку как один бит в матрице (96 * 128/8 = 1536 байт), работает, но слишком медленно. Какие приемы можно использовать для повышения производительности?

Хранение координат живых ячеек (например, в этой реализации http://dotat.at/prog/life/life.html) будет использовать слишком много памяти.

Answer 1

Выглядит как забавное железо. Сохранение 1 бита на пиксель дисплея 96x128 пикселей дает 12 288 бит. Это уже более половины из 16,384 битов, которые вы говорите, «доступны». Если вы не можете даже хранить 2 бита на ячейку, там не так много места.

Несколько идей:

• У вас 32-битный процессор. Существует несколько хитростей, позволяющих получить растровое изображение и рассчитать количество соседей нескольких ячеек параллельно на таком процессоре.

• Часто быстрее хранить число соседей, увеличивая все 8 соседей при рождении и уменьшая все 8 соседей при смерти, вместо того, чтобы пересчитывать количество соседей с нуля каждое поколение - но это не похоже на вас достаточно памяти для этого подхода.

• Возможно, вы могли бы использовать 2x2 пикселя на ячейку (чтобы было видно только 3072 ячейки) или 3x3 пикселя на ячейку (чтобы было видно только 1376 ячеек), поэтому ваше программное обеспечение выполняет меньше работы и, таким образом, создает иллюзию более быстрой работы. (Это также освобождает достаточно оперативной памяти, чтобы вы могли выполнить подсчет соседей, упомянутый выше).

• Поскольку многие шаблоны жизни имеют большие области мертвого пространства, возможно, имеется небольшая битовая карта «живых областей» - скажем, массив битов 12x16, где каждый бит равен «0», если соответствующая область ячейки 8x8 полностью мертв, и «1», если любая из клеток в соответствующей области жива. Обновлению следующего поколения нужно только посмотреть на живые регионы и границу мертвых регионов на одну ячейку; Вы можете пропустить проверку ядра 6x6 мертвых областей. Кроме того, вы можете полностью пропустить всю область ячейки 8x8, если ее 4 ближайших соседних региона также мертвы.

• Поскольку многие шаблоны жизни имеют большие области статических неизменяющихся шаблонов "натюрмортов", возможно, имеется небольшая битовая карта "динамических областей" - скажем, массив битов 12x16, где каждый бит равен "0", если соответствующая область ячеек 8x8 не имела изменений в обновлении последнего поколения, и «1», если какая-либо из ячеек в соответствующей области изменилась в последнем обновлении. Обновлению следующего поколения нужно только посмотреть на динамические области и границу статических областей на 1 ячейку; Вы можете пропустить проверку ядра ячейки 6x6 статических областей, так как оно будет таким же в следующем поколении.

• Если шаблон «достаточно большой», представление, основанное на Hashlife Gosper, может сохранить его в меньшем количестве оперативной памяти, чем непосредственное сохранение растрового изображения. Увы, я подозреваю, что вы намного ниже «достаточно большого» порога.

Answer 2

Посмотрите на главу об игре жизни в "Дзен оптимизации кода" Майкла Абраша.Была реализация, которая кодировала текущее и предыдущие состояния 3 ячеек в одно слово, и использовала трюки с таблицами поиска и битами переноса, чтобы генерировать следующие состояния.Это было невероятно быстро.

Answer 3

С маленькими жизненными вселенными довольно часто заставляют их оборачиваться со всех сторон (чтобы создать тороидальную вселенную), но это требует двойной буферизации. В вашем случае это требует 3 КБ ОЗУ, но у вас есть только 2 КБ.

Если вы не заключаете в оболочку, вам не нужно делать двойной буфер всей вселенной. Вам просто нужно избегать перезаписи ячеек, прежде чем вы закончите использовать их в качестве входных данных для вычисления.

Скажите, что ваша вселенная представлена ​​в виде обычного растрового изображения. Мы будем рассматривать это как последовательность строк, расположенных последовательно в памяти. Скажем, вселенная состоит из четырех строк, пронумерованных от 0 до 3.

  0
  1
  2
  3
  4
  ...

Когда вы вычисляете следующее поколение, новая версия строки 3 вычисляется с использованием строк 2, 3 и 4 (которая пуста). Вы можете написать новую версию строки 3 поверх строки 4. Аналогичным образом вычислите новую строку 2 из строк 1,2,3 и запишите ее поверх строки 3, так как эти данные больше не нужны после вычисления строки 2. Новая строка 1 вычисляется из строк 0,1,2 и записывается в строку 2.

Это означает, что вам нужна память только для одной дополнительной строки. 97 * 128 бит - это 1552 байта.

Недостаток в том, что ваша вселенная прокручивает память, и у вас должен быть какой-то механизм, чтобы справиться с этим. Либо скопируйте его обратно в исходное положение после каждого вычисления (что является медленным), либо сделайте так, чтобы его можно было отображать из любой позиции в памяти, и убедитесь, что ваши системы вычислений и отображения могут переходить с высоких на низкие адреса.

Answer 4

Я бы предложил начать с подпрограммы, чтобы прочитать строку доски и сгенерировать два новых буфера строки, H и L, так что бит 'n' из H будет установлен, если два или более из (bin n + 1, bitn, бит n-1) были установлены в исходной строке, а бит 'n' из L будет установлен, если в исходной строке было установлено нечетное число (bin n + 1, бит n, бит n-1).

Выделите всего три пары буферов строк (назовите их H0..H2 и L0..L2).Возьмите каждую строку исходного файла и вычислите пару буферов и сохраните их в паре HL, сохраняя ее и предыдущие два.Изучение слова из всех шести буферов покажет, какие из 32 ячеек в исходной матрице должны быть живы, если и только если они были ранее, а какие должны быть живы независимо от предыдущего состояния.

Для оптимальной производительности в машинном кодетри пары буферов могут чередоваться;это может позволить достичь скорости выполнения менее двух циклов на пиксель.Возможно, излишняя частота 52 МГц (всего 12288 пикселей, это будет частота кадров ~ 4000 кадров в секунду), но скорость крутая.

Answer 5

Придерживайтесь битового массива и пропускайте счетчики соседей с помощью этого трюка: создайте таблицу поиска с возможными битовыми комбинациями соседних блоков ячеек, которые создают или поддерживают живую ячейку.

Шаблон «index» может быть упакован в 8 битов, если вы хотите минимизировать объем памяти: 3 бита из строки выше, два бита из столбцов с каждой стороны и 3 бита из строки ниже. Вы можете закодировать вывод в виде единственного бита в справочной таблице, занимая всего 256 бит. Используйте индекс в качестве счетчика сдвигов битов для вашего поискового массива, чтобы «вычислить» результат. Сдвиги битов и операции арифметического ИЛИ все еще очень быстрые, и этот метод исключает подсчет соседних живых ячеек на лету - или, скорее, таблица поиска предварительно обрабатывает счет и вычисление.

Основными узкими местами при обработке должны быть: проверка состояния краев доски, то есть конец ряда; границы слова; извлечение и упаковка соседних битов в качестве значения индекса. Благодаря 32-разрядному процессору вы сможете очень быстро переключаться между 30 ячейками, прежде чем переходить к границе слова. Адресация строк ячеек может быть просто добавлением количества столбцов / 32, если вы упаковываете биты в целочисленные слова. Кэшируйте результаты в две резервные строки новой жизни и копируйте всю строку, когда закончите обрабатывать одну.

Могут быть некоторые симметрии шаблона, которыми вы можете воспользоваться, чтобы оптимизировать вещи еще больше, но этого может быть достаточно. Я думаю, что эта техника будет держать обработку и использование памяти в пределах ваших ограничений.

Answer 6

Если у вас есть лицензия на использование оставшихся 30 КБ на устройстве (например, флэш-память), вы всегда можете сохранить ее там, что не идеально, но это способ потенциально обойти ограниченную оперативную память.

Эффективность: вы будете обменивать производительность процессора и памяти друг на друга:

Для эффективности памяти, массив битов, вероятно, является оптимальным решением, но вы теряете эффективность процессора, перебирая эту сетку.

В зависимости от возможностей и размера адресов памяти вы можете использовать связанный список ячеек, чтобы избежать итерации по всей сетке: это определенно сэкономит ваше время на сканирование огромных областей мертвых ячеек.