1

有谁熟悉openmp，我没有得到排序列表。我究竟做错了什么。我在最后使用了critical，因此在排序后只有一个线程可以访问该部分。我想我的私人价值观不正确。他们是否应该在那里，或者我最好只使用#pragma omp for。

void shellsort(int a[])
{
    int i, j, k, m, temp;

    omp_set_num_threads(10);
    for(m = 2; m > 0; m = m/2)
    {
            #pragma omp parallel for private (j, m)
            for(j = m; j < 100; j++)
            {
                    #pragma omp critical
                    for(i = j-m; i >= 0; i = i-m)
                    {
                            if(a[i+m] >= a[i])
                                break;
                            else
                            {
                                temp = a[i];
                                a[i] = a[i+m];
                                a[i+m] = temp;
                            }

                    }
            }
    }
}
4

2 回答 2

3

所以这里有很多问题。

所以首先，正如已经指出的，i 和 j（和 temp）需要是私有的；m 和需要共享。与 openmp 一起做的一个有用的事情是使用 default(none)，这样你就不得不考虑你在并行部分中使用的每个变量的作用，以及它需要什么。所以这

   #pragma omp parallel for private (i,j,temp) shared(a,m) default(none)

是一个好的开始。特别是把 m 设为私有有点像灾难，因为这意味着 m 在并行区域内是未定义的。顺便说一下，循环应该从 m = n/2 开始，而不是 m=2。

此外，对于 shell 排序，您不需要关键区域 - 或者您不应该。我们稍后会看到，问题不在于多个线程处理相同的元素。所以如果你摆脱了这些东西，你最终会得到一些几乎可以工作的东西，但并非总是如此。这给我们带来了更根本的问题。

外壳排序的工作方式基本上是将数组分解为许多（此处为m）子数组，并对它们进行插入排序（对于小型数组来说非常快），然后重新组合；然后继续将它们分解为越来越少的子数组和插入排序（非常快，因为它们是部分排序的）。对这些子数组进行排序是可以并行完成的。（在实践中，内存争用将是这种简单方法的问题，但仍然如此）。

现在，您拥有的代码以串行方式执行此操作，但如果您只是将 j 循环包装在omp parallel for. 原因是通过 j 循环的每次迭代都会执行其中一种插入排序的一步。第 j+m 次循环迭代执行下一步。但是不能保证它们是由同一个线程或按顺序完成的！如果另一个线程在第 j 次迭代之前已经完成了第 j+m 次迭代，那么插入排序就会出错并且排序失败。

因此，实现这项工作的方法是重写 shell 排序以使并行性更加明确——不要将插入排序分解为一堆串行步骤。

#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

void insertionsort(int a[], int n, int stride) {
    for (int j=stride; j<n; j+=stride) {
        int key = a[j];
        int i = j - stride;
        while (i >= 0 && a[i] > key) {
            a[i+stride] = a[i];
            i-=stride;
        }
        a[i+stride] = key;
    }
}

void shellsort(int a[], int n)
{
    int i, m;

    for(m = n/2; m > 0; m /= 2)
    {
            #pragma omp parallel for shared(a,m,n) private (i) default(none)
            for(i = 0; i < m; i++)
                insertionsort(&(a[i]), n-i, m);
    }
}

void printlist(char *s, int a[], int n) {
    printf("%s\n",s);
    for (int i=0; i<n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int checklist(int a[], int n) {
    int result = 0;
    for (int i=0; i<n; i++) {
        if (a[i] != i) {
            result++;
        }
    }
    return result;
}

void seedprng() {
    struct timeval t;

    /* seed prng */
    gettimeofday(&t, NULL);
    srand((unsigned int)(1000000*(t.tv_sec)+t.tv_usec));
}

int main(int argc, char **argv) {
    const int n=100;
    int *data;
    int missorted;

    data = (int *)malloc(n*sizeof(int));
    for (int i=0; i<n; i++)
        data[i] = i;

    seedprng();
    /* shuffle */ 
    for (int i=0; i<n; i++) {
        int i1 = rand() % n;
        int i2 = rand() % n;
        int tmp = data[i1];
        data[i1] = data[i2];
        data[i2] = tmp;
    }

    printlist("Unsorted List:",data,n);

    shellsort2(data,n);

    printlist("Sorted List:",data,n);
    missorted = checklist(data,n);
    if (missorted != 0) printf("%d missorted nubmers\n",missorted);

    return 0;
}
于 2011-05-06T01:24:56.963 回答
1

变量“j”和“i”需要在并行区域上声明为私有。就像现在一样，我很惊讶发生了什么，因为“m”不能是私有的。临界区允许它为“i”循环工作，但临界区应该能够减少——尽管我有一段时间没有做过 shell 排序了。

于 2011-05-05T20:44:04.027 回答