OpenMP для цикла for занимает гораздо больше времени, чем последовательный код
Я попробовал распараллелить фрагмент кода с помощью OpenMP, но оказалось, что для завершения работы программы требуется в 25 раз больше времени, чем при использовании OpenMP. Что-то не так? Как я могу его оптимизировать?
#include <iostream>
#include <cmath>
#include <random>
#include <chrono>
#include <cstdlib>
#include <omp.h>
using namespace std;
int main() {
unsigned long long black_square = 1, digit_square = 13;
//auto n = ((black_square)<<11) * static_cast<unsigned long long>(pow(digit_square,10));
auto n = static_cast<unsigned long long>(1e9);
srand(0);
int tmp = 0;
std::random_device rd; // Will be used to obtain a seed for the random number engine
std::mt19937 gen(rd()); // Standard mersenne_twister_engine seeded with rd()
std::uniform_int_distribution<> distrib(1, 6);
auto tStart = std::chrono::high_resolution_clock::now();
//#pragma omp parallel for schedule(static) reduction(+:tmp)
#pragma omp parallel for schedule(static) reduction(+:tmp) num_threads(8)
for (unsigned long long i=0; i<n; i++) tmp = (tmp+(5==rand()%6))%static_cast<int>(1e9);
//for (unsigned long long i=0; i<n; i++) tmp = (tmp+(5==distrib(gen)))%static_cast<int>(1e9);
tmp%=static_cast<int>(1e9);
auto tEnd = std::chrono::high_resolution_clock::now();
cout << tmp << " obtained after " << n << " iterations in " << (tEnd-tStart).count()/1e9 << "s." << endl;
return 0;
}
Код компилируется g++ -o a.out -O3 -std=c++11 -fopenmp tmp.cpp, где g++ имеет версию 8.5.0 20210514. ОС — RHEL8.9, их 20 Intel Xeon CPUs at 2.593GHz.
Последовательный код в среднем выполняется за 7,4 с, а параллельный код — за 180 с. Варианты -O3, -O2, -O1 дают аналогичные результаты. Генератор случайных чисел mt19937 мог бы значительно сократить разрыв в производительности, но параллельный код по-прежнему намного медленнее последовательной версии. Увеличение или уменьшение n также приводит к аналогичным результатам.
Обновление с результатами.
Я попробовал как подход массива, так и подход firstprivate, как указано в ответах/комментариях. Они имеют сопоставимые результаты, и оба достигают истинного параллелизма. Не проверять, одинаковы ли случайные последовательности из каждого потока в подходе firstprivate.
void array_approach(unsigned long long n, const int nThreads) {
int tmp = 0;
std::random_device rd; // Will be used to obtain a seed for the random number engine
vector<std::mt19937> rngs;
for (int i=0; i<nThreads*64; i++) rngs.push_back(std::mt19937(rd())); // Standard mersenne_twister_engine seeded with rd()
std::uniform_int_distribution<> distrib(1, 6);
auto tStart = std::chrono::steady_clock::now();
#pragma omp parallel for schedule(static) reduction(+:tmp) num_threads(nThreads)
for (unsigned long long i=0; i<n; i++) tmp = (tmp+(5==distrib(rngs[omp_get_thread_num()*64])))%static_cast<int>(1e9);
tmp%=static_cast<int>(1e9);
auto tEnd = std::chrono::steady_clock::now();
cout << tmp << " obtained after " << n << " iterations in " << (tEnd-tStart).count()/1e9 << "s." << endl;
}
void private_approach(unsigned long long n, const int nThreads) {
int tmp = 0;
std::random_device rd; // Will be used to obtain a seed for the random number engine
std::mt19937 rng(rd());
std::uniform_int_distribution<> distrib(1, 6);
auto tStart = std::chrono::steady_clock::now();
#pragma omp parallel for schedule(static) reduction(+:tmp) firstprivate(rng) num_threads(nThreads)
for (unsigned long long i=0; i<n; i++) tmp = (tmp+(5==distrib(rng)))%static_cast<int>(1e9);
tmp%=static_cast<int>(1e9);
auto tEnd = std::chrono::steady_clock::now();
cout << tmp << " obtained after " << n << " iterations in " << (tEnd-tStart).count()/1e9 << "s." << endl;
}
Действия в (tmp+(5==rand()%6))%static_cast<int>(1e9); чрезвычайно малы по стоимости по сравнению с накладными расходами на общий доступ при наличии одного общего объекта. Это гарантирует отсутствие параллельного выполнения, больше похожего на выполнение «шагового» выполнения.
Вы суммируете броски монеты: 1 с p=1/6, 0 с 1-p? Это имеет асимптотически нормальное распределение {np,sqrt(np*(1-p)}. Если вам нужно делать это параллельно, n велико, то нормальное распределение должно давать очень близкий результат. Я думаю, что операцию по модулю можно выполнить только в самом конце вместе с округлением до ближайшего целого числа.
@Chaitanya В коде есть reduction(+:tmp). Разве для каждого потока не создается локальная копия tmp? Я новичок в OpenMP.
@Quimby Да, по сути, это монета с вероятностью 1/6. Операция по модулю предназначена для предотвращения переполнения, когда n очень велико. Есть ли способ, чтобы каждый поток мог использовать свою собственную локальную переменную для модуля?
@cat Я предполагаю, что tmp обрабатывается OpenMP, проблема в том, что все остальные состояния - rand, distrib, gen - доступ к этим переменным должен быть сериализован. Я думаю, что лучше всего было бы, чтобы у каждого потока был свой собственный RNG, но я не знаю, как это сделать в OpenMP, извините.
rand() сохраняет внутреннее состояние. Чтобы rand был потокобезопасным, он должен запускаться последовательно, поэтому, вероятно, где-то есть блокировки мьютексов. Вместо этого вы можете попробовать использовать PRNG, который вы можете выполнять параллельно, при этом каждый поток имеет свое собственное состояние. Однако если вам нужен высокий уровень равномерности, это может быть нетривиально. Я думаю, что rand в любом случае просто использует линейное сравнение, поэтому вы можете получить что-то такое же хорошее, как rand, без особых усилий.
@cat накладные расходы на уменьшение «tmp» в конце каждый раз могут быть слишком высокими, но, как утверждали другие, я думаю, что rand() может быть основной проблемой, поскольку он не является потокобезопасным и обновляет свое внутреннее состояние каждый раз, когда он вызывается
Обратите внимание, что здесь не следует использовать high_resolution_clock, поскольку он не предназначен для измерения времени на настенных часах. Например, не гарантируется монотонность, поэтому время может быть отрицательным. Вместо этого вам следует использовать steady_clock или даже лучше: omp_get_wtime.
При использовании массива каждый rng инициализируется своим начальным числом. Ваш подход firstprivate создает частную копию с тем же начальным начальным значением. В качестве альтернативы вы можете попытаться создать rng внутри параллельной области и инициализировать его с разными начальными числами для каждого потока.
Ответы 1
Функция rand() не обязана быть потокобезопасной. Поэтому небезопасно вызывать его из нескольких потоков одновременно, как вы это делаете.
Версия rand() в glibc является потокобезопасной, но делает это за счет заключения всей функции в мьютекс. Таким образом, только один поток может вызывать rand() одновременно. Поскольку за пределами вызова rand ваш код делает очень мало, практически все время выполнения будет внутри rand().
Так что параллельная версия на самом деле не параллельна. Каждый поток по очереди выполняется по одному при каждом вызове rand(). Таким образом, он не имеет преимущества перед одним потоком. Но на самом деле все еще хуже, потому что потокам приходится бороться за то, кто получит мьютекс, просыпаться и засыпать после каждого вызова, а также перемещать состояние PRNG между кешем каждого ядра ЦП. Так что это намного хуже, чем однопоточный.
Что вам нужно сделать, так это создать несколько экземпляров PRNG. Имейте массив объекта gen, по одному для каждого потока. Каждый поток должен использовать свой собственный PRNG. Убедитесь, что каждый объект находится достаточно далеко друг от друга в памяти, чтобы не иметь общей строки кэша, поэтому состояние PRNG не нужно перемещать между кэшами ЦП.
Массив PRNG, конечно, не такая уж хорошая идея, обычно из-за ложного совместного использования (сериализация выполнения из-за отказа строки кэша, как вы упомянули). Добавление такого заполнения между элементами решает проблему, но пространство зависит от процессора, и терять много места не так уж и важно (например, 64–128 байт для состояния PRNG 4–16 байт). Конечно, лучше использовать частный PRNG потока, просто объявив его в параллельном регионе. Можно также использовать firstprivate для локального копирования ГПСЧ из общего массива, если таковой имеется, чтобы избежать ложного обмена, но первый вариант более эффективен (без копирования).
Я сказал, что нужно убедиться, что в массиве состояния расположены достаточно далеко друг от друга, чтобы не делиться ими. Используйте std::hardware_destructive_interference_size, чтобы узнать, насколько это далеко друг от друга. Никто не хочет копировать PRNG для каждого потока. Если при копировании они имеют одинаковое состояние, все они будут генерировать одну и ту же последовательность PRN!
Да. Хорошая точка зрения для hardware_destructive_interference_size, но мне интересно, равно ли это 128 на процессоре Intel, загружающем 2 строки кэша по 64 байта за выборку (AFAIK, это 64, что все же намного лучше, чем без заполнения). Что касается копии, я сказал «скопировать PRNG локально из общего массива», поэтому исходные PRNG отличаются;). Общий массив меньше, но все же занимает больше места, чем простая локальная инициализация, которой следует отдать предпочтение (особенно в системах NUMA).
Похоже, что к
tmpобращаются несколько потоков с использованием OpenMP, поскольку это одна переменная, накладные расходы, вносимые OpenMP при создании и управлении несколькими потоками, каждый из которых обращается кtmp, приведут к увеличению времени обработки.