c++ - 如何使用 OpenMP 改进归并排序算法？

Question

我正在尝试使用 OpenMP 改进我的代码执行时间。我正在研究并行性并测试不同的实现方式。

我尝试将我的数组分成 4 个，我想在 4 个内核中运行我的代码（每个部分都在一个内核中），然后合并所有内容。

因此，我将其切片并使用 : 运行 4 个 mergeSorts #pragma omp single nowait，但我认为我没有以正确的方式进行操作，因为它仅使用了大约 1,5 个核心。我需要改变什么来满足我的需要？（对不起，我是 OpenMP 的新手，我是一名计算机科学专业的学生，​​我正在做这个作为课堂研究）。

此外，我的速度变慢了，因为我需要进行额外的合并，因为它分为四个部分（我的执行时间比简单的并行方式慢大约两倍。

这是我的完整代码（欢迎其他改进提示）：

#include<iostream>
#include<fstream>
#include<algorithm>
#include "omp.h"
using namespace std;

int n = 60000000;
int * Vet = new int [60000000];
double startTime, stopTime;

void generate_list(int * x, int n) {
   int i,j,t;
   for (i = 0; i < n; i++)
     x[i] = i;
   for (i = 0; i < n; i++) {
     j = rand() % n;
     t = x[i];
     x[i] = x[j];
     x[j] = t;
   }
}

void merge(int aux[], int left, int middle, int right){
    int * temp = new int [middle-left+1];
    int * temp2 = new int[right-middle];
    for(int i=0; i<(middle-left+1); i++){
        temp[i]=aux[left+i];
    }
    for(int i=0; i<(right-middle); i++){
        temp2[i]=aux[middle+1+i];
    }
    int i=0, j=0, k=left;
    while(i<(middle-left+1) && j<(right-middle))
    {
        if(temp[i]<temp2[j]){
            aux[k++]=temp[i++];
        }
        else{
            aux[k++]=temp2[j++];
        }
    }
    while(i<(middle-left+1)){
        aux[k++]=temp[i++];
    }
    while(j<(right-middle)){
        aux[k++]=temp2[j++];
    }
}

void mergeSortSerial(int aux[], int left, int right){
    if (left < right){
        int middle = (left + right)/2;
        mergeSortSerial(aux,left,middle); //call 1
        mergeSortSerial(aux,middle+1,right); //call 2
        merge(aux,left,middle,right);
    }
}

void mergeSort (int aux[], int left, int right){
    if (left < right){
        if ((right-left) > 1000){
            int middle = (left + right)/2;
           #pragma omp task firstprivate (aux, left, middle)
                mergeSort(aux,left,middle); //call 1
            #pragma omp task firstprivate (aux, middle, right)
                mergeSort(aux,middle+1,right); //call 2
            #pragma omp taskwait
            merge(aux,left,middle,right);
        } else{mergeSortSerial(aux, left, right);}
    }
}

void print(int aux[], int n)
{
    for(int i=0; i<n; i++)
        cout<<aux[i]<<" ";
    cout<<endl;
}



int main(){
    generate_list(Vet, n);
    omp_set_nested(1);
    omp_set_num_threads(4);
    //startTime = clock();
    int middle = n/2;
    int middleLeft = (n) / 4;
    int middleRight = 3 * (n) / 4;
       #pragma omp parallel
   {
      #pragma omp single nowait
        mergeSort(Vet, 0, middleLeft);
      #pragma omp single nowait
        mergeSort(Vet, middleLeft+1, middle);
      #pragma omp single nowait
        mergeSort(Vet, middle+1, middleRight);
      #pragma omp single nowait
        mergeSort(Vet, middleRight+1, n);
    }
        merge(Vet, 0, middleLeft, middle);
        merge(Vet, middle+1, middleRight, n);
        merge(Vet, 0, n/2, n);



    //stopTime = clock();
    cout<<is_sorted(Vet,Vet+n)<<endl;
    //print(Vet, n);
    //printf("\nSorted in (aprox.): %f seconds \n\n", (double)(stopTime-startTime)/CLOCKS_PER_SEC);
    return(0);
}

标签： c++openmpmergesort