In your group you are going to do the following:

  1. First come up with an algorithm for parallelizing finding the max value in an array of size N using M threads. Assume that you are starting with an already initialized array of N values, and you can start out assuming that M evenly divides N (the case when it doesn’t is an extension to try after you get this case working).

    Some questions to think about as you determine how to parallelize computing max:

    • What part of the cumulative operation does each thread do?

    • How does a thread know which work it will do?

    • Do threads need to coordinate/synchronize their actions in some way? If so, when and how and how frequently?

    • What are the limits on concurrency?

    • What global state will you need? What local state?

  2. When you are happy with your pseudo-code algorithm talk your algorithm through with one of the professors or ninjas before moving on to the next step

  3. Together, try implementing your algorithm in pthreads. You can do this on paper (and in fact this might be the preferred way at least as a first step), or you can try implementing and testing it using some starting point code:

    cd ~/cs31/
mkdir inclass
cd inclass
cp -r ~adanner/public/cs31/inclass/w12/ ./
cd w12
ls
Makefile hello.c max.c

To run:  ./max N M
example: ./max 10000 16

  4. There is already code in this file to get the command line arguments and to initialize an array of N values to random long values.

  5. You should add all the pthread code to implement your parallel max algorithm.

  6. Use the hello.c example to help you with pthread functions and syntax. (you can also use ./hello as an example to see thread execution info from top. Run ./hello 16 in one terminal and top -H in another to see.

  7. Look at the man pages for pthread functions:

    man pthread_create
man pthread_join
man pthread_mutex_lock

  8. Look at the weekly lab page for other pthread examples.

1. Sharing code

If you make edits to the code and wish to share them with your in class group, a quick way without git is to use mail

$ mail username1 < max.c
$ mail username2 < max.c
$ mail username3 < max.c

2. Extensions

If you get your solution to this working and debugged, think about a slightly different version of this problem that does two things:

  1. Compute max in parallel when the number of threads, M, does not evenly divide the number of elements in the array, N.

  2. Compute the number of times the max value occurs in the array (also in parallel).

Your solutions should only spawn off worker threads one time and only join them when all parallel computation from both parts is done.