Game "Life" in FPGA

The game of life - the cellular automaton already seems written in all possible programming languages.

I am interested in the FPGA technology - and therefore once I made the implementation of life for the Alter FPGA Cyclone III. The truth is then very small: only 32x16 cells. On such a small field it is quite difficult to experience complex shapes.
')
Now I have another board in my hands: Altera MAX10 is already there with 50 thousand logical 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: "the Gosper's gun kills itself."

Below are the implementation details.
Actually, the implementation of the game I already had in my previous project for the third cyclone. The whole project consists of several parts.

The field of life is made up of interconnected modules-cells written in Verilog HDL so that it is possible to calculate the next generation of cells in 1 clock cycle.

I would like to have just such an implementation, because it is a FPGA, which means there can and should be done. This is a model of multiple calculators that operate simultaneously in parallel and pass parameters to each other. This parallelism is just amazing. The game field is 64x32 = 2048 parallel computers working in FPGA synchronously! The module and all the logic of a single 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 endmodule 

Then, instances of this module are repeatedly created and interconnected by wires into 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 loading the initial state of the game through the serial port. The state is transmitted as a text file of approximately the following form:

one------**------------------------
2 ----- * - * -----------------------
3 ---- * ---- * ----------------------
four---*------*---------------------
five---*------*---------------------
6 ---- * ---- * ----------------------
7 ----- * - * -----------------------
eight------**------------------------
9--------------------------------
A --------------------------------
B --------------------------------
C --------------------------------
D --------------------------------
E --------------------------------
F --------------------------------

Meaningful characters are only '*' (living cell) and '-' (no life). The transfer rate is 115200, 8 bits, 1 stop, no parity. During the loading of the project, you need to hold the button on the board - then the field of life will be sown with the new state described in the text file.

And finally, the module displays the current state of the game. This is a text video adapter, in which the state of cells-cells is periodically copied. All cells are connected in a cyclic shift register, so you can read the entire game field and make an entry in the video adapter for WIDTH * HEIGHT cycles.

Well, of course, this all together turns out to be quite surprising - after all, the very logic of the game “life” is simple, but the serving modules, loading and display modules turn out to be almost more complicated than the “life” itself.

And now about the display on the screen. To port the old project to MAX10 and for a completely different motherboard Mars Rover3 will have to tinker a bit. The fact is that the board no longer has a VGA connector, which was so easy and pleasant to work with. Now the board has an HDMI connector and the HDMI lines go straight to the FPGA chip.

To manage the HDMI lines, I went through a lot of material. The project on www.fpga4fun.com/HDMI.html was taken as a basis. Everything is described in some detail here.

HDMI uses serial transmission over a differential pair. Just four pairs. Three pairs transmit 8-bit R, G, B colors plus HSYNC and VSYNC control signals. Because of the serial transmission, TMDS coding requires a working 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 signal encoding, which is a lot. The situation is saved by the fact that the FPGA outputs have built-in DDIO interface, that is, a two-to-one serializer. This means that 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 whole project for the Mars Rover3 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 think about. Despite its simplicity, it contains interesting principles of interconnected calculators. Probably, similar ideas can be used in special classes of tasks. For example, placing components on a printed circuit board is a complex combinatorial problem that must take into account many factors, including the length of the connections between 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 the connections between the components. I think that over time such tasks will be calculated using FPGA.