openmp中的希尔排序

Question

有谁熟悉 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;
                            }

                    }
            }
    }
}

Answer 1

所以这里有很多问题。

因此，首先，正如已经指出的，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 排序 的工作方式基本上是，将数组分成许多（这里，< code>m) 子数组，并对它们进行插入排序（对于小数组来说非常快），然后重新组装；然后继续将它们分成越来越少的子数组和插入排序（非常快，因为它们是部分排序的）。对这些许多子数组进行排序是可以并行完成的事情。 （实际上，内存争用将是这种简单方法的一个问题，但仍然如此）。

现在，您获得的代码以串行方式执行此操作，但如果您只是将 j 循环包装在 omp parallel for 中，则不能指望它能够工作。原因是 j 循环的每次迭代都会执行其中一个插入排序的一个步骤。第 j+m 个循环迭代执行下一步。但不能保证它们是由同一个线程或按顺序完成的！如果另一个线程在第一个线程执行第 j 次迭代之前已经完成了第 j+m 次迭代，则插入排序就会混乱并且排序失败。

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

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

Answer 2

变量“j”和“i”需要在并行区域上声明为私有。就现在而言，我对发生的一切感到惊讶，因为“m”不能是私有的。临界区域允许它为“i”循环工作，但临界区域应该能够减少 - 尽管我有一段时间没有进行希尔排序了。