Simulating cellular automata
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...
Saved in:
Main Author: | |
---|---|
Other Authors: | |
Format: | Final Year Project |
Language: | English |
Published: |
2012
|
Subjects: | |
Online Access: | http://hdl.handle.net/10356/48468 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-48468 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-484682023-03-03T20:40:50Z Simulating cellular automata Leong, Yew Long. School of Computer Engineering He Bingsheng DRNTU::Engineering::Computer science and engineering::Computing methodologies::Simulation and modeling 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. Bachelor of Engineering (Computer Science) 2012-04-24T06:43:12Z 2012-04-24T06:43:12Z 2012 2012 Final Year Project (FYP) http://hdl.handle.net/10356/48468 en Nanyang Technological University 33 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
DRNTU::Engineering::Computer science and engineering::Computing methodologies::Simulation and modeling |
spellingShingle |
DRNTU::Engineering::Computer science and engineering::Computing methodologies::Simulation and modeling Leong, Yew Long. Simulating cellular automata |
description |
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. |
author2 |
School of Computer Engineering |
author_facet |
School of Computer Engineering Leong, Yew Long. |
format |
Final Year Project |
author |
Leong, Yew Long. |
author_sort |
Leong, Yew Long. |
title |
Simulating cellular automata |
title_short |
Simulating cellular automata |
title_full |
Simulating cellular automata |
title_fullStr |
Simulating cellular automata |
title_full_unstemmed |
Simulating cellular automata |
title_sort |
simulating cellular automata |
publishDate |
2012 |
url |
http://hdl.handle.net/10356/48468 |
_version_ |
1759853741202210816 |