Assignment 3

The objective of this assignment is for you to gain experience in using OpenMP:

Complete the following programming questions.  For each design efficient well comment codes and evaluate them carefully.

1) Use OpenMP to parallelize the sequential game of life code from Assignment 1. Compare and evaluate several different approaches to getting good performance. For each produce both timing and speedup graphs.Which method works best and why?

2) Your are to write a sequential C program that implements Counting sort and then create a parallel version of it using OpenMP. First read the Dr. Dobbs article on Parallel Counting Sort Using Thread Building blocks. You can follow its lead but you are to use OpenMP (Not TBB). Also you are to implement it sor that is sorts records with integer keys rather than just integers.

The pseudocode Counting Sort algorithm is as follows:

countingsort(A[], B[], k)
	for i = 1 to k do
	   C[i] = 0
	   
	for j = 1 to length(A) do
	   C[A[j].key] = C[A[j].key] + 1
	   
	for 2 = 1 to k do
	   C[i] = C[i] + C[i-1]

	for j = 1 to length(A) do
	   B[C[A[j].key]] = A[j]
	   C[A[j].key] = C[A[j].key] - 1

Although this may look complicated, it is actually a very simple and clever algorithm.
Array A[ ] stores the initial data to be sorted. It assumes that each item is a record which includes an integer key in the range 1 to k.
Array C[ ] is used to count the occurrences of the data values
Array B[ ] is used to store the final, sorted, data.
See "Introduction to Algorithms" by Cormen, Leiserson, Revest, (Stien) for details.

Using OpenMP create and evaluate an efficient parallel versions of this code. You should submit a discussion with speedup and timing charts along with your code.

Note: For each program you are asked to evaluate its performance carefully. More details on the expected analysis and performance evaluation to follow in class.