Lab 8. Parallel Sorting (1).
Task 1.
Develop an MPI program for the bucket sort problem.
-
Start from the program SimpleSort.c.
-
Follow the steps given in the tutorial:
o Bcast the whole array onto processors.
o Collect the elements that fall in the bucket of processor rank.
o Sort these elements.
o Gather the number of elements of each bucket.
o Learn about the syntax of Gatherv
o Gatherv the buckets back to the arrays a.
-
Test the program and evaluate the execution time for
various numbers of processors.
-
Ask some questions about the code you wrote:
o What is the complexity in terms of communication and computation?
o For
that, assume that the buckets have the same number of elements.
Task 2.
Develop an MPI program for the ranking sort problem.
-
Start from the program SimpleSort.c.
-
Put in the basic elements of this sort in the program:
o Bcast the whole array onto processors.
o Processor
rank generates the array local_ranking = (local_ranking[i], i=0,1,…,n/size-1).
§ local_ranking[i] is the rank in
the whole array of the element array[rank*n/size+i]
o Gather
local_ranking to root in the array ranking.
o If
root then reorganise the array into the sorted array.
-
Test the program and evaluate the execution time for
various numbers of processors.
-
Ask some questions about the code you wrote:
o What
is the complexity in terms of communication and computation?
o What
is the amount of serial part of the sequential computation? How Amdahl’s law is
applied for this computation? Is this in line with the execution times you have
got?
o How
can we skip this serial part of how you can do it without the step of
re-organising the array into the sorted array.
[TRY IT] Task 3. Develop a Divide & Conquer program for the merge sort problem.
- Start from the program MergeSort.c.
- Draw the D&C tree for p processors, with p power of 2.
- Stage 1 computation is the divide the data from the root to the leaves processors.
- Stage 2 is to sort the local array.
- Stage 3 is to a) receive an array from below, b) merge it with the local array and c) send it over above.
Remark: Use the following picture to understand where data is sent or received from an active node rank.
