Игру жизнь — клеточный автомат уже кажется писали на всех возможных языках программирования.

Меня же интересует технология ПЛИС — и поэтому когда-то я сделал реализацию 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.