Сокращение OpenMP, переменная не частная?

У меня есть такой массив (0,0 внизу слева):

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 1 0 1 0 1 0 0
0 0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1

Моя цель - получить индекс более высокой строки, которая не полностью установлена ​​​​на 0. Для этого я сделал код ниже (который отлично работает):

max=0;
for (i=0 ; i<width ; ++i) {
  for (j=max ; j<height ; ++j) {
    if (array[i*height+j]!=0) {
      max=j;
    }
  }
}

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

Я попытался распараллелить это с OpenMp. Мой код сейчас:

max=0;
#pragma omp parallel for  default(none)                 \
                          shared(spec, width, height)   \
                          collapse(2)                   \
                          reduction(max:max)
for (i=0 ; i<width ; ++i) {
  for (j=max ; j<height ; ++j) {
    if (array[i*height+j]!=0) {
      max=j;
    }
  }
}

Что приводит к ошибке сегментации. Чтобы заставить его работать, я изменил j=max на j=0. Таким образом, проблема, похоже, связана с переменной max.

Я не понимаю, почему, потому что при сокращении эта переменная должна быть приватной (или lastprivate) между каждым потоком. Так почему это приводит к сбою? И как я могу использовать свою «оптимизацию» с OpenMP?


c openmp parallel-processing max reduction
person Phantom    schedule 18.06.2018    source источник
comment
Я думаю, что когда вы сворачиваете эти циклы, вы нарушаете одно из правил, которые OpenMP налагает на циклы, в частности, то, которое запрещает изменять количество поездок после запуска цикла. Обновляя max внутри цикла, ваш код пытается сделать именно это. OpenMP требует, чтобы количество циклов вычислялось один раз в начале, чтобы можно было распределять итерации по потокам и не изменять их позже, иначе это нарушит планирование.   -  person High Performance Mark    schedule 18.06.2018
comment
@HighPerformanceMark, я тестировал с collapse(1), и он тоже не работает, cppstudy объяснил, почему в этом ответе. Но вы породили важную вещь, которая может привести к другим проблемам, так что +1 вам;)   -  person Phantom    schedule 18.06.2018

Ответы (1)


arrow_upward
2
arrow_downward

Во-первых, пользователь High Performance Mark прав в своем комментарии. Вы не должны использовать коллапс, если ваши значения индекса цикла зависят от значения вычисления. В вашем примере «j» зависит от «max», что приведет к неправильному результату. Однако это не является причиной вашей ошибки сегментации.

Я бы посоветовал вам отладить ваш пример, чтобы вы могли найти источник сбоя; «max» по умолчанию инициализируется отрицательным числом, что приводит к тому, что «j» также имеет указанное значение. Таким образом, при попытке доступа к массиву [i*height+(-2147483648)] вы получаете ошибку сегментации.

Это происходит потому, что OpenMP указывает начальное значение для каждого оператора редукции. В случае с оператором max вы можете найти следующее описание в спецификация OpenMP 3.1:

max Наименьшее представляемое значение в типе элемента списка сокращения

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

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

#pragma omp parallel default(none) private(j) shared(array, width, height) reduction(max:max)
{
        // Explicit initialization
        max = 0;

        #pragma omp for 
        for (i=0 ; i<width ; ++i) {
          for (j=max ; j<height ; ++j) {
            if (array[i*height+j]!=0) {
                max=j;
            }
          }
        }
}

В качестве дополнительного замечания: вам не нужно каждый раз использовать max=j. Вы можете попробовать проверить, когда найден первый 0, и использовать предыдущую позицию.

Надеюсь, поможет

person cppstudy    schedule 18.06.2018