Оптимизация Conway's Game of Life для Z80
Если вдруг кто не знает что это такое, можно почитать к примеру здесь.
На ютубе попались такие ролики:
John Conway's Game of Life on the Amstrad CPC -- fastest code in the West!
Game of Life CPC - latest speed-ups, now almost 3 generations per second
В описании к первому говорится что 13860 ячеек обрабатываются 2.3 раза в секунду, а в описании ко второму сказано что время обработки удалось уменьшить до 350 мс, если размер поля тот же, то получается 39600 ячеек в секунду. Если википедия не обманывает и частота Z80 там действительно 4МГц, то получается 101 такт на ячейку.
В общем была предпринята попытка всё это ускорить. Ускорение было сделано через таблицы, но поскольку таблиц потребовалось на 42К, то в оперативную память программа уже не влезла и заняла место в ПЗУ. Результаты получились следующие: поле 190x240=45600 ячеек пересчитывается за 414 мс, что даёт 110114 ячеек в секунду и при частоте 3.5 МГц получается 32 такта на ячейку. Работает программа следующим образом:
1) крайние байты из вычисляемой области 190x240 дублируются в крайние байты экрана которые будут читаться при вычислениях, чтобы замкнуть поле в тор.
2) читаются первые две строки в буфер
далее в цикле
3) читается по 2 строки в буфер
4) вычисляется и записывается по 2 строки
Строка читается блоками по 3 байта, которые разбиваются на 4 группы по 6 бит. К каждой группе добавляется еще по одному биту справа и слева и полученные 4 байта записываются в буфер. То есть в каждом байте содержится информация необходимая для вычисления 6 бит и хитрить с пересечением границ байтов дальше не нужно. В буфере блоки от 4х строк чередуются, то есть прочитав 4 байта мы можем вычислить по 6 ячеек в двух строках. Когда мы вычислим по 24 ячейки в каждой из 2x строк и сможем записать 2x3 байта на экран. После записи двух строк, буфер наполовину обновляется чтением очередных двух строк с экрана которые вместе со второй половиной буфера нужны будут для записи следующих двух строк.
Для вычислений двух ячеек используется три таблицы: при помощи первой мы загоняем 4 бита из байта над нашей строкой в H, в L загоняем байт под нашей строкой, после чего для двух ячеек из таблицы вытаскивается сколько у каждой из них соседей (число от 0 до 4 поскольку 5 или 6 дают такой же результат как и 4 - ячейка гибнет) в строке выше и ниже и в H загружается S2*5+S1, а в L байт из вычисляемой строки, после чего мы можем вытащить из таблицы новое состояние для двух ячеек. Поскольку в байте 8 ячеек, то чтобы вычислить их все нужен комплект из 4x3 таблиц.
Вопрос в общем в том, как бы уменьшить количество таблиц не потеряв эффективности? Пока только пришла мысль как можно выиграть (4*4+3)*256 байт за счёт слияния одинаковых строк в таблицах. Правда это не даёт достаточного места для кода и развернутые циклы придётся чуть завернуть обратно.
В общем если кому интересно, программка для EmuZWin прилагается, комментарии весьма условные, компилируется она достаточно долго, если лень ждать можно загрузить life.ezx. После компиляции PC нужно установить на 0, сброс программа пережить не может, поскольку таблицы в памяти не вычисляет, а использует те, что получаются при компиляции.
Первое из выводимых чисел это за сколько миллисекунд вычисляется одно поколение.
Второе это номер поколения.
Третье это количество кадров (использовалось для ловли потерянных прерываний).
life.zip
Ответить с цитированием
Размещение рекламы на форуме способствует его дальнейшему развитию 
Сообщение от blackmirror
