Распаралелить цикл

330

26 октября 2017, 09:45

Здравствуйте! Необходимо распараллелить цикл

For(i=2;i<N;i++)
    For(j=2;i<N;j++)
        A[i,j] =A[i-2,j] +A[i,j-2];

По теории массив необходимо обрабатывать либо блоками 2*2, либо по диагонали. Ниже обработка блоками. Но распараллеливание реализовано неверно, выдает неправильные результаты.

Кто-нибудь сможет подсказать, как верно решается эта задача?

    #include <iostream>
    #include <omp.h>
    #include <iomanip>
    using namespace std;
    const int N=10;
    int A[N][N];
    int main()
    {
        int i, j, n;
        srand (time(NULL));
        // Заполнение первых двух строк и столбцов массива случайными числами от 0 до 10
        for (i = 0; i < 2; i++) {
            for (j = 0; j < N; j++) {
                A[i][j] = (rand() % 10 + 1);
                A[j][i] = (rand() % 10 + 1);
                    //cout << setw(4) << A[i][j];
            }
            //cout << endl;
        }
        //Вывод массива
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                cout << setw(4) << A[i][j];
            }
            cout << endl;
        }

        double time=omp_get_wtime();
        #pragma omp parallel num_threads(3)
        {
            //#pragma omp for
            for (i = 2; i < N+N; i++) {
                j=2;
                int k=i;
    //#pragma omp parallel private(j,k)
                while(j<=i)
                {
                    if(k<N && j<N)
                    {
                        A[k][j] = A[k-2][j] + A[k][j-2];
                        cout << omp_get_thread_num();
                    }
                    --k;
                    ++j;
                }
            }
        }
        cout << "Paraller area. End" << endl;
        cout<<"time: "<<omp_get_wtime()-time<<endl;
        cout << endl;
        cout << "New array" << endl;
        cout << endl;
        // Вывод на экран
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                cout << setw(4) << A[i][j];
            }
            cout << endl;
        }

        system ("pause");
        return 0;
    }

Answer 1

Изучил OpenMP для решения задачи :) (поверхностно, конечно). Вот моё решение на C++, можно запустить онлайн:

#include <iostream>
#include <vector>
#include <cstdint>
#include <memory>
#include <cstring>
#include <algorithm>
using namespace std;
typedef uint32_t u32;
typedef int32_t s32;
#define MEMZERO(obj) memset(&obj, 0, sizeof(obj))
#define MEMCOPY(dst, src) memcpy(&dst, &src, min(sizeof(dst), sizeof(src)))
enum {
    c_block_size = 2,
    N = 97,
};
int main() {
    u32 a[N][N]; MEMZERO(a);
    // Initial start values.
    for (u32 i = 0; i < N; ++i) {
        for (u32 j = 0; j < c_block_size; ++j) {
            a[i][j] = a[j][i] = i * c_block_size + j;
        }
    }
    u32 b[N][N]; MEMCOPY(b, a);
    // Parallel version.        
    #pragma omp parallel for num_threads(c_block_size * c_block_size)
    for (s32 tid = 0; tid < c_block_size * c_block_size; ++tid) {
        u32 i_shift = tid / c_block_size;
        u32 j_shift = tid % c_block_size;
        for (u32 i = c_block_size + i_shift; i < N; i += c_block_size) {
            for (u32 j = c_block_size + j_shift; j < N; j += c_block_size) {
                a[i][j] = a[i][j - c_block_size] + a[i - c_block_size][j];
            }
        }
    }
    // Non-parallel version.
    for (u32 i = c_block_size; i < N; ++i) {
        for (u32 j = c_block_size; j < N; ++j) {
            b[i][j] = b[i - c_block_size][j] + b[i][j - c_block_size];
        }
    }
    // Output and check correctness.
    {
        bool is_correct = true;
        u32 shift = (N / c_block_size - 1) * c_block_size;
        for (u32 i = 0; i < c_block_size; ++i) {
            for (u32 j = 0; j < c_block_size; ++j) {
                cout << a[shift + i][shift + j] << " ";
                if (a[shift + i][shift + j] != b[shift + i][shift + j]) is_correct = false;
            }
            cout << endl;
        }
        cout << (is_correct ? "CORRECT" : "INCORRECT") << endl;
    }
    return 0;
}

Замечания: я сделал обобщённую версию для любого N и для любого размера стороны квадрата c_block_size, у автора задача была для c_block_size = 2. Размер N я сделал так что можно задать не кратный c_block_size. Также я сделал проверку корректности на не-параллельной версии. Распараллеливание идёт по номеру потока, т.к. я не нашёл как в OMP задать для каждого потока точные индексы for которые только этому потоку принадлежат, т.к. для решения задачи понадобилось бы потоку давать 0й 2й 4й 6й и т.д. индексы, а OMP только похоже разбивает индексы for на интервалы. В конце я вывожу значения только последнего квадрата, т.к. он самый показательный. При вычислении массива индексы по потокам распределялись как на такой картинке (звёздочки это начальные значения, цифры это номера потоков). Цикл по tid параллелится максимальным числом потоков, но вполне можно любое число потоков задать, хоть 1.

Замерил время при N = 8192, c_block_size = 16, num_threads = 8. Получилось что параллельная версия исполняется 500мс, без распараллеливания (т.е. 1 поток) та же версия 800мс, т.е. не значительное ускорение наблюдается, наверняка тормозит уже чисто изза доступа к памяти, т.к. алгоритм не трудный по вычислениям а скорее упирается в скорость работы памяти.

Если кому нужен C++ класс который я написал для точного вычисления времени, то его я выложил тут.