Parallelize python Odd-Even Sort sorting algorithm

Question

I have developed the following serial code to perform the Odd-Even Sort sorting, which first sorts even/odd and then odd/even.

import time

def oddevenSort(x):
    sorted = False
    while not sorted:
        sorted = True

        #ordena indices par/impar
        for i in range(0, len(x)-1, 2):
            if x[i] > x[i+1]:
                x[i], x[i+1] = x[i+1], x[i]
                sorted = False

        #ordena indices impar/par
        for i in range(1, len(x)-1, 2):
            if x[i] > x[i+1]:
                x[i], x[i+1] = x[i+1], x[i]
                sorted = False
    print(x)
    return x


tic = time.time()
oddevenSort([4,3,2,1,3,6,9,1,2,3,54,76,98,12,333,331,33,1,7,9])
toc = time.time()

print("tempo gasto para processar = " + str(toc-tic)+"s")

Now I need to create for this same sorting algorithm a parallel code in python to be able to calculate the Speedup (gain of time between running serial code VS parallel code).

To first approach what I was having was to create a thread for even/odd ordering and another for odd/even ordering, but I can’t understand what the behavior of this code is going to be like. In my view this algorithm should run all the even/odd part and then in SEQUENCE the odd/even part. Thus, I would have to synchronize thread 1 and thread 2, preventing code from occurring in parallel.

Example thread 1 (even/odd):

for i in range(0, len(x)-1, 2):
    if x[i] > x[i+1]:                  
        x[i], x[i+1] = x[i+1], x[i]    
        sorted = False   

Example thread 2 (odd/even):

for i in range(1, len(x)-1, 2):
    if x[i] > x[i+1]:
        x[i], x[i+1] = x[i+1], x[i]
        sorted = False

To second approach would parallelize EVEN/ODD ordering (type thread 1 takes the first half of the numbers and sorts while thread 2 takes the second half and sorts). The same thing for the ODD/EVEN part (thread 3 sorts half and thread 4 sorts the other half).

Example: Vetor completo: (9,8,7,6,5,4,3,2,1,0)
Thread 1 sorts: 9,8,7,6,5
Thread 2 sorts: 4,3,2,1,0
Expected result thread 1: 5.6.7.8.9
Expected thread 2 result: 0.1.2.3.4
Expected result of the final ordering: 0,1,2,3,4,5,6,7,8,9

Approach 3? Suggestions? If there is no other more efficient way, would you like help to implement one of the two suggestions.

Answer 1

General idea for the ordination

To make the most of the parallelism, try to use the communication between parallel tasks as little as possible, so you won’t need synchronisation during the computations done and leaving specific moments to synchronize. This model of computing is called BSP.

So that there is no competition in the process, we can use a scheme similar to the bitonic merge Sort, both processing and visualisation.

The scheme of bitonic merge Sort is based on sorting networks. A sorting network is composed of horizontal wires representing the positions in the array, and also by vertical bridges connecting wires. Every bridge connects only and exclusively two wires; on each bridge, the elements of the two connected wires are compared and, if necessary, exchanged. It also has another interesting property in sorting networks: time passes from left to right, and a wire can only be on a bridge at the same time.

See here a sorting network:

Well, in our case, for even/odd ordering, we have a repeat of the following sort network:

---+--------------
   |
---+--+-----------
      |
---+--+-----------
   |
---+--+-----------
      |
---+--+-----------
   |
---+--+-----------
      |
---+--+-----------
   |
---+--------------

In this example network, we need 4 parallel processes in the even part and 3 parallel processes in the odd part.

On the part of sorted = False, note that any process you write to this variable will write the same value. So, if two simultaneous processes need to write the same value, the end result will be the same, regardless of race condition. So it’s not necessary in this case write sync on variable sorted. The next part that requires the synchronization of the parts in parallel is only to know if it will be necessary to repeat the processing of the sorting network.

In general, the ordination would be more or less like this:

1. parallel to the exchange function if necessary all index elements for its immediate successor
2. wait for the parallelism of the previous step to end...
3. Boat in parallel to the exchange function if necessary all odd index elements with its immediate successor
4. wait for the parallelism of the previous step to end...
5. check if you need to do the process again

Python implementation

The @Anderson Carlos Woss implemented this solution in Python:

from threading import Thread

c_sorted = False
swaps = 0

# Função que inverte os valores se necessário:
def swap (sequence, i, j):
    global c_sorted, swaps
    if sequence[i] > sequence[j]:
        sequence[i], sequence[j] = sequence[j], sequence[i]
        c_sorted = False
        swaps += 1

# Sequência a ser ordenada:
sequence = [9,8,7,6,5,4,3,2,1,0]

# Condição se a lista está ordenada:
while not c_sorted:
    c_sorted = True
    # Lista de threads para índices pares:
    evens = []

    # Swap entre todos os valores de índice par com seu sucessor imediato:
    for i in range(0, len(sequence), 2):
        t = Thread(target=swap, args=(sequence, i, i+1))
        t.run()
        evens.append(t)

    # Aguarda todas as threads anteriores:
    (t.join() for t in evens)

    # Lista de threads para índices ímpares:
    odds = []

    # Swap entre todos os valores de índice ímpar com seu sucessor imediato:
    for i in range(1, len(sequence)-1, 2):
        t = Thread(target=swap, args=(sequence, i, i+1))
        t.run()
        odds.append(t)

    # Aguarda todas as threads anteriores:
    (t.join() for t in odds)

print(sequence)
print("swaps: %d" % swaps)

See working on repl it.