Как распараллелить сдвиг массива с OpenMP? - PullRequest
Новая
       1

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

3 голосов
/ 17 мая 2011

Как я могу распараллелить сдвиг массива с 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;
}

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

Ответы [ 2 ]

4 голосов
/ 18 мая 2011

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

Здесь случай немного посередине. Проблема с выполнением этого параллельно заключается в том, что вам нужно выяснить, какое будет ваше самое правое значение, прежде чем ваш сосед изменит значение. 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;
}
4 голосов
/ 17 мая 2011

Хотя в вашем примере нет явных прагм 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());
...