Homework 2
Due by 11:59 PM on April 15, 2012
100 points
Problem 1. (100 points) [Keycode: HW2P1]
You will develop a multithreaded C program for sorting in increasing order
an array of N real numbers.
You are to use the mergesort sorting algorithm.
Your program should be invoked as
mt_sort <fn_in> <fn_out> <K>
where fn_in and fn_out are the names of the ASCII files that holds
the input and output data respectively, and K the maximum number of threads
allowed at any point of time during your programs execution.
You may assume that N and K are both powers of 2.
You are required to use POSIX Threads on your Linux system to complete this assignment.
Your program writes the sorted data in the fn_out file. Before exiting, your program prints on the standard output the total CPU time (in both user and kernel modes) for all its threads (including the main program thread).
Your program should use the maximum amount of parallelism and achieve the maximum improvement of running time when using a maximum of K threads with respect to when using only 1 thread.
Format of the input and output data files:
- the first line contains the number of elements (numbers to sort), followed by all the elements, one element per line.
- Sample datafiles are available here
What to submit
Submit your answer to each problem electronically using your git repository. You should submit your solution to the problem in a directory in your git repository that matches the keycode of the problem. You must include all source code for your solution, as well as a Makefile to build it (I should be able to type "make" into the checked out directory and build the program). You should include a README file with any references that you used in desigining your solution, as well as any other information that we should know about your program. You should not submit any sort of tarball or any other binary files (including built versions of your programs).