МАРСОХОД

Open Source Hardware Project

Проекты Altera Quartus II для платы Марсоход2

Игра Жизнь внутри ПЛИС

bacteria

Пришло мне в голову реализовать игру «жизнь» в ПЛИС в плате Марсоход2.
Не знаю, стоит ли объяснять правила этой игры — они, кажется, общеизвестны. Очень хорошее описание есть в википедии.

Ну, ладно, вкратце повторюсь:

  • есть прямоугольная решетка, в каждой ячейке решетки может жить «микроорганизм», клетка. Есть два состояния клетки решетки — «живая» или «не живая»;
  • каждая клетка имеет восемь возможных соседей. Даже на краях решетки у клеток есть 8  соседей. Решетка рассматривается как «бесконечная плоскость»: нижний край соединен без шва с верхним, а правый край с левым. Такая поверхность называется «тор». По тору-бублику можно ходить бесконечно, в любом направлении, не встречая препятствия;
  • если живых соседей меньше двух, то клетка умирает от одиночества;
  • если живых соседей больше трех, то клетка умирает от перенаселения;
  • если у клетки живых соседей ровно три, то в клетке зарождается новая жизнь;
  • если у клетки два живых соседа — ее жизнь продолжается;
  • в начале игры пространство как-то заполняется живыми клетками — на каждом шаге в каждой клетке происходит таинство жизни — где-то кто-то рождается, а где-то кто-то и умирает. Ну а зритель просто наблюдает за эти процессом.

Эта модель жизни получила название «клеточный автомат».
Программных реализаций для клеточного автомата существует огромное множество. Игру «жизнь» наверное уже написали на всех возможных языках программирования: C/C++, Javascript, Python, Pascal..

Я решил написать клеточный автомат игры «жизнь» для ПЛИС на Verilog HDL.
Меня заинтересовала эта игра тем, что в некотором роде на этой модели я могу попытаться реализовать эдакий «суперпроцессор». Это как раз задача для ПЛИС.

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

Вот так:

клетка в игре жизнь для FPGA

Если я смогу описать на 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):

qii xcell в Altera Quartus II

Потом этот графический компонент-клетку можно много раз поставить на схему и посоединять их все между собой:

qii xcells клеточный автомат в схеме Altera Quartus II для ПЛИС

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

Вот казалось бы и все — весь проект готов? Модуль одной клетки написали. Клетки расположили по поверхности тора. Что дальше? Осталось два очень важных вопроса:

  1. как засеивать поверхность первым поколением клеток?
  2. как я буду наблюдать за изменением состояния клеток?

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

Я решил, что загружать первоначальное состояние клеток проще всего через последовательный порт. Нужен модуль последовательного порта и какой-то анализатор приходящих байтов. Предположим, описывать первое поколение жизни я буду в простом текстовом редакторе, 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 пришлось сделать еще одну дополнительную последовательную связь всех клеток в один длинный последовательный регистр:

seed load

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

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

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

Получается, что я должен своей модели жизни сперва сказать «посчитай новое поколение клеток», а потом я должен считать состояние всех клеток и вписать их в память текстового экрана...

Понятно, что считывать из массива клеток проще всего опять же, как из сдвигового регистра.

cell read

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

Еще одна фишка. На плате Марсоход2 есть две кнопочки я задействовал их обе.
Одна служит для загрузки исходного поколения клеток. Нажимаю ее и тогда через последовательный порт пересылаю текстовый файл с описанием «первожизни».
Вторая кнопочка, если нажата, то запрещает вычисление следующих поколений. Удобнее пользоваться так:

  • нажимаю обе кнопки сразу;
  • через последовательный порт посылаю файл с описанием первого поколения (я использую терминал TeraTerm);
  • потом бросаю первую кнопку и вижу, что файл загрузился правильно. Пока ничего не происходит;
  • потом бросаю вторую кнопочку платы Марсоход2 — и жизнь пошла. Новые поколения вычисляются и отображаются на мониторе.

Кто захочет разобраться в тонкостях реализации должен скачать весь проект для среды Altera Quartus II вот здесь:

Игра Жизнь ( 92388 bytes )

Топ модуль проекта выглядит вот так (можно кликнуть, чтобы увидеть подробнее):

top

Ну и конечно — видео демонстрация.

Здесь продемонстрированы традиционные фигуры для игры «жизнь» - это планер/glider и octagon. Но, конечно, можно загрузить и любые другие начальные значения для поля жизни.

 

Комментарии  

0 #7 Алексей 30.10.2014 12:59
Спасибо.
0 #6 nckm 30.10.2014 12:57
Цитирую Алексей:
Ниолай. как с Вами можно связаться, есть предложение.
detkov_av@mail.ru Алексей

можно написать на info@marsohod.org
0 #5 Алексей 30.10.2014 12:41
Ниолай. как с Вами можно связаться, есть предложение.
detkov_av@mail.ru Алексей
+1 #4 nckm 21.09.2014 09:41
Цитирую jiv4ik:
Мне кажется в модуле hvsync
в строчке vsync = (vert_addr_time+vert_back_porch) && line_count < (vert_addr_time+vert_back_porch+vert_sync) );
вместо vert_back_porch должен быть vert_front_porch
как при присвоении hsync
Если я не прав, напишите почему)

ой.. мне тоже сейчас кажется, что там должно быть vert_front_porc h..
0 #3 jiv4ik 19.09.2014 11:45
Мне кажется в модуле hvsync
в строчке vsync = (vert_addr_time +vert_back_porc h) && line_count < (vert_addr_time +vert_back_porc h+vert_sync) );
вместо vert_back_porch должен быть vert_front_porch
как при присвоении hsync
Если я не прав, напишите почему)
0 #2 WolfTheGrey 07.09.2014 01:43
Нечто подобное видел написанное на языке C#. Только там был добавлен алгоритм Волк, Овца, Трава. Если применить матрицу RGB светодиодов, то еще есть над чем трудиться.
0 #1 Dronchic 05.09.2014 09:57
Здорово! "Жизни" меня учил один знакомый профессор математики, я тогда был классе в шестом наверное, произвела довольно сильное впечатление.
А я в своё время аппаратно реализовывал (правда только в симуляции) решение загадки про заключенных и лампочку (allriddles.ru/ru/riddles/logical/p2/18/). При чем эта реализация мне пришла во сне, как Дмитрию Ивановичу Менделееву его периодическая таблица :)

Добавить комментарий


Защитный код
Обновить


GitHub YouTube Twitter
Вы здесь: Начало Проекты Проект Марсоход2 Игра Жизнь внутри ПЛИС