## Description

Part 1: Implement Fibonacci Sequence using Pthreads and Win32 Thread (50 points).

The Fibonacci sequence is the series of numbers 0, 1, 1, 2, 3, 5, 8, …. Formally, it can be expressed as:

That is, after two starting values, each number is the sum of the two preceding numbers. The Fibonacci

numbers for n = 0, 1, 2, … ,20 are:

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17 F18 F19 F20

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Part 1a (25 points): Write a multithreaded program that generates the Fibonacci sequence using

Pthreads. This program should work as follows: The user will enter on the command line the number of

Fibonacci numbers that the program is to generate. The program will then create a separate thread that

will generate the Fibonacci numbers, placing the sequence in data that can be shared by the threads (an

array is probably the most convenient data structure). When the thread finishes execution, the parent

thread will output the sequence generated by the child thread. Because the parent thread cannot begin

outputting the Fibonacci sequence until the child thread finishes, this will require having the parent thread

wait for the child thread to finish, using the thread join techniques described in class.

Part 1b (25 points): Write a multithreaded program that does the same Fibonacci calculate as stated in

Part 1a using Win32 thread.

Part 2 a: Implement Matrix Multiplication using Pthreads (30 points)

Background of Matrix Multiplication

Given two matrices, A and B, where matrix A contains M rows and K columns and matrix B contains K

rows and N columns, the matrix product of A and B is matrix C, where C contains M rows and N

columns. The entry in matrix C for row i, column j, denoted as Ci,j, is the sum of the products of the

elements for row i in matrix A and column j in matrix B. That is,

∑

For example, if A is a 2-by-3 matrix and B is a 3-by-2 matrix, the result matrix will be a 2-by-2 matrix.

Passing Parameters to Each Thread

The parent thread will create M ×N worker threads, passing each worker the values of row i and column j

that it is to use in calculating the matrix product. This requires passing two parameters to each thread. The

easiest approach with Pthreads is to create a data structure using a struct. The members of this structure

are i and j, and the structure appears as follows:

/* structure for passing data to threads */

Struct v

{

int i ; /* row */

int j ; /* column */

};

The Pthreads program will create the worker threads using a strategy similar to that shown below:

/* We have to create M ×N worker threads */

for ( i = 0; i < M, i++)
for ( j = 0; j < N; j++ ) {
struct v *data = (struct v *) malloc (sizeof (struct v)) ;
data->i = i

data->j = j

/* Now create the thread passing its data as a parameter */

}

}

The data pointer will be passed to the pthread_create (), which in turn will pass it as a parameter to the

function that is to run as a separate thread.

Waiting for Threads to Complete

Once all worker threads have completed, the main thread will output the product contained in matrix C.

This requires the main thread to wait for all worker threads to finish before it can output the value of the

matrix product. Several different strategies can be used to enable a thread to wait for other threads to

finish. In this example, the main thread has to wait for multiple threads to finish before it can continue its

execution.

The following code shows how you could join on ten threads using the Pthreads:

#define NUM_THREADS 10

pthread_t workers[NUM_THREADS];

for (int i = 0; i < NUM_THREADS; i++)
pthread_join(workers[i], NULL);
For this project, you need to calculate each element Ci,j in a separate worker thread. This will involve
creating M × N worker threads. The main (or parent) thread will initialize the matrices A and B and
allocate sufficient memory for matrix C, which will hold the product of matrices A and B. These matrices
will be declared as global data so that each worker thread has access to A, B, and C.
Matrices A and B can be initialized statically, as shown below:
#define M 3
#define K 2
#define N 3
int A [M] [K] = {{1,4}, {2,5}, {3,6}};
int B [K] [N] = {{8,7,6}, {5,4,3}};
int C [M] [N] ;
Your code should be able to calculate the C = A× B and print out the correct matrix C. I may
change the elements value of A and B to test your code but you can assume I will not change the
value of M, K, and N.
Part 2b: Answer the following questions (20 points)
Now you have generated a multithreaded program which can multiply a 3-by-2 matrix and a 2-by-3
matrix. Please answer the following questions:
1. We can also write a program to do matrix multiplication without using multithreading. What are
the advantages and disadvantages of using multithreading? (5 points)
2. Is your code still applicable for multiplying two 100-by-100 matrices? If yes, why? If no, how
will you change your current code to make it applicable? You only need to write down the key
changes and you can use pseudo code. (5 points)
3. Is your code efficient in the scenario of multiplying giant matrices, say one million by one million
matrices? If yes, why? If not, what are the potential performance problems? (Hint: think about the
overhead of creating thread and data locality issue). How to solve these problems? (10 points)
Part 3: How many 99s (Pthreads and OpenMP)? (50 points).
The following sequential code will count how many 99s in an array.
#include

#include

#include

using namespace std;

int main()

{

int count = 0, i;

int const size = 100000;

int myArray [size];

double start_time, end_time;

//initialize random number generator

srand((unsigned)time(NULL));

// Initialize the array using random numbers

for (i = 0; i < size; i++)
myArray[i] = rand() % 100;
//Serial Code
start_time = omp_get_wtime();
for (i = 0; i < size; i++)
if (myArray[i] == 99)
count ++;
end_time = omp_get_wtime();
printf ("The serial code indicates that there are %d 99s in the array.\n\n", count);
printf ("The serial code used %f seconds to complete the execution.\n\n", end_time - start_time);
return 0;
}
Part 3a (20 points): Write the correct and efficient multithreading code using OpenMP. Record the
execution time of your parallel code and calculate the speedup when using 2 threads, 4 threads and 8
threads. Your score will be based on the correctness and speedup of your parallel code.
Part 3b (30 points): Write the correct and efficient multithreading code using Pthreads. Record the
execution time of your parallel code and calculate the speedup when using 2 threads, 4 threads and 8
threads. Your score will be based on the correctness and speedup of your parallel code.