CS 336: Project #3

Project 3: A Sequential Implementation of Fish Schooling Simulations

On NSCC, create a proj03 directory and cURL the code tarball to it. Then expand the tarball:
  1. curl -O http://cs.colby.edu/courses/S14/cs336/projects/proj03/proj03.tar
  2. tar -xf proj03.tar
The code is organized into the following files:

As you can see, there are many top-level programs. They begin with more IO and less computation (good for debugging) and end with more computation and less IO. We also introduce code to time the computations. Our goal as we parallelize this code in the future will be to speed it up dramatically.

  1. One Simulation at a Time, with I/O

    First, we write the code with the view of making sure it is correct. So, we write code that will simulate one ocean of fish. We supply three functions for initializing the ocean -- one that is random (which is what we will ultimately use, and others that are deterministic). And we write the output to files, so that it can later be visualized.

    1. Write fishStep (in fish_support.c). You should use the following algorithm
        For each "goal" fish,
      • Check to see if there are any fish in its zone of repulsion.
        • If there are, then set the new direction to be away from them according to equation (1) in the paper.
        • If there aren't, then check to see if there are any fish in its zone of attraction/orientation (don't worry about the blind spot - that's an extension). Set the new direction according to equation (2) in the paper.
        • Adjust the new direction by calling correctDirection. Don't worry about fish that turn too far (that's an extension). Also, don't worry about stochastic effects.
      • Set the new position according to the new direction, using equation (3) in the paper.

      Here are some constants that will help you:

        const float repulsionRadius = 1.0;
        const float attractionRadius = 7.0;
        const float weight_attraction = 1.0;
        const float weight_orientation = r;
        const float speed = 1.0;
        const float tau = 0.2;
    2. Test it by running sim_slow (I supply sim_slow.c and runSimulationWithIO and correctDirection). You can visualize the output of sim_slow using disp_sim. Feel free to use it. Remember to start small (say 2 fish for just 2 steps) and look carefully at the output. There is a function in fishIO called dumpFrame which will print the fish positions/directions to the screen. Make liberal use of it.
    3. If you would like to compare it to the output of my code, examine the following .fsh files. They run short (2 steps) and long (100 steps) simulations of fish that are positioned on a 3 by 3 grid and who are all facing northeast. In the first two simulations, they are spaced far enough apart that they don't repel each other. In the last two, they are close enough to repel each other. To generate the files, I ran sim_slow like this:
      ./sim_slow 9 3 2 1 reference_diag.fsh 1
      ./sim_slow 9 3 100 1 reference_diag_long.fsh 1
      ./sim_slow 9 4 2 1 reference_diagPacked.fsh 1
      ./sim_slow 9 4 100 1 reference_diagPacked_long.fsh 1
      You can display the simulation like this:
      ./disp_sim reference1.fsh 1
      where the last argument indicates the time (in seconds) between frames.
  2. One Simulation at a Time, with Statistics

    Now that we know how to run single simulations, let's compute the polarity and elongation values. We continue to allow for certain initial configurations, so that we can debug the statistics.

    1. Write computePolarization (in fish_support.c)
    2. Write runSimulationWithStatistics (in fish_support.c)
    3. Test it by running sim_fast (I supply sim_fast.c and my_timing.c)
  3. Lots of Simulations for one orientation/attraction ratio

    Ultimately, our goal is to run many simulations for each value of r (orientation/attraction ratio) starting from random initial conditions. First, let's write code that runs multiple simulations for one value of r.

    1. Write runRandomSimulationWithStatistics (in fish_support.c)
    2. Write runSimulations (in fish_support.c)
  4. Lots of Simulations for multiple orientation/attraction ratios

    1. Run sim_stats_nr to get a taste of how much time it can take to run sequential code. We need to run at least 32 simulations for each r value on schools of at least 100 fish. How long does it take to run 32 simulations of 100-fish schools for three values of r?



You can use my executable (this is the version without the extension) to generate additional reference files. Then, if you want to you can dump the data to the screen as numbers. This is more precise than watching the movie.

Make dump_sim. Use your version of sim_slow (without extensions) to generate .fsh files with small numbers of fish. Use mine (taylor_sim_slow) to do the same. Then dump the .fsh file and compare the output.


To hand in your project, you will gather all of the necessary files into a proj03 directory in your "turnin" directory:

  1. Create a file named README.txt for your project write-up. This week, I want you to talk about (a) what was the most challenging aspect of the project, (b) which extensions you did, and (c) how long it takes to run sim_stats_1r for different values of r (ranging from 0.25 to 16) for different sizes of fish schools (ranging from 10 to 100), and for different numbers of simulations (you will be limited by the fish school size for this one). For part (c), it is up to you to decide which simulations to run. Make your decision based on how long it takes to run the individual simulations. Don't spend more than an hour on this part (writing and running together).
  2. You should hand in all code necessary to run your solutions. Place all necessary .h, .c, and Makefile files in the proj03 directory. Stephanie will probably want to compile and run the code. It should be possible to do so without looking for any more files.

Email Stephanie to let her know your project is ready for grading.