concurrenciavital: enero 2017

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).

Para lograr el ordenamiento de un grupo de números aleatorios fue necesario unir los dos últimos algoritmos de Erlang que subió el Dr. manuel en el material numero 9 y así lograr que dos esclavos ordenen de manera independiente una de las mitades de alguna lista de números dada.

%Comandos para correr el algoritmo:

% c(merge2).

%merge2:start_amo().

%amo2!{50,ordenamiento,self()}.

%amo2!{armar,self()}.

%amo2!{100,ordenamiento,self()}.

%amo2!{armar,self()}.

-module(merge2).

-export([ciclo_amo/2, start_amo/0, fusionord/1, fusion/2, take/2, dividir/1, drop/2, esclavos/0, ciclo_esclavo1/0, ciclo_esclavo2/0]).

%12 > 5 div 2.

%13 > 5 rem 2.

fusionord([]) -> [];

fusionord([A])->[A];

fusionord(Ls) ->

{L1, L2} = dividir(Ls),

L11 = fusionord(L1), %En algún lugar

L22 = fusionord(L2), % En algún lugar más

Ms = fusion(L11, L22),

Ms.

fusion([],Ls) -> Ls;

fusion(Ms,[]) -> Ms;

fusion([A|Ms],[B|Ls]) when A =< B ->

[A|fusion(Ms,[B|Ls])];

fusion([A|Ms],[B|Ls]) when A>B ->

[B|fusion([A|Ms],Ls)].

dividir(Ls) ->

L = length(Ls),

N = L div 2,

L1=take(N,Ls),

L2=drop(N,Ls),

{L1,L2}.

take(0,_) -> [];

take(_,[]) -> [];

take(N,[A|Ls]) when N >0 ->[A|take(N-1,Ls)].

%Drop es omitir los N últimos elementos

drop(N,[_|Ls]) when N>0 -> drop(N-1,Ls);

drop(0,Ls) -> Ls.

%El amo registra el proceso principal e inicializa a los esclavos

start_amo() ->

esclavos().

%Esclavos que ordenaran las listas

esclavos() ->

%A diferencia de las potencias, el amo ordenará las dos listas que los esclavos ya ordenaron %anteriormente.

ciclo_amo(A,B) ->

receive

%{8,potencia2,self()}

{N,ordenamiento,Pid} -> %Orden emitida por el usuario

io:format("Peticion recibida ~n",[]),

{M1,M2} = dividir([rand:uniform(N) || _ <- lists:seq(1, N)]),

esclavo1 ! {M1,ordenef}, io:format("Se mandó a esclavo 1",[]),

esclavo2 ! {M2,ordenef}, io:format("Se mandó a esclavo 2",[]),

ciclo_amo(A,B);

{respuesta1, Res1} ->

io:format("Tarea realizada 1: ~p~n",[Res1]),

ciclo_amo(Res1,B);

{respuesta2, Res2} ->

io:format("Tarea realizada 2: ~p~n",[Res2]),

ciclo_amo(A,Res2);

{armar,Pid} ->

ListaUnida = fusion(A, B),

io:format("ListaUnida ~p~n",[ListaUnida]),

Pid ! {resultado, ListaUnida },

ciclo_amo(A,B)

end.

ciclo_esclavo1() ->

io:format("Listo esclavo1 ~n",[]),

receive

{Ls, ordenef} ->

Res1 = fusionord(Ls),

io:format("Ordenado1: ~p~n",[Res1]),

amo2 !{respuesta1,Res1},

ciclo_esclavo1()

end.

ciclo_esclavo2() ->

io:format("Listo esclavo2 ~n",[]),

receive

{Ls, ordenef} ->

Res2 = fusionord(Ls),

io:format("Ordenado1: ~p~n",[Res2]),

amo2 !{respuesta2,Res2},

ciclo_esclavo2()

end.

%Aplicaciones a tolerancia a fallas y a compartición de datos (shared data).

%Salidas:

%4> merge2:start_amo().

%Listo esclavo1

%Listo esclavo2

%true

%5> amo2!{50,ordenamiento,self()}.

%Peticion recibida

%{50,ordenamiento,<0.56.0>}

%Se mandó a esclavo 1Ordenado1: %[2,3,5,6,12,15,16,19,21,23,23,28,30,31,32,34,37,37,41,42,42,45,47,

% 47,50]

%Se mandó a esclavo 2Listo esclavo1

%Ordenado1: [3,4,11,12,15,16,16,18,20,25,31,32,38,38,40,42,43,45,45,45,46,47,

% 48,48,48]

%Tarea realizada 1: [2,3,5,6,12,15,16,19,21,23,23,28,30,31,32,34,37,37,41,42,

% 42,45,47,47,50]

%Listo esclavo2

%Tarea realizada 2: [3,4,11,12,15,16,16,18,20,25,31,32,38,38,40,42,43,45,45,45,

% 46,47,48,48,48]

%6> amo2!{armar,self()}.

%ListaUnida [2,3,3,4,5,6,11,12,12,15,15,16,16,16,18,19,20,21,23,23,25,28,30,31,

% 31,32,32,34,37,37,38,38,40,41,42,42,42,43,45,45,45,45,46,47,47,47,

% 48,48,48,50]

%{armar,<0.56.0>}

%7> amo2!{100,ordenamiento,self()}.

%Peticion recibida

%{100,ordenamiento,<0.56.0>}

%Se mandó a esclavo 1Ordenado1: %[7,7,9,11,13,14,18,19,20,24,25,26,26,27,28,29,30,33,40,42,53,55,56,

59,59,59,61,62,63,66,66,66,68,68,70,71,72,73,76,76,79,80,80,80,82,

84,90,90,95,96]

%Se mandó a esclavo 2Ordenado1: %[9,12,13,17,18,18,20,26,27,29,31,33,33,34,34,34,35,36,37,40,44,45,

48,50,52,52,55,56,59,59,62,64,67,74,77,79,80,82,83,83,83,84,84,85,

88,91,92,94,95,95]

%Listo esclavo1

%Tarea realizada 1: [7,7,9,11,13,14,18,19,20,24,25,26,26,27,28,29,30,33,40,42,

% 53,55,56,59,59,59,61,62,63,66,66,66,68,68,70,71,72,73,76,

% 76,79,80,80,80,82,84,90,90,95,96]

%Listo esclavo2

%Tarea realizada 2: [9,12,13,17,18,18,20,26,27,29,31,33,33,34,34,34,35,36,37,

% 40,44,45,48,50,52,52,55,56,59,59,62,64,67,74,77,79,80,82,

% 83,83,83,84,84,85,88,91,92,94,95,95]

%8> amo2!{armar,self()}.

%ListaUnida [7,7,9,9,11,12,13,13,14,17,18,18,18,19,20,20,24,25,26,26,26,27,27,

% 28,29,29,30,31,33,33,33,34,34,34,35,36,37,40,40,42,44,45,48,50,52,

% 52,53,55,55,56,56,59,59,59,59,59,61,62,62,63,64,66,66,66,67,68,68,

% 70,71,72,73,74,76,76,77,79,79,80,80,80,80,82,82,83,83,83,84,84,84,

% 85,88,90,90,91,92,94,95,95,95,96]

%{armar,<0.56.0>}

concurrenciavital

viernes, 13 de enero de 2017

Otra explicación del algoritmo de fusión en paralelo

jueves, 12 de enero de 2017

Ordenamiento union de algoritmo merge con potencia