11

最近，我回答了一个关于优化可能的可并行化方法以生成任意基数的每个排列的问题。我发布了一个类似于Parallelized, bad implementation code block list 的答案，有人几乎立即指出了这一点：

这几乎可以保证给您虚假共享，并且可能会慢很多倍。（归功于gjvdkamp）

他们是对的，这是死亡缓慢。也就是说，我研究了该主题，并找到了一些有趣的材料和建议（仅限 MSDN 杂志存档，.NET Matters: False Sharing）来对抗它。如果我理解正确，当线程访问连续内存（比如说，可能支持它的数组ConcurrentStack）时，可能会发生错误共享。

对于水平线以下的代码，aBytes是：

struct Bytes {
  public byte A; public byte B; public byte C; public byte D;
  public byte E; public byte F; public byte G; public byte H;
}

对于我自己的测试，我想获得这个运行的并行版本并且真正更快，所以我基于原始代码创建了一个简单的示例。6这limits[0]是我懒惰的选择——我的电脑有 6 个内核。

单线程块 平均运行时间：10s0059ms

  var data = new List<Bytes>();
  var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

  for (byte a = 0; a < limits[0]; a++)
  for (byte b = 0; b < limits[1]; b++)
  for (byte c = 0; c < limits[2]; c++)
  for (byte d = 0; d < limits[3]; d++)
  for (byte e = 0; e < limits[4]; e++)
  for (byte f = 0; f < limits[5]; f++)
  for (byte g = 0; g < limits[6]; g++)
  for (byte h = 0; h < limits[7]; h++)
    data.Add(new Bytes {
      A = a, B = b, C = c, D = d, 
      E = e, F = f, G = g, H = h
    });

并行化，实施不佳 平均运行时间：81s729ms，~ 8700 次争用

  var data = new ConcurrentStack<Bytes>();
  var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

  Parallel.For(0, limits[0], (a) => {
    for (byte b = 0; b < limits[1]; b++)
    for (byte c = 0; c < limits[2]; c++)
    for (byte d = 0; d < limits[3]; d++)
    for (byte e = 0; e < limits[4]; e++)
    for (byte f = 0; f < limits[5]; f++)
    for (byte g = 0; g < limits[6]; g++)
    for (byte h = 0; h < limits[7]; h++)
      data.Push(new Bytes {
        A = (byte)a,B = b,C = c,D = d,
        E = e,F = f,G = g,H = h
      });
  });

并行化，?? 执行 平均运行时间：5s833ms，92 次争用

  var data = new ConcurrentStack<List<Bytes>>();
  var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

  Parallel.For (0, limits[0], () => new List<Bytes>(), 
    (a, loop, localList) => { 
      for (byte b = 0; b < limits[1]; b++)
      for (byte c = 0; c < limits[2]; c++)
      for (byte d = 0; d < limits[3]; d++)
      for (byte e = 0; e < limits[4]; e++)
      for (byte f = 0; f < limits[5]; f++)
      for (byte g = 0; g < limits[6]; g++)
      for (byte h = 0; h < limits[7]; h++)
        localList.Add(new Bytes {
          A = (byte)a, B = b, C = c, D = d,
          E = e, F = f, G = g, H = h
        });
      return localList;
  }, x => {
    data.Push(x);
  });

我很高兴我有一个比单线程版本更快的实现。我预计结果接近 10s / 6 或 1.6 秒左右，但这可能是一个幼稚的期望。

我的问题是对于实际上比单线程版本更快的并行化实现，是否有可以应用于操作的进一步优化？我想知道与并行化相关的优化，而不是用于计算值的算法的改进。具体来说：

  • 我知道将存储和填充为 astruct而不是的优化byte[]，但它与并行化无关（或者是吗？）
  • 我知道可以使用波纹进位加法器对所需值进行惰性评估，但与struct优化相同。
4

1 回答 1

1

Parallel.For()首先，我最初的假设Parallel.ForEach()是错误的。

糟糕的并行实现很可能有 6 个线程都试图一次写入单个线程CouncurrentStack()。使用线程局部变量的良好实现（下面将详细解释）每个任务只访问一次共享变量，几乎消除了任何争用。

使用Parallel.For()and时Parallel.ForEach()，您不能简单地用它们进行内联替换for或foreach循环。这并不是说它不能是盲目的改进，而是如果不检查问题并对其进行检测，使用它们就是将多线程抛出一个问题，因为它可能会使其更快。

**Parallel.For()并且Parallel.ForEach()具有允许您为Task它们最终创建的本地状态创建的重载，并在每次迭代执行之前和之后运行表达式。

如果您有一个使用Parallel.For()or并行化的操作Parallel.ForEach()，则使用此重载可能是个好主意：

public static ParallelLoopResult For<TLocal>(
    int fromInclusive,
    int toExclusive,
    Func<TLocal> localInit,
    Func<int, ParallelLoopState, TLocal, TLocal> body,
    Action<TLocal> localFinally
)

例如，调用For()对从 1 到 100 的所有整数求和， 

var total = 0;

Parallel.For(0, 101, () => 0,  // <-- localInit
(i, state, localTotal) => { // <-- body
  localTotal += i;
  return localTotal;
}, localTotal => { <-- localFinally
  Interlocked.Add(ref total, localTotal);
});

Console.WriteLine(total);

localInit应该是一个初始化本地状态类型的 lambda，它被传递给body和localFinallylambdas。请注意，我不建议使用并行化实现 1 到 100 的总和，而只是提供一个简单的示例来缩短示例。

于 2015-04-25T06:20:04.213 回答