分别用PThread和OpenMP两个不同的库，练习排序算法中的多线程的使用方法。
Introduction
In this assignment, you have to solve a problem using multi-threading. You have to write two versions, one using PThread (asg3-pthread), one using OpenMP (asg3-openmp).
The program shall take two files as input. Each input file contains a list of integers. The job of the program is to output a sorted list of unique integers that are common between the two files.
Usage
To run the Pthread program:
./asg3-pthread [inputfile1] [inputfile2] [outputfile] [ThreadNum]
To run the OpenMP program:
./asg3-openmp [inputfile1] [inputfile2] [outputfile] [ThreadNum]
File Format
- inputfile1 : The input file contains only 2 lines. The first line shows the number of integers in this file. The second line shows the integers, separated by one space character.
- inputfile2 : Same as the above.
- outputfile : The output file should list the result in ascending order, line by line.
Example
If we execute the following:
./asg3-openmp testcases/C0/input1.txt testcases/C0/input2.txt res/output.txt 4
./asg3-pthread testcases/C0/input1.txt testcases/C0/input2.txt res/output.txt 4
Then, we expect the program executes using 4 threads and generates the following content to output.txt:
0
1
2
5
6
That is, we expect the output contains a sorted list of unique integers (in ascending order) that appear in both input1.txt and input2.txt.
Grading
The grading of this assignment is divided into two parts: (A) correctness and (B) scale-out.
Part (A) Correctness
Its aim is to check the correctness of your program under multi-threading. For this part,
- 12 test cases, C1, C2, …, C12, in total.
- All test cases will be tested under 4 threads.
- Each test case will feed the same input data to test your asg3-pthread and your asg3-openmp.
Different test cases would have different input data, in different sizes and orders. For example, sometimes the data may contain duplicate but sometimes not. The largest integer in the test data would be ≤ 100, 000, 000.
Part (B) Scale-out
A multi-threaded program is a BAD program if it does not scale-out - it runs slower with more threads! For example, if your program finishes the job in 60 seconds using 1 thread but finishes the job in 78 second using 2 threads, then your multi-threaded program is completely useless. This part therefore grades whether your program can scale-out. For this part,
- 3 test cases, S0, S1, S2, in total. They test your programs using very large input data.
- The first test case (test case S0) is to ensure that your program can run faster given more threads. That is, in addition to correctness, it also checks the real time (by the time tool) 1 of your PThread and OpenMP programs to see if: real-time-4threads < real-time-3threads < real-time-2threads < real-time-thread This test case takes NO marks. But passing this case is the prerequisite of executing the next two scale-out oriented test cases for you.
- Test cases S1 and S2 run your programs on large input using 4 threads and measures their real execution time in addition to their correctness. Each test case will feed the same input data to test your asg3-pthread (X pthread marks) and your asg3-openmp (X openmp marks)
Bonus
Bonus will be awarded to the following students.
- Top Coder Award (TCA): the one who gets the highest mark in Part A plus Plus B.
- Top Local Coder Award: the local one who gets the highest mark in Part A plus Plus B.
- Top Non-Local Coder Award: the non-local one who gets the highest mark in Part A plus Plus B.
- Top Female Coder Award: the lady who gets the highest mark in Part A plus Plus B.
- Top Male Coder Award: the gentleman who gets the highest mark in Part A plus Plus B.
The condition is that their programs must pass all test cases in Part (A) and Part (B). A student can get at most one award.
Your assignment
Submission
You are required to submit two source codes asg3-pthread.c and asg3-openmp.c files as one zip file to eLearning.
Notes and Tips
- Hardcoding won’t work. We will use another similar set of test data and expected output when grading. The good news is that, if you pass all the test cases during the assignment, you should also pass all the test cases during grading (unless you do hardcoding).
- The grading will be fully automated. The grading platform is our course’s VM: Ubuntu 14.04 32-bit, 4 cores, 1GB memory. Once we start the grading processing, we reserve the right to deduct marks from you for any request that requires TA’s extra manual effort.
- Use the synchronization primitives (e.g., condition variable) judiciously in order to get a good balance between correctness and performance. For example, deliberately define the critical section to be the whole program can make your program correct (Part A) but cannot scale-out (Part B).