Important notes:
CSE 415 – Spring 2019 Homework 4
Due 5 pm, Friday, March 29, 2019
Please use a word processing software (e.g., MS Word, Mac Pages, Latex, etc.) to type your homework. Follow the homework submission instructions to turn in an electronic copy of your work.
This homework can optionally be done in pairs. Each pair would need to submit a single report.
OpenMP-enabled Simulation of Crystal Growth via Diffusion-Limited Aggregation [100 pts]
Overview:
In this assignment, you are expected to develop an OpenMP-based multi-threaded simulation of the physical process known as diffusion-limited aggregation (DLA).
Background and Specifications:
Diffusion-limited aggregation(DLA) is a crystal formation process whereby particlesperforming Brownian motion (i.e., random motion in all directions) are “glued”together to form aggregates. The formations that result from this process are alsoknown as Brownian trees.
DLA can be simulated in two dimensions by having a 2D grid of cells populatedby moving particles and crystal parts. Forsimplicity, we will assume that each cell can be occupied by one or more free-moving particles. A particle becomes part of the crystal (and stops moving) when it movesinto a cell that is in proximity (i.e., one of the eight cells surrounding it) to the already formed crystal. A visualization of the formed crystal over multiple iterations is shown in the figure below.
Inputs
Input parameters to the simulation code will be the size of the 2D grid, the total numberof particles, the number of iterations, and the initial crystal “seed,” i.e., the fixed partto which particles will start attaching as the simulation progresses. The seed is a single cell fixed right at the center of the 2D grid. Your program must accept the remainingparameters, i.e., n – size of the square 2D grid, p – the total number of particles, i – the number of simulation iterations and s – which particle is the seed (an integer value) as command-line parameters.
Initialization
• Allocations – a list of particle positions (could be stored as two arrays to represent x & y positions), a matrix to represent the current state of the simulation, and other data structures you may find necessary.
• Clear all 2D grid points, i.e., matrix entries
• Place the seed particle at the center of the grid. (Update the initial positions of the seed.)
• Randomly assign initial positions of all particles, except the seed. Make sure to use a thread safe random number generator, for instance the rand_r() function in C.
Simulation
• For i iterations, all free particles perform a random walk, i.e., they randomly move into an adjacent cell (one of the eight cells surrounding its current location) or they may stay in the same cell.
• Any free particles that come into contact with the fixed particles, i.e., the growing crystal, also become fixed. If a particle moves outside the 2D grid at any point, it disappears from the simulation.
• Note that two (or more) particles (free or fixed) are allowed to occupy the same cell during the simulation.
• The simulation will continue until all i iterations are completed, and the results are then visualized.
Develop an OpenMP enabled multi-threaded simulation of crystal growth via DLA. You can use your programming language of your choosing (provided that it has OpenMP support).
One characteristic of this problem to exploit when developing a parallel solution is the independence of particle movements. They may be performed in any order and still be correct. Of course, you still have to isolate old/new matrices that represent the grid state–at iteration t, free particles can be fixed by only coming into the proximity of fixed particles at iteration t-1.
Note that there are a number of different ways to leverage concurrency in this problem. For example, one can designate each thread to be responsible for a pre-defined portion of the lattice.Or each thread can be associated with moving a set of particles. Put some thought into your implementation as to which option would be better in terms of performance and scalability.
Deliverables:
1. Your sourcecode together with a makefile to compile it. 2. A report containing your answers to the questions below.
– Discuss your parallelization approach (for instance, pre-defined thread domains or multiple particles assigned to each thread) and why you expect it to perform well in terms of load balancing or scalability.
– Create multiple visualizations of the final state of your simulation for different inputs; try to draw examples that lead to different looking crystals. Make sure to omit from your visualizations any particles that are still free at the end of the simulation. Any package, framework, language is acceptable for visualization. Your visualization images must be embedded into the report.
– Instrument and time the core of your simulation code (the actual simulation, not writing out results or visualizing points). Conduct a speedup analysis with using different number of threads, different number of particles. You can use the intel16 or intel18 cluster, but make a note of which cluster you have used in your report.
– Provide an example on how to execute your code, or provide multiple examples if there are different execution modes, such as 3D support (see below).
BONUS [25 pts]
Extend your implementation and visualizations into 3D. Good visualizations are important to receive full credit.