Как избежать накладных расходов openMP в вложенных циклах

У меня есть две версии кода, которые дают эквивалентные результаты, когда я пытаюсь распараллелить только внутренний цикл вложенного цикла for. Я не получаю много ускорения, но я не ожидал от 1 до 1, так как я пытаюсь только распараллелить внутренний цикл.

Мой главный вопрос: почему эти две версии имеют схожие версии? Разве только второй вариант fork нить один раз и избежать накладных расходов на запуск новых потоков на каждой итерации по i, как в первой версии?

Первая версия кода запускает потоки на каждой итерации внешнего цикла следующим образом:

for(i=0; i<2000000; i++){
  sum = 0;
  #pragma omp parallel for private(j) reduction(+:sum)
  for(j=0; j<1000; j++){
    sum += 1;
  }
  final += sum;
}
printf("final=%d\n",final/2000000);

С этим выходом и временем выполнения:

OMP_NUM_THREADS = 1

final=1000
real    0m5.847s
user    0m5.628s
sys     0m0.212s

OMP_NUM_THREADS = 4

final=1000
real    0m4.017s
user    0m15.612s
sys     0m0.336s

Вторая версия кода запускает потоки один раз (?) перед внешним циклом и распараллеливает внутренний цикл следующим образом:

#pragma omp parallel private(i,j)
for(i=0; i<2000000; i++){
  sum = 0;
  #pragma omp barrier
  #pragma omp for reduction(+:sum)
  for(j=0; j<1000; j++){
    sum += 1;
  }
  #pragma omp single
  final += sum;
}
printf("final=%d\n",final/2000000);

С этим выходом и временем выполнения:

OMP_NUM_THREADS = 1

final=1000
real    0m5.476s
user    0m4.964s
sys     0m0.504s

OMP_NUM_THREADS = 4

final=1000
real    0m4.347s
user    0m15.984s
sys     0m1.204s

Почему вторая версия не намного быстрее первой? Разве не избежать накладных расходов на запуск потоков на каждой итерации цикла или я что-то не так?

Ответы

Ответ 1

Реализация OpenMP может использовать объединение потоков для устранения накладных расходов на запуск потоков при столкновении с параллельной конструкцией. Пул потоков OMP_NUM_THREADS запускается для первой параллельной конструкции, и после завершения построения подчиненные потоки возвращаются в пул. Эти незанятые потоки могут быть перераспределены, когда встречается более поздняя параллельная конструкция.

См., например, это объяснение объединение потоков в реализации Sun Studio OpenMP.

Ответ 2

Похоже, вы возвращаете шаги Закон Amdahl: в нем говорится о параллельном процессе и его собственных накладных расходах. Одна вещь, найденная Amadhl, была независимо от того, сколько parallelism вы вложили в программу, для начала всегда будет одинаковое ускорение. parallelism только начинает улучшать время выполнения/производительность, когда программе требуется достаточная работа, чтобы компенсировать дополнительную вычислительную мощность.