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:
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:
- bote em paralelo a função de troca se necessário todos os elementos de índice par com o seu sucessor imediato
- espere o paralelismo do passo anterior acabar...
- bote em paralelo a função de troca se necessário todos os elementos de índice ímpar com o seu sucessor imediato
- espere o paralelismo do passo anterior acabar...
- 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