Parallelization: Conway's Game of Life
By Aaron Weeden
Shodor, Durham, North Carolina
This module teaches Conway's Game of Life as an example of a cellular automaton, how cellular automata are used in solutions to scientific problems, how cellular automata fall into the Structured Grid "dwarf" (a class of algorithms that have similar communication and computation patterns), how to implement parallel code for a Structured Grid application (including versions that use distributed memmory via the Message Passing Interface (MPI), shared memory via OpenMP, and hybrid via a combination of MPI and OpenMP), and how to measure the performance and scaling of a Structured Grid application in multicore and manycore environments. Upon completion of this module, students should be able to understand the importance of cellular automata in solving scientific problems, explain the communication and computation patterns of the Structured Grid "dwarf", design a parallel algorithm for a Structured Grid application, implement it using MPI and/or OpenMP, and measure the scalability of a parallel code over multiple or many cores. The documents can be downloaded below:
Resources:
life.zip : zip file with coded implementations of the parallel algorithm.
Exercise 1 (docx) : Exercise for students to develop the parallel algorithm (Microsoft Word version).
Exercise 1 (pdf) : Exercise for students to develop the parallel algorithm (PDF version).
Exercise 2 (docx) : Exercise for students to write a small parallel code and run it on a cluster (Microsoft Word version).
Exercise 2 (pdf) : Exercise for students to write a small parallel code and run it on a cluster (PDF version).
Exercise 3 (docx) : Exercise for students to explore strong and weak scaling of the code on a cluster (Microsoft Word version).
Exercise 3 (pdf) : Exercise for students to explore strong and weak scaling of the code on a cluster (PDF version).
Module Document (docx) : Module document providing description of Conway's Game of Life and cellular automata, the applications of cellular automata to scientific problems, parallel implementation in code, performance and scaling in multicore and manycore environments, and the Structured Grid "dwarf" (Microsoft Word version).
Module Document (pdf) : Module document providing description of Conway's Game of Life and cellular automata, the applications of cellular automata to scientific problems, parallel implementation in code, performance and scaling in multicore and manycore environments, and the Structured Grid "dwarf" (PDF version).
Parallelization: Conway's Game of Life : PowerPoint for lecture introducing the concepts presented in the module document.
Scaling Conway's Game of Life : PowerPoint for lecture introducing the scaling of the parallel Game of Life algorithm.