Пришло мне в голову реализовать игру «жизнь» в ПЛИС в плате Марсоход2.
Не знаю, стоит ли объяснять правила этой игры — они, кажется, общеизвестны. Очень хорошее описание есть в википедии.
Ну, ладно, вкратце повторюсь:
- есть прямоугольная решетка, в каждой ячейке решетки может жить «микроорганизм», клетка. Есть два состояния клетки решетки — «живая» или «не живая»;
- каждая клетка имеет восемь возможных соседей. Даже на краях решетки у клеток есть 8 соседей. Решетка рассматривается как «бесконечная плоскость»: нижний край соединен без шва с верхним, а правый край с левым. Такая поверхность называется «тор». По тору-бублику можно ходить бесконечно, в любом направлении, не встречая препятствия;
- если живых соседей меньше двух, то клетка умирает от одиночества;
- если живых соседей больше трех, то клетка умирает от перенаселения;
- если у клетки живых соседей ровно три, то в клетке зарождается новая жизнь;
- если у клетки два живых соседа — ее жизнь продолжается;
- в начале игры пространство как-то заполняется живыми клетками — на каждом шаге в каждой клетке происходит таинство жизни — где-то кто-то рождается, а где-то кто-то и умирает. Ну а зритель просто наблюдает за эти процессом.
Эта модель жизни получила название «клеточный автомат».
Программных реализаций для клеточного автомата существует огромное множество. Игру «жизнь» наверное уже написали на всех возможных языках программирования: C/C++, Javascript, Python, Pascal..
Я решил написать клеточный автомат игры «жизнь» для ПЛИС на Verilog HDL.
Меня заинтересовала эта игра тем, что в некотором роде на этой модели я могу попытаться реализовать эдакий «суперпроцессор». Это как раз задача для ПЛИС.
И действительно, предположим, что каждая клетка представляет собой отдельный вычислитель, отдельный, пусть простой, но процессор. Состояние клетки, живая она или нет, хранится в процессоре в одном единственном регистре-триггере. Вычисление следующего состояния выполняет логическая функция связанная с соседними восемью клетками.
Вот так:
Если я смогу описать на Verilog поведение одной клетки в виде одного модуля, то потом я наверное смогу установить их в схему, скажем 32х16=512 штук. Получится довольно большая сеть из множества одинаковых вычислителей.
Важно, что все вычислители должны работать одновременно и синхронно. Все ячейки переходят в следующее новое состояние одновременно. Это обеспечивается тем, что регистры в клетках должны питаться одной тактовой частотой.
Ну вот, попробуем описать одну клетку на языке Verilog:
module xcell(
input wire clk,
input wire in_up_left,
input wire in_up,
input wire in_up_right,
input wire in_left,
input wire in_right,
input wire in_down_left,
input wire in_down,
input wire in_down_right,
output reg cell_life
);
wire [3:0]neighbor_number;
assign neighbor_number =
in_up_left +
in_up +
in_up_right +
in_left +
in_right +
in_down_left +
in_down +
in_down_right;
always @(posedge clk)
if( neighbor_number == 3 )
cell_life <= 1'b1; //born
else
if( neighbor_number < 2 || neighbor_number > 3 )
cell_life <= 1'b0; //die
endmodule
Тут все просто: есть восемь входов, куда подключены сигналы от «соседей»: in_up_left, in_up, in_up_right, in_left, in_right, in_down_left, in_down, in_down_right. Сигнал neighbor_number — это сумма соседей, то есть число живых соседей. Есть один выход из регистра cell_life, отображающий текущее состояние клетки (живая «1» или не живая «0»). Еще есть вход тактирования clk, по фронту этой тактовой частоты клетка переходит в новое состояние в зависимости от числа соседей вокруг.
В принципе, в среде Altera Quartus II можно из текста Verilog модуля сделать графический компонент (меню File => Create / Update => Create Symbol Files for Current File):
Потом этот графический компонент-клетку можно много раз поставить на схему и посоединять их все между собой:
Вот возможный фрагмент схемы. Пока рисовал аж утомился. Может где-то и ошибся даже..
Представляете себе такой титанический труд если ставить 512 или 1024 или 4096 компонентов и в графическом виде соединять их? Это кажется невозможным. Ну я так дальше делать и не буду.
Я буду использовать специальную возможность языка описания аппаратуры Verilog HDL. В Verilog можно генерировать экземпляры модуля прямо во время компиляции. Для этого используется конструкция generate / endgenerate и переменные типа genvar для перечисления экземпляров модулей. Смотрите как это работает:
module torus(
input wire clk,
output wire [TORUS_WIDTH*TORUS_HEIGHT-1:0]torusv,
);
parameter TORUS_WIDTH = 32;
parameter TORUS_HEIGHT = 16;
localparam WMASK = (TORUS_WIDTH-1);
localparam HMASK = (TORUS_HEIGHT-1);
genvar x;
genvar y;
generate
for(y=0; y<TORUS_HEIGHT; y=y+1)
begin: crow
for(x=0; x<TORUS_WIDTH; x=x+1)
begin: ccol
wire value;
xcell my_xcell(
.clk( clk ),
.in_up_left( crow[ (y-1)&HMASK ].ccol[ (x-1)&WMASK ].value ),
.in_up( crow[ (y-1)&HMASK ].ccol[ (x-0)&WMASK ].value ),
.in_up_right( crow[ (y-1)&HMASK ].ccol[ (x+1)&WMASK ].value ),
.in_left( crow[ (y-0)&HMASK ].ccol[ (x-1)&WMASK ].value ),
.in_right( crow[ (y-0)&HMASK ].ccol[ (x+1)&WMASK ].value ),
.in_down_left( crow[ (y+1)&HMASK ].ccol[ (x-1)&WMASK ].value ),
.in_down( crow[ (y+1)&HMASK ].ccol[ (x-0)&WMASK ].value ),
.in_down_right(crow[ (y+1)&HMASK ].ccol[ (x+1)&WMASK ].value ),
.cell_life( value )
);
assign torusv[y*TORUS_WIDTH+x] = crow[ y ].ccol[ x ].value;
end
end
endgenerate
endmodule
В моем проекте я буду использовать пространство для жизни в виде таблицы размером 32х16:
parameter TORUS_WIDTH = 32;
parameter TORUS_HEIGHT = 16;
Поскольку каждая клетка располагается в узлах прямоугольной решетки, то для описания координат каждой клетки мне понадобятся две простые переменные, целочисленные genvar x и genvar y.
Дальше внутри конструкции generate / endgenerate описываю два цикла «for», один цикл по координате x вложен в цикл по координате y.
Доступ ко всем объектам, созданным внутри цикла
for(y=0; y<TORUS_HEIGHT; y=y+1)
begin: crow
…..
end
может быть осуществлен через имя блока и индекс сгенерированного блока crow[index]. Я сам даю имя блоку, у меня это — crow, то есть строка (row) клеток (cell).
Примерно так же и для цикла по горизонтали: там создаются блоки ccol и доступ к экземпляру блока дается по индексу колонки:
for(x=0; x<TORUS_WIDTH; x=x+1)
begin: ccol
…..
end
Теперь посмотрим внимательно. Внутри циклов объявлен провод wire value и еще объявлена установка в проект экземпляра модуля xcell my_xcell(...). На самом деле теперь эти оба объявления происходят в момент компиляции многократно, TORUS_HEIGHT * TORUS_WIDTH раз. Обратиться к конкретному экземпляру можно по его индексу, например, crow[5].ccol[11].value – берет сигнал от клетки в координатах [11,5] – сигнал cell_file от клетки подключен к этому конкретному экземпляру провода value.
Теперь понятно, что объявление типа
xcell my_xcell(
.clk( clk ),
.in_up_left( crow[ (y-1)&HMASK ].ccol[ (x-1)&WMASK ].value ),
.in_up( crow[ (y-1)&HMASK ].ccol[ (x-0)&WMASK ].value ),
.in_up_right( crow[ (y-1)&HMASK ].ccol[ (x+1)&WMASK ].value ),
.in_left( crow[ (y-0)&HMASK ].ccol[ (x-1)&WMASK ].value ),
.in_right( crow[ (y-0)&HMASK ].ccol[ (x+1)&WMASK ].value ),
.in_down_left( crow[ (y+1)&HMASK ].ccol[ (x-1)&WMASK ].value ),
.in_down( crow[ (y+1)&HMASK ].ccol[ (x-0)&WMASK ].value ),
.in_down_right(crow[ (y+1)&HMASK ].ccol[ (x+1)&WMASK ].value ),
.cell_life( value )
будет обозначать соединение текущего экземпляра клетки с соседями?.
Есть еще ньюанс — индексы по которым идет обращение к клеткам приходится побитно маскировать с масками HMASK=0x1F и WMASK=0x0F. Это как раз для бесшовного соединения низа таблицы с верхом и левой стороны таблицы с правой. То есть у клетки в строке 0 сосед сверху будет иметь индекс 0xF. Это потому, что 0-1=-1, что в шестнадцатеричном виде 0xFFFFFFFF для 32-х битного числа. После маски 0xFFFFFFFF&0x0F=0x0F – это в десятичном виде 15. У клетки в строке 15 сосед снизу находится в строке 0 (ведь (0x0F+1)&0x0F=0x10&0x0F=0x00). Все точно так же и для горизонтальной оси.
Вот казалось бы и все — весь проект готов? Модуль одной клетки написали. Клетки расположили по поверхности тора. Что дальше? Осталось два очень важных вопроса:
- как засеивать поверхность первым поколением клеток?
- как я буду наблюдать за изменением состояния клеток?
Самое интересное, что решить эти два вопроса оказалось гораздо сложнее, чем собственно написать ядро игры.
Я решил, что загружать первоначальное состояние клеток проще всего через последовательный порт. Нужен модуль последовательного порта и какой-то анализатор приходящих байтов. Предположим, описывать первое поколение жизни я буду в простом текстовом редакторе, notepad. Файл может выглядеть как-то так:
0--------------------------------
1--------------------------------
2--------------------------------
3--------------------------------
4----******----------------------
5-----********-*-----------------
6---------------*----------------
7-------------***----------------
8--------------------------------
9--------------------------------
A-------------*******------------
B------------***--***------------
C--------------*****-------------
D---------------********---------
E--------**********--------------
F--------------------------------
Я буду в плату прямо этот текстовый файл посылать. Имеют значение только байты 0x2A – это звездочка, обозначающая живую клетку и байт 0x2D – это символ «минус», обозначающий мертвую клетку. Остальные байты из потока будут игнорироваться. Полезных символов в файле должно быть 32*16=512 штук.
Для того, чтобы сделать загрузку потока в массив клеток пришлось в каждой клетке сделать еще дополнительный сигнал seed_ena. Если этот сигнал активен, то по фронту тактовой частоты я буду загружать в регистр cell_life не обычное вычисленное значение следующего состояния клетки, а просто сигнал in_left от клетки слева.
В модуле torus пришлось сделать еще одну дополнительную последовательную связь всех клеток в один длинный последовательный регистр:
То есть в режиме загрузки, в режиме засеивания клеток жизнью, все клетки получаются соединенными не в сеть, как в обычной жизни, а в последовательный регистр.
По поводу отображения состояния жизни я решил, что нагляднее всего будет подключить к плате Марсоход2 (я ведь на ней все пробую) монитор и показывать на нем всю таблицу с ячейками.
Когда-то я делал текстовый терминал, вот оттуда взял готовый модуль txtd. Тут проблема в том, что мой текстовый экран представляет собой как бы память. В эту память нужно писать символы, чтобы они появились на экране.
Получается, что я должен своей модели жизни сперва сказать «посчитай новое поколение клеток», а потом я должен считать состояние всех клеток и вписать их в память текстового экрана...
Понятно, что считывать из массива клеток проще всего опять же, как из сдвигового регистра.
Примерно так же как я загружаю первое поколение, только теперь я еще должен регистр закольцевать. Это сделано для того, чтобы после считывания 512 значений клеток все они вернулись обратно на свои места. Получилось конечно довольно мудрено, но как иначе?
Еще одна фишка. На плате Марсоход2 есть две кнопочки я задействовал их обе.
Одна служит для загрузки исходного поколения клеток. Нажимаю ее и тогда через последовательный порт пересылаю текстовый файл с описанием «первожизни».
Вторая кнопочка, если нажата, то запрещает вычисление следующих поколений. Удобнее пользоваться так:
- нажимаю обе кнопки сразу;
- через последовательный порт посылаю файл с описанием первого поколения (я использую терминал TeraTerm);
- потом бросаю первую кнопку и вижу, что файл загрузился правильно. Пока ничего не происходит;
- потом бросаю вторую кнопочку платы Марсоход2 — и жизнь пошла. Новые поколения вычисляются и отображаются на мониторе.
Кто захочет разобраться в тонкостях реализации должен скачать весь проект для среды Altera Quartus II вот здесь:
Топ модуль проекта выглядит вот так (можно кликнуть, чтобы увидеть подробнее):
Ну и конечно — видео демонстрация.
Здесь продемонстрированы традиционные фигуры для игры «жизнь» - это планер/glider и octagon. Но, конечно, можно загрузить и любые другие начальные значения для поля жизни.
Подробнее...