OpenMP вложенный для, неравное число.итераций

Question

Я использую OpenMP для распараллеливания циклов.В обычном случае можно использовать:

#pragma omp for schedule(static, N_CHUNK)
for(int i = 0; i < N; i++) {
    // ...
}

Для вложенных циклов я могу поставить pragma на внутренний или внешний цикл

#pragma omp for schedule(static, N_CHUNK) // can be here...
for(int i = 0; i < N; i++) {
#pragma omp for schedule(static, N_CHUNK) // or here...
    for(int k = 0; k < N; k++) {
    // both loops have consant number of iterations
    // ...
    }
}

Но!У меня есть два цикла, где количество итераций во 2-м цикле зависит от 1-го цикла:

for(int i = 0; i < N; i++) {
    for(int k = i; k < N; k++) {
    // k starts from i, not from 0...
    }
}

Каков наилучший способ сбалансировать использование ЦП для этого вида цикла?

Answer 1

Как всегда:

• зависит от профиля
• .
• В этом случае: см. Также Переменная среды OMP_NESTED

Вещи, которые могут изменить ситуацию, здесь не показаны:

• (не) линейная адресация памяти (также следите за порядком циклов
• использование общих переменных;

Что касается вашего последнего сценария:

for(int i = 0; i < N; i++) {
    for(int k = i; k < N; k++) {
    // k starts from i, not from 0...
    }
}

Я предлагаю распараллеливание внешнего цикла по следующим причинам:

• при прочих равных условиях грубое распараллеливание обычно приводит к повышению производительности из-за

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

• внутренний цикл может стать настолько коротким, что его неэффективно распараллеливать (IOW: диапазон внешнего цикла предсказуем, внутреннийпетля меньше или нетТакже можно использовать статическое планирование)

• вложенный параллелизм редко хорошо масштабируется

Answer 2

баллы sehe - особенно «это зависит» и «профиль» - чрезвычайно важны.

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

Обычный способ решения этой проблемы - динамическое планирование внешнего цикла, чтобы тот факт, что каждая итерация цикла имеет различную длину типа, не вызывает проблем с балансировкой нагрузки (поскольку итерация i==N-1 завершается практически сразу в то время как итерация i==0 занимает вечность)

#pragma omp parallel for default(none) shared(N) schedule(dynamic)
for(int i = 0; i < N; i++) {
    for(int k = i; k < N; k++) {
    // k starts from i, not from 0...
    }
}

Прагма свертывания очень полезна для существенного избавления от вложенности и особенно полезна, если внешний цикл мал (например, N < num_threads):

#pragma omp parallel for default(none) shared(N) collapse(2)
for(int i = 0; i < N; i++) {
    for(int k = 0 ; k < N; k++) {

    }
}

Таким образом, две петли складываются в одну, и уменьшается количество порций, что означает меньшие накладные расходы. Но это не сработает в этом случае, потому что диапазоны цикла не фиксированы; Вы не можете collapse цикл, границы цикла которого изменяются (например, с i).