Понимание предложения collapse в openmp

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

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

Я думал, что понял, что это значит, поэтому я попробовал следующую простую программу:

int i, j;
#pragma omp parallel for num_threads(2) private(j)
for (i = 0; i < 4; i++)
    for (j = 0; j <= i; j++)
        printf("%d %d %d\n", i, j, omp_get_thread_num());

Что вызвало

Затем я добавил предложение collapse(2). Я ожидал, что будет иметь тот же результат в первых двух столбцах, но теперь будет иметь равное количество 0 и 1 в последнем столбце. Но я получил

Итак, мои вопросы:

Что происходит в моем коде?
При каких обстоятельствах следует использовать collapse?
Можете ли вы привести пример, показывающий разницу между использованием collapse и не использованием его?

Ответ 1

Проблема с вашим кодом заключается в том, что итерации внутреннего цикла зависят от внешнего цикла. Согласно спецификации OpenMP в описании раздела о привязке и в предложении collapse:

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

Вы можете использовать сбой, если это не так, например, с квадратным циклом

#pragma omp parallel for private(j) collapse(2)
for (i = 0; i < 4; i++)
    for (j = 0; j < 100; j++)

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

Вы можете спланировать цикл вручную для кода выше, как этот

#pragma omp parallel for
for(int n=0; n<4*100; n++) {
    int i = n/100; int j=n%100;

Здесь - пример, показывающий, как вручную включить плавный контур с плавким предохранителем.

Наконец, здесь - пример, показывающий, как сплавить треугольный цикл, для которого collapse не определен.

Вот решение, которое отображает прямоугольную петлю в треугольную петлю в вопросе OP. Это можно использовать для слияния треугольной петли OPs.

//int n = 4;
for(int k=0; k<n*(n+1)/2; k++) {
    int i = k/(n+1), j = k%(n+1);
    if(j>i) i = n - i -1, j = n - j;
    printf("(%d,%d)\n", i,j);
}

Это работает для любого значения n.

Карта для вопроса OPs идет от

(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),
(3,0), (3,1), (3,2), (3,3),

к

(0,0), (3,3), (3,2), (3,1), (3,0),
(1,0), (1,1), (2,2), (2,1), (2,0),

Для нечетных значений n отображение не является точно прямоугольником, но формула все еще работает.

Например, n = 3 отображается из

(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),

to

(0,0), (2,2), (2,1), (2,0),
(1,0), (1,1),

Вот код для проверки этого

#include <stdio.h>
int main(void) {
    int n = 4;
    for(int i=0; i<n; i++) {
        for(int j=0; j<=i; j++) {
            printf("(%d,%d)\n", i,j);
        }
    }
    puts("");
    for(int k=0; k<n*(n+1)/2; k++) {
        int i = k/(n+1), j = k%(n+1);
        if(j>i) i = n - i - 1, j = n - j;
        printf("(%d,%d)\n", i,j);
    }
}

Ответ 2

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

#pragma omp for
for (int iy0=0; iy0<n; ++iy0){
  int iy = iy0;
  if (iy0 >= n/2) iy = n-1 -iy0 +n/2;
  for (int ix=iy+1; ix<n; ++ix){
    work(ix, iy);
  }
}