Difference between revisions of "DPS921 Team Optimize"
(→The Game of Life) |
(→Serial Implementation) |
||
| (24 intermediate revisions by the same user not shown) | |||
| Line 11: | Line 11: | ||
Assignment page (Optimize) has been created and he following project topic is being researched on | Assignment page (Optimize) has been created and he following project topic is being researched on | ||
* The Game Of Life - Cilk Plus Implementation - [https://en.wikipedia.org/wiki/Conway's_Game_of_Life] | * The Game Of Life - Cilk Plus Implementation - [https://en.wikipedia.org/wiki/Conway's_Game_of_Life] | ||
| − | |||
| − | |||
'''Entry on: November 14th 2016 ''' | '''Entry on: November 14th 2016 ''' | ||
| Line 33: | Line 31: | ||
* Comway's Game Of Life - Rules - [http://web.mit.edu/sp.268/www/2010/lifeSlides.pdf] | * Comway's Game Of Life - Rules - [http://web.mit.edu/sp.268/www/2010/lifeSlides.pdf] | ||
* Example Generations - [https://en.wikipedia.org/wiki/Conway's_Game_of_Life] | * Example Generations - [https://en.wikipedia.org/wiki/Conway's_Game_of_Life] | ||
| − | + | * Serial Implementation - [https://rosettacode.org/wiki/Conway%27s_Game_of_Life#C.2B.2B] | |
'''Entry on: November 27th 2016 by Luv Kapur''' | '''Entry on: November 27th 2016 by Luv Kapur''' | ||
---- | ---- | ||
| + | |||
=== Algorithm Description === | === Algorithm Description === | ||
Comway's Game of Life is a algorithmic representation of cellular automation developed by John Conway in 1970. The game is played on an infinite two-dimensional rectangular grid of cells. Each cell has two probable states, alive or dead. Depending on the state of that cell's 8 neighbors, the state of each cell changes each turn of the game, constituting a unique generation on every computation . Neighbors of a cell are cells that touch that cell, either horizontal, vertical, or diagonal from that cell. | Comway's Game of Life is a algorithmic representation of cellular automation developed by John Conway in 1970. The game is played on an infinite two-dimensional rectangular grid of cells. Each cell has two probable states, alive or dead. Depending on the state of that cell's 8 neighbors, the state of each cell changes each turn of the game, constituting a unique generation on every computation . Neighbors of a cell are cells that touch that cell, either horizontal, vertical, or diagonal from that cell. | ||
| Line 56: | Line 55: | ||
* Triomino Patterns | * Triomino Patterns | ||
| − | [[File:Gol_Example.png|600px|thumb| | + | [[File:Gol_Example.png|600px|thumb|none|alt| Triomino Patterns]] |
* Still Life Patterns | * Still Life Patterns | ||
| − | [[File:still_life_example.png|600px|thumb| | + | [[File:still_life_example.png|600px|thumb|none|alt| Still Life Patterns]] |
| + | ---- | ||
| + | |||
| + | === UI Simulation === | ||
| + | The following pictures show the UI simulation of the Game of Life. | ||
| + | |||
| + | [[File:Generation1.png|thumb|none|alt=Generation1.]] | ||
| + | Generation 1 | ||
| + | |||
| + | [[File:Generation2.png|thumb| none |alt=Generation2.]] | ||
| + | Generation 2 | ||
| + | |||
| + | [[File:GenerationFinal.png|thumb| none |alt=GenerationFinal.]] | ||
| + | Generation 44 | ||
| + | |||
---- | ---- | ||
| + | |||
=== Serial Implementation === | === Serial Implementation === | ||
| + | |||
| + | ==== Structure ==== | ||
The serial implementation of the above algorithm divides the problem in two three distinct classes. | The serial implementation of the above algorithm divides the problem in two three distinct classes. | ||
* Cellular - the class which defines the cell. It keeps track of the generation, pointer to a world class which defines the dimensions in which the cell exists and a pointer to the rule class which governs the change in the cell on every generation. | * Cellular - the class which defines the cell. It keeps track of the generation, pointer to a world class which defines the dimensions in which the cell exists and a pointer to the rule class which governs the change in the cell on every generation. | ||
| − | [[File:cellular_class.png| | + | [[File:cellular_class.png|600px|thumb|none|alt| Cellular Class ]] |
| + | |||
| + | * World - the class which defines the world, the environment for the cell in which the cell undergoes evolution. The class contains the dimensions for the 2D dimensional matrix where the cell is positioned. [[File:world_class.png|600px|thumb|none|alt| World Class ]] | ||
| + | |||
| + | * Rule - the class which defines the rule which govern the evolution in every generation. It contains pointers to two world object, the current and the next computed one. | ||
| + | [[File:rule_class.png|600px|thumb|none|alt| Rule Class ]] | ||
| + | |||
| + | ==== Serial Hot Spot ==== | ||
| + | The serial implementation basically applies the rule to every cell in the 2D dimensional matrix, and computes another world determining the position of every cell using the number of neighbours surrounding it. The following loop takes the maximum amount of computation time in determining the position of the cells in the next generation. This will be parallelized in the coming sections. | ||
| + | [[File:serial_hotspot.png|600px|thumb|none|alt| Apply Rules Class ]] | ||
| + | |||
| + | ==== Results ==== | ||
| + | The following diagram shows the serial implementation of The Game of Life, running in a 500x500 matrix. Every generation indicates a generation along with the number of live cells. Generation 1 has been hard coded with a fixed amount of live cells to initiate the process and then the rule class determines the number of live cells in coming generations. | ||
| + | [[File:serial_500x500.png|600px|thumb|none|alt| Serial 500x500 ]] | ||
| + | |||
| + | === Cilk Plus Implementation === | ||
| + | |||
| + | ==== Code ==== | ||
| + | The following code parallelizes the nested loop using, '''cilk_for''' | ||
| + | [[File:cilk_for.png|600px |thumb| none |alt| cilk_for]] | ||
| − | + | ==== Results ==== | |
| + | A 500 x 500 matrix world, generates a new generation in every 1200ms, which half the time taken when compared to the serial version | ||
| + | [[File:cilk_plus.png|600px|thumb|none|alt| cilk_plus result 500x500]] | ||
Latest revision as of 21:47, 28 November 2016
Contents
The Game of Life
Group Members
- Luv Kapur, Research, and everything else.
Progress
Entry on: November 6th 2016
Assignment page (Optimize) has been created and he following project topic is being researched on
- The Game Of Life - Cilk Plus Implementation - [1]
Entry on: November 14th 2016
The Game of Life, is thoroughly researched and the following key points have been derived:
- Problem Description and Algorithm Analysis
- Serial Implementation
- Cilk Plus Implementation
- OpenMP Implementation
- TBB Implementation
- Comparative Analysis of all the parallel versions
Research
References
All the research is based from the following resources:
- Comway's Game Of Life - Algorithm Description - [2]
- Comway's Game Of Life - Rules - [3]
- Example Generations - [4]
- Serial Implementation - [5]
Entry on: November 27th 2016 by Luv Kapur
Algorithm Description
Comway's Game of Life is a algorithmic representation of cellular automation developed by John Conway in 1970. The game is played on an infinite two-dimensional rectangular grid of cells. Each cell has two probable states, alive or dead. Depending on the state of that cell's 8 neighbors, the state of each cell changes each turn of the game, constituting a unique generation on every computation . Neighbors of a cell are cells that touch that cell, either horizontal, vertical, or diagonal from that cell.
The initial pattern is the first generation. The second generation evolves from applying the rules simultaneously to every cell on the game board, i.e. births and deaths happen simultaneously. Afterwards, the rules are iteratively applied to create future generations. For each generation of the game, a cell's status in the next generation is determined by a set of rules.
Rules
The rules of the game are simple, and describe the next generation of cells in the grid:
- Birth: a cell that is dead at time t will be alive at time t +1 if exactly 3 of its eight neighbors were alive at time t
- Death: a cell can die by:
- Overcrowding: if a cell is alive at time t + 1 and 4 or more of its neighbors are also alive at time t, the cell will be dead at time t + 1
- Exposure: If a live cell at time t has only 1 live neighbor or no live neighbors, it will be dead at time t + 1
- Survival: a cell survives from time t to time t + 1 if and only if 2 or 3 of its neighbors are alive at time t
Examples
Using the above two dimensional infinite playground and rules as outline above, the following patterns emerge during various cell positions during various generations.
- Triomino Patterns
- Still Life Patterns
UI Simulation
The following pictures show the UI simulation of the Game of Life.
Generation 1
Generation 2
Generation 44
Serial Implementation
Structure
The serial implementation of the above algorithm divides the problem in two three distinct classes.
- Cellular - the class which defines the cell. It keeps track of the generation, pointer to a world class which defines the dimensions in which the cell exists and a pointer to the rule class which governs the change in the cell on every generation.
- World - the class which defines the world, the environment for the cell in which the cell undergoes evolution. The class contains the dimensions for the 2D dimensional matrix where the cell is positioned.
- Rule - the class which defines the rule which govern the evolution in every generation. It contains pointers to two world object, the current and the next computed one.
Serial Hot Spot
The serial implementation basically applies the rule to every cell in the 2D dimensional matrix, and computes another world determining the position of every cell using the number of neighbours surrounding it. The following loop takes the maximum amount of computation time in determining the position of the cells in the next generation. This will be parallelized in the coming sections.
Results
The following diagram shows the serial implementation of The Game of Life, running in a 500x500 matrix. Every generation indicates a generation along with the number of live cells. Generation 1 has been hard coded with a fixed amount of live cells to initiate the process and then the rule class determines the number of live cells in coming generations.
Cilk Plus Implementation
Code
The following code parallelizes the nested loop using, cilk_for
Results
A 500 x 500 matrix world, generates a new generation in every 1200ms, which half the time taken when compared to the serial version
