9

Elaborei o seguinte código serial para realizar a ordenação Odd-even sort, que primeiro vai ordenando os índices par/ímpar e depois ímpar/par.

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")

Agora eu preciso criar para este mesmo algoritmo de ordenação um código paralelo em python para poder calcular o speedup (ganho de tempo entre executar o código serial VS código paralelo).

A primeira abordagem que eu estava tendo era criar uma thread para a ordenação par/ímpar e outra para a ordenação ímpar/par, mas não consigo entender como vai ser o comportamento deste código. Na minha visão esse algoritmo deve executar toda a parte par/ímpar e depois em SEQUÊNCIA a parte ímpar/par. Assim, eu teria que sincronizar a thread 1 e a thread 2, impedindo de o código ocorrer em paralelo.

Exemplo thread 1 (par/ímpar):

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   

Exemplo thread 2 (ímpar/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

A segunda abordagem seria paralelizar a ordenação PAR/ÍMPAR (tipo thread 1 pega a primeira metade dos números e ordena enquanto a thread 2 pega a segunda metade e ordena). A mesma coisa para a parte ÍMPAR/PAR (thread 3 ordena metade e a thread 4 ordena a outra metade).

Exemplo: Vetor completo: (9,8,7,6,5,4,3,2,1,0)
Thread 1 ordena: 9,8,7,6,5
Thread 2 ordena: 4,3,2,1,0
Resultado esperado thread 1: 5,6,7,8,9
Resultado esperado thread 2: 0,1,2,3,4
Resultado esperado da ordenação final: 0,1,2,3,4,5,6,7,8,9

Abordagem 3? Sugestões? Caso não haja outra forma mais eficiente, gostaria de ajuda para implementar uma das duas sugestões.

5
  • Parece bastante com o Bubble sort, só que evita o excesso de coelhos e tartarugas. Mais paralelizável do que o cocktail sort... creio que estratégia 2 desconfigura essa ordenação, e a estratégia 1 torna difícil a sincronização dessas ordenações todas... Commented 20/06/2017 às 19:57
  • @JeffersonQuesado poderia elaborar um pouco mais? Não consegui compreender na integra sua resposta. Commented 20/06/2017 às 20:24
  • 1
    foi um comentário só. Elaborando melhor: parte 1) ordenação nova para mim, parece com bubble sort, parte 2) estratégia 3 é a correta, não as anteriores. Falando em estratégia 3, eu já tenho uma ideia de como. Commented 20/06/2017 às 21:31
  • Hmmmm, bem, na verdade, eu não sei como seria em Python, mas eu tenho a ideia geral de como seria Commented 20/06/2017 às 21:44
  • estou procurando aqui alguém para ajudar com a parte Python, enquanto isso, vou escrevendo o esquema geral Commented 20/06/2017 às 21:57

1 Resposta 1

9

Ideia geral para a ordenação

Para utilizar ao máximo o paralelismo, procure usar ao mínimo possível a comunicação entre as tarefas paralelas, assim não será necessário sincronismos durante as computações feitas e deixando momentos específicos para sincronizar. Esse modelo de computação é chamado de BSP.

Para que não haja concorrência no processo, podemos utilizar um esquema semelhante ao do bitonic merge sort, tanto de processamento quanto de visualização.

O esquema do bitonic merge sort é baseado em redes de ordenação. Uma rede de ordenação é composta por fios horizontais que representam as posições no array, e também por pontes verticais que ligam fios. Toda ponte conecta única e exclusivamente dois fios; em cada ponte, os elementos dos dois fios conectados são comparados e, caso seja necessário, trocados. Também tem outra propriedade interessante em redes de ordenação: o tempo passa da esquerda para a direita, e um fio só pode estar em uma ponte ao mesmo tempo.

Veja aqui uma rede de ordenação:

rede de ordenação para 8 fios

Bem, no nosso caso, para a ordenação par/ímpar, temos uma repetição da seguinte rede de ordenação:

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

Nessa rede de exemplo, precisamos de 4 processos em paralelo na parte par e de 3 processos em paralelo na parte ímpar.

Sobre a parte de sorted = False, note que qualquer processo que escrever nessa variável fará escrito do mesmo valor. Então, caso dois processos simultâneos precisem escrever o mesmo valor, o resultado final será o mesmo, independente da condição de corrida. Portanto, não é necessário neste caso fazer sincronismo de escrita na variável sorted. A próxima parte que exige a sincronização das partes em paralelo é apenas para saber se vai ser necessário repetir o processamento da rede de ordenação.

De modo geral, a ordenação seria mais ou menos assim:

  1. bote em paralelo a função de troca se necessário todos os elementos de índice par com o seu sucessor imediato
  2. espere o paralelismo do passo anterior acabar...
  3. bote em paralelo a função de troca se necessário todos os elementos de índice ímpar com o seu sucessor imediato
  4. espere o paralelismo do passo anterior acabar...
  5. verifique se precisa fazer o processo novamente

Implementação em Python

O @Anderson Carlos Woss implementou esta solução em 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)

Veja funcionando no repl.it

3
  • 1
    muito boa a sua resposta, tanto pela parte teórica, quanto pela parte prática (código). Obrigado, testado e aprovado ! Commented 21/06/2017 às 13:59
  • 1
    A parte prática/codificação foi o Anderson quem fez =] Vou passar seus agradecimentos para ele Commented 21/06/2017 às 14:02
  • @umusuarioqualquer, depois manda o resultado dos testes, o sequencial e o paralelo Commented 21/06/2017 às 14:05

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .