为什么D中的并行代码如此严重？

Question

这是我在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:

• http://algohub.iti.kit.edu/parco/Prototypes/PLPd
• http://algohub.iti.kit.edu/parco/Prototypes/PLPcpp

Answer 1

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

我把它添加到了结尾PLP.run:

writeln(nIterations);

1个螺纹,nIterations = 19
10个螺纹,nIterations = 34
100个螺纹nIterations = 90

正如你所看到的,它花费的时间更长,并不是因为它存在一些问题std.parallelism,而仅仅是因为它正在做更多的工作.

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

你在并行运行的功能propagateLabels,这已经共享,不同步的访问labels,nUpdated和active.谁知道这造成了什么奇怪的行为,但它并不好.

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

Answer 2

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

在某些情况下,复制这种状态的过程可以通过将算法编写为减少并使用std.parallelism.reduce(可能与std.algorithm.map或组合std.parallelism.map)来进行繁重的自动化来自动化.