Распараллелить цикл со сложной индексацией используя OpenMP

@BlackUser · Регистрация: 20.01.2014

Author24 — интернет-сервис помощи студентам

Пусть есть такой цикл, преобразующий массив:

C++

#define N 6
#define RADIUS 1
 
int arr[N][N];
 
int flag;
int x,y;
do {
    flag = 0;
    for(int i=RADIUS; i<(N-RADIUS); i++) {
        for(int j=RADIUS; j<(N-RADIUS); j++) {
            x = arr[i-RADIUS][j]+arr[i+RADIUS][j];
            y = arr[i][j-RADIUS]+arr[i][j+RADIUS];
            arr[i][j] = x+y;
            if(arr[i][j]<20000)
                flag = 1;
        }
    }
} while(flag);

Нужно распараллелить при помощи OpenMP. Очевидно, если распараллелить следующим образом, то получаются неверные результаты:

C++

do {
    flag = 0;
    #pragma omp parallel for
    for(int i=RADIUS; i<(N-RADIUS); i++) {
        for(int j=RADIUS; j<(N-RADIUS); j++) {
            x = arr[i-RADIUS][j]+arr[i+RADIUS][j];
            y = arr[i][j-RADIUS]+arr[i][j+RADIUS];
            arr[i][j] = x+y;
            if(arr[i][j]<20000)
                flag = 1;
        }
    }
} while(flag);

Код всей программы:

Кликните здесь для просмотра всего текста

C++

#include <stdio.h>
#include <omp.h>
 
#define N 8
#define RADIUS 1
 
void print(int arr[][N]) {
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++)
            printf(" %4d", arr[i][j]);
        printf("\n");
    }
    printf("\n");
}
 
int main()
{
    int arr[N][N];
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            arr[i][j]=1;
    
    print(arr);
    
    int x,y;
    #pragma omp parallel for
    for(int i=RADIUS; i<(N-RADIUS); i++) {
        for(int j=RADIUS; j<(N-RADIUS); j++) {
            x = arr[i-RADIUS][j]+arr[i+RADIUS][j];
            y = arr[i][j-RADIUS]+arr[i][j+RADIUS];
            arr[i][j] = x+y;
        }
    }
    
    print(arr);
    
    return 0;
}

У меня есть следующие идеи. У нас есть внешний do-while цикл, который выполняется определенное число раз до достижения условия. То есть некоторое подобие волн. Одна волна преобразований, затем следующая, если первая завершилась неуспешно. Когда первый внутренний for пройдет несколько итераций, для радиуса 1 это 3 итерации, то можно заного его запускать в других потоках, до того как он завершится. При радиусе 1 у нас охватывается 3 элемента и когда пройдет 3 итерации первого for, его можно будет запустить еще раз в другом потоке не дожидаясь завершения. Но как это реализовать непонятно.

Спецификации по OpenMP на openmp.org:
http://www.openmp.org/mp-documents/OpenMP3.1.pdf

@mat_for_c · 31.05.2015, 01:19

если не ошибаюсь, у тебя результат i-й итерации зависит от результата (i-1)-й итерации, а такие вещи не параллелятся...

@nonedark2008 · 31.05.2015, 02:27

BlackUser, что хоть твоя штука должна делать? Может есть метод эффекивнее.
Какого порядка у тебя могут быть значения N и RADIUS? Может параллелить и нет смысла вовсе.

@BlackUser · 31.05.2015, 14:38 **[ТС]**

Сообщение от mat_for_c

i-й итерации зависит от результата (i-1)-й итерации, а такие вещи не параллелятся

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

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

Сообщение от nonedark2008

N и RADIUS

Радиус не более 5, N может быть достаточно большим, либо массив может быть многомерным.

@nonedark2008 · 31.05.2015, 14:51

Сообщение от BlackUser

N может быть достаточно большим, либо массив может быть многомерным.

Вы уж определитесь. Или хотите получить универсальное решение на все случаи жизни?

Сообщение от nonedark2008

что хоть твоя штука должна делать?

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

@mat_for_c · 31.05.2015, 15:16

Смотри: при радиусе в 1 у тебя 2 строка заполняется в зависимости от значений 1 и 3 строки. В них стоят 1, ничего плохого пока нет. После того, как заполнили 2 строку, начинаем заполнять 3-ю. Данные уже берутся из 2-й строки и 4-й, в которой по прежнему 1. Тем самым у тебя i-я строка зависит от i-1 -й строки. Аналогично для столбцов. Поэтому никак не распараллелишь...

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	31.05.2015, 01:19	2
	если не ошибаюсь, у тебя результат i-й итерации зависит от результата (i-1)-й итерации, а такие вещи не параллелятся... 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	31.05.2015, 02:27	3
	BlackUser, что хоть твоя штука должна делать? Может есть метод эффекивнее. Какого порядка у тебя могут быть значения N и RADIUS? Может параллелить и нет смысла вовсе. 0

@BlackUser 3 / 3 / 0 Регистрация: 20.01.2014 Сообщений: 69
	31.05.2015, 14:38 [ТС]	4
	Сообщение от mat_for_c i-й итерации зависит от результата (i-1)-й итерации, а такие вещи не параллелятся В рамках одноразовой обработки может и нет, но там цикл do-while. В нем вся суть, он может выполняться огромное число раз. Я задачу намеренно упростил, что бы было понятнее, в дальнейшем структура циклов еще может усложниться на многомерный случай(сейчас там двумерный). В случае многих выполнений do-while можно обработать первые несколько элементов и не дожидаясь завершения первого, начать обработку начала массива в другом потоке. Естественно второй поток недолжен опережать индексацию первого потока. Сообщение от nonedark2008 N и RADIUS Радиус не более 5, N может быть достаточно большим, либо массив может быть многомерным. 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	31.05.2015, 14:51	5
	Сообщение от BlackUser N может быть достаточно большим, либо массив может быть многомерным. Вы уж определитесь. Или хотите получить универсальное решение на все случаи жизни? Сообщение от nonedark2008 что хоть твоя штука должна делать? И да "код всей программы" отличается от кусков выше, что вызывает еще большую неразбериху. 0

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	31.05.2015, 15:16	6
	Смотри: при радиусе в 1 у тебя 2 строка заполняется в зависимости от значений 1 и 3 строки. В них стоят 1, ничего плохого пока нет. После того, как заполнили 2 строку, начинаем заполнять 3-ю. Данные уже берутся из 2-й строки и 4-й, в которой по прежнему 1. Тем самым у тебя i-я строка зависит от i-1 -й строки. Аналогично для столбцов. Поэтому никак не распараллелишь... 0