Игру жизнь — клеточный автомат уже кажется писали на всех возможных языках программирования.
Меня же интересует технология ПЛИС — и поэтому когда-то я сделал реализацию life для ПЛИС Альтера Cyclone III. Правда поместилось в чип тогда очень мало: всего 32x16 клеток. На таком маленьком поле довольно трудно испытать сложные фигуры.
Сейчас у меня в руках другая плата: тут уже стоит Altera MAX10 с 50-ю тысячами логических элементов. Было интересно, смогу ли я расширить поле хотя бы в 4 раза? В общем задумал сделать хотя бы 64x32.
Результат представлен на этом видео, я называю эту картину: «ружье Госпера убивает самоё себя».
Ниже подробности реализации.
Собственно реализация игры у меня уже была в предыдущем моем проекте для третьего циклона. Весь проект как бы состоит из нескольких частей.
Поле игры жизнь составлено из взаимосвязанных модулей-ячеек написанных на Verilog HDL так, чтобы было возможным за 1 такт вычислить все следующее поколение клеток.
Хочется иметь именно такую реализацию, ведь это ПЛИС, значит там можно и нужно делать. Это модель множественных вычислителей, которые работают одновременно параллельно и передают параметры друг другу. Вот этот параллелизм как раз и поражают воображение: поле игры 64x32=2048 параллельных вычислителей работающих в FPGA синхронно! Модуль и вся логика одной ячейки написана на Verilog HDL:
module xcell(
input wire clk,
input wire seed_ena,
input wire life_step,
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(seed_ena)
cell_life <= in_left; //do load initial life into cell
else
if(life_step) //recalculate new generation of life
begin
if( neighbor_number == 3 )
cell_life <= 1'b1; //born
else
if( neighbor_number < 2 || neighbor_number > 3 )
cell_life <= 1'b0; //die
end
endmoduleПотом экземпляры этого модуля многократно создаются и соединяются между собой проводами в единое плоское поле с помощью конструкции generate-endgenerate языка Verilog HDL.
Второй по важности модуль в проекте — это модуль загрузки исходного состояния игры через последовательный порт. Состояние передается в виде текстового файла примерно вот такого вида:
1------**------------------------
2-----*--*-----------------------
3----*----*----------------------
4---*------*---------------------
5---*------*---------------------
6----*----*----------------------
7-----*--*-----------------------
8------**------------------------
9--------------------------------
A--------------------------------
B--------------------------------
C--------------------------------
D--------------------------------
E--------------------------------
F--------------------------------
Значащие символы только '*' (живая клетка) и '-' (нет жизни). Скорость передачи 115200, 8 бит, 1 стоп, без четности. Во время загрузки проекта нужно подержать кнопочку на плате — тогда поле жизни будет засеяно новым состоянием, описанным в текстовом файле.
Ну и последнее — модуль отображения текущего состояния игры. Это текстовый видеоадаптер, в который периодически переписывается состояние ячеек-клеток. Все клетки связаны в циклический сдвиговый регистр, так что можно за WIDTH*HEIGHT тактов прочитать все поле игры и сделать запись в видеоадаптер.
Ну конечно, это все вместе получается довольно мудрено — ведь сама логика игры «жизнь» простая, но обслуживающие модули, модули загрузки и отображения оказываются чуть ли не сложнее самой «жизни».
И вот еще про отображение на экране. Чтобы портировать старый проект на MAX10 и для абсолютно другой платы Марсоход3 придется немного повозиться. Дело в том, что на плате уже нет разъема VGA, с которым было так просто и приятно работать. Теперь на плате стоит HDMI разъем и линии HDMI идут прямо к чипу ПЛИС.
Чтобы управлять линиями HDMI прошлось поизучать довольно много материала. За основу был взят проект на www.fpga4fun.com/HDMI.html Здесь довольно подробно все рассказывается.
HDMI использует последовательную передачу через дифференциальную пару. Всего пар четыре. Три пары передают 8-ми битные цвета R, G, B плюс управляющие сигналы HSYNC и VSYNC. Из-за последовательной передачи для TMDS кодирования требуется рабочая частота в 10 раз выше частоты пикселов на экране. Если частота пикселов 74 МГц при разрешении 1280х720, то для кодирования сигнала уже требуется 740 МГц и это очень много. Ситуацию спасает то факт, что на выходах ПЛИС есть встроенные интерфейс DDIO, то есть сериализатор два-к-одному. Значит максимальная частота в проекте может быть снижена до 370 МГц.
Исходный код модуля HDMI приведен ниже.
module hdmi(
input wire pixclk, // 74MHz
input wire clk_TMDS2, // 370MHz
input wire hsync,
input wire vsync,
input wire active,
input wire [7:0]red,
input wire [7:0]green,
input wire [7:0]blue,
output wire TMDS_bh,
output wire TMDS_bl,
output wire TMDS_gh,
output wire TMDS_gl,
output wire TMDS_rh,
output wire TMDS_rl
);
wire [9:0] TMDS_red, TMDS_green, TMDS_blue;
TMDS_encoder encode_R(.clk(pixclk), .VD(red ), .CD(2'b00) , .VDE(active), .TMDS(TMDS_red));
TMDS_encoder encode_G(.clk(pixclk), .VD(green), .CD(2'b00) , .VDE(active), .TMDS(TMDS_green));
TMDS_encoder encode_B(.clk(pixclk), .VD(blue ), .CD({vsync,hsync}), .VDE(active), .TMDS(TMDS_blue));
reg [2:0] TMDS_mod5=0; // modulus 5 counter
reg [4:0] TMDS_shift_bh=0, TMDS_shift_bl=0;
reg [4:0] TMDS_shift_gh=0, TMDS_shift_gl=0;
reg [4:0] TMDS_shift_rh=0, TMDS_shift_rl=0;
wire [4:0] TMDS_blue_l = {TMDS_blue[9],TMDS_blue[7],TMDS_blue[5],TMDS_blue[3],TMDS_blue[1]};
wire [4:0] TMDS_blue_h = {TMDS_blue[8],TMDS_blue[6],TMDS_blue[4],TMDS_blue[2],TMDS_blue[0]};
wire [4:0] TMDS_green_l = {TMDS_green[9],TMDS_green[7],TMDS_green[5],TMDS_green[3],TMDS_green[1]};
wire [4:0] TMDS_green_h = {TMDS_green[8],TMDS_green[6],TMDS_green[4],TMDS_green[2],TMDS_green[0]};
wire [4:0] TMDS_red_l = {TMDS_red[9],TMDS_red[7],TMDS_red[5],TMDS_red[3],TMDS_red[1]};
wire [4:0] TMDS_red_h = {TMDS_red[8],TMDS_red[6],TMDS_red[4],TMDS_red[2],TMDS_red[0]};
always @(posedge clk_TMDS2)
begin
TMDS_shift_bh <= TMDS_mod5[2] ? TMDS_blue_h : TMDS_shift_bh [4:1];
TMDS_shift_bl <= TMDS_mod5[2] ? TMDS_blue_l : TMDS_shift_bl [4:1];
TMDS_shift_gh <= TMDS_mod5[2] ? TMDS_green_h : TMDS_shift_gh [4:1];
TMDS_shift_gl <= TMDS_mod5[2] ? TMDS_green_l : TMDS_shift_gl [4:1];
TMDS_shift_rh <= TMDS_mod5[2] ? TMDS_red_h : TMDS_shift_rh [4:1];
TMDS_shift_rl <= TMDS_mod5[2] ? TMDS_red_l : TMDS_shift_rl [4:1];
TMDS_mod5 <= (TMDS_mod5[2]) ? 3'd0 : TMDS_mod5+3'd1;
end
assign TMDS_bh = TMDS_shift_bh[0];
assign TMDS_bl = TMDS_shift_bl[0];
assign TMDS_gh = TMDS_shift_gh[0];
assign TMDS_gl = TMDS_shift_gl[0];
assign TMDS_rh = TMDS_shift_rh[0];
assign TMDS_rl = TMDS_shift_rl[0];
endmodule
module TMDS_encoder(
input clk,
input [7:0] VD, // video data (red, green or blue)
input [1:0] CD, // control data
input VDE, // video data enable, to choose between CD (when VDE=0) and VD (when VDE=1)
output reg [9:0] TMDS = 0
);
wire [3:0] Nb1s = VD[0] + VD[1] + VD[2] + VD[3] + VD[4] + VD[5] + VD[6] + VD[7];
wire XNOR = (Nb1s>4'd4) || (Nb1s==4'd4 && VD[0]==1'b0);
wire [8:0] q_m = {~XNOR, q_m[6:0] ^ VD[7:1] ^ {7{XNOR}}, VD[0]};
reg [3:0] balance_acc = 0;
wire [3:0] balance = q_m[0] + q_m[1] + q_m[2] + q_m[3] + q_m[4] + q_m[5] + q_m[6] + q_m[7] - 4'd4;
wire balance_sign_eq = (balance[3] == balance_acc[3]);
wire invert_q_m = (balance==0 || balance_acc==0) ? ~q_m[8] : balance_sign_eq;
wire [3:0] balance_acc_inc = balance - ({q_m[8] ^ ~balance_sign_eq} & ~(balance==0 || balance_acc==0));
wire [3:0] balance_acc_new = invert_q_m ? balance_acc-balance_acc_inc : balance_acc+balance_acc_inc;
wire [9:0] TMDS_data = {invert_q_m, q_m[8], q_m[7:0] ^ {8{invert_q_m}}};
wire [9:0] TMDS_code = CD[1] ? (CD[0] ? 10'b1010101011 : 10'b0101010100) : (CD[0] ? 10'b0010101011 : 10'b1101010100);
always @(posedge clk) TMDS <= VDE ? TMDS_data : TMDS_code;
always @(posedge clk) balance_acc <= VDE ? balance_acc_new : 4'h0;
endmodule
module ddio(
input wire d0,
input wire d1,
input wire clk,
output wire out
);
reg r_d0;
reg r_d1;
always @(posedge clk)
begin
r_d0 <= d0;
r_d1 <= d1;
end
assign out = clk ? r_d0 : r_d1;
endmodule
Весь проект для платы Марсоход3 можно взять на github: github.com/marsohod4you/FPGA_game_life
Отчет компилятора Altera Quartus Prime:
Flow Status Successful — Thu Apr 28 16:08:48 2016
Quartus Prime Version 15.1.0 Build 185 10/21/2015 SJ Lite Edition
Revision Name max10_50
Top-level Entity Name top
Family MAX 10
Device 10M50SAE144C8GES
Timing Models Preliminary
Total logic elements 29,432 / 49,760 ( 59 % )
Total combinational functions 28,948 / 49,760 ( 58 % )
Dedicated logic registers 2,238 / 49,760 ( 4 % )
Total registers 2254
Total pins 23 / 101 ( 23 % )
Total virtual pins 0
Total memory bits 147,456 / 1,677,312 ( 9 % )
Embedded Multiplier 9-bit elements 0 / 288 ( 0 % )
Total PLLs 1 / 1 ( 100 % )
UFM blocks 0 / 1 ( 0 % )
ADC blocks 0 / 1 ( 0 % )
Вероятно игра «жизнь» уже многим надоела. Однако, на мой взгляд тут есть над чем поразмыслить. Несмотря на свою простоту, в ней заложены интересные принципы взаимосвязанных вычислителей. Вероятно, похожие идеи могут быть использованы в специальных классах задач. Например, размещение компонентов на печатной плате — это сложная комбинаторная задача, которая должна учитывать множество факторов и в том числе длины связей между компонентами. Можно представить себе, что компоненты на печатной плате — это клетки, борющиеся за более удачное расположение на поле жизни под влиянием сил связей между компонентами. Думаю, что со временем такие задачи будут рассчитываться с помощью FPGA.
