PLINQ并行化访问资源通过AsParallel().ForAll()

Question

假设我有许多在X,Y空间中的“粒子”，我想将它们全部归一化，使得平均X和Y值为0。

串行实现：

public void Normalise()
{
  double avgX = 0.0;
  double avgY = 0.0;

  foreach (Particle p in Particles)
  {
    avgX += p.X;
    avgY += p.Y;
  }

  avgX /= (double)Particles.Count;
  avgY /= (double)Particles.Count;

  foreach (Particle p in Particles)
  {
    p.X -= avgX;
    p.Y -= avgY;
  }
}

这个方法可以工作，并且性能不错，因为它是O(n)级别的，但它也是“尴尬并行”的。看一下我的PLINQ实现：

public void PNormalise()
{
  double avgX = 0.0;
  double avgY = 0.0;

  Particles.AsParallel().ForAll(p =>
  {
    avgX += p.X;
    avgY += p.Y;
  });

  avgX /= (double)Particles.Count;
  avgY /= (double)Particles.Count;

  Particles.AsParallel().ForAll(p =>
  {
    p.X -= avgX;
    p.Y -= avgY;
  });
}

我不确定这里的性能如何，但我想象它应该会更好。问题是，粒子都在随机跳动。我只能假设 avgX 和 avgY 上的 += 操作彼此竞争，即使它们已经相当原子化。

有什么办法可以解决吗？我不能锁定它们，因为它们不是对象，但我也不确定是否要锁定，因为锁定非常昂贵，是吗？

- Ozzah

---

“相对原子性”这种说法并不存在，一个操作要么是原子的，要么不是。 - svick

Answer 1

您可以通过使用Parallel LINQ的普通机制来避免需要锁定（或原子操作）：

var avgX = Particles.AsParallel().Average(p => p.X);
var avgY = Particles.AsParallel().Average(p => p.Y);

Particles.AsParallel().ForAll(p => { p.X -= avgX; p.Y -= avgY });

由于求和是一个 O(N) 的操作，如果这部分占据了任何显著的时间，我会非常惊讶。

- Mike Bailey

Answer 2

使用

Particles.AsParallel().ForAll(p =>
{
    Interlocked.Add(avgX, p.X);
    Interlocked.Add(avgY, p.Y);
}

要执行线程安全的原子加法操作。更多信息请参阅Interlocked Class的文档。

- Mathias Becher

---

更好的解决方案可能是进行并行求和，它可以自动为您处理这个问题。 - Mike Bailey

"Interlocked.Add" 只重载了 "(ref int, int)" 和 "(ref long, long)"，但我正在使用 "double"。 - Ozzah

Answer 3

实际上，并行化这个O(n)算法不会带来更好的性能，因为你大约有相同数量的内存访问和计算指令。

- Mathias Becher

---

我不知道JIT编译器是否这样做，但很可能它可以通过SSE处理器扩展将指令更改为 SIMD指令。这里有一篇博客，提供了关于CLR和SSE等扩展的更多信息。 - Scott Chamberlain

是的，但算法仍然受到内存限制，因此CPU仍然大部分处于空闲状态，但它所做的少量工作现在在其核心之间均匀分布。 - Mathias Becher

@MathiasBecher：像这样的O(N)问题在并行计算中非常好处理。如果问题规模变得更大，你可以基本上通过增加硬件来使其以与之前相似的水平运行。不过我同意，除非你有类似N = 10^7这样的情况，否则它可能有点琐碎。 - Mike Bailey