arrays - 如何使用openmp并行化数组元素的移动

Question

如果 pArray 非常大，下面的代码片段是我程序中最耗时的。 last是这个数组结束位置的变量，idx是数组特定位置的变量，所以我想要的是将部分数组元素从Idx向后移动1。

for(long i = last; i >= Idx; i--)
{
    pArray[i] = pArray[i-1];
}

我只是尝试使用 parallel for 来并行化它，但它肯定行不通。谁能告诉我这段代码是否可以与 openmp 并行化？如果是，如何编码？谢谢。

#pragma omp parallel for
for(long i = last; i >= Idx; i--)
{
    pArray[i] = pArray[i-1];
}

Answer 1

您遇到的主要问题是您的代码具有循环携带的依赖性，即迭代之间存在依赖性。

所以你的代码是:

for(long i = last; i >= Idx; i--)
{
  pArray[i] = pArray[i-1];
}

现在，假设 last = 4 和 Idx=1。你会有这样的东西:

  iteration 0: pArray[4] = pArray[3];
  iteration 1: pArray[3] = pArray[2];
  iteration 2: pArray[2] = pArray[1];
  iteration 3: pArray[1] = pArray[0];

如果您将其与四个线程并行化(假设是静态的)并且线程 0 被指定为迭代 0，线程 1 被指定为迭代 1，依此类推，您将得到不正确的结果，具体取决于哪个线程先执行。如果线程 0 在线程 1 之前执行，线程 0 将使用 pArray[3] 的旧值，而如果线程 0 在线程 1 之后执行，线程 0 将使用由线程 1 计算的 pArray[3] 的新值。

由于您的迭代不是独立的，因此无法直接并行化循环。

因为显然你想要的只是将数组的值向前移动一个位置，我认为更好的方法是使用指针算法或重新组织你的循环和你的代码的其他部分来尝试消除依赖或完全循环。