Otra explicación del algoritmo de fusión en paralelo...
El amo toma como elementos de fusión a dos listas
que ya están ordenadas,
pero solo las entremezcla correctamente. La parte de ordenamiento ha
sido asignada a cada
esclavo (quizás buscando mergesort en la red halles más información
del algoritmo de ordenamiento
subyacente). En nuestro caso planteado, tenemos las siguientes acciones:
amo recibe a la lista Ls: [8,4,5,1,6,9,2]
amo divide a Ls en partes casi iguales (en este caso): [8,4,5] y [1,6,9,2]
amo reparte trabajo: Esclavo1 debe ordenar [8,4,5], y esclavo2 a [1,6,9,2]
Esclavo1 devuelve [4,5,8] a amo
Esclavo2 devuelve [1,2,6,9] a amo
Amo entremezcla correctamente los resultados:
[1,2,4,5,6,8,9]
(De [4,5,8]
[1,2,6,9] arme [1], queda
[4,5,8]
[2,6,9].
De [4,5,8]
[2,6,9] ponga [1,2]
queda
[4,5,8]
[6,9],
y así...)
Notemos que una lista super grande puede dividirse en n porciones
aproximadamente iguales,
utiliando para ordenamiento n procesos (computadoras); el amo se
encargaría de armar
la solución (lo cual es algo muy rápido de hacer).
Notemos, finalmente, que en la versión que les dí de este algoritmo
distribuido de fusión es necesario enviar una orden "armar" al final
de las notificaciones de terminación de cada esclavo; no obstante, y
similarmente al problema del sistema de limpieza, es posible recibir
tales notificaciones y automáticamente armar la solución (quedaría
pendiente cómo hacerlo).
Hasta que punto conviene o como se podría medir la conveniencia de mandar los números desordenados a nodos remotos? si es un conjunto pequeño el que se va a subdividir obviamente el costo de comunicación es mayor a la tarea a realizar, pero si fuera 1 GB de información y que esta se pudiera ordenar en dos computadoras esclavas, para que al final el proceso amo sólo entremezcle los datos obtenidos de los esclavos, ahí creo que si convendría, mi pregunta está orientada a si hay alguna manera de saberlo con alguna fórmula.
ResponderEliminarCiertamente, el algoritmo de fusión es en promedio el
Eliminarmejor algoritmo de ordenamiento conocido: Para una lista de tamaño n, su tiempo es de O(n(log n)). Por ejemplo, para una lista de 1 millón de elementos, tendríamos que para este algoritm a lo más se requieren 6 millones de operaciones para ordenarlos. Si se tienen 6 computadoras para hacer cada parte subdividida de ordenamiento, y dado que que la fusión es a lo más de tamaño O(n), se tendría que una computadora individual realiza su tarea en a lo más un millón de operaciones. Nota que el número de computadoras definitivamente impacta en el tiempo de ejecución: Si antes tardábamos 6 días en ordernar una enorme cantidad de datos, ahora solo tardaremos 1. Para fórmulas asintóticas de complejidad busca por ejempo "insertion sort", "mergesort" y "quicksort" en la red.