HPCU Bi-Weekly Challenge Precipitate Algorithm: Distributed Memory Author: Aaron Weeden, June 23, 2014 main function: 1. [SINGLE PROCESS] [Read data from user] Call the readData function. -[SINGLE PROCESS SENDS MESSAGE TO ALL PROCESSES WITH environment width, environment height, particle width, particle height, number of particles, number of time steps, and percent chance of collision]- 2. [ALL PROCESSES] [Randomize particle positions] Call the randomizePositions function. -[ALL PROCESSES SEND MESSAGE TO ALL PROCESSES WITH x and y position of each particle]- 3. [ALL PROCESSES] [Start the time] Set current time step to 0. 4. [ALL PROCESSES] [Loop over time steps] For each time step, 4a. [ALL PROCESSES] [Pick directions] Call the pickDirections function. -[ALL PROCESSES SEND MESSAGE TO ALL PROCESSES WITH direction and state of each particle]- 4b. [ALL PROCESSES] [Move particles] Call the moveParticles function. -[ALL PROCESSES SEND MESSAGE TO ALL PROCESSES WITH x and y position and state of each particle]- 4c. [ALL PROCESSES] [Check for collisions] Call the checkCollisions function. -[ALL PROCESSES SEND MESSAGE TO ALL PROCESSES WITH states and directions of each particle]- 4d. [SINGLE PROCESS] [Display] Display the time step. readData function: 1. [SINGLE PROCESS] [Set container wall positions] Read in environment width and height. 2. [SINGLE PROCESS] [Set particle data] Read in particle width and height as well as the number of particles. 3. [SINGLE PROCESS] [Set time data] Read in the number of time steps. 4. [SINGLE PROCESS] [Set % chance] Read in the percent chance of collision. randomizePositions function: -[Divide number of particles as evenly as possible among processes; some processes will each get part of the remainder]- 1. [ALL PROCESSES] [Loop over particles] For each particle, 1a. [ALL PROCESSES] [Generate random number for x] generate a random number between 0 exclusive and (the width of the container minus the width of a particle) inclusive. 1b. [ALL PROCESSES] [Set x] Set the random number as the x position of the particle. 1c. [ALL PROCESSES] [Generate random number for y] generate a random number between 0 exclusive and (the height of the container minus the height of a particle) inclusive. 1d. [ALL PROCESSES] [Set y] Set the random number as the y position of the particle. pickDirections function: -[Divide number of particles as evenly as possible among processes; some processes will each get part of the remainder]- 1. [ALL PROCESSES] [Loop over particles] For each particle, 1a. [ALL PROCESSES] [Skip precipitating particles] If the state of the particle is not 'precipitating', 1a1. [ALL PROCESSES] [Generate random number for direction] generate a random number between 0 exclusive and 4 inclusive. 1a2. [ALL PROCESSES] [Try direction] If the random number is 0, call the tryMove function with the particle and 'left' as parameters. Otherwise, if the random number is 1, call the tryMove function with the particle and 'right' as parameters. Otherwise, if the random number is 2, call the tryMove function with the particle and 'up' as parameters. Otherwise, call the tryMove function with the particle and 'down' as parameters. 1a3. [ALL PROCESSES] [Prepare for move] If the tryMove function returned true, store the direction in the particle, and set the particle's state to 'moving'. Otherwise, set the particle's state to 'blocked'. tryMove function: 1. [ALL PROCESSES] [Check for wall] If the direction is 'left' and the particle's x position is 0, return false. Otherwise, if the direction is 'right' and the particle's x position is the width of the container minus the width of a particle, return false. Otherwise, if the direction is 'up' and the particle's y position is 0, return false. Otherwise, if the direction is 'down' and the particle's y position is the height of the container minus the height of a particle, return false. 2. [ALL PROCESSES] [Check for other particle] If the direction is 'left' and there is a particle to the left of the current particle (the x position is 1 less than the particle's, the y position is the same as the particle's), return false. Otherwise, if the direction is 'right' and there is a particle to the right of the current particle (the x position is 1 more than the particle's, the y position is the same as the particle's), return false. Otherwise, if the direction is 'up' and there is a particle above the current particle (the y position is 1 less than the particle's, the x position is the same), return false. Otherwise, if the direction is 'down' and there is a particle below the current particle (the y position is 1 more than the particle's, the x position is the same), return false. 3. [ALL PROCESSES] [No obstructions found] Return true. moveParticles function: -[Divide number of particles as evenly as possible among processes; some processes will each get part of the remainder]- 1. [ALL PROCESSES] [Loop over particles] For each particle, 1a. [ALL PROCESSES] [Is particle moving?] If the particle's state is 'moving', 1a1. [ALL PROCESSES] [Set new position] If the particle's direction is 'left', set the new x position of the particle to be 1 less than its current x position, and keep the y position the same. Otherwise, if the particle's direction is 'right', set the new x position of the particle to be 1 more than its current x position, and keep the y position the same. Otherwise, if the particle's direction is 'up', set the new y position of the particle to be 1 less than its current y position, and keep the x position the same. Otherwise, if the particle's direction is 'down', set the new y position of the particle to be 1 more than its current y position, and keep the x position the same. 1b. [ALL PROCESSES] [Check for precipitate forming at bottom] Otherwise, call the checkPrecipitate function with the particle as its argument. If it returns true, set the particle's state as 'precipitate'. checkCollisions function: -[Divide number of particles as evenly as possible among processes; some processes will each get part of the remainder]- 1. [ALL PROCESSES] [Loop over particles] For each particle, 1a. [ALL PROCESSES] [Loop over other particles] For each other particle, 1a1. [ALL PROCESSES] [Check for left/right adjacency] If the first particle's y position is the same as the second particle's y position, and the first particle's x position is 1 less than the second particle's x position, then 1a1a. [ALL PROCESSES] [Calculate random number for % chance] Calculate a random number between 0 inclusive and 100 exclusive. 1a1b. [ALL PROCESSES] [Apply % chance] If the random number is less than the percent chance, set the state of both particles to 'colliding', and the direction of both particles to 'down'. 1a2. [ALL PROCESSES] [Check for top/bottom adjacency] If the second particle's state is 'precipitating', and the y position of the second particle is 1 less than the y position of the first particle, and their x positions are the same, set the state of the first particle to 'precipitating', and set its direction to 'down'. checkPrecipitate function: 1. [ALL PROCESSES] [Check for floor] If the particle's y position is the height of the container minus the height of a particle, return true. 2. [ALL PROCESSES] [Loop over other particles] Otherwise, for each of the other particles, 2a. [ALL PROCESSES] [Is precipitate?] If the other particle's state is 'precipitate', and the other particle's y position is 1 more than the first particle's y value, and the two particles have the same x position, return true. 3. [ALL PROCESSES] [None found] Return false.