c# - programming - Escalado no lineal de operaciones.NET en máquinas multinúcleo

task parallel library

Question

He encontrado un comportamiento extraño en una aplicación .NET que realiza un procesamiento altamente paralelo en un conjunto de datos en memoria.

Cuando se ejecuta en un procesador multinúcleo (IntelCore2 Quad Q6600 2.4GHz) exhibe una escala no lineal ya que se inician varios hilos para procesar los datos.

Cuando se ejecuta como un bucle no multiproceso en un único núcleo, el proceso puede completar aproximadamente 2.4 millones de cálculos por segundo. Cuando se ejecuta como cuatro hilos esperaría cuatro veces más rendimiento, en algún lugar en la vecindad de 9 millones de cálculos por segundo, pero ¡ay !, no. En la práctica, solo completa unos 4.1 millones por segundo ... bastante corto del rendimiento esperado.

Además, el comportamiento ocurre independientemente de si uso PLINQ, un grupo de subprocesos o cuatro subprocesos creados explícitamente. Bastante extraño...

No se está ejecutando nada más en la máquina usando el tiempo de CPU, ni hay bloqueos u otros objetos de sincronización involucrados en el cálculo ... simplemente debería avanzar a través de los datos. Lo he confirmado (en la medida de lo posible) mirando los datos perfmon mientras se ejecuta el proceso ... y no hay conflictos de hilos informados ni actividad de recolección de basura.

Mis teorías en este momento:

1. La sobrecarga de todas las técnicas (interruptores de contexto de hilo, etc.) es abrumadora para los cálculos
2. Los hilos no se asignan a cada uno de los cuatro núcleos y pasan algún tiempo esperando en el mismo núcleo del procesador. No estoy seguro de cómo probar esta teoría ...
3. Los subprocesos .NET CLR no se ejecutan con la prioridad esperada o tienen algunos gastos indirectos internos ocultos.

A continuación se muestra un extracto representativo del código que debe exhibir el mismo comportamiento:

    var evaluator = new LookupBasedEvaluator();

    // find all ten-vertex polygons that are a subset of the set of points
    var ssg = new SubsetGenerator<PolygonData>(Points.All, 10);

    const int TEST_SIZE = 10000000;  // evaluate the first 10 million records

    // materialize the data into memory...
    var polygons = ssg.AsParallel()
                      .Take(TEST_SIZE)
                      .Cast<PolygonData>()
                      .ToArray();

    var sw1 = Stopwatch.StartNew();
    // for loop completes in about 4.02 seconds... ~ 2.483 million/sec
    foreach( var polygon in polygons )
        evaluator.Evaluate(polygon);
    s1.Stop(); 
    Console.WriteLine( "Linear, single core loop: {0}", s1.ElapsedMilliseconds );

    // now attempt the same thing in parallel using Parallel.ForEach...
    // MS documentation indicates this internally uses a worker thread pool
    // completes in 2.61 seconds ... or ~ 3.831 million/sec
    var sw2 = Stopwatch.StartNew();
    Parallel.ForEach(polygons, p => evaluator.Evaluate(p));
    sw2.Stop();
    Console.WriteLine( "Parallel.ForEach() loop: {0}", s2.ElapsedMilliseconds );

    // now using PLINQ, er get slightly better results, but not by much
    // completes in 2.21 seconds ... or ~ 4.524 million/second
    var sw3 = Stopwatch.StartNew();
    polygons.AsParallel(Environment.ProcessorCount)
            .AsUnordered() // no sure this is necessary...
            .ForAll( h => evalautor.Evaluate(h) );
    sw3.Stop();
    Console.WriteLine( "PLINQ.AsParallel.ForAll: {0}", s3.EllapsedMilliseconds );

    // now using four explicit threads:
    // best, still short of expectations at 1.99 seconds = ~ 5 million/sec
    ParameterizedThreadStart tsd = delegate(object pset) { foreach (var p in (IEnumerable<Card[]>) pset) evaluator.Evaluate(p); };
     var t1 = new Thread(tsd);
     var t2 = new Thread(tsd);
     var t3 = new Thread(tsd);
     var t4 = new Thread(tsd);

     var sw4 = Stopwatch.StartNew(); 
     t1.Start(hands);
     t2.Start(hands);
     t3.Start(hands);
     t4.Start(hands);
     t1.Join();
     t2.Join();
     t3.Join();
     t4.Join();
     sw.Stop();
     Console.WriteLine( "Four Explicit Threads: {0}", s4.EllapsedMilliseconds );

Answer 1

Ciertamente no esperaría una relación lineal, pero habría pensado que habría visto una ganancia mayor que esa. Estoy asumiendo que el uso de la CPU está al máximo en todos los núcleos. Solo un par de pensamientos fuera de mi cabeza.

• ¿Está utilizando estructuras de datos compartidas (explícita o implícitamente) que requieren sincronización?
• ¿Has probado perfilar o registrar contadores de rendimiento para determinar dónde está el cuello de botella? ¿Puedes dar más pistas?

Editar: Lo siento, me acabo de dar cuenta de que ya ha abordado mis dos puntos.

Answer 2

Eche un vistazo a este artículo: http://blogs.msdn.com/pfxteam/archive/2008/08/12/8849984.aspx

Específicamente, limite las asignaciones de memoria en la región paralela e inspeccione cuidadosamente las escrituras para asegurarse de que no ocurran cerca de las ubicaciones de memoria que otros hilos leen o escriben.

Answer 3

El escalado no lineal es de esperar con un algoritmo paralelo en comparación con un algoritmo secuencial, ya que hay una sobrecarga inherente en la paralelización. (Idealmente, por supuesto, desea acercarse lo más posible).

Además, generalmente habrá ciertas cosas que debe tener en cuenta en un algoritmo paralelo que no necesita en un algoritmo secuencial. Más allá de la sincronización (que realmente puede empantanar su trabajo), hay algunas otras cosas que pueden suceder:

• La CPU y el sistema operativo no pueden dedicar todo su tiempo a su aplicación. Por lo tanto, debe hacer el cambio de contexto de vez en cuando para permitir que otros procesos realicen algún trabajo. Cuando solo está utilizando un único núcleo, es menos probable que su proceso esté desactivado, ya que tiene otros tres núcleos para elegir. Tenga en cuenta que aunque piense que no se está ejecutando nada más, el sistema operativo o algunos servicios aún podrían estar realizando algún trabajo en segundo plano.
• Si cada uno de sus subprocesos tiene acceso a una gran cantidad de datos, y estos datos no son comunes entre los subprocesos, lo más probable es que no pueda almacenar todo esto en el caché de la CPU. Eso significa que se requiere mucho más acceso a la memoria, que es (relativamente) lento.

Por lo que puedo decir, su enfoque explícito actual utiliza un iterador compartido entre los hilos. Esa es una buena solución si el procesamiento varía enormemente en toda la matriz, pero es probable que haya una sobrecarga de sincronización para evitar que se salte un elemento (recuperar el elemento actual y mover el puntero interno al siguiente elemento debe ser una operación atómica para evitar omitiendo un elemento).

Por lo tanto, podría ser una mejor idea dividir la matriz, suponiendo que se espera que el tiempo de procesamiento de cada elemento sea aproximadamente igual independientemente de la posición del elemento. Dado que tiene 10 millones de registros, eso significa que el hilo 1 debe trabajar en los elementos 0 a 2,499,999, el hilo 2 funciona en los elementos 2,500,000 a 4,999,999, etc. Puede asignar a cada hilo una ID y usar esto para calcular el rango real.

Otra pequeña mejora sería dejar que el hilo principal actúe como uno de los hilos que calcula. Sin embargo, si mal no recuerdo, es algo muy leve.

Answer 4

Así que finalmente descubrí cuál era el problema, y ​​creo que sería útil compartirlo con la comunidad SO.

Todo el problema con el rendimiento no lineal fue el resultado de una sola línea dentro del método Evaluate() :

var coordMatrix = new long[100];

Dado que Evaluate() se invoca millones de veces, esta asignación de memoria se producía millones de veces. Como ocurre, el CLR realiza internamente alguna sincronización entre subprocesos al asignar memoria; de lo contrario, la asignación en varios subprocesos podría solaparse inadvertidamente. Cambiar el conjunto de una instancia local de método a una instancia de clase que solo se asigna una vez (pero luego inicializar en un bucle local de método) eliminó el problema de escalabilidad.

Normalmente, es un antipatrón crear un miembro de nivel de clase para una variable que solo se usa (y tiene sentido) dentro del alcance de un único método. Pero en este caso, dado que necesito la mayor escalabilidad posible, viviré con (y documentaré) esta optimización.

Epílogo: Después de hacer este cambio, el proceso simultáneo pudo lograr 12.2 millones de cálculos / seg.

PD Felicitaciones a Igor Ostrovsky por su enlace relacionado con los blogs de MSDN que me ayudó a identificar y diagnosticar el problema.

Answer 5

He hecho una pregunta similar aquí titulada "¿Por qué mi aplicación roscada .Net no escala linealmente cuando se asignan grandes cantidades de memoria?"

¿Por qué mi aplicación roscada .Net no escala linealmente cuando se asignan grandes cantidades de memoria?