Conway's Game of Life on GPU using CUDA

This project compares performance of CPU and GPU in evaluation of famous Conway's Game of Life. The performance was tested on three different implementations. The most sophisticated version of the algorithm on GPU stores data in one bit-per-cell array and leads to speed-up of 480x compared to serial CPU algorithm. The best implementation for CPU turned out to be lookup-table approach leading to 60x speedups over serial CPU. The report contains detailed explanation of used algorithms, measurements, and code of whole project for download.

Source code is available on GitHub: NightElfik/Game-of-life-CUDA

Chapter 1: Introduction

Conway's Game of Life is well known cellular automaton which simulates alive and dead cells on infinite square grid (a world). The word game is quite misleading because only interaction of human is usually initial state of the world.

Every cell in the world is either dead or alive. The world evolves in generations also called iterations. Alive state of every cell is determined by number of living cells around it.

This project was final assignment in GPU Programming in CUDA (CGT 620) class. The goal of this assignment was to compare single threaded CPU implementation to GPU implementation using CUDA. I thought that this comparison is quite unfair for the CPU because it can perform parallel operations as well as GPU so I decided to implement parallel algorithm for the CPU as well. And on top of that, I implemented two other and faster algorithms on both CPU and GPU that use only one bit per cell and performs life iterations using bit counting and lookup table methods.

All described algorithms in this article were developed by me from scratch — no textbooks or other sources were used. Full source code is available on GitHub.

Figure 1: Print-screen of finished program of Conway's game of life.

Game of Life rules

Rules of Conway's Game of Life are pretty simple. The world is infinite square grid where every cell has eight neighbors (Moore neighborhood). Every cell is dead or alive. The world can be visualized as an image with a white pixel for alive cell and a black pixel for dead cell (or vice versa).

The life is evolving iteratively. In every iteration, the alive state of every cell is evaluated according to following rules:

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The rules can be observed on evolving patterns in Figure 2.

The rules can be simplified to alive condition shown in Code listing 1. In words, a cell is born (or stays alive) if it has exactly three alive neighbors or if it has two alive neighbors and it is alive as well. Otherwise it dies (or stays dead).

1
2
3
4
5
6

if (aliveNeighbors == 3 || (aliveNeighbors == 2 && isCellAlive[x][y])) {
	isCellAlive[x][y] = true;
}
else {
	isCellAlive[x][y] = false;
}

Any condition in form if (...condition...) { x = true; } else { x = false; } can be simplified and inlined to x = ...condition...; so Code listing 2 shows the inlined alive condition.

1

isCellAlive[x][y] = aliveNeighbors == 3 || (aliveNeighbors == 2 && isCellAlive[x][y]));

Cyclic world

By definition, the life world is infinite. Unfortunately, computers are not very good at representing infinite data structures so world size has to be limited. There are some clever ways how to represent very, very big worlds that seems infinite but this is not the direction I want to go.

The simplest way how to make a world infinite is make it cyclic. This means that left neighbor of the leftmost column is the rightmost column and vice versa. This makes the world infinite in terms that you can go any direction as far as you want without hitting any edge. Of course that total number of cells is cyclic world is finite and the infinity is not real, but good enough for Game of Life purposes. An example of cells and their neighborhood in cyclic world is shown in Figure 3.

Actual implementation of cyclic world is done by using to modulus operator.

Figure 3: Red, green, and blue cells with their Moore neighborhood in a cyclic world.