Haciendo pruebas con erlang, se me ocurrió que sería divertido probar a paralelizar algún algoritmo típico (sobretodo debido a que mi cpu es ahora un quadcore). Como mi imaginación no está muy avanzada, probé con el quicksort.

Su implementación en un lenguaje funcional suele ser bastante simple. Y en Erlang podría ser algo simplemente como:

 
qsort([]) ->
   [];
qsort([Pivot|T]) ->
   qsort([X || X <- T, X < Pivot])   ++
   [Pivot]                           ++
   qsort([X || X <- T, X >= Pivot]).

En un primer (y estúpido) intento por paralelizarlo, probé simplemente a que cada llamada recursiva fuese un nuevo proceso. El asunto terminó con el ordenador medio bloqueado al intentar crear millones de procesos (pues inicié erlang poniéndole explícitamente que no hubiese límite , por defecto tiene 2¹⁶ como límite).

El asunto tiene simple solución. Si tenemos un problema por permitir un exceso de procesos, pues se pone un límite y arreglado, ¿no?. El esquema usado simplemente es que para cada llamada recursiva, se indicará el número máximo de procesos que puede crear el proceso en cuestión y todos sus hijos. Si las llamadas recursivas de un quicksort van a ser un árbol donde cada nodo tendrá dos hijos, simplemente vamos a podarlo para que finalmente las hojas de dicho árbol ejecuten el algoritmo quicksort normal y el resto, los nodos, realizarán el quicksort paralelo (p_qsort lo he llamado).

 
%%
%% Params:
%%   - List to be sorted
%%
p_qsort(L) ->
   S   = self(),
   Ref = erlang:make_ref(),
 
   spawn(fun() ->
            p_qsort(L, ?THREAD_LIMIT, S, Ref)
         end),
 
   gather(Ref).
%%
%% Params:
%%   - List to be sorted
%%   - Maximum number of processes can be created
%%   - Father process (the results will be sent to him)
%%   - Unique reference for knowing what position the results are in
p_qsort([], _, Father, Ref) ->
   Father ! {Ref, []};
p_qsort([Pivot|T], Limit, Father, Ref) when Limit > 2 ->
   S       = self(),
   R_right = erlang:make_ref(),
   R_left  = erlang:make_ref(),
 
   spawn(fun() ->
            p_qsort( [X || X <- T, X <   Pivot], Limit div 2, S, R_left)
         end),
   spawn(fun() ->
            p_qsort( [X || X <- T, X >=  Pivot], Limit div 2, S, R_right)
         end),
 
   Father ! {Ref, gather(R_left) ++ [Pivot] ++ gather(R_right)};
p_qsort(L, _, Father, Ref) ->
   Father ! {Ref, qsort(L)}.

La función con un único parámetro es la función pública de entrada. Ésta, crea un proceso con la función de quicksort paralelo indicando un número, como segundo parámetro, que significa el número máximo de procesos que puede crear. En las funciones siguientes tenemos primero el caso de lista vacía, seguido de la función que ejecutarán los nodos (los que todavía pueden crear procesos hijos) y finalmente cuando no podemos crear más procesos se resolverá simplemente llamando a qsort(L) (los procesos hoja del árbol de llamadas).

Algunas aclaraciones adicionales por si no estas muy puesto en Erlang:

• Con spawn estamos creando un nuevo proceso. En este caso le pasamos una referencia al actual proceso, tercer parámetro, para que nos "mande" sus resultados
• Con Variable ! Algo se está mandando el mensaje 'Algo' al proceso 'Variable'
• Erlang llama a las funciones con un matching de los parámetros (similar a prolog), en este ejemplo es bastante importante la condición when Limit > 2 que condicionará si crearemos más procesos o no
• La función gather es solo una función para "recolectar" un resultado que me he montado copié de Joe Amstrong:

   
  %%
  %% Purpose: Receive a response of a process which have sent {Ref, Something}
  %% Params :
  %%   - A erlang reference for matching the message
  %% Return : The second item inside the received message
  gather(Ref) ->
     receive
        {Ref, Ret} -> Ret
     end.

  Para hacer pruebas, me he creado un par de módulos erlang para facilitar la ejecución:

  • benchmark.erl: define do/1 y do_silent/1 a las cuales les pasamos una función y nos devolverá el tiempo en µs (e imprimiendo un mensaje por pantalla).
  • test_sorting.erl: define funciones para ejecutar algoritmos de ordenación generando listas de tamaño variable de forma aleatoria. Usa el modulo de benchmark anteriormente citado, para crear csv's con los resultados de las ejecuciones.

  Mientras se ejecutaban los algoritmos, me pareció que sería curioso capturar el consumo de cpu de ambos, te dejo que intentes adivinar cual se corresponde con el algoritmo "tradicional" y cual con el "paralelo" (no vale mirar el nombre ).

  
  

  Los resultados detallados, los he copiado en esta hoja de cálculo para OpenOffice, y un resumen de ellos los podemos ver en esta gráfica creada con gruff en ruby leyendo los csv generados desde erlang.

  

  El algoritmo paralelo es el doble de rápido que el tradicional, con valores medianos o grandes. Con valores menores a 1000 elementos es más costoso (al crear procesos, aunque erlang es mucho erlang, estamos incorporando un coste adicional, principalmente por el envío de mensajes, no por la creación per-se), pero en tales casos no sé para qué narices estamos mirando formas de mejorar el rendimiento, pues mil elementos los ordena hasta MySQL mi vecino.

  Lo que hay que destacar es la mejora sustancial conseguida, prácticamente sin cambiar nada (el código paralelo es trivial una vez se tiene la versión "normal").

  Algunas cosas interesantes de probar serían:

  • Intentar ésto mismo con un número de cpus mayor a 4, y encontrar la relación entre cpus y ganancia.
  • Crear algún "behaviour" para erlang para poder generalizar la paralelización de algoritmos de divide y vencerás (que son bastante comunes) y siguen este esquema con bastante homogeneidad.

  Si quieres obtener todos los ficheros para ojear o jugar por ti mismo, aquí lo tenemos.

  Have fun.