如何使用OpenMP并行处理数组移位? [英] How to parallelize an array shift with OpenMP?

问题描述

如何使用OpenMP并行处理数组移位?

How can I parallelize an array shift with OpenMP?

在以下示例中，我尝试了一些尝试，但未获得任何准确的结果(该示例旋转了Carteira对象数组的元素，用于置换算法):

I've tryed a few things but didn't get any accurate results for the following example (which rotates the elements of an array of Carteira objects, for a permutation algorithm):

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;
}

非常感谢！

推荐答案

这是带有循环承载的依赖项，因此由于编写任务(循环的每个迭代)不是独立的，因此很难像编写的那样并行化.打破依赖关系可以从微不足道的修改到完全不可能的修改 (例如，迭代循环).

This is an example of a loop with loop-carried dependencies, and so can't be easily parallelized as written because the tasks (each iteration of the loop) aren't independent. Breaking the dependency can vary from a trivial modification to the completely impossible (eg, an iteration loop).

这里，情况介于两者之间.并行执行此操作的问题是，您需要在邻居更改值之前先找出最右边的值.用于构造的OMP不会向您展示哪个循环迭代值将是您的"，因此我认为您不能使用OpenMP进行工作共享构造来破坏循环.但是，您可以自己做；但是它需要更多代码，并且再也无法简化为串行格式了.

Here, the case is somewhat in between. The issue with doing this in parallel is that you need to find out what your rightmost value is going to be before your neighbour changes the value. The OMP for construct doesn't expose to you which loop iterations values will be "yours", so I don't think you can use the OpenMP for worksharing construct to break up the loop. However, you can do it yourself; but it requires a lot more code, and it won't nicely reduce to the serial case any more.

但是，下面显示了如何执行此操作的示例.您必须自己打破循环，然后获得最正确的价值. OpenMP屏障可确保在所有线程都已缓存其新的最右边的值之前，没有人可以开始修改值.

But still, an example of how to do this is shown below. You have to break the loop up yourself, and then get your rightmost value. An OpenMP barrier ensures that no one starts modifying values until all the threads have cached their new rightmost value.

#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;
}

这篇关于如何使用OpenMP并行处理数组移位?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！