OpenMP:并行快速排序 [英] OpenMP : Parallel QuickSort

问题描述

我尝试使用 OpenMP 在分区部分和 QuickSort 部分并行化 QuickSort.我的C代码如下:

I try to use OpenMP to parallelize QuickSort in partition part and QuickSort part. My C code is as follows:

#include "stdlib.h"
#include "stdio.h"
#include "omp.h"

// parallel partition
int ParPartition(int *a, int p, int r) {
    int b[r-p];
    int key = *(a+r); // use the last element in the array as the pivot
    int lt[r-p]; // mark 1 at the position where its element is smaller than the key, else 0
    int gt[r-p]; // mark 1 at the position where its element is bigger than the key, else 0
    int cnt_lt = 0; // count 1 in the lt array
    int cnt_gt = 0; // count 1 in the gt array
    int j=p;
    int k = 0; // the position of the pivot
    // deal with gt and lt array
    #pragma omp parallel for
    for ( j=p; j<r; ++j) {
        b[j-p] = *(a+j);
        if (*(a+j) < key) {
            lt[j-p] = 1;
            gt[j-p] = 0;
        } else {
            lt[j-p] = 0;
            gt[j-p] = 1;
        }
    }
    // calculate the new position of the elements
    for ( j=0; j<(r-p); ++j) {
        if (lt[j]) {
            ++cnt_lt;
            lt[j] = cnt_lt;
        } else
            lt[j] = cnt_lt;
        if (gt[j]) {
            ++cnt_gt;
            gt[j] = cnt_gt;
        } else
            gt[j] = cnt_gt;
    }
    // move the pivot
    k = lt[r-p-1];
    *(a+p+k) = key;
    // move elements to their new positon
    #pragma omp parallel for 
    for ( j=p; j<r; ++j) {
        if (b[j-p] < key)
            *(a+p+lt[j-p]-1) = b[j-p];
        else if (b[j-p] > key)
            *(a+k+gt[j-p]) = b[j-p];
    }
    return (k+p);
}

void ParQuickSort(int *a, int p, int r) {
    int q;
    if (p<r) {
        q = ParPartition(a, p, r);
        #pragma omp parallel sections
        {
        #pragma omp section
        ParQuickSort(a, p, q-1);
        #pragma omp section
        ParQuickSort(a, q+1, r);
        }
    }
}

int main() {
    int a[10] = {5, 3, 8, 4, 0, 9, 2, 1, 7, 6};
    ParQuickSort(a, 0, 9);
    int i=0;
    for (; i!=10; ++i)
        printf("%d\t", a[i]);
    printf("\n");
    return 0;
}

以main函数为例，排序结果为:

For the example in the main function, the sorting result is:

0   9   9   2   2   2   6   7   7   7

我使用 gdb 进行调试.在早期的递归中，一切顺利.但是在一些递归中，它突然搞砸了开始重复元素.然后生成上面的结果.

I used gdb to debug. In the early recursion, all went well. But in some recursions, it suddenly messed up to begin duplicate elements. Then generate the above result.

谁能帮我找出问题所在?

Can someone help me figure out where the problem is?

推荐答案

我为我的第一条评论感到抱歉.这与你的问题无关.我还没有找到你问题的真正问题(也许你的移动元素有问题).根据你的意见，我写了一个类似的程序，它的工作原理很好.(我也是 OpenMP 新手).

I feel sorry for my first comment.It does not matter with your problem.I have not found the true problem of your question(Maybe your move element has the problem).According to your opinion, I wrote a similar program, it works fine.(I am also new on OpenMP).

#include <stdio.h>
#include <stdlib.h>


int partition(int * a, int p, int r)
{
    int lt[r-p];
    int gt[r-p];
    int i;
    int j;
    int key = a[r];
    int lt_n = 0;
    int gt_n = 0;

#pragma omp parallel for
    for(i = p; i < r; i++){
        if(a[i] < a[r]){
            lt[lt_n++] = a[i];
        }else{
            gt[gt_n++] = a[i];
        }   
    }   

    for(i = 0; i < lt_n; i++){
        a[p + i] = lt[i];
    }   

    a[p + lt_n] = key;

    for(j = 0; j < gt_n; j++){
        a[p + lt_n + j + 1] = gt[j];
    }   

    return p + lt_n;
}

void quicksort(int * a, int p, int r)
{
    int div;

    if(p < r){ 
        div = partition(a, p, r); 
#pragma omp parallel sections
        {   
#pragma omp section
            quicksort(a, p, div - 1); 
#pragma omp section
            quicksort(a, div + 1, r); 

        }
    }
}

int main(void)
{
    int a[10] = {5, 3, 8, 4, 0, 9, 2, 1, 7, 6};
    int i;

    quicksort(a, 0, 9);

    for(i = 0;i < 10; i++){
        printf("%d\t", a[i]);
    }
    printf("\n");
    return 0;
}

这篇关于OpenMP:并行快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！