CSE 160 Homework Assignment #5
Sharks and Fishes
TO BE DONE IN TEAMS OF TWO
(20 points)

Due: Friday 12/5 at 2PM (in section)

Changelog

Introduction

In this assignment you'll parallelize the game of "Sharks and Fishes" using OpenMP. A working serial version of the code has been provided as sf.tgz Try and make the code go as fast as you can; thus you should not only optimize multithreaded performance scheme, but also single processor performance.

Sharks and Fishes

The Sharks and Fishes simulation is intended to model the dynamics of a population of predators and prey using an idealized model that makes simplifying assumptions. Scientists often make these assumptions in the interest of reducing the computational cost of the simulation, and hence practical to run on the available computing resources.

The simulator models a system in terms of discrete events, where sea animals move in an idealized world represented as a mesh, and they move and interact at discrete points in time (called timesteps) on discrete positions of the mesh. At each time step, each fish will decide to move in a direction according to the following rules: if a snapper has a shark in the nearest neighbor cells it decides to move in the opposite direction, otherwise its instinct (a repulsive force equal to 1/distance from each shark) will tell in which direction to move; if a shark has a snapper in the nearest neighbor cells it decides to eat the snapper and move into its cell, otherwise its senses (an attractive force equal to 1/distance^2 from each snapper) will tell in which direction to move. Nearest neighbors are defined on the 4 manhattan directions only: north, south, east and west. Corner moves are not allowed.

The simulation sorts the sharks and the fishes according to their chosen direction; e.g. all fish that chose to move North will do, then those wanting East, and so on.

Serial Code

We are providing you with a working serial program that implements the Sharks and Fish simulation. It includes a plotting capability (as before, with gnuplot) which you can use to debug your code, and also to observe the population dynamics. Your timings results will be taken when the plotting is disabled.

The provided code creates 2D simulation ocean, distributing sharks and fish randomly throughout the ocean. You may choose the number of each type of animal you wish to add to the simulation. The options are described as comments within the code.

The program may be run from the command prompt as follows:

With the arguments interpreted as follows:

The default parameters are described in fish.c.

Thus, the command line

will initialize a 50 × 50 sea populated by 300 snappers and 25 sharks and run the simulation for 500 time steps.

In this simulation, the number of fishes will diminish over time, and given enough time the sharks may or may not consume all the fish. If you increase the number of sharks sufficiently, they will consume all the fish within the allotted time frame (perhaps less). Experiment with these parameters with the display enabled to understand the dynamics.

NOTE: If a gnuplot window does not appear on your screen, then your SSH display settings are not set correctly. If you are using a Linux based machine and are connecting to a Linux machine using SSH, use the -X option:

If you are using a Windows based machine, and are using a 'secure shell client' AND 'exceed' (or xwin32, or cygwin) to log into Linux machine, you must ensure that 'X11 tunneling' is set. [If you have problems with this, first read our web-board on this issue. If you still have the problem, send email to Pietro.]

The Assignment

In this assignment, you'll make modifications to the provided code. In particular, you’ll parallelize it with OpenMP. You’ll also conduct strong scaling studies. With a fixed problem size N run on 1, 2, 4 , and 8 cores. What speedups do you observe? Discuss you observations and explore the underlying causes. If you see perfect speedup, shrink the problem size until you see differently, and explain your results. If you see poor speedups, grow the problem size until the speedups improve. Also perform the following study on 8 cores. Determine the smallest value of N for which you obtain linear speedups. To reduce the number of runs, you need run with only 1 random number seed (see below).

Because the simulation chooses random configurations, you will need to run with different random number seeds (using the -s option) and take the average. In addition, you should run at least 3 times for each random number seed, and take the minimum running time. We recommend that you run with at least 5 different random seeds, thus, you will make 15 runs for each number of cores, for a total of 60 runs. Plan your assignment accordingly. Runs should last not more than 5 seconds on 8 cores.

How to test your code

Things you should turn in

Document your work in a well-written report which discusses your findings carefully. This part of your assignment will be worth 50% the grade. Your report should present a clear evaluation of the design of your code, including bottlenecks of the implementation, and describe any special coding or tuned parameters. Provide pseudo code listings that illustrates how you parallelized the code.

Your report should cite any written works or software as appropriate in the text of the report. Citations should include any software you used that was written by someone else, or that was written by you for purposes other than this class.

Transmit the report electronically along with your source code and your report. by the deadline. Be sure and delete all .o files and executables before creating the tar file. Transmit a single archive file, e.g. .zip, .tgz, containing your writeup, and source code, plus any output files. Email the archive file as an attachment to the following address:

The name of your tar file should start with your login ID, e.g. baden.tgz. Your archive file should create a directory with the name of your login ID. The directory should contain two subdirectories

src:     All source code including your makefile, so we can build the software.
report: Your report including any separate image files, screen shots, or other output.