Twitter Facebook RSS Feed

jueves, 15 de octubre de 2009 a las 15:36hs por Gustavo Cantero (The Wolf)

Parallel.For

La clase Parallel, del namespace System.Threading, posee varios métodos estáticos para realizar operaciones paralelas de forma sencilla y sin mucho código agregado. Uno de esos métodos es el For, el cual crea un ciclo (al igual que su sentencia homónima) donde se van a ejecutar tantas iteraciones al mismo tiempo como procesadores libres disponga la aplicación. Este método posee tres parámetros: el número desde el cual se realizará el ciclo (inclusive), el número hasta el que se realizará (excluido) y un delegado:

Parallel.For(int desdeInclusive, int hastaExcluido, Action acción)

Action es un delegado con generic a ejecutar: aquí deberemos poner el delegado con el código a correr en cada iteración. Para entenderlo mejor vamos a hacer un ejemplo: supongamos que necesitamos obtener la cantidad de números primos que hay entre el número 0 y el 99.999, comúnmente haríamos algo como esto:

int cant1 = 0;
for (int valor = 0; valor < 100000; valor++)
{
    if (valor < 2)
        cant1++;
    else
    {
        bool divisible = false;
        for (int temp = 2; !divisible && temp < valor; temp++)
        {
            if (valor % temp == 0)
                divisible = true;
        }
        if (!divisible)
            cant1++;
    }
}

Este ejemplo es un algoritmo sencillo creado sólo para esta demostración y no es la manera más eficiente de verificar si un número es primo ya que se le podrían hacer mejoras, por ejemplo, verificando la divisibilidad sólo hasta el resultado de la raíz cuadrada del valor a verificar. Esto mismo sucede con los algoritmos que modificaremos para que utilicen paralelismo, los cuales aunque usen TPL trataremos de que queden lo más parecidos posibles al original para comparar sus tiempos.
Volviendo al ejemplo, si modificamos el ciclo para que utilice Parallel.For, como en el siguiente código, probablemente el resultado lo devolverá en mucho menos tiempo, dependiendo de los procesadores disponibles de nuestra máquina:

int cant2 = 0;
Parallel.For(0, 100000, (valor) =>
{
    if (valor < 2)
        cant2++;
    else
    {
        bool divisible = false;
        for (int temp = 2; !divisible && temp < valor; temp++)
        {
            if (valor % temp == 0)
                divisible = true;
        }
        if (!divisible)
            cant2++;
    }
});

En el ejemplo hay dos ciclos “for” que se podrían ejecutar con paralelismo, pero gracias al primero tenemos hasta 100.000 tareas potencialmente ejecutables en paralelo y, al menos hasta dentro de varios años, no existen PCs de escritorio con tantos procesadores, por lo tanto crear otro ciclo anidado con paralelismo sólo generaría un overhead innecesario. Otro punto que posee esta rutina es que los distintos threads van a acceder a la variable “cant2”, lo cual podría generar errores en la contabilidad de números primos encontrados, pero más adelante veremos cómo resolver este tema. Para los que no están familiarizados con las expresiones lambda, cabe mencionar que en C# el código:

(valor) => {...}

es equivalente a esto:

delegate(int valor) {...}

Al ejecutar ambos códigos, en mi computadora que posee un procesador de doble núcleo, el primero demoró 11,241 segundos en recorrer los 100.000 números y verificar cuales eran primos, mientras que el segundo (que utiliza paralelismo) demoró 5,883 segundos, casi la mitad de tiempo. Si vemos el gráfico de utilización de los procesadores creado por el administrador de tareas (lo configuré para que muestre la suma de los procesadores) veremos cuanto consumió del total disponible cada rutina:

Administrador de tareas y TPL

Parallel.ForEach

Hay veces donde no nos sirve recorrer una secuencia ordenada de valores como nos ofrece el ciclo Parallel.For, sino que necesitamos recorrer los valores de una colección o un vector y, por cada ítem, realizar una acción. Para estos casos TPL posee otro ciclo llamado Parallel.ForEach, el cual realiza la misma acción que el ciclo foreach clásico pero con paralelismo, tomando cada uno de los ítems de un objeto que herede de IEnumerable. Supongamos que en lugar de querer obtener la cantidad de números primos entre el 0 y el 99.999 necesitamos saber cuáles números de una lista son primos. La lista que vamos a utilizar para el ejemplo es la que se muestra a continuación, a la cual le agregué 84 números primos para hacer que la tarea sea más larga (ya que cuando un número es primo se verifica si es divisible por todos los números entre 2 y ese mismo número menos uno):

int[] numeros = new int[] {
    1998697, 1998701, 1998727, 1998739, 1998761, 1998793,
    1998817, 1998827, 1998839, 1998881, 1998917, 1998923,
    1998943, 1998947, 1998949, 1998961, 1998977, 1998991,
    1999007, 1999021, 1999033, 1999043, 1999061, 1999069,
    1999099, 1999103, 1999111, 1999121, 1999163, 1999177,
    1999187, 1999211, 1999219, 1999223, 1999243, 1999247,
    1999817, 1999819, 1999853, 1999859, 1999867, 1999871,
    1999889, 1999891, 1999957, 1999969, 1999979, 1999993,
    1999273, 1999297, 1999301, 1999303, 1999307, 1999331,
    1999339, 1999343, 1999363, 1999379, 1999423, 1999441,
    1999471, 1999499, 1999511, 1999513, 1999537, 1999549,
    1999559, 1999561, 1999567, 1999603, 1999607, 1999619,
    1999631, 1999633, 1999651, 1999661, 1999667, 1999681,
    1999691, 1999703, 1999721, 1999733, 1999771, 1999799,
    1000000, 34000000, 7654321, 9876543, 76544321, 2000000000,
    1745345434, 2143945834, 1232435643, 2123432424 };

Un ejemplo de cómo realizar la tarea de forma secuencial utilizando esta lista sería como se muestra en el siguiente código:

int cant1 = 0;
foreach (int valor in numeros)
{
    if (valor < 2)
        cant1++;
    else
    {
        bool divisible = false;
        for (int temp = 2; !divisible && temp < valor; temp++)
        {
            if (valor % temp == 0)
                divisible = true;
        }
        if (!divisible)
            cant1++;
    }
}

Pero si queremos utilizar paralelismo para acelerar la ejecución podríamos hacerlo de esta forma:

int cant2 = 0;
Parallel.ForEach(numeros, (valor) =>
{
    if (valor < 2)
        cant2++;
    else
    {
        bool divisible = false;
        for (int temp = 2; !divisible && temp < valor; temp++)
        {
            if (valor % temp == 0)
                divisible = true;
        }
        if (!divisible)
            cant2++;
    }
});

Este código en mi PC con sin y con paralelismo demoró 5,482 y 2,849 segundos en ejecutar respectivamente.
Cuando se utiliza la librería TPL hay que tener cuidado de no intentar reducir el tiempo de respuesta de nuestras aplicaciones ejecutando en paralelo rutinas que demoran muy poco, o de anidar rutinas que ya se ejecutan con paralelismo, ya que el overhead y la asignación de memoria de las variables de los delegados puede hacer que el tiempo empleado en ejecutarlas se incremente. Por ejemplo, si en el código anterior comentamos las primeras líneas del la asignación del vector dejando sólo las últimas 3 líneas, con un total de 16 números (de los cuales sólo 6 son primos) los tiempos cambian, demorando en mi máquina 0,395 segundos en ejecutarse secuencialmente y 0,507 segundos en ejecutarse con paralelismo. La decisión de que rutinas ejecutar en paralelo y cuáles no es una tarea que se aprende con el análisis, las pruebas y la experiencia.

Parallel.Invoke

Los ciclos anteriores son muy útiles para muchos casos, pero no sirven si necesitamos ejecutar distintas subrutinas en paralelo (en realidad se puede hacer con un switch o case dentro del ciclo, pero no es muy claro a la hora de leer o modificar el código). Para esto la clase Parallel provee otro método estático llamado Invoke, el cual toma como parámetro un vector de delegados (params en C# o ParamArray en Visual Basic), los cuales apuntan a las distintas subrutinas que son potencialmente ejecutables en paralelo.
Por ejemplo, supongamos que tenemos que correr tres tareas independientes que no necesitan ejecutarse secuencialmente, podríamos hacerlo de la siguiente manera:

Parallel.Invoke(Tarea1, Tarea2, Tarea3);

Los tres métodos de la clase Parallel poseen la misma forma de manejar los errores: si en alguna de las tareas se genera un error, se cancelarán todas las tareas pendientes y se lanzará la excepción AggregateException, con las excepciones generadas dentro de su propiedad InnerExceptions.

0 comentarios »

Deja un comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.