Skip to main content
4 de 5
Removendo marcas temporais
Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158

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]

# Sequência ordenada para controle:
ordered = sorted(sequence)

# 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

Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158