Parallel Partition Algorithmus in C#: Wie Parallelität zu maximieren

Question

Ich habe einen parallelen Algorithmus in C# geschrieben, um ein Array in zwei Listen, eine, die Elemente enthält, die ein bestimmtes Prädikat erfüllt und die andere Liste enthält die Elemente, die nicht erfüllt erfüllen das Prädikat. Es ist ein Ordnung konservierender Algorithmus.

Ich habe es wie folgt geschrieben, aber ich möchte wissen, wie Sie die Möglichkeit maximieren können, von Hardware-Nebenläufigkeit zu profitieren.

static void TestPLinqPartition(int cnt = 1000000) 
    { 
     Console.WriteLine("PLINQ Partition"); 
     var a = RandomSequenceOfValuesLessThan100(cnt).ToArray(); 
     var sw = new Stopwatch(); 
     sw.Start(); 
     var ap = a.AsParallel(); 
     List<int> partA = null; 
     List<int> partB = null; 
     Action actionA =() => { partA = (from x in ap where x < 25 select x).ToList(); }; 
     Action actionB =() => { partB = (from x in ap where !(x < 25) select x).ToList(); }; 
     Parallel.Invoke(actionA, actionB); 
     sw.Stop(); 

     Console.WriteLine("Partion sizes = {0} and {1}", partA.Count, partB.Count); 
     Console.WriteLine("Time elapsed = {0} msec", sw.ElapsedMilliseconds); 
    } 

Answer 1

Ich würde die Daten in kleine Segmente (z. B. unter Verwendung der Partitioner Klasse) partitionieren und jeder Partition einen Index in Bezug auf ihre Position zuweisen. Für jede nummerierte Partition würde ich eine Task erstellen, die die Partition in zwei Gruppen teilt, eine, die mit dem Prädikat übereinstimmt und eine, die das nicht tut, und die beiden Gruppen zusammen mit dem Index der Partition, von der sie stammen Rückgabewert. Ich würde dann warten, bis alle Aufgaben abgeschlossen sind, und dann .Concat() (um zu verhindern, dass beim Zusammenführen aller Daten Zeit verschwendet wird) die übereinstimmenden Gruppen nach ihrem Index und die gleichen nach den nicht übereinstimmenden Gruppen. Sie sollten in der Lage sein, auf diese Weise einen beliebigen Grad an Parallelität zu erreichen, während Sie die relative Reihenfolge der Objekte beibehalten.

Answer 2

Wenn Ihre Listen sehr lang sind, werden Sie nicht viel Parallelität erhalten (2x). Stattdessen würde ich empfehlen, eine Parallel.For zu verwenden und eine Thread-lokale Tuple<List<int>, List<int>> als den parallelen Loop-Status zu verwenden. Mit der Parallel.For-API können Sie dies problemlos durchführen. Sie können die einzelnen Teillisten am Ende zusammenführen.

Diese Version ist peinlich parallel und verursacht fast keinen Kohärenzverkehr auf dem CPU-Bus, weil es keine Synchronisation gibt.

Edit: Ich möchte betonen, dass Sie nicht nur zwei Listen von allen Threads geteilt verwenden können, weil das Synchronisation Overhead wie verrückt verursachen wird. Sie müssen Thread-lokale Listen verwenden. Nicht einmal eine ConcurrentQueue ist für dieses Szenario geeignet, da sie Interlocked-Operationen verwendet, die CPU-Kohärenzverkehr verursachen, der begrenzt ist.