Parallel Framework et éviter les faux échanges

Récemment, j’avais répondu à une question sur l’optimisation d’une méthode probablement parallélisable pour la génération de chaque permutation de nombres de base arbitraires. J’ai posté une réponse similaire à la liste de blocs de code à implémentation parallèle et médiocre , et quelqu’un a presque immédiatement signalé ceci:

Ceci est quasiment garanti pour vous donner un faux partage et sera probablement beaucoup plus lent. (crédit à gjvdkamp )

et ils avaient raison, la mort était lente. Cela dit, j’ai effectué des recherches sur le sujet et trouvé des éléments intéressants et des suggestions (magazine archivé MSDN uniquement, .NET Matters: False Sharing ) pour le combattre. Si je le comprends bien, lorsque les threads accèdent à la mémoire contiguë (par exemple, le tableau qui sauvegarde probablement ce ConcurrentStack ), un faux partage se produit probablement.


Pour le code situé sous la règle horizontale, un Bytes est:

 struct Bytes { public byte A; public byte B; public byte C; public byte D; public byte E; public byte F; public byte G; public byte H; } 

Pour mes propres tests, je voulais obtenir une version parallèle de cette opération et être véritablement plus rapide. J’ai donc créé un exemple simple basé sur le code d’origine. 6 comme limits[0] était un choix paresseux de ma part – mon ordinateur a 6 cœurs.

Bloc de threads Temps d’exécution moyen: 10s0059ms

  var data = new List(); var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 }; for (byte a = 0; a < limits[0]; a++) for (byte b = 0; b < limits[1]; b++) for (byte c = 0; c < limits[2]; c++) for (byte d = 0; d < limits[3]; d++) for (byte e = 0; e < limits[4]; e++) for (byte f = 0; f < limits[5]; f++) for (byte g = 0; g < limits[6]; g++) for (byte h = 0; h < limits[7]; h++) data.Add(new Bytes { A = a, B = b, C = c, D = d, E = e, F = f, G = g, H = h }); 

Mise en œuvre parallélisée et médiocre Temps d’ exécution moyen: 81s729ms, ~ 8700 conflits

  var data = new ConcurrentStack(); var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 }; Parallel.For(0, limits[0], (a) => { for (byte b = 0; b < limits[1]; b++) for (byte c = 0; c < limits[2]; c++) for (byte d = 0; d < limits[3]; d++) for (byte e = 0; e < limits[4]; e++) for (byte f = 0; f < limits[5]; f++) for (byte g = 0; g < limits[6]; g++) for (byte h = 0; h < limits[7]; h++) data.Push(new Bytes { A = (byte)a,B = b,C = c,D = d, E = e,F = f,G = g,H = h }); }); 

Parallélisé, ?? mise en oeuvre durée moyenne: 5s833ms, 92 contentions

  var data = new ConcurrentStack<List>(); var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 }; Parallel.For (0, limits[0], () => new List(), (a, loop, localList) => { for (byte b = 0; b < limits[1]; b++) for (byte c = 0; c < limits[2]; c++) for (byte d = 0; d < limits[3]; d++) for (byte e = 0; e < limits[4]; e++) for (byte f = 0; f < limits[5]; f++) for (byte g = 0; g < limits[6]; g++) for (byte h = 0; h  { data.Push(x); }); 

Je suis heureux d’avoir une implémentation plus rapide que la version à thread unique. Je m’attendais à un résultat plus proche d’environ 10s / 6, soit environ 1,6 seconde, mais c’est probablement une attente naïve.

Ma question concerne l’implémentation parallélisée qui est en réalité plus rapide que la version à thread unique. Existe-t-il d’autres optimisations qui pourraient être appliquées à l’opération? Je m’interroge sur les optimisations liées à la parallélisation, pas sur les améliorations apscopes à l’algorithme utilisé pour calculer les valeurs. Plus précisément:

  • Je connais l’optimisation de stocker et peupler en tant que struct au lieu d’ byte[] , mais ce n’est pas lié à la parallélisation (ou est-ce?)
  • Je sais qu’une valeur désirée peut être évaluée paresseuse avec un additionneur à transfert, mais identique à l’optimisation de la struct .

Premièrement, mon hypothèse initiale concernant Parallel.For() et Parallel.ForEach() était fausse.

La faible implémentation parallèle a très probablement 6 threads essayant tous d’écrire sur un seul CouncurrentStack() à la fois. La bonne mise en œuvre utilisant les sections locales de thread (expliquées plus en détail ci-dessous) n’accède qu’à la variable partagée une fois par tâche, ce qui élimine presque tout conflit.

Lorsque vous utilisez Parallel.For() et Parallel.ForEach() , vous ne pouvez pas simplement remplacer en ligne une boucle for ou foreach par eux. Cela ne veut pas dire que cela ne pourrait pas être une amélioration aveugle, mais sans examiner le problème et l’inventer, son utilisation jetterait le problème de la lecture à répétition multiple car cela pourrait accélérer les choses.

** Parallel.For() et Parallel.ForEach() ont des surcharges qui vous permettent de créer un état local pour la Task finalement créée et d’exécuter une expression avant et après l’exécution de chaque itération.

Si vous avez une opération que vous parallélisez avec Parallel.For() ou Parallel.ForEach() , il est probablement judicieux d’utiliser cette surcharge:

 public static ParallelLoopResult For( int fromInclusive, int toExclusive, Func localInit, Func body, Action localFinally ) 

Par exemple, appelez For() pour additionner tous les entiers de 1 à 100,

 var total = 0; Parallel.For(0, 101, () => 0, // <-- localInit (i, state, localTotal) => { // <-- body localTotal += i; return localTotal; }, localTotal => { <-- localFinally Interlocked.Add(ref total, localTotal); }); Console.WriteLine(total); 

localInit doit être un lambda qui initialise le type d'état local, qui est transmis au body et à localFinally lambdas. Veuillez noter que je ne recommande pas de mettre en oeuvre la sommation 1 à 100 en utilisant la parallélisation, mais juste un exemple simple pour le rendre bref.