Влияние на статические затраты на планирование в OpenMP
Я думал о том, какие факторы будут влиять на статическое планирование в OpenMP.
На мой взгляд на это влияют:
- Производительность процессора
- конкретная реализация библиотеки времени выполнения OpenMP
- количество потоков
Но я пропускаю другие факторы? Может быть, размер задач, …?
И более того: линейно ли зависят накладные расходы от количества итераций?
В этом случае я ожидаю, что при статическом планировании и 4 ядрах накладные расходы возрастают линейно с 4 * i итерациями. Поправить пока?
РЕДАКТИРОВАТЬ:
Я заинтересован только в статических (!) Расписаниях. Я не говорю о накладных расходах при запуске потоков и о времени, затрачиваемом на синхронизацию и критические издержки секций.
Решение
Вам нужно разделить накладные расходы для OpenMP, чтобы создать команду / пул потоков, и накладные расходы для каждого потока, чтобы управлять отдельными наборами итераторов в цикле for.
Статическое планирование легко реализовать вручную (что иногда очень полезно). Давайте рассмотрим то, что я считаю двумя наиболее важными статического планирования schedule(static) а также schedule(static,1) тогда мы можем сравнить это с schedule(dynamic,chunk),
#pragma omp parallel for schedule(static)
for(int i=0; i<N; i++) foo(i);
эквивалентно (но не обязательно равно)
#pragma omp parallel
{
int start = omp_get_thread_num()*N/omp_get_num_threads();
int finish = (omp_get_thread_num()+1)*N/omp_get_num_threads();
for(int i=start; i<finish; i++) foo(i);
}
а также
#pragma omp parallel for schedule(static,1)
for(int i=0; i<N; i++) foo(i);
эквивалентно
#pragma omp parallel
{
int ithread = omp_get_thread_num();
int nthreads = omp_get_num_threads();
for(int i=ithread; i<N; i+=nthreads) foo(i);
}
Из этого вы можете видеть, что реализовать статическое планирование довольно тривиально, поэтому накладные расходы незначительны.
С другой стороны, если вы хотите реализовать schedule(dynamic) (что так же, как schedule(dynamic,1)) от руки все сложнее:
int cnt = 0;
#pragma omp parallel
for(int i=0;;) {
#pragma omp atomic capture
i = cnt++;
if(i>=N) break;
foo(i);
}
Для этого требуется OpenMP> = 3.1. Если вы хотите сделать это с OpenMP 2.0 (для MSVC), вам нужно использовать критическое, как это
int cnt = 0;
#pragma omp parallel
for(int i=0;;) {
#pragma omp critical
i = cnt++;
if(i>=N) break;
foo(i);
}
Вот эквивалент schedule(dynamic,chunk) (Я не оптимизировал это, используя атомарный доступ):
int cnt = 0;
int chunk = 5;
#pragma omp parallel
{
int start, finish;
do {
#pragma omp critical
{
start = cnt;
finish = cnt+chunk < N ? cnt+chunk : N;
cnt += chunk;
}
for(int i=start; i<finish; i++) foo(i);
} while(finish<N);
}
Очевидно, что использование атомарного доступа приведет к дополнительным расходам. Это также показывает, почему использование больших кусков для schedule(dynamic,chunk) может уменьшить накладные расходы.
Другие решения