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

• Learn about false sharing and prevent it. Chapter 7 in Introduction to Parallel Computing talks about Pthreads. They have a nice description of false sharing. Read this and then try to prevent false sharing in the global array version of this problem. To do so, use an array of padded ints instead of an array of ints. Here is my definition of a padded int.
```typedef struct {
int value;