Parallel sorting algorithm Odd-even sort in python

Question

Parallel sorting algorithm Odd-even sort in python

Navigation

#1 by (8 votes)

7

I created the following serial code to perform the Odd-even sort ordering, which first sorts the odd / even and odd / even indices.

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 a parallel code in python for this same algorithm to be able to calculate the speedup (time gain between executing the serial code VS parallel code).

The first approach I was having was to create a thread for odd / even ordering and another for odd / even sorting, but I can not understand how the behavior of this code will be. In my view this algorithm must execute the whole even / odd part and then in SEQUENCE the odd / even part. So I would have to synchronize thread 1 and thread 2, preventing the 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

The second approach would be to parallelize the PAR / TIAR ordering (type 1 thread takes the first half of the numbers and sorts while thread 2 takes the second half and sorts). The same thing for the WIP / PAR part (thread 3 orders half and thread 4 orders the other half).

Example: Vector complete: (9,8,7,6,5,4,3,2,1,0)
Thread 1 orders: 9,8,7,6,5
Thread 2 orders: 4,3,2,1,0
Expected result thread 1: 5,6,7,8,9
Expected result thread 2: 0,1,2,3,4
Expected result of final ordering: 0,1,2,3,4,5,6,7,8,9

Approach 3? Suggestions? If there is no other way, I'd love to help you implement one of the two suggestions.

python multithreading thread python-3.x

asked by anonymous 20.06.2017 / 21:30

1 answer

What benefits of using the = operator in common methods that are not related to Lists or Lambda Expression? What is the Law of Demetrius?

score 8 · Accepted Answer

General idea for the ordering

To make the most of parallelism, try to use as little communication as possible between parallel tasks, so you do not need to synchronize during computations and leave specific times to synchronize. This computing model is called BSP .

In order for there to be no concurrency in the process, we can use a bitonic merge sort scheme, both processing and viewing.

The bitonic merge sort scheme is based on sorting networks. A sort network consists of horizontal wires that represent the positions in the array, and also vertical bridges that bind wires. Each bridge connects only and exclusively two wires; in each bridge, the elements of the two connected wires are compared and, if necessary, replaced. It also has another interesting property in ordering networks: time goes from left to right, and a wire can only be on a bridge at the same time.

Here's a sort network:

Well,inourcase,foreven/oddordering,wehavearepeatofthefollowingorderingnetwork:

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

Inthisexamplenetwork,weneed4processesinparallelintheevenand3inparallelintheoddpart.

Onthesorted=Falsepart,notethatanyprocesswritingtothisvariablewilldowritingofthesamevalue.Then,iftwosimultaneousprocessesneedtowritethesamevalue,thefinalresultwillbethesame,regardlessoftheracecondition.Thereforeinthiscasedonotwritesyncinthesortedvariable.Thenextpartthatrequiresthesynchronizationofthepartsinparallelisjusttoknowifitwillbenecessarytorepeattheorderingnetworkprocessing.

Ingeneral,sortingwouldlooksomethinglikethis:

potinparallelexchangefunctionifnecessaryallindexelementspairwithitsimmediatesuccessor

waitfortheparallelismoftheprevioussteptoend...

potinparallelexchangefunctionifnecessaryallelementsofoddindexwithitsimmediatesuccessor

waitfortheparallelismoftheprevioussteptoend...

Checkifyouneedtodotheprocessagain

Pythonimplementation

@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 at repl.it