为什么D中的这个并行代码缩放非常糟糕？

这是我在C++和D中比较并行性的一个实验。我使用相同的设计在两种语言中实现了一种算法（用于网络中社区检测的并行标签传播方案）：并行迭代器获取句柄函数（通常为闭包）并将其应用于图中的每个节点。为什么D中的这个并行代码缩放非常糟糕？

下面是使用在d迭代器，实现从taskPoolstd.parallelism：

/** 
* Iterate in parallel over all nodes of the graph and call handler (lambda closure). 
*/ 
void parallelForNodes(F)(F handle) { 
    foreach (node v; taskPool.parallel(std.range.iota(z))) { 
     // call here 
     handle(v); 
    } 
}

这是被传递手柄功能：

auto propagateLabels = (node v){ 
     if (active[v] && (G.degree(v) > 0)) { 
      integer[label] labelCounts; 

      G.forNeighborsOf(v, (node w) { 
       label lw = labels[w]; 
       labelCounts[lw] += 1; // add weight of edge {v, w} 
      }); 

      // get dominant label 
      label dominant; 
      integer lcmax = 0; 
      foreach (label l, integer lc; labelCounts) { 
       if (lc > lcmax) { 
        dominant = l; 
        lcmax = lc; 
       } 
      } 

     if (labels[v] != dominant) { // UPDATE 
      labels[v] = dominant; 
      nUpdated += 1; // TODO: atomic update? 
      G.forNeighborsOf(v, (node u) { 
       active[u] = 1; 
      }); 
     } else { 
      active[v] = 0; 
     } 

     } 
    };

的C++ 11执行几乎是相同但是使用OpenMP进行并行化。那么缩放实验显示了什么？

scaling

在这里，我检查弱缩放，加倍输入图形的尺寸，同时也增加一倍的线程的数目和测量的运行时间。理想将是一条直线，但当然有一些并行的开销。我在主函数中使用defaultPoolThreads(nThreads)来设置D程序的线程数。 C++曲线看起来不错，但D曲线看起来非常糟糕。我做错了什么吗？ D并行性，还是这反映严重的并行D程序的可扩展性？

p.s.编译器标记

为d：rdmd -release -O -inline -noboundscheck

为C++：-std=c++11 -fopenmp -O3 -DNDEBUG

PPS。东西一定是真的错了，因为d实现并行顺序比慢：

enter image description here

购买力平价。对于好奇，这里有水银克隆网址，这两种方案：

来源

2013-07-30 clstaudt

如果你没有使用openmp，那么性能会如何？ – greatwolf

从检查它看起来不像dmd编译器目前支持openmp。如果一个版本使用openmp，而另一个版本不使用，它看起来不像是一个苹果对苹果的比较。 – greatwolf

@greatwolf除非我误解了你，否则我相信你错过了这一点。 D没有OpenMP，但它有'std.parallelism'库，它提供了类似的并行结构。实际上，D程序在运行时使用了许多内核。 – clstaudt

这很难说，因为我不完全理解你的算法是如何工作的，但它看起来像你的代码不是线程安全的，这导致算法运行更多的迭代超过必要的。

我已将此添加的PLP.run末：

writeln(nIterations);

随着1线程nIterations = 19
随着10个线程nIterations = 34
随着100个线程3210

因此，大家可以看到，它需要更长的时间不因为std.parallelism有些问题，但只是因为它正在做更多的工作。

为什么你的代码不是线程安全的？

你并行运行的功能是propagateLabels，这已共享，非同步访问labels，nUpdated，和active。谁知道这是什么奇怪的行为造成的，但它不可能是好的。

在开始分析之前，您需要修复算法以确保线程安全。

来源

2013-07-31 17:59:51

良好的观察。对我而言，有趣的问题是：为什么这种行为与D几乎完全相同的C++实现有如此不同？我知道线程共享'labels'，'active'和'nUpdated'。这种情况对于C++/OpenMP实现来说是一样的，它不是问题。 – clstaudt

不幸的是，我对OpenMP并不熟悉，但它从事作业的方式可能与std.parallelism不同，因此OpenMP解决方案可能“正常工作”并且与您正在运行的东西有关。 –

正如Peter Alexander指出的那样，您的算法似乎是线程不安全的。为了使其成为线程安全的，您需要消除可能在不同线程中同时或以未定义顺序发生的事件之间的所有数据依赖关系。一种方法是使用WorkerLocalStorage（在std.parallelism中提供）跨线程复制某些状态，并可能在算法结束时以相对便宜的循环合并结果。

在某些情况下复制此状态的过程中可以通过写算法作为还原和使用std.parallelism.reduce（可能与std.algorithm.map或std.parallelism.map组合），以做繁重自动化。

来源

2013-07-31 19:47:18 dsimcha

为什么D中的这个并行代码缩放非常糟糕？

回答

相关问题