Почему этот параллельный код в D так плохо масштабируется?

Вот один эксперимент, который я выполнил, сравнивая параллелизм в C ++ и D. Я реализовал алгоритм (параллельная схема распространения меток для обнаружения сообщества в сетях) на обоих языках, используя один и тот же дизайн: параллельный итератор получает функцию дескриптора (обычно замыкание) и применяет его для каждого узла в графе.

Вот итератор в D, реализованный с использованием taskPool от 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) в моей основной функции, чтобы установить количество потоков для программы D. Кривая для C ++ выглядит хорошо, но кривая для D выглядит на удивление плохо. Я делаю что-то не так с W.r.t. D параллелизм, или это плохо отражается на масштабируемости параллельных D программ?

постскриптум флаги компилятора

для D: rdmd -release -O -inline -noboundscheck

для C ++: -std=c++11 -fopenmp -O3 -DNDEBUG

имп. Что-то должно быть действительно неправильно, потому что реализация D медленнее параллельно, чем последовательно:

введите описание изображения здесь

ЧГП. Для любопытных вот URL Mercurial clone для обеих реализаций:

10

Решение

Трудно сказать, потому что я не совсем понимаю, как должен работать ваш алгоритм, но похоже, что ваш код не является потокобезопасным, что заставляет алгоритм выполнять больше итераций, чем необходимо.

Я добавил это в конце PLP.run:

writeln(nIterations);

С 1 нить nIterations = 19
С 10 темы nIterations = 34
С 100 нитями nIterations = 90

Итак, как вы можете видеть, это занимает больше времени не из-за некоторых проблем с std.parallelism, но просто потому, что он делает больше работы.

Почему ваш код не является потокобезопасным?

Функция, которую вы запускаете параллельно propagateLabels, у которого есть общий, несинхронизированный доступ к labels, nUpdated, а также active, Кто знает, какое странное поведение это вызывает, но оно не может быть хорошим.

Перед тем, как приступить к профилированию, вам нужно исправить алгоритм, чтобы он был потокобезопасным

8

Другие решения

Как указывает Питер Александр, ваш алгоритм выглядит небезопасным. Чтобы сделать его потокобезопасным, вам необходимо устранить все зависимости данных между событиями, которые могут происходить в разных потоках одновременно или в неопределенном порядке. Один из способов сделать это — реплицировать состояние между потоками, используя WorkerLocalStorage (предоставлено в std.parallelism), и, возможно, объедините результаты в относительно дешевый цикл в конце вашего алгоритма.

В некоторых случаях процесс репликации этого состояния можно автоматизировать, написав алгоритм как сокращение и используя std.parallelism.reduce (возможно в сочетании с std.algorithm.map или же std.parallelism.map) сделать тяжелую работу.

5