Какова эффективная реализация Conway Game of Life для использования с низким объемом памяти?
Я ищу быстрый и эффективный подход к памяти для реализации игры жизни Конвея.
Ограничения: плата 96x128, оперативная память около 2 КБ и процессор 52 МГц (см. Технические характеристики здесь: http://www.getinpulse.com/features).
Мое текущее наивное решение, которое представляет каждую ячейку как один бит в матрице (96*128/8=1536 байт), работает, но слишком медленно. Какие приемы можно использовать для повышения производительности?
Хранение координат живых ячеек (например, в этой реализации http://dotat.at/prog/life/life.html) будет занимать слишком много памяти.
6 ответов
Выглядит как забавная железка. Сохранение 1 бита на пиксель дисплея 96x128 пикселей дает 12 288 бит. Это уже более половины из 16384 битов, которые вы говорите, "доступны". Если вы не можете даже хранить 2 бита на ячейку, не так уж много места для этого.
Несколько идей:
У вас есть 32-битный процессор. Существует несколько хитростей, позволяющих получить растровое изображение и рассчитать число соседей нескольких ячеек параллельно на таком процессоре.
Часто быстрее хранить число соседей, увеличивая все 8 соседей при рождении и уменьшая все 8 соседей при смерти, вместо того, чтобы пересчитывать число соседей с нуля каждое поколение - но, похоже, у вас недостаточно памяти для этого подхода,
Возможно, вы могли бы использовать 2x2 пикселя на ячейку (чтобы было видно только 3072 ячейки) или 3x3 пикселя на ячейку (чтобы было видно только 1376 ячеек), чтобы ваше программное обеспечение работало меньше и создавало иллюзию более быстрой работы. (Это также освобождает достаточно оперативной памяти, чтобы вы могли выполнить подсчет соседей, упомянутый выше).
Поскольку многие шаблоны жизни имеют большие области мертвого пространства, возможно, имеют небольшую битовую карту "живых областей" - скажем, массив битов 12x16, где каждый бит равен "0", если соответствующая область ячейки 8x8 полностью мертва, и "1", если какая-либо из клеток в соответствующем регионе жива. Обновлению следующего поколения нужно только взглянуть на живые регионы и границы мертвых областей на одну ячейку; Вы можете пропустить проверку ядра 6x6 мертвых областей. Кроме того, вы можете полностью пропустить всю область ячейки 8x8, если ее 4 ближайших соседних региона также мертвы.
Поскольку многие шаблоны жизни имеют большие области статических неизменяемых шаблонов "натюрмортов", возможно, имеется небольшая битовая карта "динамических областей" - скажем, массив битов 12x16, где каждый бит равен "0", если соответствующая область ячейки 8x8 имела без изменений в последнем обновлении поколения, и "1", если любая из ячеек в соответствующей области изменилась в последнем обновлении. Обновлению следующего поколения нужно только посмотреть на динамические области и границу статических областей на 1 ячейку; Вы можете пропустить проверку ядра ячейки 6x6 статических областей, так как оно будет таким же в следующем поколении.
Если шаблон "достаточно большой", представление, основанное на Hashlife Gosper, может сохранить его в меньшем количестве ОЗУ, чем непосредственно для сохранения растрового изображения. Увы, я подозреваю, что вы намного ниже "достаточно большого" порога.
С маленькими жизненными вселенными довольно часто заставлять их оборачиваться со всех сторон (чтобы создать тороидальную вселенную), но это требует двойной буферизации. В вашем случае это требует 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 ячеек в одно слово, и использовала трюки с таблицами поиска и битами переноса, чтобы генерировать следующие состояния. Это было невероятно быстро.
Я бы предложил начать с подпрограммы, чтобы прочитать строку платы и сгенерировать два новых буфера строки, H и L, так что бит 'n' из H будет установлен, если два или более из (bin n+1, bit n, bit n-1) были установлены в исходной строке, и бит 'n' из L будет установлен, если в исходной строке было установлено нечетное число (bin n + 1, бит n, бит n-1).
Выделите всего три пары буферов строк (назовите их H0..H2 и L0..L2). Возьмите каждую строку исходного файла и вычислите пару буферов и сохраните их в паре HL, сохраняя ее и предыдущие два. Изучение слова из всех шести буферов покажет, какие из 32 ячеек в исходной матрице должны быть живы, если и только если они были ранее, а какие должны быть живы независимо от предыдущего состояния.
Для оптимальной производительности в машинном коде три пары буферов могут чередоваться; это может позволить достичь скорости выполнения менее двух циклов на пиксель. Возможно, излишняя частота 52 МГц (всего 12288 пикселей, частота кадров ~4000 кадров в секунду), но скорость крутая.
Если у вас есть лицензия на использование оставшихся 30 КБ на устройстве (она же флэш-память), вы всегда можете сохранить ее там, что не идеально, но это способ потенциально обойти ограниченную оперативную память.
Говоря об эффективности, вы будете обменивать производительность процессора и памяти друг на друга:
С точки зрения эффективности памяти, массив битов, вероятно, является оптимальным решением, но вы теряете эффективность процессора, перебирая эту сетку.
В зависимости от возможностей и размера адресов памяти вы можете использовать связанный список ячеек, чтобы избежать итерации по всей сетке: это определенно сэкономит ваше время на сканирование огромных областей мертвых ячеек.
Придерживайтесь битового массива и пропустите счет соседей с помощью этого трюка: создайте таблицу поиска с возможными битовыми комбинациями соседних блоков ячеек, которые создают или поддерживают живую ячейку.
Шаблон "index" может быть упакован в 8 битов, если вы хотите минимизировать объем памяти: 3 бита из строки выше, 2 бита из столбцов с каждой стороны и 3 бита из строки ниже. Вы можете закодировать вывод в виде единственного бита в справочной таблице, занимая всего 256 бит. Используйте индекс в качестве счетчика сдвигов битов для вашего поискового массива, чтобы "вычислить" результат. Сдвиги битов и операции арифметического ИЛИ все еще очень быстрые, и этот метод исключает подсчет соседних живых ячеек на лету - или, скорее, таблица поиска предварительно обрабатывает счет и вычисление.
Основными узкими местами при обработке должны быть: проверка состояния кромки платы, т. Е. Конца ряда; границы слова; извлечение и упаковка соседних битов в качестве значения индекса. С 32-битным процессором вы сможете очень быстро перебирать 30 ячеек, прежде чем переходить к границе слова. Адресация строк ячеек может быть просто вопросом добавления количества столбцов /32, если вы упаковываете биты в целочисленные слова. Кэшируйте результаты в две резервные строки новой жизни и копируйте всю строку, когда закончите обрабатывать одну.
Могут быть некоторые симметрии шаблона, которыми вы можете воспользоваться, чтобы оптимизировать вещи еще больше, но этого может быть достаточно. Я думаю, что эта техника будет держать обработку и использование памяти в пределах ваших ограничений.