Publicado el 20 de Mayo del 2018
471 visualizaciones desde el 20 de Mayo del 2018
861,7 KB
13 paginas
Creado hace 14a (17/01/2010)
Paralelismo en la ordenación
por mezcla
Índice
➲ MergeSort secuencial.
➲ MergeSort paralelo : descomposición en
tareas.
● Descomposición funcional.
● Descomposición recursiva.
● Descomposición de dominio.
● Grafo de dependencias y asignación de tareas.
● Pseudoalgoritmo.
● Pensando en la implementación.
MergeSort secuencial
➲ Entrada : una secuencia de n números desordenada.
➲ Salida : secuencia de n números ordenada.
➲ La ordenación por mergesort, se basa en obtener un vector ordenado
de n números a partir de uno desordenado; ello lo consigue aplicando
el esquema algorítmico divide y vencerás, mediante el cual
descompone un vector de tamaño n en dos subvectores de tamaño n/
2 sucesivamente, hasta que el tamaño del vector obtenido sea lo
suficientemente pequeño como para considerar que está ordenado
(tamaño 1); una vez obtenido este vector mínimo, recuperaremos el
vector original mezclando los resultados, los cuales se volverán a
mezclar recursivamente hasta obtener un vector de tamaño n
ordenado.
MergeSort paralelo :
descomposición en tareas
➲ Para poder resolver de forma paralela el problema de la ordenación
por mezcla es necesario descomponer de alguna forma el algoritmo
en una serie de subtareas. A continuación presento una serie de
posibles descomposiciones acompañadas con un pequeño estudio y
conclusiones:
● Descomposición funcional : la cual se realizará mediante la versión
pipeline.
sort secuencial.
● Descomposición recursiva : utilizando el esquema algorítmico del merge-
● Descomposición de dominio, centrada en los datos de entrada :
aprovecharemos la independencia de los datos de entrada para dividirlos
directamente entre los procesos.
Descomposición funcional
Leer
Ordenar
Mezclar
➲
➲
➲
➲
➲
➲
➲
➲
➲
➲
➲
➲
La idea de esta descomposición, es descomponer el algoritmo en una serie de módulos,
de modo que la ejecución de los mismos se solape de un paso al siguiente.
Vamos a ver cuánto tardaría esta descomposición en resolver un problema de tamaño
n; para simplificar los cálculos consideraremos el tiempo en el peor caso:
T (Leer ) = n , T (Ordenar ) = n/b * log ( n/b ) , T(Mezclar ) = k * n/b + n/b
Donde b = número de bloques y k = paso del algoritmo.
El siguiente paso es inferir el coste del algoritmo a partir de observar el comportamiento
en unos pocos pasos.
Supongamos que el número de bloques b es igual a 3 , el funcionamiento sería el
siguiente:
T (Mezcla 1 ) = T (leer) + T (Ordenar, b) + T(Mezclar,1,b) = n/b + n/b * log (n/b) + n/b
T (Mezcla 2 ) = T (leer) + T (Ordenar, b) + T(Mezclar,2,b) = n/b + n/b * log (n/b) + 2*n/b
T (Mezcla 2 ) = T (leer) + T (Ordenar, b) + T(Mezclar,3,b) = n/b + n/b * log (n/b) + 3*n/b
Dado que la ejecución de los módulos se solapa de un paso al siguiente, sólo es
necesario quedarnos con los pasos más costosos, quedando la siguiente solución:
4n/b + 2 n/b * log (n/b) + (n/b log n/b ó 2 n/b ) -- En función de si log n/b es mayor o no
que 2.
Supongamos por simplicidad que log n/b es siempre mayor que el número de paso, en
ese caso, para un algoritmo de b pasos tardaríamos: (b+1) * n/b + b * n/b log ( n/b)
➲ Que si nos quedamos con el mayor término sería t(b) = n * log ( n / b )
Consideraciones sobre la anterior
descomposición
➲
➲
➲
➲
➲
➲
➲
La versión anterior es bastante mala , como se puede observar en el cálculo del speed-up cuando n
tiende a infinito:
Lim Speedup = n* log n / ( n * log (n/b) ) = log n / ( log n – log b ) = 1
Haciendo aproximaciones podemos observar cómo, en el mejor de los casos, no tenemos ninguna
mejora significativa respecto del algoritmo secuencial, y eso que no hemos considerado el coste de
las comunicaciones ...
Esta mala eficiencia del algoritmo se debe a los siguientes factores:
No aparece por ningún lado el factor número de procesadores (p) , el cual se supone que tiene que
ser 3 (un mayor número no mejoraría el tiempo de ejecución).
No está balanceado el tiempo de cada operación, claramente el tiempo que el algoritmo tardará en
leer va a ser mucho menor que el tiempo que tarda en ordenar e incluso el tiempo que tarda en
mezclar.
Granularidad muy elevada : los bloques en que hemos descompuesto el algoritmo, siguen siendo
muy grandes, con lo que no aprovecharemos las ventajas de la computación paralela, aunque al
menos, el coste de las comunicaciones que no hemos considerado, no será muy elevado.
Descomposición recursiva
➲
➲
➲
➲
Siguiendo la lógica de la versión secuencial de la ordenación por mezcla,
podemos idear una versión palalela donde cada subtarea puede ser
ejecutada por un procesador.
El nodo raíz leerá los datos y los repartirá equitativamente entre sus dos
hijos, los cuales repartirán sus datos entre sus respectivos dos hijos...
hasta llegar a un tamaño de los datos a partir del cual no nos interese
descomponer más; llegados a este punto, los nodos receptores de la
fracción mínima de datos, los ordenarán y los enviarán a uno de sus
vecinos (determinado por el paso de la mezcla) para que procedan a
mezclar los datos ordenados.
El tamaño mínimo de datos determina la granularidad de la
descomposición, la cual va a depender directamente del número de
procesadores de los que dispongamos; tendremos por tanto, un tamaño
mínimo de los datos de n/p antes de empezar a ordenar.
Para el estudio de la eficiencia de esta versión sí que vamos a tener en
cuenta las comunicaciones, así que distinguimos los siguientes tipos de
tiempo:
T(Leer) = n
T(Dividir) = constante
T(Ordenar) = ( n / p ) * log ( n / p )
T(Envío ) = variable y dependiente de n/p
T(Mezcla ) = variable y dependiente de n/p
:
:
...
Estudio de la descomposición
recursiva
➲
➲
➲
➲
➲
Al igual que antes, vamos a partir de un problema, sencillo y a partir del mismo inferiremos el coste
para problemas más complejos.
Supongamos una lista de tamaño n y un número de procesadores = 4.
El límite de datos a descomponer es por tanto n/4, lo que implica que solo descompondremos los
datos 2 veces (logaritmo en base 2 de p ).
T(Raíz) = T ( Leer ) + T (Dividir) + T (Enviar,n/2) = n + (despreciable) + 2* (ts + tw * n/2 ) (dos
envíos de la mitad de la lista de valores) = n + 2 ts + 2 tw * n/2 = n + 2ts + tw * n
T(Repartir nivel 1 ) = T(Dividir) + T(Enviar , n/4 ) = 2 * ( ts + tw * n/4)
(Los nodos hermanos de un nivel son capaces de ejecutar sus tareas en paralelo, de modo que el
tiempo de las mismas en cada uno de ellos se solapa y podemos simplificar el cálculo a las tareas
llevadas a cabo por solo uno de ellos).
T(Repartir nivel 2) = T(Ordenar) = (n/p) * log (n/p) (Igual que antes, esta tarea también se solapa
en los hermanos).
T(Mezcla paso 1) = T (Enviar, n/4) + T (Mezclar, n / 4 ) = ts + tw * n/4 + 2 * n/4
T(Mezcla paso 2) = T(Enviar, n/2) + T(Mezclar, n/2 ) = ts + tw * n/2 + 2 * n/2
Y finalmente tendremos nuestro vector ordenado.
Podemos generalizar el tiempo de la siguiente forma:
T(n,p ) =
Lo cual, tras eliminar expresiones que no dependen de n y haciendo unos pocos redondeos que no
afectarán prácticamente nada para tamaños de n muy grandes, nos queda en :
Donde se puede observar que el término de mayor orden es n/p * log (n/p).
T Leer T Raíz∑ T hijo nivel iT Mezcla paso iT Ordenar
2×n×1 /22/log ptw×n×1/22/log pn/ p×logn/ p
Consideraciones sobre la
descomposición recursiva
n ∞
➲
➲
➲
➲
●
●
Este método parece bueno, vamos a observar el speed-up cuando n tiene a infinito para confirmarlo.
Para este cálculo solo vamos a considerar del tiempo obtenido anteriormente, el factor de mayor
orden.
n ∞ t n/t n/ p=lim
lim
El resultado es p, lo cual significa que con tamaños de n MUY grandes, conseguiremos un speed-up
de p (número de procesadores), lo cual es bastante prometedor.
A grandes rasgos, la descomposición es bastante buena, sin embargo , presenta algunos
problemas que deben ser comentados:
n×log n/n / p×logn / p= p
Este algoritmo realiza una gran cantidad de comunicaciones y en el estudio hemos asumido que
todos los mensajes se envían correctamente a la primera.
¿Qué ha
Comentarios de: Paralelismo en la ordenación por mezcla (0)
No hay comentarios