10

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

这是 D 中的迭代器，使用taskPoolfrom实现std.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 进行并行化。那么缩放实验表明了什么？

缩放

在这里，我检查了弱缩放，将输入图大小加倍，同时将线程数加倍并测量运行时间。理想情况下应该是一条直线，但并行性当然会有一些开销。我defaultPoolThreads(nThreads)在我的 main 函数中使用来设置 D 程序的线程数。C++ 的曲线看起来不错，但 D 的曲线看起来非常糟糕。我在 D 并行性方面做错了什么，或者这是否严重反映了并行 D 程序的可扩展性？

ps 编译器标志

对于 D：rdmd -release -O -inline -noboundscheck

对于 C++：-std=c++11 -fopenmp -O3 -DNDEBUG

pps。一定是真的错了，因为并行的 D 实现比顺序的慢：

在此处输入图像描述

购买力平价。出于好奇，这里是两种实现的 Mercurial 克隆 url：

4

2 回答 2

8

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

我将此添加到末尾PLP.run：

writeln(nIterations);

1个线程nIterations = 19
10个线程nIterations = 34
100个线程nIterations = 90

正如您所看到的，它花费的时间更长并不是因为std.parallelism.

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

您并行运行的函数是propagateLabels，它具有对、和的共享、非同步访问。谁知道这会导致什么奇怪的行为，但它不会是好的。labelsnUpdatedactive

在开始分析之前，您需要将算法修复为线程安全的。

于 2013-07-31T17:59:51.517 回答
5

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

在某些情况下，复制此状态的过程可以通过将算法编写为约简并使用std.parallelism.reduce（可能与std.algorithm.mapor结合std.parallelism.map）来完成繁重的工作来自动化。

于 2013-07-31T19:47:18.227 回答