我的归并排序算法使用 OpenMP 时速度较慢，如何使其比序列化形式更快？

Question

我正在研究并行编程并在排序算法上对其进行测试。我发现最简单的方法是使用 OpenMP，因为它提供了一种实现线程的简单方法。我做了研究，发现其他人已经这样做了，然后我尝试了一些代码。但是，当我perf stat -r 10 -d在 Linux 上测试它时，我得到的时间比序列化代码更糟糕（在某些情况下是两倍）。我尝试在数组上使用不同数量的元素，我使用的最大数量是 1.000.000 个数字，就好像我使用更多我收到错误一样。

void merge(int aux[], int left, int middle, int right){
    int temp[middle-left+1], temp2[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 mergeSort (int aux[], int left, int right){
    if (left < right){
        int middle = (left + right)/2;
        omp_set_num_threads(2);
        #pragma omp parallel
        {

            #pragma omp sections
            {
                #pragma omp section
                    mergeSort(aux,left,middle); //call 1
                #pragma omp section
                    mergeSort(aux,middle+1,right); //call 2
            }
        }
        merge(aux,left,middle,right);
    }
}

int main(){
    generate_list(Vet, n);
    mergeSort(Vet, 0, n-1);

    return(0);
}

以下是我收到的结果：

OpenMP 代码：

性能计数器统计信息./mergeomp（10 次运行）：

         12,489169      task-clock (msec)         #    0,717 CPUs utilized            ( +-  3,58% )
                 8      context-switches          #    0,681 K/sec                    ( +-  6,62% )
                 0      cpu-migrations            #    0,000 K/sec                  
               167      page-faults               #    0,013 M/sec                    ( +-  0,79% )
   <not supported>      cycles                                                      
   <not supported>      instructions                                                
   <not supported>      branches                                                    
   <not supported>      branch-misses                                               
   <not supported>      L1-dcache-loads                                             
   <not supported>      L1-dcache-load-misses                                       
   <not supported>      LLC-loads                                                   
   <not supported>      LLC-load-misses                                             

           0,01743 +- 0,00211 seconds time elapsed  ( +- 12,10% )

序列化方式（简单代码）：

性能计数器统计信息./mergesort（10 次运行）：

          3,757053      task-clock (msec)         #    0,449 CPUs utilized            ( +-  0,72% )
                 1      context-switches          #    0,293 K/sec                    ( +- 16,32% )
                 0      cpu-migrations            #    0,000 K/sec                  
               139      page-faults               #    0,037 M/sec                    ( +-  0,34% )
   <not supported>      cycles                                                      
   <not supported>      instructions                                                
   <not supported>      branches                                                    
   <not supported>      branch-misses                                               
   <not supported>      L1-dcache-loads                                             
   <not supported>      L1-dcache-load-misses                                       
   <not supported>      LLC-loads                                                   
   <not supported>      LLC-load-misses                                             

          0,008375 +- 0,000276 seconds time elapsed  ( +-  3,29% )

我做错了什么吗？我正在用-fopenmp标志编译它，但不知道合并排序是否不适合并行化，或者我的 linux 虚拟机（我在 VM Virtual Box 机器上运行 Ubuntu，我的 PC 有一个 Core I7 处理器) 配置不当。

Answer 1

感谢大家的帮助，我解决了这个问题。

首先，我没有在虚拟机上设置多核。

然后，我更改了sections的构造task。

我还在数组中使用了更多数量的元素（200 万）。

最后，我添加了一个过滤器，以在数组小于“n”个元素时停止使用并行性：

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

我发现 1.000.000 是“n”的最佳数字，我的算法比顺序算法快 2 倍。