Merge sort se paraleliza bien debido al uso del método divide y vencerás. Varias variantes paralelas diferentes del algoritmo se han desarrollado a lo largo de los años. Algunos algoritmos de ordenación de combinación paralela están fuertemente relacionados con el algoritmo de combinación secuencial de arriba hacia abajo, mientras que otros tienen una estructura general diferente y utilizan el método de combinación K-way.
merge sort with parallel recursionEdit
el procedimiento de ordenación de fusión secuencial se puede describir en dos fases, la fase de división y la fase de fusión., La primera consiste en muchas llamadas recursivas que realizan repetidamente el mismo proceso de división hasta que las subsecuencias se ordenan trivialmente (que contienen uno o ningún elemento). Un enfoque intuitivo es la paralelización de esas llamadas recursivas. El siguiente pseudocódigo describe la ordenación combinada con recursión paralela utilizando las palabras clave fork y join:
este algoritmo es la modificación trivial de la versión secuencial y no se paraleliza bien. Por lo tanto, su aceleración no es muy impresionante., Tiene un intervalo de Θ (n ) {\displaystyle \Theta ( n)} , que es solo una mejora de Θ (log n ) {\displaystyle \Theta (\log n)} en comparación con la versión secuencial (ver Introducción a los Algoritmos). Esto se debe principalmente al método de fusión secuencial, ya que es el cuello de botella de las ejecuciones paralelas.
merge sort with parallel mergingEdit
Se puede lograr un mejor paralelismo usando un algoritmo de fusión paralelo. Cormen et al. presente una variante binaria que fusiona dos sub-secuencias ordenadas en una secuencia de salida ordenada.,
en una de las secuencias (la más larga si es de longitud desigual), se selecciona el elemento del índice medio. Su posición en la otra secuencia se determina de tal manera que esta secuencia quedaría ordenada si este elemento se inserta en esta posición. Por lo tanto, se sabe cuántos otros elementos de ambas secuencias son más pequeños y se puede calcular la posición del elemento seleccionado en la secuencia de salida. Para las secuencias parciales de los elementos más pequeños y más grandes creados de esta manera, el algoritmo de fusión se ejecuta de nuevo en paralelo hasta que se alcanza el caso base de la recursión.,
el siguiente pseudocódigo muestra el método modificado de ordenación por fusión paralela utilizando el algoritmo de fusión paralela (adoptado de Cormen et al.).
con el fin de analizar una relación de recurrencia para el peor intervalo de casos, las llamadas recursivas de parallelMergesort tienen que ser incorporadas solo una vez debido a su ejecución paralela, obteniendo
para obtener información detallada sobre la complejidad del procedimiento de fusión paralela, consulte algoritmo de fusión.,
la solución de esta recurrencia viene dada por
T ∞ sort = Θ ( log ( n ) 3 ) {\textstyle T_{\infty }^{\text{sort}}=\Theta \left(\log(n)^{3}\right)} .
Parallel multiway merge sortEdit
parece arbitrario restringir los Algoritmos de ordenación de fusión a un método de fusión binario, ya que generalmente hay procesadores p > 2 Disponibles. Un mejor enfoque puede ser utilizar un método de fusión k-way, una generalización de fusión binaria, en la que k {\displaystyle K} secuencias ordenadas se fusionan juntas., Esta variante de combinación es muy adecuada para describir un algoritmo de ordenación en un PRAM.
Basic IdeaEdit
El paralelo multiway mergesort proceso en cuatro procesadores de t 0 {\displaystyle t_{0}} para t 3 {\displaystyle t_{3}} .
Multisequence selectionEdit
PseudocodeEdit
a Continuación, el pseudocódigo del paralelo multiway combinación de algoritmo de ordenación es dado., Asumimos que hay una sincronización de barrera antes y después de la selección multisecuencia de tal manera que cada procesador puede determinar los elementos de división y la partición de secuencia correctamente.
Analizadoeditar
adaptación y aplicacióneditar
el algoritmo multiway merge sort es muy escalable gracias a su alta capacidad de paralelización, que permite el uso de muchos procesadores. Esto hace que el algoritmo sea un candidato viable para ordenar grandes cantidades de datos, como los procesados en clústeres de computadoras., Además, dado que en tales sistemas la memoria no suele ser un recurso limitante, la desventaja de la complejidad espacial de merge sort es insignificante. Sin embargo, otros factores se vuelven importantes en tales sistemas, que no se tienen en cuenta al modelar en un cochecito. Aquí, los siguientes aspectos deben ser considerados: jerarquía de memoria, cuando los datos no caben en la caché del procesador, o la sobrecarga de comunicación del intercambio de datos entre procesadores, que podría convertirse en un cuello de botella cuando los datos ya no se puede acceder a través de la memoria compartida.
Sanders et al., han presentado en su trabajo un algoritmo paralelo síncrono masivo para mergesort multinivel multiway, que divide los procesadores p {\displaystyle P} en grupos r {\displaystyle R} de tamaño p ‘{\displaystyle p’} . Todos los procesadores ordenan localmente primero. A diferencia del mergesort multiway de un solo nivel, estas secuencias se dividen en partes r {\displaystyle R} y se asignan a los grupos de procesadores apropiados. Estos pasos se repiten recursivamente en esos grupos. Esto reduce la comunicación y especialmente evita problemas con muchos mensajes pequeños., La estructura jerárquica de la red real subyacente se puede utilizar para definir los grupos de procesadores(por ejemplo, racks, clusters,…).
otras Varianteseditar
Merge sort fue uno de los primeros algoritmos de Ordenación donde se logró una velocidad óptima, con Richard Cole utilizando un algoritmo de submuestreo inteligente para garantizar la fusión O(1). Otros sofisticados algoritmos de Ordenación paralela pueden lograr los mismos o mejores límites de tiempo con una constante más baja., Por ejemplo, en 1991 David Powers describió un quicksort paralelizado (y un tipo radix relacionado) que puede operar en tiempo o(log n) en una máquina CRCW de acceso aleatorio paralelo (PRAM) con n procesadores mediante la realización de particiones implícitamente. Powers muestra además que una versión segmentada de la combinación Bitónica de Batcher en el tiempo O((log n)2) en una red de ordenación de mariposas es en la práctica más rápida que su ordenación o(log n) en un PRAM, y proporciona una discusión detallada de los gastos generales ocultos en comparación, radix y ordenación paralela.