CS 336: Project #4

Project 4: Counting and Counting and Counting

On NSCC, create a proj04 directory.

In this project, you will be exploring different methods of counting the number of 3's in an array of integers. You will use 8 threads, and each will be given a chunk of the array in which to count 3's. The question is: where do you store your counter? Do you use a local variable? Do you use a global variable?

  1. Sequential

    Write a sequential version of the program. It should create an array of a given length, count the 3's in it, and print to the screen the number of 3's. You should also time the work, from after the array creation to before the print statement. Print out how long it took to run.

    To help you out, here is a function that creates an array of length N. I am using the random number generator, but I seed it to 1 so that it returns the same array every time. This is useful for debugging:

    /* Create an array of len random integers between 0 and 9 */
    int *create_random_int_array(int len)
    {
      int i;
      int *ret;
      ret = (int *)malloc(sizeof(int)*length);
      srand(1); // use the same seed every time!
      for (i=0; i<len; i++)
        ret[i] = rand() % 10;
        return ret;
    } // create_random_int_array
    
    To use rand, you must include stdlib.h.
  2. Parallel

    The remaining versions should use 8 pthreads. Each thread counts a section of the array (divide the array length by the number of threads and just give them successive chunks) - it is alright to mandate that the length of the array be a multiple of 8 so that it divides evenly among the threads. It doesn't matter if the array length is a global variable, constant, or command line input. I have found that the value N=80000000 is a good one (it takes long enough for me to time it, but not too long).

    To test the Pthreads version, just compare it to the sequential version.

    You will also need to add code to time these programs. Time them from before the pthreads are created to after they have all been joined. To do this, copy my_timing.h and my_timing.c from the fish schooling code into your proj03 directory. Be sure to link my_timing.o into your executable.

    1. Global Counter (Scalar)

      Use a global variable to keep track of the total number of 3's. Since all threads will be reading and writing to it like crazy, we need to protect it with a mutex lock. So, make a global variable mutex lock. Every time a thread sees a 3, it locks the lock, updates the counter, and then unlocks the lock.

    2. Global Counter (Array), Global Scalar Update

      Use a global variable that is an array of counters - one counter for each thread. When a thread sees a 3, it updates its entry in the global array. Before the thread exits, it should update a mutex-protected global scalar variable.

    3. Global Counter (Array), Global Array Update

      Use a global variable that is an array of counters - one counter for each thread. When a thread sees a 3, it updates its entry in the global array. The main code should be responsible for summing the entries in this array. I do this after each thread is joined.

    4. Local Counter, Global Scalar Update

      Use a local variable to keep track of an individual thread's 3's count. Then, before the thread exits, it should update a mutex-protected global scalar value.

    5. Local Counter, Global Array Update

      Use a local variable to keep track of an individual thread's 3's count. Then, before the thread exits, place the value in its slow in a global array. The main code should be responsible for summing the entries in this array. I do this after each thread is joined.

Extensions

Writeup and Handin

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

  1. Create a file named README.txt for your project write-up. This week, I want you to collect timing information from all of your runs and then analyze the results. The analysis is a significant part of the project, so don't leave it until the last minute, when you are too tired to think clearly. Here's the data I want you to collect: the number of seconds it takes to run each version of the program. You should record this 5 times for each program. Drop the min and max values from these 5 and then report the mean of the middle 3. What conclusions can you draw? What can you say about the roles of mutex locks for this problem? If you did the extension, then talk about false sharing as well. Which version of the code is the one you would most like to write? Which would you most like to run?
  2. You should hand in all code necessary to run your solutions. Place all necessary .h, .c, and Makefile files in the proj04 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.