CSCE 435 HW 2: Parallel Programming with Threads II

Minimum of a List

You are provided with a program list_minimum.c to compute the minimum element of a list using threads. The main program initializes data structures and calls pthread_create to create threads that execute the function find_minimum. Each thread is assigned a sublist ranging from my_start to my_end, and is responsible for computing the minimum value in this range. The thread is also responsible for updating the global variable minimum to ensure that the global minimum is no larger than the minimum value in its sublist. The program is missing code to update minimum. You need to add code to the find_minimum routine so that the program computes the minimum correctly. Access to minimum is controlled by the mutex lock_minimum. The variable count has been initialized to zero in the main program, and can be used to determine how many threads have accessed minimum.

Once you complete the code, it can be compiled with the command:

icc -o list_minimum.exe list_minimum.c –lpthread –lc -lrt

Note the use of –lc to link the library that provides the random number generator. Also note that –lrt links to the real time library that provides a higher resolution timing function. To execute the program, use

./list_minimum.exe <n> <p>

where <n> represents the number of elements in the list and <p> represents the number of threads.

The output of a sample run is shown below.

./list_minimum.exe 100000 8

Threads = 8, minimum = 18074, time (sec) = 0.0006

1. (20 points) Complete the function find_minimum so that the program computes the minimum of the list correctly. You will get full points if you add code only to the find_minimum routine.

1. (10 points) Execute the code for n = 2×108 with p chosen to be 2k for k = 0, …, 13. Plot execution time versus p to demonstrate how time varies with the number of threads. Use logarithmic scale for the x-axis. Plot speedup versus p to demonstrate the change in speedup with p.

1. (10 points) Give reasons for the observed variation in execution time as p is varied from 1 to 213.

Barrier

You are provided with a program barrier.c that has code to implement a barrier for a multithreaded program. The main program initializes data structures and calls pthread_create to create threads that execute the function work before calling the barrier function. The file csce435.h includes work that forces a thread to sleep for a specified time before returning. The program is missing code for the barrier function called barrier_simple. You need to add code to barrier_simple to implement a barrier among the threads. Threads should wait for all