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

Ответ 1

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

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

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

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

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

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

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

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

Ответ 2

Очень часто с малыми живыми вселенными они обматывают их со всех сторон (чтобы сделать тороидальную вселенную), но для этого требуется двойная буферизация. В вашем случае это требует 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 байта.

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

Ответ 3

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

Ответ 4

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

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

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

Ответ 5

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

Эффективность, говорящая о том, что вы будете торговать процессором и памятью друг с другом:

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

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

Ответ 6

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

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

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

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