CI7515 Real Time Development and Artificial Intelligence Assignment 2
Parallel programming
Jean-Christophe Nebel
Hand in Date: 29/03/2019 at 23:59
Overview
This assignment asks you to implement serial and parallel versions of a prey/predator simulation using cellular automata and provide performance and behaviour analysis.
In this project, visual output can be generated using Ascii characters. If you want to provide a more advanced graphical output it is up to you.
Code of the ‘Game of Life’ studied during the class is provided and can be used as a starting point for your implementation.
You are required to hand in all of your source code and to use C/C++ and visual studio.
This is an individual project and no group work is permitted.
Prey/predator simulation model
The prey/predator simulation model used in this assignment uses cellular automata. It deals with populations of fishes and sharks in an ocean, which is represented by an array of cells and where each cell can hold one fish or one shark (but not both).
Given parameters:
• At birth, age =1
• Fish breeding age >= 2,
• Shark breeding age >=3,
• Initially, there is randomly distributed population of fish, sharks, and empty cells following those proportions:
• 50% of the cells are occupied by fishes
• 25% are occupied by sharks
• 25% are empty
Fishes and sharks’ behaviours are governed by a set of simple rules dealing with:
• Breeding
• Aging
• Sudden death
• Starving
• Feeding
• Overpopulation
• Breeding Rule (applies to empty cells only)
For a given empty cell,
If there are >= 4 neighbours of one species, and >= 3 of them are of breeding age,
and there are <4 of the other species
then create a species of that type
• Fish Rules
For a given cell containing a fish,
• Fish live for 10 generations
• If >=5 neighbours are sharks, fish dies (shark food)
• If all 8 neighbours are fish, fish dies (overpopulation)
• If a fish does not die, increment age
• Shark Rules
For a given cell containing a fish,
• Sharks live for 20 generations
• If >=6 neighbours are sharks, and fish neighbours=0, then the shark dies (starvation)
• A shark has a 1/32 (.031) chance of dying due to random causes
• If a shark does not die, increment age
Note: you may want to use the following scheme for coding the state of a cell
• value >0 if fish is present
• value <0 if shark is present
• value =0 if cell is empty
• absolute value of cell is age
Assignment Details
This assignment asks you to implement serial and parallel versions of a prey/predator simulation using the previously described model and performing some performance evaluation on the hardware platform of your choice (it requires at least a dual core processor). It has 5 parts:
Part I: Serial implementation of the proposed prey/predator simulation model
• Algorithm description including strategy to deal with grid boundaries – 10 marks
• Implementation - 5 marks
• Results including screen shots – 5 marks
• Performance analysis according to grid size – 5 marks
Part II: Study of the potential for parallelisation of the algorithm
• Identification of purely sequential sections – 5 marks
• Identification of sections which can be executed in parallel – 5 marks
• Identification of critical sessions and points of synchronisation – 5 marks
• Reflection about potential issues of load balancing – 5 marks
• Identification of potential for global operations e.g. reductions and collective communications – 5 marks
Part III: Parallel implementation using OpenMP of the proposed prey/predator simulation model
• Algorithm description – 5 marks
• Implementation and results including screen shots – 5 marks
• Performance analysis according to number of processors and grid size – 5 marks
Part IV: Parallel implementation using MPI of the proposed prey/predator simulation model
• Algorithm description – 5 marks
• Implementation and results including screen shots – 5 marks
• Performance analysis according to number of processors and grid size – 5 marks
Part V: Parallel implementation using hybrid approach of the proposed prey/predator simulation model
• Algorithm description – 5 marks
• Implementation and results including screen shots – 5 marks
• Performance analysis according to number of processors and grid size – 5 marks
• Reflection about the different proposed parallel solutions - 5 marks
Following items will be taken into account in the process of marking:
• Completed parts
• Code quality
• Effort – how difficult was that to implement, what technical skills have been demonstrated
• Result quality: screen shots of the status of the grid after, for example, 0, 100, 1000 and 10000 generations
• Quality of documentation
Deliverables
Online submission of the report using Canvas.
Regarding the project it should be send using BOX.COM and your KU account providing a direct link to the files (all the files and data should be zipped in one file). The link should be on the first page of the report submitted online using Canvas
The project folder should contain:
• Executable program of your solution accompanied with all the files required to run.
• All the source and project files required to build the executable (whole solution)
• A copy of the report
Mode of submission: On line
Late submissions: for details please refer to the Module Guide.
Plagiarism is a serious academic offence and will always be challenged where it is suspected. When submitting work for assessment ensure it is your own and not someone else’s code, ideas, words and images. You must declare that the task submitted for assessment is your own independent work and that all sources used in the submission are referenced.
Please ensure that your name is on all components of the work presented.
If there are any ambiguities or requirements that you do not understand then tell me immediately either in person, or email: J.Nebel@kingston.ac.uk