Description
HW1: Parallel Odd-Even Transposition Sort
Description:
In this homework, you are required to write a parallel odd-even transposition sort by using MPI. A
parallel odd-even transposition sort is performed as follows:
Initially, m numbers are distributed to n processes, respectively.
1. Insides each process, compare the odd element with the posterior even element in odd
iteration, or the even element with the posterior odd element in even iteration respectively.
Swap the elements if the posterior element is smaller.
2. If the current process rank is P, and there some elements that are left over for comparison in
step 1, Compare the boundary elements with process with rank P-1 and P+1. If the posterior
element is smaller, swaps them.
3. Repeat 1-2 until the numbers are sorted.
You need to use MPI to design the program. The number of processors used to execute the
program is n that is much less than m. The following gure is an example to design your MPI
program:
P1, P2, P3 are three dierent processes
There are three operators that might need the communication among processes, i.e.,
comparison, swap, left over (boundary elements that should be compared).
Requirement
The array data should be randomly generated.
You need to implement two versions of the tasks including a MPI version and a Sequential
version.
The implementations of both versions need to be submitted in separate files.
You need to print the following information that identies your name, student id, assignment
id, implementation version, running time of the whole program. (see following as an
example.)
You need to print out the 20-dims input array and the output array as running results of the
submitted code.
You need to specify the command line that you compile and run your program in your
report.
You need to compare the performance of different implementations or configurations in
your report:
the number of cores used in the MPI program. (Only 1-20 cores comparison is enough)
the size of the random generated array. (Small, Medium, Large)
MPI vs Sequential
More if you have
You need to include a figure describing the flow chart of your MPI program
The report should be in appropriate format, with a title page, introduction session to
introduce the basic problem and task, method session to describe your parallel
implementation, result session to compare performance under different configurations, and
a conclusion session which concludes your experiment results.
Where and What to Turn in Your Homework
Please turn in below several material:
Report
Source codes for you program for both sequential and MPI implementation
Zip all your material and submitted them to BlackBoard. And make sure to name it
studentid.zip
No late submission is accepted.
Tips
1. Try to start doing your homework earlier. Since the current server has very limited resource,
and everybody will wait in a queue to submit their jobs. If you start your homework too late,
you may not be able to finish your experiments.
2. Do not run your program without submitting it using the qsub command. Although we use
some tricks to forbid direct running, but some of you may find some ways to run it directly,
and it will ruin other’s student experiment data and you will not be able to get a valid
experiment data.
