Slaying a Life: Optimizing GPU-accelerated Game of Life Stencil

Abstract

Iterative stencil loops (ISL) form a specific group of algorithms widely employed in simulations, image processing, or cellular automata. In this paper, we focus on Conway's Game of Life, a zero-player game implemented by a stencil that uses a 2D grid of bool values indicating whether a cell contains a live organism. This stencil is suitable for data-parallel processing on GPUs; however, we discovered that current state-of-the-art implementations are suboptimal and can be improved. Furthermore, we use this stencil as a proof of concept for our proposed optimization technique that eliminates unnecessary computations on the areas of the grid that did not change in the last iteration. Our implementation based on more efficient bitwise encoding and the work-reduction optimization exhibits 22.8x speedup over a baseline GPU implementation and 7.5x speedup over the state-of-the-art packet-coding method. Compared to the code generated by the state-of-the-art AN5D framework, our solution is 19.1x faster.