C# 中的并行分区算法:如何最大化并行性

本文关键字：最大化 并行性 算法 并行 分区 | 更新日期: 2023-09-27 18:30:29

我用 C# 编写了一个并行算法，将数组划分为两个列表，一个列表包含满足给定谓词的元素，另一个列表包含无法满足谓词的元素。它是一种顺序保持算法。

我写的如下，但我想知道如何最大化从硬件并发中获利的机会。

    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);
    }

C# 中的并行分区算法:如何最大化并行性

如果你的列表很长，你不会从中获得太多的并行性（2x）。相反，我建议使用 Parallel.For 并使用线程本地Tuple<List<int>, List<int>>作为并行循环状态。Parallel.For API 允许您轻松完成此操作。您可以在末尾合并各个子列表。

这个版本是令人尴尬的并行的，并且由于没有同步，因此在 CPU 总线上几乎没有一致性流量。

编辑：我想强调的是，您不能只使用所有线程共享的两个List，因为这会导致疯狂的同步开销。您需要使用线程本地列表。甚至 ConcurrentQueue 都不适合这种情况，因为它使用互锁操作，这会导致 CPU 一致性流量受到限制。

我会将数据分区成小段（例如，使用 Partitioner 类），并根据其位置为每个分区分配一个索引。对于每个编号的分区，我将创建一个 Task，将分区拆分为两组，一组与谓词匹配，另一组不匹配，并返回这两个组以及它们源自的分区的索引作为任务的返回值。然后，我会等待所有任务完成，然后根据索引.Concat()（以防止浪费时间实际合并所有数据）匹配组，对于不匹配的组也是如此。您应该能够以这种方式实现任意程度的并行性，同时保留相对项目顺序。

相关文章：