Task 1: All Pairwise Computation is defined as performing computation (e.g., correlations) between every pair of the elements in a given dataset. In this assignment, we consider a set of N sequences, each being of length M, which are stored in a two-dimensional (2D) matrix of size N by M (i.e., N rows and M columns). We then calculate a dot product for every possible pair of sequences (row vectors) in the matrix.

A dot product of two sequences, or vectors is defined as

M − 1

x · y =  xi yi

i =0

If we allow a vector to pair with itself, then there are N(N+1)/2 such pairs in total for Nvectors. Assume N is equal to 5 for example. We then have the following 15 vector pairs:

(0, 0)(0, 1)(0, 2)(0, 3)(0, 4)

(1, 1)(1, 2)(1, 3)(1, 4)

(2, 2)(2, 3)(2, 4)

(3, 3)(3, 4)

(4, 4)

In the above dot product formula, (i, j) denotes the pair of sequences i and j. After the dot product computation for pair (i,j), we will have a single value as the output.

In this task you are asked to design an efficient parallel algorithm to solve the above problem on a shared-memory computing platform and implement the algorithm using C and OpenMP.

In your design:

•     Since the dot products of (i,j) and (j, i) will give the same result, you must only compute the dot product of (i,j) for i ≤ j and store the results in the upper triangle of a 2D matrix as shown in the above example;

•     You must consider load balancing across the threads;

•    You must use loop unrolling technique to unroll at least two for loops with unrolling factor equal to 4 to improve the performance.

In your implementation:

•     Your program needs to ask for N, M and T (i.e., the number of threads to be created in executing your program) as user defined parameters;

•    After the parallel  computation, your main program must  conduct  a  self-check  for correctness, i.e., perform a sequential computation using the same data set and then compare the result of this computation with the parallel computation result.

The implementation must be in C and OpenMP.

Task 2: Gaussian elimination with partial pivoting is a technique used to solve a system of linear equations. It adds multiple of each row to later rows to transform the matrix into triangular matrices L and U. Partial pivoting technique is applied to make the algorithm stable, that is, in each elimination iteration rows are swapped so that the leading element A(i,i) is the largest in the leading column to prevent division by zero. A serial pseudocode is give as follows:

// Gaussian elimination with partial pivoting

for (i=0; i<n- 1; i++)

//find and record k where  |A(k,i)|=maxi≤j<n |A(j,i)|

if (|A(k,i)|== 0)

//exit with a warning that A is singular, or nearly so

else if (k != i)

//swap row i and row k of A

//store multiplier in place of A(j,i)

for (j=i+1; j<n; j++)

A[j][i] = A[j][i] / A[i][i]; //now each  |quotient| ≤ 1

//subtract multiple of row A(i,:) to zero out A(j,i)

for (j=i+1; j<n; j++)

for (k=i+1; k<n; k++)

A[j][k] − = A[j][i] * A[i][k];

In this task you are asked to design and implement an efficient parallel algorithm to solve the above problem on a shared-memory computing platform.

In your implementation:

•    Your program needs to ask for N and T (i.e., the number of threads to be created in executing your program) as user defined parameters;

•    After the parallel  computation, your main program must  conduct  a  self-check  for correctness, i.e., perform a sequential computation using the same data set and then compare the result of this computation with the parallel computation result.

The implementation must be in C and OpenMP.

Report: You must write a report. The report should be concise, clear (3-6 A4 pages) and contain the following sections for each task:

1.   Problem definition and requirements

2.   Parallel algorithm design and implementation

3.   Testing and performance evaluation

4.   Discussion

5.   Known issues in program

6.   Manual (e.g. how to compile and run the program, input and output)

Your assignments will be marked on correctness of results, the efficiency of your algorithm, program logic and readability, and quality ofyour report.

You MUST attempt this assignment individually.