Simulating cellular automata

• Main Author: Leong, Yew Long.
• Other Authors: School of Computer Engineering
• Format: Final Year Project
• Language: English
• Published: 2012
• Subjects: DRNTU::Engineering::Computer science and engineering::Computing methodologies::Simulation and modeling
• Online Access: http://hdl.handle.net/10356/48468
• Institution: Nanyang Technological University

This project implements cellular automata, specifically, John Conway’s Game of Life (GoL). Cellular automata are simulation models where cells in a lattice change their states according to rules that are applied to their local neighbourhoods. They have become important in scientific simulation because they can exhibit complex behaviours despite simple rules, making them powerful yet easy to apply. This project chose a prominent cellular automaton, the GoL, and identified a property unique to GoL’s rules that was exploited to yield an optimised (faster) simulation speed. The project also aimed to plug a gap left by current cellular automata programs that are used for very large simulations. These programs are hash-based and work well for large predictable patterns but not for large arbitrary inputs. Lastly, the localised rules of cellular automata lend themselves naturally to parallel process- ing and this project also explored methods to run a multi-threaded GoL. The resulting implementations of GoL were then tested and benchmarked, of which the faster GoL yielded a good speedup while trading off memory usage. The program to simulate large arbitrary input worked and exhibited low overheads when scaled but suffered from an addressable limitation on file size. The multi-threaded GoL worked well and could pave the way for a similar GPU implementation.