1. Develop a pseudocode solution
First, come up with an algorithm for parallelizing finding the maximum
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. Implement your algorithm
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 p inclass/max
$ cd inclass/max
$ cp r ~richardw/public/cs31/inclass/max/* ./
$ ls
Makefile max.c
# To run: ./max num_values num_threads print[0/1]
# example: ./max 10000 16 1

There is already code in the max.c file to get the command line arguments and to initialize an array of
N
values to random long values. 
You should add all the
pthread
code to implement your parallel max algorithm. 
Use the
hello_j.c
example from theinclass/pthreads
code to help you withpthread
functions and syntax. (You can also usehello_j.c
as an example to see thread execution info fromtop
. Run./hello_j 16
in one terminal andtop H
in another to see.) 
Look at the
man
pages forpthread
functions:$ man pthread_create $ man pthread_join $ man pthread_mutex_lock
3. Extensions
If you get your solution to this working and debugged, think about a slightly different version of this problem that does two things:

Compute max in parallel when the number of threads,
M
, does not evenly divide the number of elements in the array,N
. (This solution will be helpful for Lab 9.) 
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.