Assignment 1 (due Wednesday, 13 September, 10 pm)

In this assignment, you will implement merge sort using the multiprogramming paradigm. This assignment can be done either individually or in groups of two. Assignments submitted with more than two group members will not be accepted. This assignment can be done either in JAVA or in C.

You are free to choose either option.

What to do?

Java:

As you know, merge sort is an algorithm where the array of numbers is split into two halves, each half is sorted recursively using merge sort, and the sorted halves are merged. For this assignment, you will use the java thread package. You will use a thread to run every recursive call of merge sort i.e., at each stage you will create two threads to merge sort the two halves. When the two threads finish sorting, the parent thread merges the two halves by itself.

You will also measure a couple of important parameters of this program. In particular, you will measure the time taken to sort the entire array, and the number of threads that were used to do so. You must vary the size of the array to obtain the values for time taken and number of threads. You should be able to find out the optimal number of threads that the system can support efficiently.

In the second part of this assignment, you would port the same program to UNIX OS. Since java is machine independent, you should not have any problems in porting the program to UNIX. You would carry out the same measurements in UNIX.

For a tutorial on how to use threads see online java tutorial .

C:

As you know, merge sort is an algorithm where the array of numbers is split into two halves, each half is sorted recursively using merge sort, and the sorted halves are merged. For this assignment, you will use the POSIX thread libraries in UNIX. You will spawn a thread to run every recursive call of merge sort i.e., at each stage you will create two threads to merge sort the two halves. When the two threads finish sorting, the parent thread merges the two halves by itself. You could use the pthread_join system call to wait for the child threads to finish.

You will also measure a couple of important parameters of this program. In particular, you will measure the time taken to sort the entire array, and the number of threads that were used to do so. You must vary the size of the array to obtain the values for time taken and number of threads. You should be able to find out the optimal number of threads that the system can support efficiently.

For this part of the assignment, you would need to use pthread_create , pthread_exit and pthread_join among other commands. For a detailed list of pthread commands, go to <pthread.h>. You could also have a look at a sample program. You could also have a look at this site on Introduction to Programming with Threads.

What to submit?

You should submit the following things as a part of this assignment.

1. The java/C program or programs used to implement merge sort.

2. A file called README.txt where you give a tutorial on how to compile and run a program. This file should also contain the names, netids and cornellids of all the individuals in the group.

3. Relevant graphs and a file called RESULT.txt where you give the analysis of your experiment.

How will you be graded?

The following will play a crucial role in your grades for this assignment.

1. Correctness of the java/C programs written to implement merge sort.

2. Rigorousness of the experiment and analysis of results.

3. Clarity of the java/C programs (comments!!!).

4. Ease of using the README to test your programs and results.

What is a rigorous analysis?

The quantities of study here are the array size and therefore the number of threads and the time elapsed. A rigorous analysis would include testing for different values of array size (therefore number of threads) and giving a graphical interpretation. This should be followed by your interpretation of the results.