C＃の並列パーティションアルゴリズム

Question

私は、配列を2つのリストに分割するために並列アルゴリズムを作成しました.1つの述語を満たす要素を含むものと、他のリストには満足しない要素が含まれています述語。これは注文保存アルゴリズムです。

私は以下のように書いていますが、ハードウェアの同時性から利益を得る機会を最大限に生かす方法を知りたいと思います。

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

データを小さなセグメントに分割し（例：Partitionerクラスを使用）、その位置に関連して各パーティションにインデックスを割り当てます。番号が付けられたパーティションごとに、パーティションを2つのグループに分割する「Task」を作成します.1つは述語と一致し、2つのグループは元のパーティションのインデックスとともに返されます。戻り値私はすべてのタスクが完了するのを待ってから、.Concat()（すべてのデータを実際にマージする際に時間を無駄にしないようにするため）、一致するグループをインデックスに、一致しないグループを同じグループにします。相対的なアイテムの順序を保持しながら、このように任意の程度の並列性を達成できるはずです。

Answer 2

リストが非常に長い場合は、2倍の並列性が得られません。代わりに、Parallel.Forを使用し、並列ループ状態としてスレッドローカルTuple<List<int>, List<int>>を使用することをお勧めします。 Parallel.For APIを使用すると、これを簡単に行うことができます。最後に個々のサブリストをマージすることができます。

このバージョンは恥ずかしそうに並行しており、同期がないためCPUバス上のコヒーレンシトラフィックがほとんど発生しません。

編集：すべてのスレッドで2つのリストを共有するだけでは、狂ったような同期オーバーヘッドが発生するため、共有することはできません。スレッドローカルリストを使用する必要があります。限られたCPU一貫性トラフィックを引き起こす連動操作を使用するため、ConcurrentQueueはこのシナリオには適していません。