为什么 MPI 和 OpenMP 合并排序比我的顺序代码慢？

Question

我已经用 C 编写了合并排序代码。我按顺序、OpenMP 和 MPI 应用了这个算法。我使用了 100 个随机元素的数组。顺序代码如下：


int main(){
    int N = 100;
    int my_array[N];
    int outputArray[N];
    int length = sizeof(my_array) / sizeof(my_array[0]);
    double start_time, end_time;
    srand(time(NULL));
    int i;
    for (i=0; i<N; i++){
        my_array[i]=rand()%100 + 1;
    }
    //print the array 
    for (i=0; i<N; i++){
        printf("%d ", my_array[i]);
    }   

    printf("\n--------------\n");
    start_time = MPI_Wtime();
    mergeSort(my_array, 0, length-1, outputArray); 
    end_time = MPI_Wtime();
    for(i=0; i<N; i++){
        printf("%d ", my_array[i]);
    }
    printf("\n");
    printf("\n Tempo impiegato: %f ", (end_time - start_time));
} 


void merge(int arr[], int indexA, int indexB, int end, int arrOut[]){
    int i=indexA, j=indexB, k=indexA;
    while(i<=indexB-1 && j<=end){
        if(arr[i]<arr[j]){
            //i=i+1;
            arrOut[k]=arr[i++];
        }
        else{
            //j=j+1;
            arrOut[k]=arr[j++];
        }
        k++;
    }
    while(i<=indexB-1){
        //i++;
        arrOut[k]=arr[i++];
        k++;
    }
    while(j<=end){
        //j++;
        arrOut[k]=arr[j++];
        k++;
    }
    for(i=indexA; i<=end; i++)
        arr[i]=arrOut[i];
}

void mergeSort(int arr[], int inf, int sup, int arrOut[]){
    int medium;
    if(inf<sup){
        medium=(inf+sup)/2;
        mergeSort(arr, inf, medium, arrOut);
        mergeSort(arr, medium+1, sup, arrOut);
        merge(arr, inf, medium+1, sup, arrOut);
    }
}

然后，使用 MPI 的实现如下（它在创建随机数组后开始）：

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &n_ranks);
    start_time = MPI_Wtime();

    size=N/n_ranks;
    sub_array=malloc(size*sizeof(int));
    temp=malloc(size*sizeof(int));
    MPI_Scatter(my_array, size, MPI_INT, sub_array, size, MPI_INT, 0, MPI_COMM_WORLD);
    mergeSort(sub_array, 0, length-1, temp);
    MPI_Gather(sub_array, size, MPI_INT, outputArray, size, MPI_INT, 0, MPI_COMM_WORLD);

    if(rank==0){
        int *temp_array=malloc(N*sizeof(int));
        mergeSort(outputArray, 0, length-1, temp_array);
        for(i=0; i<N; i++){
            printf("%d ", temp_array[i]);
        }
        free(temp_array);
    }

    //free(&my_array);
    free(sub_array);
    free(temp);

    //MPI_Barrier(MPI_COMM_WORLD);
    end_time = MPI_Wtime();

编辑代码 OPENMP：最后这是 OpenMP（主要是相同的）

void parallelMergeSort(int arr[], int inf, int sup, int arrOut[], int level){
    if (level==0){
        #pragma omp parallel
        #pragma omp single
        parallelMergeSort(arr, inf, sup, arrOut, 1);
    }
    else if(level<8){
        #pragma omp task shared(arr, arrOut)
        {
            parallelMergeSort(arr, inf, (inf+sup)/2, arrOut, level+1);
        }
        #pragma omp task shared(arr, arrOut)
        {
            parallelMergeSort(arr, (inf+sup)/2 + 1, sup, arrOut, level+1);
        }
    }
    #pragma omp taskwait
    {
        mergeSort(arr, inf, sup, arrOut);
    }   
}

如果我将这些代码应用于包含 100 个元素的数组，则 MPI 和 OpenMP 代码的执行时间会更长。时间顺序：0.000044

OpenMP 时间：0.00949953

时间 MPI：0.003077

编辑：如果我尝试使用 10^6 个随机元素，结果如下：

时间顺序：0.899016

时间 OpenMP：分段错误

时间 MPI：25.625195 我怎样才能改善这些结果？

Answer 1

我不懂MPI，所以只回答问题的OpenMP部分。在不更改算法的情况下，mergeSort 函数的 OpenMP 版本应如下所示：

void parallelMergeSort(int arr[], int inf, int sup, int arrOut[], int level){
    if(inf<sup){
        int medium=(inf+sup)/2;
        #pragma omp task shared(arr, arrOut) if(level>0)
          parallelMergeSort(arr, inf, medium, arrOut, level-1);   
        parallelMergeSort(arr, medium+1, sup, arrOut, level-1);
        #pragma omp taskwait
         merge(arr, inf, medium+1, sup, arrOut);
    }
}

我使用了 if(level>0) 子句来避免启动太多任务。在我的计算机上使用 level=4 会出现短路运行次，但这当然取决于可用内核的数量和阵列的大小。请注意，在第二个 parallelMergeSort 函数调用之前我没有使用第二个 #pragma omp task 行，因为这样会更快运行。您应该使用以下方式调用此函数：

#pragma omp parallel
#pragma omp single
parallelMergeSort(my_array, 0, length-1, outputArray,4);

如果您希望更改算法以获得更好的并行化，请阅读我在评论中链接的文档。

为什么 MPI 和 OpenMP 合并排序比我的顺序代码慢？

Why MPI and OpenMP Merge Sort are slower than my sequential code?

c

parallel-processing

mpi

openmp