mise à l'échelle non linéaire des opérations .NET sur la machine multi-core

Question

Je l'ai rencontré un comportement étrange dans une application .NET qui effectue un traitement hautement parallèle sur un ensemble de données en mémoire.

Lorsqu'il est exécuté sur un processeur à plusieurs noyaux (IntelCore2 Quad Q6600 2,4 GHz), il présente une mise à l'échelle non linéaire en plusieurs threads débuté pour traiter les données.

Lorsqu'il est exécuté sous forme de boucle non multithread sur un noyau unique, le procédé est capable de compléter environ 2,4 millions de calculs par seconde. Lorsqu'il est exécuté en quatre threads que vous attendez quatre fois plus débit - quelque part dans le quartier de 9 millions de calculs par seconde - mais hélas, pas. Dans la pratique, il complète seulement environ 4,1 millions par seconde ... un peu court du débit attendu.

En outre, le problème se produit, peu importe si j'utilise PLINQ, un pool de threads, ou quatre fils explicitement créés. Très étrange ...

Rien d'autre est en cours d'exécution sur la machine en utilisant le temps CPU ni qu'il y ait des verrous ou d'autres objets de synchronisation impliqués dans le calcul ... il devrait juste se déchirer avant les données. J'ai confirmé ce (dans la mesure du possible) en examinant les données perfmon alors que le processus fonctionne ... et il n'y a pas de fil contentions signalés ou l'activité de collecte des ordures.

Mes théories au moment:

1. Les frais généraux de toutes les techniques (changements de contexte de fil, etc.) submergent les calculs
2. Les fils ne reçoivent pas assignés à chacun des quatre cœurs et passer un peu de temps d'attente sur le même noyau de processeur .. ne sais pas comment tester cette théorie ...
3. threads CLR .NET ne sont pas en cours d'exécution à la priorité prévu ou ont une surcharge interne cachée.

Voici un extrait représentatif du code qui devrait présenter le même comportement:

    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

Alors j'ai finalement compris quel était le problème -. Et je pense qu'il serait utile de partager avec la communauté SO

Toute la question avec des performances non-linéaire est le résultat d'une seule ligne à l'intérieur de la méthode de Evaluate():

var coordMatrix = new long[100];

Depuis Evaluate() est invoqué des millions de fois, cette allocation de mémoire se produisait des millions de fois. En l'occurrence, le CLR effectue intérieurement une certaine synchronisation inter-fil lors de l'allocation mémoire - sinon, l'affectation sur plusieurs threads pourrait par inadvertance se chevaucher. Modification de la matrice à partir d'une instance de procédé locale à une instance de classe qui est seulement attribué une fois (mais alors dans une boucle d'initialisation de la méthode locale) éliminé le problème d'évolutivité.

Normalement, il est un anti créer un élément de niveau classe pour une variable qui est utilisée uniquement (et significative) dans le cadre d'un procédé unique. Mais dans ce cas, puisque je besoin de la plus grande évolutivité possible, je vais vivre avec (et document) cette optimisation.

Epilogue:. Après avoir fait ce changement, le processus simultané a été en mesure d'atteindre 12,2 millions de calculs / s

P.S. Kudos à Igor Ostrovsky pour son lien germane aux blogs MSDN qui m'a aidé à identifier et à diagnostiquer le problème.

Answer 2

Jetez un oeil à cet article: http: // blogs.msdn.com/pfxteam/archive/2008/08/12/8849984.aspx

Plus précisément, limiter les allocations de mémoire dans la région parallèle, et inspecter soigneusement écrit pour vous assurer qu'ils ne se produisent pas à proximité des emplacements de mémoire que d'autres threads lecture ou d'écriture.

Answer 3

mise à l'échelle non linéaire est à prévoir avec un algorithme parallèle par rapport à un algorithme séquentiel, car il y a une surcharge inhérente à la parallélisation. (Idéalement, bien sûr, vous voulez obtenir aussi près que possible.)

De plus, il y aura généralement certaines choses que vous devez prendre en charge dans un algorithme parallèle que vous n'avez pas besoin dans un algorithme séquentiel. Au-delà de la synchronisation (qui peut vraiment enliser votre travail), il y a d'autres choses qui peuvent se produire:

• La CPU et l'OS ne peut pas consacrer tout son temps à votre application. Ainsi, il doit faire le changement de contexte de temps en temps pour laisser d'autres processus se fait un peu de travail. Lorsque vous utilisez seulement un seul noyau, il est moins probable que votre processus est passé en marche, parce qu'il a trois autres noyaux à choisir. Notez que même si vous ne le pensez rien est en cours d'exécution d'autre, le système d'exploitation ou certains services pourraient encore être performants des travaux de fond.
• Si chacun de vos fils accède à un grand nombre de données, et ces données n'est pas commun entre les threads, vous aurez très probablement pas être en mesure de stocker tout cela dans le cache du processeur. Cela signifie que beaucoup plus de mémoire accédant nécessaire, ce qui est (relativement) lente.

Pour autant que je peux dire, votre approche explicite actuelle utilise un iterator partagé entre les fils. C'est une solution acceptable si le traitement varient énormément à travers le tableau, mais il est susceptible d'être en tête de synchronisation pour empêcher un élément d'être sautée (récupérer l'élément en cours et en déplaçant le pointeur interne à l'élément suivant doit être une opération atomique pour empêcher sauter un élément).

Par conséquent, il pourrait être une meilleure idée de diviser le tableau, en supposant que le temps de traitement de chaque élément devrait être à peu près égale quelle que soit la position de l'élément. Étant donné que vous avez 10 millions de disques, cela signifie dire fil 1 à travailler sur des éléments 0 à 2.499.999, fil 2 travaille sur des éléments 2.500.000 à 4.999.999, etc. Vous pouvez attribuer chaque thread un ID et utiliser pour calculer la portée réelle.

Une autre petite amélioration serait de laisser le principal instrument de fil comme l'un des fils qui calcule. Cependant, si je me souviens bien, c'est un très petite chose.

Answer 4

Je ne voudrais certainement pas attendre une relation linéaire, mais je l'aurais pensé que vous auriez vu un gain plus grand que cela. Je suppose que l'utilisation du processeur est maximisé sur tous les cœurs. Juste quelques pensées sur le dessus de ma tête.

• Utilisez-vous des structures de données partagées (explicitement ou implicitement) qui nécessitent une synchronisation?
• Avez-vous essayé le profilage ou l'enregistrement des compteurs de performance pour déterminer le goulot d'étranglement est où? Pouvez-vous donner plus d'indices.

Edit:. Désolé, je viens de remarquer que vous avez déjà abordé à la fois de mes points