openmp - 如何使用 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

这是一个带有 loop-carried dependencies 的循环示例，因此不能像编写的那样轻松并行化，因为任务(循环的每次迭代)不是独立的。打破依赖关系可以是微不足道的修改，也可以是完全不可能的修改(例如，迭代循环)。

这里的情况介于两者之间。并行执行此操作的问题是，您需要在邻居更改值之前找出最右边的值是什么。 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;
}