Распараллеливание во вложенных циклах с помощью OPENMP
Я пытаюсь распараллелить эту функцию в C, используя openmp, но, похоже, ничего не получается, я знаю, что есть зависимости в итерациях и в двух строках, но я застрял, может кто-нибудь помочь мне, если это возможно.
void loop_reference(double C[N][N], double A[N][N], double B[N][N]) {
size_t i, j;
for (i = 1; i < N; i++) {
for (j = 1; j < N; j++) {
B[i][j] = B[i-1][j] + A[i][j-1];
A[i][j] = A[i-1][j] + C[i][j];
}
}
}
Я попытался разделить две строки и распараллелить каждый цикл, но это не сработало.
void loop_parallel(double C[N][N], double A[N][N], double B[N][N]) {
size_t i, j;
#pragma omp parallel for private(i, j) shared(A, B, C)
for (i = 1; i < N; i++) {
for (j = 1; j < N; j++) {
A[i][j] = A[i-1][j] + C[i][j];
}
}
#pragma omp parallel for private(i, j) shared(A, B, C)
for (i = 1; i < N; i++) {
for (j = 1; j < N; j++) {
A[i][j] = A[i-1][j] + C[i][j];
}
}
}
Я попробовал ваше предложение, но, к сожалению, оно все еще дает мне плохие результаты.
Возможно, вы сможете распараллелить это, используя параллелизм волнового фронта и перекос петли.
«Я застрял» или «это не работает» совершенно неинформативно. Уточните пожалуйста, в чем проблема ваших попыток: ошибка компиляции? Неправильные результаты? Не ожидаемое ускорение? Другой?
Прошу прощения за отсутствие информации, именно я получаю неправильные результаты, хотя ускорение все еще выше, чем 2.
Ответы 1
Ваша проблема в том, что ваш алгоритм нельзя распараллелить напрямую. Составьте картину потока данных. Ваш a[0,0] используется a[0,1] и a[1,0], поэтому ни внешний, ни внутренний цикл не имеют независимых итераций.
Вам нужно полностью переписать это, перебирая «диагонали» в пространстве i,j. Сначала вычислите a[0,0], затем a[1,0], a[0,1], затем a[2,0], a[1,1], a[0,2]. Другими словами:
for (int d=0... 2N)
for ( i,j such that i+j=s )
compute a[i,j]
Это дает вам последовательный внешний и параллельный внутренний цикл. Полный параллелизм невозможен.
Конечно, если это шаг сглаживания в каком-то итеративном процессе, вас на самом деле не интересует полная воспроизводимость последовательного результата. В этом случае беспечное объявление всего гнезда цикла параллельным будет соответствовать «хаотической итерации», и внешний процесс все еще может сходиться. Чуть менее радикально, если это действительно более гладко, замените лексикографический порядок красно-черным, и вы получите намного больше параллелизма. Опять же, без точного воспроизведения результата одного последовательного шага сглаживания в исходном коде.
Стоит отметить, что здесь можно распараллелить только внутренний цикл.
Начните с объявления переменных цикла в заголовке цикла. Это, вероятно, решит вашу проблему. Вы также можете объявить
jзакрытым, но использование локальных переменных, вероятно, будет более простой идеей.