Почему этот параллельный код в 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 для обеих реализаций:
Решение
Трудно сказать, потому что я не совсем понимаю, как должен работать ваш алгоритм, но похоже, что ваш код не является потокобезопасным, что заставляет алгоритм выполнять больше итераций, чем необходимо.
Я добавил это в конце PLP.run:
writeln(nIterations);
С 1 нить nIterations = 19
С 10 темы nIterations = 34
С 100 нитями nIterations = 90
Итак, как вы можете видеть, это занимает больше времени не из-за некоторых проблем с std.parallelism, но просто потому, что он делает больше работы.
Почему ваш код не является потокобезопасным?
Функция, которую вы запускаете параллельно propagateLabels, у которого есть общий, несинхронизированный доступ к labels, nUpdated, а также active, Кто знает, какое странное поведение это вызывает, но оно не может быть хорошим.
Перед тем, как приступить к профилированию, вам нужно исправить алгоритм, чтобы он был потокобезопасным
Другие решения
Как указывает Питер Александр, ваш алгоритм выглядит небезопасным. Чтобы сделать его потокобезопасным, вам необходимо устранить все зависимости данных между событиями, которые могут происходить в разных потоках одновременно или в неопределенном порядке. Один из способов сделать это — реплицировать состояние между потоками, используя WorkerLocalStorage (предоставлено в std.parallelism), и, возможно, объедините результаты в относительно дешевый цикл в конце вашего алгоритма.
В некоторых случаях процесс репликации этого состояния можно автоматизировать, написав алгоритм как сокращение и используя std.parallelism.reduce (возможно в сочетании с std.algorithm.map или же std.parallelism.map) сделать тяжелую работу.