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

Answer 2

尽管您的示例没有显示任何显式的 openmp pragma，但我认为它并不容易工作：

您正在对重叠区域进行就地操作。
如果将循环分成块，则会在边界处出现竞争条件（因为 el[n] 是从 el[n+1] 复制的，而 el[n+1] 可能已在另一个线程中更新）。

我建议你进行手动分块（这是可以完成的），但我怀疑 openmp parallel for 不够灵活（还没有尝试过），所以你可以有一个并行区域来分块工作，并修复线程屏障/并行块结束后的边界元素

---

其他想法：

1. 如果您的值是 POD，则可以使用 memmove 代替（
2. 如果可以的话），只需切换到 list

。

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

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