MPI Lab 12 Parallel Programming Application 4
Sorting in Parallel: Odd-Even Transposition Sort
Part 2: More than one number per processor

Assignment
Program the Odd-Even Transposition sort using MPI and multiple processors with more than one number per processor.

  • Version 2 of Odd even sort
  • Use multiple values on each processor.
    Ex. 32 values on 4 proacessors, 128 values on 4 processors, etc.
  • See Fig. 9.6, page 220
  • oddEvenStarter.c

  • Example run through, using 12 values to be sorted: 21, 16, 35, 50, 13, 20, 32, 45, 24, 30, 8, 46.
    In this example, four processors are used to sort these twelve values.

    Values are arranged n/p = 12/4 = 3 numbers per processor. Array A's are on odd processors, and array B's are on the even processors: 

         0          1         2        3       
   21,16,35  50,13,20  32,45,24  30,8,46 
     B          A         B        A
    Part 1: The Even phase

    Step 1: If processor P has an odd rank, these odd processors send a copy of their array A to the even processor on the left: 

              0                  1                    2                 3
 21,16,35  50,13,20  <--  50,13,20       32,45,24  30,8,46  <--  30,8,46
    Step 2: The even processors each sort the combined values (using some kind of serial sort), and each even process sends back the upper half of their values to array A in the odd processors to the right:
    (Only if the even processor is not the last process) 
             0                  1                    2                 3
 13,16,20,21,35,50      50,13,20         8,24,30,32,45,46       30,8,46

     0               1             2              3
 13,16,20  -->   21,35,50      8,24,30  -->   32,45,46
    At this point, the maximum half of each section of the array is stored on the odd processors, and the minimum half is stored in the even processors.

    Part 2, the Odd phase.

    Step 1: If processor P is odd, send a copy of it's array to processor P+1 to the right:
    (Only if the odd processor is not the last processor) 

         0            1                 2                3
 13,16,20     21,35,50 -->  21,35,50  8,24,30     32,45,46
    Step 2: The Even processors (other than process 0) sort the combined values and send the minimum half back to the processor on their left. 
         0            1               2                3
 13,16,20     21,35,50     8,21,24,30,35,50     32,45,46    

     0            1              2            3
 13,16,20      8,21,24  <--   30,35,50     32,45,46
    The algorithm now repeats.

    Part 1: Repeat the Even phase.

    Current state of the values on the eight processors: 

         0            1            2            3
 13,16,20      8,21,24     30,35,50     32,45,46
    Step 1: Odd processors send their array to the left 
     
        0                   1                2                   3
 13,16,20  8,21,24  <--  8,21,24     30,35,50 32,45,46  <--   32,45,46
    Step 2: Even processors sort the combined values and send the maximum half to the odd processor on the right (not if the even processor is the last one): 
            0                1                2                 3
 8,13,16,20,21,24     8,21,24     30,32,35,45,46,50      32,45,46  

        0           1             2            3
    8,13,16 -->  20,21,24     30,32,35 -->  45,46,50
    At this point note that that values are sorted. I think (?) this process normally needs to be repeated logn times: log(12) = 3.6 so I think you repeat this 3 or 4 times(?) How can we verify this?

    The values on the process can be collected (MPI_Gather) back onto processor 0.