嵌套 Parallel.For 循环中的资源共享 C#

Question

背景

我有一段代码是高度可并行化的，我发现大多数时候我只使用一个 100% 的核心，而其余的什么都不做。为了解决这个问题，我修改了多线程、实现信号量以及没有意识到 Parallel.For() 比我的任何解决方案都更细粒度和更高效。

代码

为简化起见，我将只编写结构上重要的代码片段。

int sharedResource = 0;

for (int i = 0; i < someMax; i++)
{
    for (int j = 0; j <= i; j++)
    {
        if (someCondition(i, j))
            sharedResource += someFunction(i, j);
        else break;
    }
}

所有命名模糊的函数或多或少只是数学方程式，时间复杂度为 O(1)。

重要细节

注意以变量i为上边界的内循环以及名为[=34=的求和变量]共享资源。这种情况下的执行顺序并不重要，因为加法是可交换的，而且我没有看到任何明显的理由应用 Amdahl 定律，因为两个循环的所有实例组合 (i, j) 都可以独立计算。

问题

在这种情况下使用嵌套的 Parallel.For() 循环是否明智，或者我应该只使用它而不是外部循环（或分别只在内部循环）？

我唯一关心的是 sharedResource 因为我没有从文档中深入了解 Parallel.For() 的工作原理.另一件重要的事情是，如果我确实使用两个 Parallel.For() 循环，一些实例将由于 break 几乎立即完成，而其他实例将花费更多时间。它能平衡这个吗？

Answer 1

您可以使用一些启用了负载平衡的自定义分区程序，并在 Parallel.ForEach 循环中使用它。负载平衡确保每个核心都处于忙碌状态，直到执行结束。例如：

int sharedResource = 0;
var iterations = Enumerable.Range(0, someMax);

//this creates partitioner with load balancing (true is default for IEnumerable really)
var customPartitioner = Partitioner.Create(iterations, true); 

Parallel.ForEach(customPartitioner, i =>
{
    for (int j = 0; j <= i; j++)
    {
        if (someCondition(i, j))
            Interlocked.Add(ref sharedResource, someFunction(i, j)); 
        else break;
    }
});

在您的示例中，赋值运算符确实不是线程安全的，因此我改用了 Interlocked.Add。

您还可以编写一些可以通过设计使用 LINQ 并行化的功能代码。注意没有任何共享资源或线程同步，因为在 FP 中没有状态。

var result = customPartitioner
    .AsParallel()
    .Select(i => Enumerable.Range(0, i + 1)
        .AsParallel()
        .TakeWhile(j => someCondition(i, j))
        .Sum(j => someFunction(i, j)))
    .Sum();

您还需要考虑的一件事是线程创建成本。您创建的线程越多，处理器浪费在它上面而不是做实际工作的时间就越多。此外 Parallel.Foreach 在确定每次迭代应在哪个线程上提供额外成本运行。所以有时候最好有一些内部循环 single-threaded 。在 LINQ 示例中，在某些情况下，内部 AsParallel 可能确实会提供额外的成本。

Answer 2

是使用嵌套并行循环，仅并行化内部循环还是仅并行化外部循环，在很大程度上取决于数据的性质。嵌套的并行循环设计得相当好。例如，如果外循环和内循环的并行度均为 8 - 这并不意味着当嵌套时它们将在 8x8=64 线程上处理项目，就像天真地看这个时可能会想的那样。

您应该衡量所有选项在您的特定数据集上的性能，并找出最适合您的选项。

请注意，Parallel.For 循环分区间隔一定数量的范围（取决于并行度），然后这些范围在单独的线程上并行执行。这意味着：如果您的项目的处理时间是分布式的 non-evenly - 某些范围可能比其他范围更快完成。假设您运行的并行度为 4，并处理 100 个项目，其中前 75 个 return false 用于 someCondition，因此执行时间为 0，而最后 25 return true。结果，前 3 个范围将立即完成，所有实际工作的最后一个范围将在一个线程上执行，基本上使整个事情顺序进行。

如果预期分布不均匀，您可以使用 Parallel.ForEach 和 "real" IEnumerable 代替（我的意思是它不是数组或列表，而是真实的 "lazy" IEnumerable):

Parallel.ForEach(Enumerable.Range(0, i), j => {...})

但请注意，在均匀分布的数据上，它会比 pre-partitioned 版本慢。

如果 run-time 分布不均，嵌套 Parallel.For 也可能有帮助，但同样 - 您必须根据真实数据衡量每个选项并选择最佳的。

至于线程安全。当然，这个

sharedResource += someFunction(i, j);

在并行循环中不是线程安全的。如果 someFunction 很快，那么在这里使用 lock 可能会大大降低性能，而且无论如何都没有必要。要么只使用

Interlocked.Add(ref sharedResource, someFunction(i, j))

或者您可以使用 Parallel.For`Parallel.ForEach` 的重载，允许每个运行ning 线程累积值，然后聚合结果。例如：

Parallel.For(0, 100, (i, outerState) =>
{
   Parallel.ForEach(Enumerable.Range(0, i), () => 0, (j, innerState, subTotal) =>
   {
       if (someCondition(i, j))
           return subTotal + someFunction(i, j);
       else {
           innerState.Break();
           return subTotal;
       }
   }, subTotalOfThread => Interlocked.Add(ref sharedResource, subTotalOfThread));
});

嵌套 Parallel.For 循环中的资源共享 C#

Resource sharing in nested Parallel.For loop C#

c#

parallel-processing

parallel.for