Life Game in FPGA
The game of life - a cellular automaton already seems to have been written in all possible programming languages.
I’m interested in FPGA technology - and therefore, once I made a life implementation for FPGA Alter Cyclone III. The truth fit in the chip then very little: only 32x16 cells. In such a small field, it is quite difficult to experience complex figures.
Now I have another board in my hands: there is already an Altera MAX10 with 50,000 logic elements. It was interesting, can I expand the field at least 4 times? In general, I decided to make at least 64x32.
The result is presented in this video, I call this picture: "Gosper's gun kills itself."
Below are implementation details.
Actually, the implementation of the game I already had in my previous project for the third cyclone. The whole project, as it were, consists of several parts.
The life field of the game is made up of interconnected cell modules written in Verilog HDL so that it is possible to calculate the entire next generation of cells in 1 beat.
I would like to have just such an implementation, because this is FPGA, which means you can and should do it. This is a model of multiple calculators that work simultaneously in parallel and pass parameters to each other. This parallelism is just what astounds the imagination: the game field 64x32 = 2048 parallel computers working in FPGA synchronously! The module and all the logic of one cell is written in 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
endmoduleThen instances of this module are repeatedly created and interconnected by wires in a single flat field using the generate-endgenerate construction of the Verilog HDL language.
The second most important module in the project is the module for loading the initial state of the game through the serial port. The status is transmitted in the form of a text file of something like this:
1 ------ ** ------------------------
2 ----- * - * -----------------------
3 ---- * ---- * ------------ ----------
4 --- * ------ * ---------------------
5 --- * - ---- * ---------------------
6 ---- * ---- * ------------- ---------
7 ----- * - * -----------------------
8 ------ * * ------------------------
9 ------------------------ --------
A --------------------------------
B --------------------------------
C ---------------- ----------------
D --------------------------------
E --------------------------------
F ----------------- ---------------
Significant characters are only '*' (living cell) and '-' (no life). 115200 baud rate, 8 bits, 1 stop, no parity. While loading the project, you need to hold the button on the board - then the life field will be seeded with a new state described in the text file.
Well and the last - a module for displaying the current state of the game. This is a text video adapter into which the state of cell cells is periodically copied. All cells are connected in a cyclic shift register, so you can read the entire field of the game and write to the video adapter in WIDTH * HEIGHT measures.
Well, of course, this all together turns out quite tricky - because the logic of the “life” game itself is simple, but the service modules, loading and display modules are almost more complicated than the “life” itself.
And here's more about the display on the screen. To port an old project to MAX10 and for a completely different board, Mars rover3 will have to tinker a bit. The fact is that the board no longer has a VGA connector, which was so simple and pleasant to work with. Now there is an HDMI connector on the board and the HDMI lines go straight to the FPGA chip.
To manage the HDMI lines, a lot of material was studied. The project was taken as a basis at www.fpga4fun.com/HDMI.html Here everything is described in quite some detail.
HDMI uses serial transmission over a differential pair. Only four pairs. Three pairs transmit 8-bit R, G, B colors plus HSYNC and VSYNC control signals. Due to serial transmission, TMDS encoding requires an operating frequency 10 times higher than the pixel frequency on the screen. If the pixel frequency is 74 MHz with a resolution of 1280x720, then 740 MHz is already required for encoding the signal, and that is a lot. The situation is saved by the fact that the FPGA outputs have a built-in DDIO interface, that is, a two-to-one serializer. So the maximum frequency in the project can be reduced to 370 MHz.
The source code for the HDMI module is shown below.
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
The entire project for the Mars rover3 board can be taken on github: github.com/marsohod4you/FPGA_game_life
Altera Quartus Prime compiler report:
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%)
Probably the game "life" is already tired of many. However, in my opinion there is something to ponder. Despite its simplicity, it contains interesting principles of interconnected calculators. Probably similar ideas can be used in special classes of problems. For example, placing components on a circuit board is a complex combinatorial task that must take into account many factors, including the length of the connections between the components. One can imagine that the components on the printed circuit board are cells fighting for a better location on the field of life under the influence of the forces of bonds between the components. I think that over time, such tasks will be calculated using FPGA.