Implementation of the parallel odd-even transposition sort algorithm with Open MPI

Today I want to share with you my experiments with Open MPI, an open sources implementation of the MPI interface. Open MPI is a C library that allow you to write parallel programs and run them on a computer cluster.
I start my experiments during labs of the parallel programing course at ESIAL. We implements servals algorithm including the parallel odd-even transposition sort algorithm I will show today.




Here is a quick explanation of the algorithm :

1. It starts by distributing n/p sub-lists (p is the number of processors and n the size of the array to sort) to all the processors.
2. Each processor then sequentially sorts its sub-list.
3. The algorithm then operates by alternating between an odd and an even phase :
   
1. In the even phase, even numbered processors(processor i) communicate with the next odd numbered processors (processor i+1). In this communication process, the two sub-lists for each 2 communicating processes are merged together. The upper half of the list is then kept in the higher number processor and the lower half is put in the lower number processor.
   
2. In the odd phase, odd number processors (processor i) communicate with the previous even number processors (i-1) in exactly the same way as in the even phase.

This algorithm is not efficient, the average complexity is 0(n^2), but the aim isn't to write a fast program but to experiment Open MPI.

Implementation
The first step is to distribute a sub list to each process, the master process send to all process a sub-array, to do that we use the MPI_Scatter() function :

1:  int *subArray = malloc(N/hostCount * sizeof(int));  
2:       if(rank == 0) { /* The master send data to everyone */  
3:            MPI_Scatter(arrayToSort,N/hostCount,MPI_INT,subArray,N/hostCount,MPI_INT,0,MPI_COMM_WORLD);  
4:       }  

After that each process has to receive data, we use MPI_Scatterv(), we need 2 particular array : displs that specifies the displacement of sub-array relative to arrayToSort and sendcnts that specifies the number of elements to send to each host.

1:  int *displs = malloc(hostCount * sizeof(int));  
2:  int i;  
3:  for (i=0;i<hostCount;i++) {  
4:       displs[i] = i*(N/hostCount);  
5:  }  
6:  int *sendcnts = malloc(hostCount * sizeof(int));  
7:  for (i=0;i<hostCount;i++) {  
8:       sendcnts[i]=N/hostCount;  
9:  }  
10:  /* reieve data */  
11:  MPI_Scatterv(arrayToSort,sendcnts,displs,MPI_INT,subArray,N/hostCount,MPI_INT,0,MPI_COMM_WORLD);  
12:  free(displs);  
13:  free(sendcnts);  

The next step, is to write a sequential sort algorithm. I choose the odd-even sort algorithm. Here is my C function :

1:  void sequentialSort(int *arrayToSort, int size) {  
2:       int sorted = 0;  
3:       while( sorted == 0) {  
4:            sorted= 1;  
5:            int i;  
6:            for(i=1;i<size-1; i += 2) {  
7:                 if(arrayToSort[i] > arrayToSort[i+1])  
8:                 {  
9:                      int temp = arrayToSort[i+1];  
10:                      arrayToSort[i+1] = arrayToSort[i];  
11:                      arrayToSort[i] = temp;  
12:                      sorted = 0;  
13:                 }  
14:            }  
15:            for(i=0;i<size-1;i+=2) {  
16:                 if(arrayToSort[i] > arrayToSort[i+1])  
17:                 {  
18:                      int temp = arrayToSort[i+1];  
19:                      arrayToSort[i+1] = arrayToSort[i];  
20:                      arrayToSort[i] = temp;  
21:                      sorted = 0;  
22:                 }  
23:            }       
24:       }  
25:  }  

The third step is the odd-even phases. For this step we need 2 functions. One function to send data to the next host and keep the lower part of the to arrays. And another one to send data to the previous host and keep the higher part.

1:  /* Parameter :   
2:   * subArray : an integer array   
3:   * size : the size of the integer  
4:   * rank : the rank of the host  
5:   * Send to the next host an array, recieve array from the next host  
6:   * keep the lower part of the 2 array  
7:   */  
8:  void exchangeWithNext(int *subArray, int size, int rank)  
9:  {  
10:       MPI_Send(subArray,size,MPI_INT,rank+1,0,MPI_COMM_WORLD);  
11:       /* recieve data from the next odd numbered host */  
12:       int *nextArray = malloc(size*sizeof(int));  
13:       MPI_Status stat;  
14:       MPI_Recv(nextArray,size,MPI_INT,rank+1,0,MPI_COMM_WORLD,&stat);  
15:       /* Keep the lower half of subArray and nextArray */  
16:       lower(subArray,nextArray,size);  
17:       free(nextArray);  
18:  }  
19:  /* Parameter :   
20:   * subArray : an integer array   
21:   * size : the size of the integer  
22:   * rank : the rank of the host  
23:   * Send to the previous host an array, recieve array from the previous host  
24:   * keep the higher part of the 2 array  
25:   */  
26:  void exchangeWithPrevious(int *subArray, int size, int rank)  
27:  {  
28:       /* send our sub-array to the previous host*/  
29:       MPI_Send(subArray,size,MPI_INT,rank-1,0,MPI_COMM_WORLD);  
30:       /* recieve data from the previous host */  
31:       int *previousArray = malloc(size*sizeof(int));  
32:       MPI_Status stat;  
33:       MPI_Recv(previousArray,size,MPI_INT,rank-1,0,MPI_COMM_WORLD,&stat);  
34:       /* Keep the higher half of subArray and previousArray */  
35:       higher(subArray,previousArray,size);  
36:       free(previousArray);  
37:  }  

Then we can write easily the odd-even phase :

1:  i =0;  
2:       for(i=0;i<hostCount;i++) {  
3:            /* even phase */  
4:            if (i%2==0) {  
5:                 /* even numbered host */  
6:                 if(rank%2==0) {   
7:                      /* even numbered host communicate with the next odd numbered host */  
8:                      /* make sure the next odd exits */  
9:                      if(rank<hostCount-1) {  
10:                           /* send our sub-array to the next odd numbered host  
11:                            * receive data from the next odd numbered host  
12:                            * Keep the lower half of our array and of the next host array's  
13:                            */  
14:                           exchangeWithNext(subArray,N/hostCount,rank);  
15:                      }  
16:                 } else {   
17:                      /* odd numbered host communicate with the previous even numbered host */  
18:                      /* make sure the previous even exits */  
19:                      if (rank-1 >=0 ) {  
20:                           /* send our sub-array to the previous even numbered host  
21:                            * receive data from the previous even numbered host  
22:                            * Keep the higher half of our array and of the previous host array's  
23:                            */  
24:                            exchangeWithPrevious(subArray,N/hostCount,rank);  
25:                      }  
26:                 }  
27:            }  
28:            /* odd phase */  
29:            else {   
30:                 /* odd host */  
31:                 if(rank%2!=0) {   
32:                      /* In the odd phase odd numbered host communicate with the next   
33:                       * even numbered host make sure the next even exits */  
34:                      if (rank<hostCount-1) {  
35:                           /* send our sub-array to the next even numbered host  
36:                            * receive data from the next even numbered host  
37:                            * Keep the lower half of our array and the next host array's  
38:                            */  
39:                           exchangeWithNext(subArray,N/hostCount,rank);  
40:                      }  
41:                 }   
42:                 /* even host */  
43:                 else {  
44:                      /* In the odd phase even numbered host communicate with the previous  
45:                       * odd numbered host make sure the previous host exits */  
46:                      if (rank-1 >=0 ) {  
47:                           /* send our sub-array to the previous odd numbered host  
48:                            * receive data from the previous odd numbered host  
49:                            * Keep the higher half of our array and of the previous host array's  
50:                            */  
51:                            exchangeWithPrevious(subArray,N/hostCount,rank);  
52:                      }  
53:                 }  
54:            }  
55:       }  

Now our array is sorted, the lower element own to the host with the rank 0 and the higher to p-1. We just need to gather data, we use MPI_Gather()

 MPI_Gather(subArray,N/hostCount,MPI_INT,arrayToSort,N/hostCount,MPI_INT,0,MPI_COMM_WORLD);  

Performances
The question is : what is the execution time of the parallel algorithm compare to the sequential one. Well it's pretty good, on average in a cluster of 8 machines and for an array of 128 000 elements the parallel algorithm run in 1.50 s, while the sequential one run in 81.71 s on a single machine.
We are in a case of super-linearity because sort a sub-array 8 times smaller than the original array run 64 times faster.

Feel free to reproduce this experiment : you can use my C program for the parallel version as well as my sequential one.