Sorting in a distributed environment is complicated by the fact we will not have all of the data available on one processor.
In some cases, the amount of data would not even fit into the memory of a single machine at once.
To handle this, we can sort our data according to the following rules:
The goal of our parallel sorting algorithm will be to make these two true. This can be done without ever loading all of the data onto any one process.
The basis for one method of distributed sorting is the "odd-even transposition sort". The serial version of this algorithm is given below:
For example, if our data is as follows:
6, 9, 3, 1
Then we would start with phase 0. This is an even phase, so we will compare/swap each even/odd pair. This means pairs where the first element is an even index and the second is odd:
(6, 9) (3, 1)Becomes:
6, 9, 1, 3
Now we move to phase 1. This is an odd phase so we will compare swap the odd/even pairs:
6, (9, 1), 3Becomes:
6, 1, 9, 3Next, we have phase 2, which is an even phase:
(6, 1) (9, 3)Becomes:
1, 6, 3, 9,Lastly, we have phase 3 which is an odd phase:
1, (6, 3), 9Becomes:
1, 3, 6, 9
How many phases will we need in the worst case with N values?
The odd-even transposition algorithm can be extended to work in a distributed system.
In this scenario, each process will store its own portion of the data. It will keep its own data sorted.
It will then share its data with either the process to its left or right based on the phase we are in.
This algorithm is given below:
This is an extension of the serial algorithm, where we are comparing and swapping a subset of the data rather than a single element.
How could we implement this algorithm with an MPI program?
Copyright © 2022 Ian Finlayson | Licensed under a Attribution-NonCommercial 4.0 International License.