1

openmp に詳しい人はいますか? 並べ替えられたリストを取得できません。私は何を間違っていますか。最後にクリティカルを使用しているため、ソートされたときにそのセクションにアクセスできるのは1つのスレッドだけです。私の個人的な価値観は正しくないと思います。それらが存在する必要があるのか​​、それとも #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 と a を共有する必要があります。openmp で行う便利な方法は、default(none) を使用することです。これにより、並列セクションで使用する各変数が何をするのか、およびそれが何を必要とするのかを考える必要があります。したがって、この

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

良いスタートです。特に m を非公開にすることは、並列領域内で m が定義されていないことを意味するため、ちょっとした災害です。ところで、ループは m=2 ではなく m = n/2 で開始する必要があります。

さらに、シェル ソートの場合、クリティカル領域は必要ありません。または必要ありません。この問題は、すぐにわかりますが、同じ要素で複数のスレッドが動作することではありません。したがって、これらのものを取り除くと、ほとんど機能するものになりますが、常に機能するとは限りません. そして、それは私たちをより根本的な問題に導きます。

シェルソートの仕組みは、基本的に、配列を多くの (ここではm) サブ配列に分割し、それらを挿入ソート (小さな配列の場合は非常に高速) してから再構築することです。次に、それらをますます少ないサブ配列と挿入ソートに分割して続行します（部分的にソートされているため、非常に高速です）。これらの多くのサブアレイのソートは、並行して実行できるものです。(実際には、この単純なアプローチではメモリの競合が問題になりますが、それでもなお)。

今、あなたが手に入れたコードはそれを順番に実行しますが、 j ループをomp parallel for. その理由は、j ループを通る各反復が、挿入ソートの 1 つのステップを 1 つ実行するためです。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;
}
于 2011-05-06T01:24:56.963 に答える
1

変数 "j" と "i" は、並列領域でプライベートに宣言する必要があります。「m」は非公開にできないので、今のところ、何かが起こっていることに驚いています。クリティカル領域は「i」ループで機能することを許可していますが、クリティカル領域は縮小できるはずです-しばらくシェルソートを行っていません.

于 2011-05-05T20:44:04.027 に答える