неуравновешенный вложенные петли в openmp

Question

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

for (i = 0; i < 100; i++) { 
    #pragma omp parallel for private(j, k) 
    for (j = 0; j < 1000000; j++) { 
     for (k = 0; k < 2; k++) { 
      temp = i * j * k;  /* dummy operation (don't mind the race) */ 
     } 
     if (i % 2 == 0) temp = 0; /* so I can't use openmp collapse */ 
    } 
} 

В настоящее время этот пример работает медленнее в нескольких потоках (~ 1 сек в одном потоке ~ 2,4 с в 2 потоках и т. Д.).

Things отметить:

• Внешний цикл должно быть сделано для того, (в зависимости от предыдущего шага) (Насколько я знаю, OpenMP обрабатывает внутренние петли хорошо, поэтому потоки не получают созданные/уничтожены на каждом шаге, верно?)

• Типичные номера индексов приведены в примере (100, 1000000, 2)

• операция пустышки состоит всего из нескольких операций

• Есть некоторые условные операции за пределами внутренней большей петли, так Распад не вариант (не кажется, что это приведет к увеличению производительности в любом случае)

Похоже смущающий параллельному алгоритм, но я могу» t, похоже, получает ускорение за последние два дня. Что было бы лучшей стратегией здесь?

Answer 1

К сожалению, этот неловко параллельный алгоритм является неловким примером того, как должен реализовываться исполнительный параллелизм. И так как мой кристаллический шар говорит мне, что кроме i, temp также является общей переменной переменной, я бы предположил ее для остальной части этого текста. Это также говорит мне, что у вас есть процессор pre-Nehalem ...

Здесь есть два источника замедления - преобразование кода и когерентность кэша.

Способ параллельных областей заключается в том, что их код извлекается отдельными функциями. Общие локальные переменные извлекаются в структуры, которые затем распределяются между нитями в команде, которая выполняет параллельную область.Под OpenMP преобразований вашего пример коды станет чем-то похоже на это:

typedef struct { 
    int i; 
    int temp; 
} main_omp_fn_0_shared_vars; 

void main_omp_fn_0 (void *data) { 
    main_omp_fn_0_shared_vars *vars = data; 

    // compute values of j_min and j_max for this thread 

    for (j = j_min; j < j_max; j++) { 
     for (k = 0; k < 2; k++) { 
      vars->temp = vars->i * j * k; 
     if (vars->i % 2 == 0) vars->temp = 0; 
    } 
} 

int main (void) { 
    int i, temp; 
    main_omp_fn_0_shared_vars vars; 

    for (i = 0; i < 100; i++) 
    { 
     vars.i = i; 
     vars.temp = temp; 

     // This is how GCC implements parallel regions with libgomp 

     // Start main_omp_fn_0 in the other threads 
     GOMP_parallel_start(main_omp_fn_0, &vars, 0); 

     // Start main_omp_fn_0 in the main thread 
     main_omp_fn_0(&vars); 

     // Wait for other threads to finish (implicit barrier) 
     GOMP_parallel_end(); 

     i = vars.i; 
     temp = vars.temp; 
    } 
} 

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

Другим источником деградации является протокол когерентности кэш-памяти. Доступ к одной и той же ячейке памяти из нескольких потоков, выполняемых на нескольких ядрах ЦП, приводит к большому количеству событий аннулирования кеша. Хуже того, vars.i и vars.temp, скорее всего, окажутся в одной и той же строке кэша, и хотя vars.i считывается только с vars.temp, записывается только с полным недопустимым кэшем кэша на каждой итерации внутреннего цикла.

Обычно доступ к общим переменным защищен явными конструкциями синхронизации, такими как атомарные утверждения и критические разделы, и в этом случае ожидается высокая деградация производительности.

Answer 2

Think накладных расходов:

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

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

У вас есть стоимость создания потоков здесь и выделение частных переменных.

Если работа внутри внутреннего контура мала, преимущества параллелизации этого цикла могут не превышать затраты на накладные расходы на параллелизацию выше, следовательно, вы оказываетесь в замедлении.