Как распараллелить сдвиг массива с OpenMP?

Question

Как я могу распараллелить сдвиг массива с OpenMP?

Я попробовал несколько вещей, но не получил точных результатов для следующего примера (который вращает элементы массива объектов Carteira для алгоритма перестановки):

void rotaciona(int i)
{
    Carteira aux = this->carteira[i];
    for(int c = i; c < this->size - 1; c++)
    {
        this->carteira[c] = this->carteira[c+1];
    }
    this->carteira[this->size-1] = aux;
}

Большое спасибо!

Answer 1

Это пример цикла с зависимостями, переносимыми циклом, и поэтому его нельзя легко распараллелить, как написано, потому что задачи (каждая итерация цикла) не являются независимыми. Нарушение зависимости может варьироваться от тривиальной модификации до абсолютно невозможной (например, итерационный цикл).

Здесь случай несколько промежуточный. Проблема с выполнением этого параллельно заключается в том, что вам нужно выяснить, какое будет ваше самое правое значение, прежде чем ваш сосед изменит значение. OMP для конструкции не раскрывает, какие значения итераций цикла будут "вашими", поэтому я не думаю, что вы можете использовать OpenMP для конструкции разделения, чтобы разорвать цикл. Тем не менее, вы можете сделать это самостоятельно; но это требует намного больше кода, и это не будет приятно сводиться к последовательному случаю больше.

Но все же пример того, как это сделать, показан ниже. Вы должны сами разорвать петлю, а затем получить самое правильное значение. Барьер OpenMP гарантирует, что никто не начнет изменять значения, пока все потоки не кешируют свое новое самое правое значение.

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

int main(int argc, char **argv) {
    int i;
    char *array;
    const int n=27;

    array = malloc(n * sizeof(char) );
    for (i=0; i<n-1; i++)
        array[i] = 'A'+i;

    array[n-1] = '\0';

    printf("Array pre-shift  = <%s>\n",array);

    #pragma omp parallel default(none) shared(array) private(i)
    {
        int nthreads = omp_get_num_threads();
        int tid = omp_get_thread_num();

        int blocksize = (n-2)/nthreads;
        int start = tid*blocksize;
        int end = start + blocksize - 1;
        if (tid == nthreads-1) end = n-2;

        /* we are responsible for values start...end */

        char rightval = array[end+1];
        #pragma omp barrier 

        for (i=start; i<end; i++)
            array[i] = array[i+1];

        array[end] = rightval;
    }
    printf("Array post-shift = <%s>\n",array);

    return 0;
}

Answer 2

Хотя в вашем примере нет явных прагм openmp, я не думаю, что он может сработать легко:

Вы делаете операцию на месте с перекрывающимися регионами. Если вы разделите цикл на порции, вы получите условия гонки на границах (потому что el[n] копируется из el[n+1], который, возможно, уже был обновлен в другом потоке).

Я предлагаю вам выполнить ручное разбиение на блоки (что может быть сделано), но я подозреваю, что openmp параллельный для недостаточно гибок (не пробовал), так что вы можете просто иметь параллельный регион, который выполняет работу кусками, и исправить граничные элементы после резьбового барьера / конца параллельного блока

---

Другие мысли:

1. если ваши значения POD, вы можете использовать memmove вместо
2. если можешь, просто переключись на список

,

std::list<Carteira> items(3000);

// rotation is now simply:
items.push_back(items.front());
items.erase(items.begin());