CS 336: Project #2

Project 2: Fish Schooling with a focus on correctness

Fish-schooling exercises

This week we will get the fish-schooling simulation working on a single processor. Next week, we will add support to collect statistics about the performance (both timing and program output).

  1. Read sections 1, 2, 5, and 6 of the paper on fish-schooling simulation.
  2. On NSCC, cURL the code tarball to it. Then expand the tarball:
    1. curl -O http://cs.colby.edu/courses/S16/cs336/projects/proj02/proj02.tar
    2. tar -xf proj02.tar
    The code is organized into the following files:
    • Main programs:
      • sim_slow.c: Runs a single simulation using the initial_schools code to generate an initial configuration, outputting the results (or even every step) to a file that can later be displayed by disp_sim.
      • sim_from_file.c: Runs a single simulation, reading the initial configuration from a file, outputting the results (or even every step) to a file that can later be displayed by disp_sim.
      • disp_sim.c: A program Stephanie wrote to graphically display the results of a simulation. It reads in a file output by sim_slow.
      • dump_sim.c: A program that Stephanie wrote to make it easy to read the contents of a .fsh file.
    • Data files: Stephanie developed a file format that contains the information that allows us to view and visualize the movement of every fish in a simulation. It is a binary file format, so don't try to read it with Xemacs.
    • Support routines:
      • my_timing.c and my_timing.h: contains a function that allows us to time code in seconds with precision up to milliseconds.
      • fishIO.c and fishIO.h: contains file IO routines for the slow simulation and disp_sim.
      • initial_schools.h: routines to initialize oceans at the beginning of simulations. You will be writing initial_schools.c
      • my_math.h: mathematical functions. You will be suppling my_math.c.
      • fish_support.c and fish_support.h: the heart of the simulation. Routines for simulating and computing statistic go here. You will adding code to this file..

    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.

  3. Add the necessary functions to my_math.c. For each of the following functions, put the function prototype in my_math.h, implement the function in my_math.c, and add an appropriate test function to test_my_math.c.
    • Add a countNans function:
          // return the number of Nans in the array.
          int countNans(float *array, int N);
          
    • Add a max function:
          // Return the maxium value in the array (of length N)
          float max(float *array, int N);
          
    • Add a sum function:
          // Return the sum of the N floats in the array.
          float sum(float *array, int N);
          
    • Add a mean function:
          // Return the mean value of N floats in the array.
          float mean(float *array, int N);
          
    • Add a std function:
          // Return the standard deviation of N floats in the array.
          // Note: This uses the Bessel correction.
          float std(float *array, int N);
          
    • Add a swapArraysfunction. This function is meant to swap to arrays of floats, i.e. to float * values. Recall that we need to be sent the address of the value we are swapping, so the type we need to pass in is float **. The function prototype should be:
          // swap the pointers a and b
          void swapArrays(float **a, float **b);
          
  4. Write test functions for my_math.c (in test_my_math.c) testing. I suggest you add at least createAscendingArray and createDescendingArray. They create arrays and fill them with data. Use these functions to make your test-writing simpler (see test_min for hints).

    Here is the code for createAscendingArray.

    float *createAscendingArray(int N) {
      float *ret = malloc(sizeof(float)*N);
      int i;
      for (i=0; i<N; i++)
        ret[i] = (float)i;
      return ret;
    }
    
  5. Write the code for initial_schools.c. Test it by visualizing it with disp_sim or dump_sim.
  6. 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;
    

    The radii are chosen under the assumption that the size of the board is approximately sqrt(N) by sqrt(N) when N is the number of fix. You may need to scale the constants if you have a board that is 1 by 1.

  7. Test it by running sim_slow (I supply sim_slow.c and runSimulationWithIO and correctDirection) or sim_from_file. You can visualize the output of sim_slow (or sim_from_file) using disp_sim or dump_sim. 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.

    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 run simulations beginning from the same initial configurations:
    ./sim_from_file reference_diag.fsh 2 1 my_diag.fsh 1
    ./sim_from_file reference_diag_long.fsh 100 1 my_diag_long.fsh 1
    ./sim_from_file reference_diagPacked.fsh 2 1 my_diagPacked.fsh 1
    ./sim_from_file reference_diagPacked_long.fsh 100 1 my_diagPacked_long.fsh 1
    
    You should then use disp_sim and/or dump_sim to compare my files to yours, e.g. ./disp_sim reference_diag.fsh 1 where the last argument indicates the time (in seconds) between frames.

Additional Exercises

Let's spend a short amount of time making sure we understand the memory model of C. Here is your opportunity to play around and to get credit for it. Let's write additional functions in test_my_math.c that are intended to break the program.
  1. Draw the memory before and after two float arrays are swapped. As in class, assume the variables are stored on the stack and the contents are stored on the heap. Assume that before the swap, array a contains 1,2,3 and array b contains 4,5,6.
  2. Write a function that "tests" one of your math functions, but which gives the wrong value for the length N. What goes wrong? What can you infer from the memory?
  3. Tell me how much time you spent on this project outside of class.

Extensions

Handin

  1. Create a named README.txt. Your project write-up should be in README.txt. For each exercise above, either answer the question or indicate which code file contains the solution.
  2. You should hand in all code necessary to run your solutions. Place all necessary .h, .c, and Makefile files in the proj02 directory. Stephanie will probably want to compile and run the code. It should be possible to do so without looking for any more files.

Zip up the folder and email it to Stephanie.