如何使用 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 for 构造不会向您公开哪些循环迭代值将是“您的”，因此我认为您不能使用 OpenMP for worksharing 构造来分解循环。但是，您可以自己做；但它需要更多的代码，并且不会再很好地减少到串行情况。

但是，下面显示了如何执行此操作的示例。你必须自己打破循环，然后得到你最正确的价值。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;
}