辅导COMP3400、辅导C/C++编程、讲解Operating Systems、辅导C/C++语言
辅导R语言程序|解析Java程序
Wentworth Institute of Technology
COMP3400 – Operating Systems
Project
The goal of the project is to use threads to get performance gain on a uniprocessor or on a multicore processor. The basic idea is to divide the problem into subtasks, assign each subtask to a separate thread and then combine the results to get the complete solution. The strategy is called the divide and conquer.
A single task, sorting a file, is divided into subtasks which are delegated to separate threads. Merge-sort, in which the array to be sorted is divided into smaller arrays, is a divide and conquer algorithm. Each small array is sorted individually, and the individual sorted arrays are merged in pairs to yield larger sorted arrays. The pairwise merging continues until the entire array is sorted.
Generally, merge-sort starts with small arrays, which can be sorted efficiently with a simple algorithm such as qsort, as shown below.
Array to be sorted
Wait (thread 1)
Thread 0 wait (thread 2)
Thread 1
Wait (thread 3)
Thread 2
Thread 3
Sort Phase Merge Phase
After the sort phase, the sorted subarrays are merged in pairs to generate larger sorted arrays. The merging continues until completion.
The environment and input for this experiment consists of:
1.Linux OS (Linux Server in the Lab)
2.pthreads
3.Memory mapped file so Merge-sort can sort and merge the file in memory
4.You will be provided a test file consisting of 128, 64 byte records for testing and debugging. Each record has an 8 byte key and 56 byte data.
5.You will also be provided a file consisting of one million fixed size records of 64 bytes each to run the experiment
The program finds the number of cores, N, programmatically and displays it to the user. The user specifies the threads to use on the command line.
Run the experiment with 2, 4, 8, …. N threads and display the elapsed time for each run. If the number of cores is <= 2, you can stop the test after 8 threads. The number of threads used must be a power of 2.
Running the experiment
Name your application sortMerge. The syntax of the command to run the program is
./sortMerge
1.Run sortMerge with the test data file and record the elapsed times. Save the sorted test file.
2.Run sortMerge with the one million records data file and record the elapsed times.
3.Graph the elapsed times versus the number of threads from step #2.
Submissions
1.All Source files (.c and .h)
2.Output file, showing the user interactions, and the graph showing elapsed times for the various runs.
3.The sorted test file.