Merge sort (Português)

Merge sort paralleliza bem devido ao uso do método divide-e-conquista. Várias variantes paralelas diferentes do algoritmo foram desenvolvidas ao longo dos anos. Alguns algoritmos de merge sort paralelos estão fortemente relacionados com o algoritmo de merge sequencial top-down, enquanto outros têm uma estrutura geral diferente e usam o método de merge K-way.

Merge sort com recursão paralela

o procedimento sequencial de merge sort pode ser descrito em duas fases, a fase de divisão e a fase de merge., A primeira consiste de muitas chamadas recursivas que repetidamente realizam o mesmo processo de divisão até que as subsequentes sejam trivialmente ordenadas (contendo um ou nenhum elemento). Uma abordagem intuitiva é a paralelização dessas chamadas recursivas. A seguir pseudocode descreve a ordenação de junção com recursão paralela usando o fork e as palavras-chave de junção:

Este algoritmo é a modificação trivial da versão sequencial e não se paralleliza bem. Portanto, sua rapidez não é muito impressionante., Ele tem uma extensão de Θ (n ) {\displaystyle \Theta ( n)} , que é apenas uma melhoria de Θ (log ⁡ n ) {\displaystyle \Theta (\log n)} Em comparação com a versão sequencial (veja Introdução aos algoritmos). Isto deve-se principalmente ao método de fusão sequencial, pois é o gargalo das execuções paralelas.

Merge sort com mergingEdit

Better parallelism can be achieved by using a parallel merge algorithm. Cormen et al. apresentar uma variante binária que mescla duas sub-sequências ordenadas numa sequência de saída ordenada.,

numa das sequências (A maior, se for desigual de comprimento), o elemento do índice médio é seleccionado. A sua posição na outra sequência é determinada de forma a que esta sequência permaneça ordenada se este elemento for inserido nesta posição. Assim, sabe-se quantos outros elementos de ambas as sequências são menores e a posição do elemento selecionado na sequência de saída pode ser calculada. Para as sequências parciais dos elementos menores e maiores criados desta forma, o algoritmo de junção é novamente executado em paralelo até que o caso base da recursão seja atingido.,

o seguinte pseudocódigo mostra o método modificado de junção paralela usando o algoritmo de junção paralela (adotado por Cormen et al.).

a fim de analisar uma relação de recorrência para o pior caso, o período, as chamadas recursivas de parallelMergesort têm de ser incorporadas somente uma vez, devido à sua execução em paralelo, obtendo

Para informações detalhadas sobre a complexidade do paralelo procedimento de impressão, consulte o algoritmo de junção.,

a solução desta recorrência é dada por

t ∞ sort = Θ ( log ⁡ (n ) 3 ) {\textstyle T_{\infty }^{\text{sort}}=\Theta \left (\log (n)^{3}\right)} .

sortEdit Merge Multiway paralela

parece arbitrário restringir os algoritmos de merge sort a um método de merge binária, uma vez que existem geralmente p > 2 processadores disponíveis. Uma melhor abordagem pode ser usar um método de junção K-way, uma generalização da junção binária, na qual as sequências ordenadas k {\displaystyle k} são reunidas., Esta variante de junção é adequada para descrever um algoritmo de ordenação em um carrinho de mão.

Basic IdeaEdit

Multisequence selectionEdit

PseudocodeEdit

abaixo, é indicado o pseudocódigo completo do algoritmo de junção múltipla paralela., Nós assumimos que há uma sincronização de barreira antes e depois da seleção de multisequência tal que cada processador pode determinar os elementos de divisão e a partição de sequência corretamente.

AnalysisEdit

Practical adaption and applicationEdit

o algoritmo multi merge sort é muito escalável através da sua elevada capacidade de parallelização, que permite o uso de muitos processadores. Isso faz do algoritmo um candidato viável para a triagem de grandes quantidades de dados, tais como aqueles processados em clusters de computador., Além disso, uma vez que em tais sistemas a memória não é geralmente um recurso limitante, a desvantagem da complexidade do espaço de merge sort é negligenciável. No entanto, outros factores tornam-se importantes nesses sistemas, que não são tidos em conta na modelização num programa. Aqui, os seguintes aspectos devem ser considerados: hierarquia de Memória, quando os dados não cabem em processadores de cache, ou a sobrecarga de comunicação de troca de dados entre os processadores, o que poderia se tornar um gargalo quando os dados não podem ser acessados através de memória compartilhada.Sanders et al., apresentaram no seu artigo um algoritmo paralelo síncrono para a junção multi-níveis, que divide os processadores p {\displaystyle p} em r {\displaystyle R} grupos de tamanho p ‘{\displaystyle p’} . Todos os processadores ordenam localmente primeiro. Ao contrário de um único nível multiway mergesort, estas sequências são então particionadas em partes r {\displaystyle R} e atribuídas aos grupos de processadores apropriados. Estes passos são repetidos recursivamente nesses grupos. Isso reduz a comunicação e, especialmente, evita problemas com muitas mensagens pequenas., A estrutura hierárquica da rede real subjacente pode ser utilizada para definir os grupos de processadores (por exemplo, racks, clusters, etc…).o Merge sort foi um dos primeiros algoritmos de ordenação onde a velocidade máxima foi alcançada, com Richard Cole usando um algoritmo de subamostragem inteligente para garantir a fusão de O(1). Outros algoritmos sofisticados de ordenação paralela podem alcançar os mesmos ou melhores limites de tempo com uma constante mais baixa., Por exemplo, em 1991 David Powers descreveu um quicksort paralelizado (e um tipo radix relacionado) que pode operar em tempo O(log n) em uma máquina de acesso aleatório paralelo CRCW (PRAM) com processadores N, realizando partições implicitamente. Powers também mostra que uma versão pipelinada do Batcher’s Bitonic Mergesort em O (log n)2) time on a butterfly sorting network é na prática mais rápido do que seu o(log n) sortes em um PRAM, e ele fornece uma discussão detalhada sobre as despesas ocultas em comparação, radix e ordenação paralela.