utilizar - repetir ciclos c#

Ahorre tiempo con el ciclo FOR paralelo

Question

Tengo una pregunta referente a los bucles 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 trato de 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 estándar para bucle, calcula aproximadamente 2 minutos, pero con el bucle paralelo para paralelo toma 3 min. ¿Por qué?

Answer 1

Consulte Particiones personalizadas para PLINQ y TPL :

En un bucle For , el cuerpo del bucle se proporciona al método como un delegado. El costo de invocar a ese delegado es casi lo mismo que una llamada de método virtual. En algunos casos, 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 del bucle sea significativo. En tales situaciones, puede usar una de las sobrecargas de Create para crear un IEnumerable<T> de particiones de rango sobre los elementos de origen. Luego, puede pasar esta colección de rangos a un método ForEach cuyo cuerpo consiste en un bucle normal para. 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;
        }
    });
}

Consulte también: documentación de Parallel.ForEach y documentación de Partitioner.Create .

Answer 2

Parallel.For implica una gestión de memoria más compleja. El resultado puede variar según las especificaciones de la CPU, como #cores, caché L1 y L2 ...

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

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

Answer 3

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 debe procesar grandes porciones de datos .

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

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 sencillo 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 demás respuestas es granularidad .

Answer 4

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 ejecutan su for, pero se intenta que la iteración de for se ejecute en paralelo, por lo que incluso con uno solo está usando varios subprocesos / procesos.

esto significa que la interacción con el índice = 0 y el índice = 1 se pueden ejecutar al mismo tiempo.

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

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

Answer 5

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

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

Para verificar esto, realicé algunas medidas: Ejecuté diferentes implementaciones de MultiplicateArray() en una matriz de 200 000 000 elementos (el código que usé está abajo). En mi máquina, la versión en serie consistentemente tomó 0.21 sy Parallel.For() usualmente tomó algo alrededor de 0.45 s, pero de vez en cuando, aumentó a 8–9 s.

Primero, trataré de mejorar el caso común y luego abordaré esos picos. Queremos procesar la matriz por N CPU, por lo que la dividimos en N partes del mismo tamaño y procesamos cada parte por separado. ¿El resultado? 0.35 s. Eso es aún peor que la versión serial. Pero 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 computando el límite del bucle podría ayudar. Resulta que sí: 0.18 s. Eso es mejor que la versión serial, pero no por mucho. Y, curiosamente, cambiar el grado de paralelismo de 4 a 2 en mi máquina de 4 núcleos (sin HyperThreading) no cambia el resultado: aún 0.18 s. Esto me hace concluir que la CPU no es el cuello de botella aquí, el ancho de banda de la memoria es.

Ahora, volviendo a los picos: mi paralelización personalizada no los tiene, pero Parallel.For() , ¿por qué? Parallel.For() usa particiones de rango, lo que significa que cada hilo procesa su propia parte de la matriz. Pero, si un hilo termina antes, tratará de ayudar a procesar el rango de otro hilo que aún no ha terminado. Si eso sucede, obtendrás un montón 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 de Parallel.For() parece ayudar un poco con los picos.

Por supuesto, todas esas mediciones son específicas del hardware en 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