Ahorre tiempo con parallel FOR loop

Question

Ahorre tiempo con parallel FOR loop

Tengo una pregunta sobre los bucles for paralelos. Tengo el siguiente código:

    public static void MultiplicateArray(double[] array, double factor)
    {
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = array[i] * factor;
        }
    }

    public static void MultiplicateArray(double[] arrayToChange, double[] multiplication)
    {
        for (int i = 0; i < arrayToChange.Length; i++)
        {
            arrayToChange[i] = arrayToChange[i] * multiplication[i];
        }
    }

    public static void MultiplicateArray(double[] arrayToChange, double[,] multiArray, int dimension)
    {
        for (int i = 0; i < arrayToChange.Length; i++)
        {
            arrayToChange[i] = arrayToChange[i] * multiArray[i, dimension];
        }
    }

Ahora intento agregar la función paralela:

    public static void MultiplicateArray(double[] array, double factor)
    {
        Parallel.For(0, array.Length, i =>
            {
                array[i] = array[i] * factor;
            });
    }

    public static void MultiplicateArray(double[] arrayToChange, double[] multiplication)
    {
        Parallel.For(0, arrayToChange.Length, i =>
        {
            arrayToChange[i] = arrayToChange[i] * multiplication[i];
        });
    }

    public static void MultiplicateArray(double[] arrayToChange, double[,] multiArray, int dimension)
    {
        Parallel.For(0, arrayToChange.Length, i =>
        {
            arrayToChange[i] = arrayToChange[i] * multiArray[i, dimension];
        });
    }

El problema es que quiero ahorrar tiempo, no desperdiciarlo. Con el bucle for estándar calcula unos 2 minutos, pero con el bucle for paralelo tarda 3 minutos. ¿Por qué?

41

c#.net parallel-extensions

Author: Anton K, 2012-09-13

Source

5 answers

Svick ya proporcionó una gran respuesta, pero me gustaría enfatizar que el punto clave no es "paralelizar su código manualmente" en lugar de usar Parallel.For(), sino que tiene que procesar trozos más grandes de datos .

Esto todavía se puede hacer usando Parallel.For() así:

static void My(double[] array, double factor)
{
    int degreeOfParallelism = Environment.ProcessorCount;

    Parallel.For(0, degreeOfParallelism, workerId =>
    {
        var max = array.Length * (workerId + 1) / degreeOfParallelism;
        for (int i = array.Length * workerId / degreeOfParallelism; i < max; i++)
            array[i] = array[i] * factor;
    });
}

Que hace lo mismo que svicks CustomParallelExtractedMax() pero es más corto, más simple y (en mi máquina) funciona incluso un poco más rápido:

Serial: 3,94 s
Parallel.For: 9,28 s
Parallel.For (degree of parallelism): 9,58 s
Custom parallel: 2,05 s
Custom parallel (extracted max): 1,19 s
Custom parallel (extracted max, half parallelism): 1,49 s
Custom parallel (false sharing): 27,88 s
My: 0,95 s

Por cierto, la palabra clave para esto que falta en todas las otras respuestas es granularidad.

14

Author: Roman Reiner,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-08-04 14:44:50

Paralelo.Para implica una gestión de memoria más compleja. Ese resultado podría variar dependiendo de las especificaciones de la cpu, como # cores, caché L1 y L2...

Por favor, echa un vistazo a este interesante artículo:

Http://msdn.microsoft.com/en-us/magazine/cc872851.aspx

6

Author: Jordi,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-09-13 13:38:52

Ver Particionadores personalizados para PLINQ y TPL :

En un bucle For, el cuerpo del bucle se proporciona al método como delegado. El costo de invocar ese delegado es aproximadamente el mismo que una llamada a un método virtual. En algunos escenarios, el cuerpo de un bucle paralelo puede ser lo suficientemente pequeño como para que el costo de la invocación del delegado en cada iteración de bucle sea significativo. En tales situaciones, puede usar una de las sobrecargas Create para crear un IEnumerable<T> de particiones de rango sobre los elementos fuente. Luego, puede pasar esta colección de rangos a un método ForEach cuyo cuerpo consiste en un bucle for regular. El beneficio de este enfoque es que el costo de invocación del delegado se incurre solo una vez por rango, en lugar de una vez por elemento.

En su cuerpo de bucle, está realizando una sola multiplicación, y la sobrecarga de la llamada de delegado será muy notable.

Prueba esto:

public static void MultiplicateArray(double[] array, double factor)
{
    var rangePartitioner = Partitioner.Create(0, array.Length);

    Parallel.ForEach(rangePartitioner, range =>
    {
        for (int i = range.Item1; i < range.Item2; i++)
        {
            array[i] = array[i] * factor;
        }
    });
}

Véase también: Parallel.ForEach documentación y Partitioner.Create documentación.

4

Author: Kris Vandermotten,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-02-07 11:52:41

De http://msdn.microsoft.com/en-us/library/system.threading.tasks.parallel.aspx y http://msdn.microsoft.com/en-us/library/dd537608.aspx

No está creando tres subprocesos/procesos que ejecuten su for, pero la iteración del for se intenta que sea executet en paralelo, por lo que incluso con solo uno para está utilizando múltiples subprocesos/procesos.

Esto significa que la interación con index = 0 e index = 1 puede ejecutarse al mismo tiempo.

Probablemente usted están forzando a usar demasiado hilo / proceso,y la sobrecarga para la creación/ejecución de ellos es mayor que la ganancia de velocidad.

Intente usar tres normales para pero en tres subprocesos/procesos diferentes, si su sistema es multinúcleo (3x al menos) debería tomar menos de un minuto

-6

Author: Lesto,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-09-13 13:33:16

score 53 · Accepted Answer

Parallel.For() puede mejorar mucho el rendimiento al paralelizar su código, pero también tiene sobrecarga (sincronización entre subprocesos, invocando al delegado en cada iteración). Y dado que en su código, cada iteración es muy corta (básicamente, solo unas pocas instrucciones de CPU), esta sobrecarga puede llegar a ser prominente.

Debido a esto, pensé que usar Parallel.For() no es la solución correcta para usted. En su lugar, si paraleliza su código manualmente (lo cual es muy simple en este caso), puede ver el rendimiento mejora.

Para verificar esto, realicé algunas mediciones: Ejecuté diferentes implementaciones de MultiplicateArray() en una matriz de 200 000 000 elementos (el código que utilicé está a continuación). En mi máquina, la versión en serie tomó consistentemente 0.21 s y Parallel.For() por lo general tomó algo alrededor de 0.45 s, pero de vez en cuando, se disparó a 8-9 s!

En primer lugar, voy a tratar de mejorar el caso común y voy a llegar a esos picos más tarde. Queremos procesar el array por N CPUs, así que lo dividimos en N partes de igual tamaño y procesar cada parte por separado. El resultado? 0.35 s. Eso es aún peor que la versión en serie. Pero for el bucle sobre cada elemento en una matriz es una de las construcciones más optimizadas. ¿No podemos hacer algo para ayudar al compilador? Extraer la computación del límite del bucle podría ayudar. Resulta que sí: 0.18 s. Eso es mejor que la versión en serie, pero no por mucho. Y, curiosamente, cambiar el grado de paralelismo de 4 a 2 en mi máquina de 4 núcleos (no HyperThreading) no cambia el resultado: todavía 0.18 s. Esto me hace concluir que la CPU no es el cuello de botella aquí, el ancho de banda de memoria es.

Ahora, de vuelta a los picos: mi paralelización personalizada no los tiene, pero Parallel.For() los tiene, ¿por qué? Parallel.For() utiliza particiones de rango, lo que significa que cada subproceso procesa su propia parte de la matriz. Pero, si un hilo termina temprano, intentará ayudar a procesar el rango de otro hilo que aún no ha terminado. Si eso sucede, obtendrá mucho de intercambio falso, lo que podría ralentizar mucho el código. Y mi propia prueba con forzar el intercambio falso parece indicar que este podría ser el problema. Forzar el grado de paralelismo del Parallel.For() parece ayudar un poco con los picos.

Por supuesto, todas esas mediciones son específicas para el hardware de mi computadora y serán diferentes para usted, por lo que debe hacer sus propias mediciones.

El código que utilicé:

static void Main()
{
    double[] array = new double[200 * 1000 * 1000];

    for (int i = 0; i < array.Length; i++)
        array[i] = 1;

    for (int i = 0; i < 5; i++)
    {
        Stopwatch sw = Stopwatch.StartNew();
        Serial(array, 2);
        Console.WriteLine("Serial: {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        ParallelFor(array, 2);
        Console.WriteLine("Parallel.For: {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        ParallelForDegreeOfParallelism(array, 2);
        Console.WriteLine("Parallel.For (degree of parallelism): {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        CustomParallel(array, 2);
        Console.WriteLine("Custom parallel: {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        CustomParallelExtractedMax(array, 2);
        Console.WriteLine("Custom parallel (extracted max): {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        CustomParallelExtractedMaxHalfParallelism(array, 2);
        Console.WriteLine("Custom parallel (extracted max, half parallelism): {0:f2} s", sw.Elapsed.TotalSeconds);

        sw = Stopwatch.StartNew();
        CustomParallelFalseSharing(array, 2);
        Console.WriteLine("Custom parallel (false sharing): {0:f2} s", sw.Elapsed.TotalSeconds);
    }
}

static void Serial(double[] array, double factor)
{
    for (int i = 0; i < array.Length; i++)
    {
        array[i] = array[i] * factor;
    }
}

static void ParallelFor(double[] array, double factor)
{
    Parallel.For(
        0, array.Length, i => { array[i] = array[i] * factor; });
}

static void ParallelForDegreeOfParallelism(double[] array, double factor)
{
    Parallel.For(
        0, array.Length, new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount },
        i => { array[i] = array[i] * factor; });
}

static void CustomParallel(double[] array, double factor)
{
    var degreeOfParallelism = Environment.ProcessorCount;

    var tasks = new Task[degreeOfParallelism];

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
    {
        // capturing taskNumber in lambda wouldn't work correctly
        int taskNumberCopy = taskNumber;

        tasks[taskNumber] = Task.Factory.StartNew(
            () =>
            {
                for (int i = array.Length * taskNumberCopy / degreeOfParallelism;
                    i < array.Length * (taskNumberCopy + 1) / degreeOfParallelism;
                    i++)
                {
                    array[i] = array[i] * factor;
                }
            });
    }

    Task.WaitAll(tasks);
}

static void CustomParallelExtractedMax(double[] array, double factor)
{
    var degreeOfParallelism = Environment.ProcessorCount;

    var tasks = new Task[degreeOfParallelism];

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
    {
        // capturing taskNumber in lambda wouldn't work correctly
        int taskNumberCopy = taskNumber;

        tasks[taskNumber] = Task.Factory.StartNew(
            () =>
            {
                var max = array.Length * (taskNumberCopy + 1) / degreeOfParallelism;
                for (int i = array.Length * taskNumberCopy / degreeOfParallelism;
                    i < max;
                    i++)
                {
                    array[i] = array[i] * factor;
                }
            });
    }

    Task.WaitAll(tasks);
}

static void CustomParallelExtractedMaxHalfParallelism(double[] array, double factor)
{
    var degreeOfParallelism = Environment.ProcessorCount / 2;

    var tasks = new Task[degreeOfParallelism];

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
    {
        // capturing taskNumber in lambda wouldn't work correctly
        int taskNumberCopy = taskNumber;

        tasks[taskNumber] = Task.Factory.StartNew(
            () =>
            {
                var max = array.Length * (taskNumberCopy + 1) / degreeOfParallelism;
                for (int i = array.Length * taskNumberCopy / degreeOfParallelism;
                    i < max;
                    i++)
                {
                    array[i] = array[i] * factor;
                }
            });
    }

    Task.WaitAll(tasks);
}

static void CustomParallelFalseSharing(double[] array, double factor)
{
    var degreeOfParallelism = Environment.ProcessorCount;

    var tasks = new Task[degreeOfParallelism];

    int i = -1;

    for (int taskNumber = 0; taskNumber < degreeOfParallelism; taskNumber++)
    {
        tasks[taskNumber] = Task.Factory.StartNew(
            () =>
            {
                int j = Interlocked.Increment(ref i);
                while (j < array.Length)
                {
                    array[j] = array[j] * factor;
                    j = Interlocked.Increment(ref i);
                }
            });
    }

    Task.WaitAll(tasks);
}

Ejemplo de salida:

Serial: 0,20 s
Parallel.For: 0,50 s
Parallel.For (degree of parallelism): 8,90 s
Custom parallel: 0,33 s
Custom parallel (extracted max): 0,18 s
Custom parallel (extracted max, half parallelism): 0,18 s
Custom parallel (false sharing): 7,53 s
Serial: 0,21 s
Parallel.For: 0,52 s
Parallel.For (degree of parallelism): 0,36 s
Custom parallel: 0,31 s
Custom parallel (extracted max): 0,18 s
Custom parallel (extracted max, half parallelism): 0,19 s
Custom parallel (false sharing): 7,59 s
Serial: 0,21 s
Parallel.For: 11,21 s
Parallel.For (degree of parallelism): 0,36 s
Custom parallel: 0,32 s
Custom parallel (extracted max): 0,18 s
Custom parallel (extracted max, half parallelism): 0,18 s
Custom parallel (false sharing): 7,76 s
Serial: 0,21 s
Parallel.For: 0,46 s
Parallel.For (degree of parallelism): 0,35 s
Custom parallel: 0,31 s
Custom parallel (extracted max): 0,18 s
Custom parallel (extracted max, half parallelism): 0,18 s
Custom parallel (false sharing): 7,58 s
Serial: 0,21 s
Parallel.For: 0,45 s
Parallel.For (degree of parallelism): 0,40 s
Custom parallel: 0,38 s
Custom parallel (extracted max): 0,18 s
Custom parallel (extracted max, half parallelism): 0,18 s
Custom parallel (false sharing): 7,58 s