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

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

0 голосов
/ 11 марта 2019

Я хочу сделать следующий цикл, который заполняет матрицу A параллельно. Для каждого вычисляемого элемента A [i] [j] я хочу, чтобы цена в A [i-1] [j], A [i-1] [j -1] и A [i0] [j-1] равнялась были рассчитаны в первую очередь. Так что мой поток должен дождаться, пока потоки в этих позициях вычислили свои результаты. Я пытался добиться этого так: 

 #pragma omp parallel for num_threads(threadcnt) \
            default(none) shared(A, lenx, leny) private(j)
            for (i=1; i<lenx; i++)
            {   
                for (j=1; j<leny; j++)
                {
                    do
                    {

                    } while (A[i-1][j-1] == -1 || A[i-1][j] == -1 || A[i][j-1] == -1);

                    A[i][j] = max(A[i-1][j-1]+1,A[i-1][j]-1, A[i][j-1] -1);

                }
            }

Моя матрица A инициализируется в -1, поэтому, если A [] [] равно -1, операция в этой ячейке не завершается. Хотя это занимает больше времени, чем последовательная программа. Любая идея, чтобы избежать цикла while?

Ответы [ 2 ]

1 голос
/ 11 марта 2019

Ваше решение не может работать. Поскольку 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]);
    }
  }
1 голос
/ 11 марта 2019

Цикл ожидания кажется неоптимальным.Помимо горящих ядер, ожидающих вращения, вам также понадобится множество хорошо расположенных директив 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: приведенный выше код не проверен, но он должен дать приблизительное представление.

...