Programming Included
How often do we remember our first programs? Was it hello world? Or perhaps a simple calculator? One of my firsts was Conway's Game of Life in my Java programming class. Having just recently bought a Raspberry Pi 4, I decided it would a great time to get myself acquainted with Linux kernels. Conway's Game of Life seemed simple at first to program, but turns out the rabbit hole can be deep.
In the span of about 3-4 days I wrote Conway's Game of Life on Raspberry Pi 4 using a simple matrix based implementation with Raspberry Pi 4 specific setup in order to optimize the implementation. At the end, I was averaging around 23 fps on a 2000 by 2000 size grid with roughly 4 threads no GPU. The program was controlled via a terminal that can remotely change the display of the Raspberry Pi regardless of the state of the Pi's display. The game was controllable via ssh and any other forms of communication that support TTY.
The game had been known to show how simple rules can produce complicated results. Just like how the cell is to the human body. For those of new to Conway's Game of Life, the idea is simple, have a board space where each space on the board is represented by a pixel. Each pixel is either alive (colored) or dead (blank). There are simple sets of rules to dictate if a pixel is alive or dead:
1
2
3
4
5
6
7
8
9
10
# Basic high level implementation example of life rules
# There is a more compact way to write the rule, can you think of it?
def cellAlive(cell):
if cell.alive:
# Cell can live if two or more surounds it but dies otherwise due
# to overpopulation or underpopulation
return alive(cell.surrounding) == 2 or alive(cell.surrounding) == 2
else:
# Stricter rule for a dead cell to live
return alive(cell.surrounding) == 3
There is much that has already been said about Conway's Game of Life. I recommend checking out the Wikipedia page or the official Game of Life Wiki which contains various different information on game board configurations. Below you will find some recent things that I've learned in the domain of Conway's Game of Life while implementing the algorithms.
The main goal of diving through this exercise was to understand more about Linux, particularly the Raspberry Pi 4 with Raspbian installed with no GUI. I ended up developing Conway's Game of Life Here were some highlights while developing the features:
I initially wanted to keep development as simple as possible. Instead of attempting to tinker around with the on-board GPU/QPU (see later pointer for more details) I thought it would be best to be able to blitz to screen immediately. Windows API had something similar to this. Looking at the documentation, I was able to find out that Raspbian allows directly writes to /dev/fb0. This allows any writes to this device on Linux to be automatically shown on screen. All I had to do was mmap it in the program and write to it directly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Raspberry Conway: source/app.cpp
void setupFrameBuffer() {
// Prep buffer for writing
FDSCREEN = open(FRAMEBUFFER, O_RDWR);
fb_var_screeninfo varInfo;
ioctl(FDSCREEN, FBIOGET_VSCREENINFO, &varInfo);
// Print Screen Info
SCREEN_X = varInfo.xres;
SCREEN_Y = varInfo.yres;
// Write back file description
ioctl(FDSCREEN,FBIOPUT_VSCREENINFO, &varInfo);
DISPLAY = (uint *) mmap(
0,
SCREEN_X * SCREEN_Y * sizeof(uint),
PROT_WRITE | PROT_READ,
MAP_SHARED,
FDSCREEN,
0
);
}
But wait, there's more! If you run this code by itself, you will quickly notice that the terminal cursor will still be drawn upon the application. This is because of the graphics mode. By default, tty, or the terminal, defaults to TEXT_MODE which means that any graphics rendered will have terminal text rendered over as priority! We can disable this via KDSETMODE and setting the mode to graphics mode (see app.cpp for the code).
What do you think of when you think of key input on Linux? Do you think ncurses or perhaps QT? If you thought so, congrats! You are numbered among the many who have recommended this approach to capture control input. I did not want to use either because I wanted to see if I can learn more about the kernel and also reduce overhead. Turns out to implement a simple, key input system through ssh, it was as simple as changing a file descriptor! The secret sauce is to disable canonical and echo flags for tty:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Rasberry Conway: app.cpp
void setupKeyInputs() {
// Get the terminal process, may not be necessary
INPUT = ttyname(STDIN_FILENO);
// Set terminal mode for listening to input
termios termios_p;
tcgetattr(STDIN_FILENO, &termios_p);
// Set non-canonical mode and remove echo
termios_p.c_lflag = termios_p.c_lflag & !ICANON & !ECHO;
tcsetattr(STDIN_FILENO, TCSANOW, &termios_p);
// Open for reading
FDKEY = open(INPUT, O_RDONLY | O_NONBLOCK);
}
The Pi 4 is powerful but not powerful enough. Originally with a 2000 x 2000 board, I could only run around 1 fps. Here are the ways that I was able to speed things up.
The game was embarassingly easy to multithread. Split the image up into multiple rows (rows for cache friendliness), and then run multiple threads. Since each compute is per pixel with reads across other rows, there is no need to atomize operations. This can be done for both game updates and blitzing to screen via CPU. This optimization sped up the rendering the most (which was the bottleneck) and allowed for 20-25 fps increases almost immediately.
There were a few algorithmic specific approaches. Some amazing internet coders have written life in binary implementations to incredibly efficient algorithms. I did not have time to implement every single algorithm, but I was able to take some ideas and learn a bunch more. There are code specific implementations that can be optimized such as the rule for calculating life:
1
2
3
4
5
6
7
8
9
// Raspberry Conway: source/game.hpp
inline bool life (
bool nw, bool nn, bool ne,
bool ww, bool cc, bool ee,
bool sw, bool ss, bool se
) {
uint count = nw + nn + ne + ww + ee + sw + ss + se;
return (count == 2) ? cc : (count == 3);
}
There are other approaches to representing life efficiently. By using a quadtree, one can hash the board space to skip calculations per pixel over time. This implementation is called Hashlife. I was not able to finish implementing this algorithm at the time of writing this article but plan to dive more into this algorithm the next blog as I could not find a simple succinct way to summarize this algorithm without diving through code. Please stayed tuned.
Dear Raspberry Pi development team, please do not delay official support for OpenGLES. As of December 2019, there are still no officially supported OpenGLES implementations for Raspberry Pi 4. Part of the reason for this breakage was because of a new chip: VideoCore 6 which is different from VideoCore 4 from Raspberry Pi 3. VC6 was closer to VC5 than VC4 is to VC6. As a result most OpenGLES demo examples packaged with the Pi under /opt/vc simply do not work.
Last I looked into this, however, there are ongoing talks to get rid of the old way of binding devices for the GPU and instead focus on DRM and OpenGLES API based approach which is more common for Linux desktops today. I attempted to pull and work with the active upstream Mesa repository which housed the upto date Raspberry Pi 4 graphics demo but did not have time to complete it without spending hours of reading and building expertise on the graphics pipeline. At this point, I'll wait until the Raspberry Pi team solidifies the API. Until then, the project code has experimental build flags to use opengl header files but do not compile successfully.
Overall this project has been an amazing experience. Being able to write for an embedded system with a small memory has been a great way for me to push myself to optimize where it matters. There is still much to discuss in the real of Conway's Game of Life itself. Specific algorithms and all. I look forward to be able to share that knowledge another time.