Как заставить поток ждать другого, чтобы закончить использовать потоки OpenMP?

Цикл ожидания кажется неоптимальным. Помимо горящих ядер, которые ожидают вращения, вам также понадобится множество хорошо расположенных директив flush, чтобы этот код работал.

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

#pragma omp parallel
#pragma omp single
for (i=1; i<lenx; i++) {
    for (j=1; j<leny; j++) {
#pragma omp task depend(in:A[i-1][j-1],A[i-1][j],A[i][j-1]) depend(out:A[i][j])
        A[i][j] = max(A[i-1][j-1]+1,A[i-1][j]-1, A[i][j-1] -1);
    }
}

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

Еще одна полезная функция OpenMP могла бы быть конструкцией ordered, и она способна придерживаться именно такой зависимости данных:

#pragma omp parallel for
for (int i=1; i<lenx; i++) {
    for (int j=1; j<leny; j++) {
#pragma omp ordered depend(source)
#pragma omp ordered depend(sink:i-1,j-1)        
        A[i][j] = max(A[i-1][j-1]+1,A[i-1][j]-1, A[i][j-1] -1);
    }
}

PS: приведенный выше код не проверен, но он должен получить грубую идея поперек.

Ваше решение не может работать. Поскольку A инициализируется в -1, а A[0][j] никогда не изменяется, если i==1, он будет проверять A[1-1][j] и всегда будет терпеть неудачу. Кстати, если A инициализируется в -1, как у вас не может быть ничего кроме -1 с максимумом?

Когда у вас есть проблема зависимостей, есть два решения.

Первый - это упорядочить ваш код. Openmp имеет директиву ordered для этого, но недостатком является то, что вы теряете параллелизм (при этом все равно оплачивая стоимость создания потока). В Openmp 4.5 есть способ описания зависимостей с помощью операторов зависимостей и приемника / источника, но я не знаю, насколько эффективным может быть компилятор, чтобы справиться с этим. А мои компиляторы (gcc 7.3 или clang 6.0) не поддерживают эту функцию.

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

// compute b[i][j]=max_k<j(a[i][k]
#pragma omp parallel for
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      // max per row
      if((j!=0)) b[i][j]=max(a[i][j],b[i][j-1]);
      else b[i][j]=a[i][j]; //  left column initialised to value of a
    }
  }

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

// compute c[i][j]=max_i<k(b[k,j])
  for(int i=0;i<n;i++){
#pragma omp parallel for
    for(int j=0;j<n;j++){
      // max per column
      if((i!=0)) c[i][j]=max(b[i][j],c[i-1][j]);
      else c[i][j]=b[i][j]; //  upper row initialised to value of b
    }
  }

Теперь вам просто нужно объединить эти вычисления, чтобы получить ожидаемый результат. Вот окончательный код (с использованием уникального массива и некоторой очистки в коде).

#pragma omp parallel for
  for(int i=0;i<n;i++){
    for(int j=1;j<n;j++){
      // max per row
      a[i][j]=max(a[i][j],a[i][j-1]);
    }
  }
  for(int i=1;i<n;i++){
#pragma omp parallel for
    for(int j=0;j<n;j++){
      // max per column
      a[i][j]=max(a[i][j],a[i-1][j]);
    }
  }