使用 C 中的 openmp，如何并行化包含用于 qsort 的嵌套比较函数的 for 循环？

Question

我想并行化 for 循环，其中包含 qsort 的嵌套比较函数：

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

int main(){
    int i;
#pragma omp parallel for
    for(i = 0; i < 100; i++){
        int *index= (int *) malloc(sizeof(int)*10);
        double *tmp_array = (double*) malloc(sizeof(double)*10);
        int j;
        for(j=0; j<10; j++){
            tmp_array[j] = rand();
            index[j] = j;
        }
        // QuickSort the index array based on tmp_array:
        int simcmp(const void *a, const void *b){
            int ia = *(int *)a;
            int ib = *(int *)b;
            if ((tmp_array[ia] - tmp_array[ib]) > 1e-12){
                return -1;
            }else{
                return 1;
            }
        }
        qsort(index, 10, sizeof(*index), simcmp);
        free(index);
        free(tmp_array);
    }
    return 0;
}

当我尝试编译它时，出现错误：

internal compiler error: in get_expr_operands, at tree-ssa-operands.c:881
 }

据我所知，这个错误是由于嵌套比较函数引起的。有没有办法让 openmp 使用这个嵌套比较函数？如果不行，有没有不用嵌套比较函数也能达到类似结果的好方法？

编辑：我正在使用允许嵌套函数的 GNU C 编译器。代码在没有 pragma 语句的情况下编译和运行良好。我不能在 for 循环之外定义 simcmp，因为 tmp_array 必须是一个全局变量，这会扰乱多线程。但是，如果有人建议在没有嵌套函数的情况下实现相同的结果，那将是最受欢迎的。

Answer 1

我用 qsort_r 解决了我的问题，它允许您将一个额外的指针传递给比较函数。

#define _GNU_SOURCE
#include    <stdio.h>
#include    <stdlib.h>
#include    <omp.h>

int simcmp(const void *a, const void *b, void *tmp_array){
    int ia = *(int *)a;
    int ib = *(int *)b;
    double aa = ((double *)tmp_array)[ia];
    double bb = ((double *)tmp_array)[ib];
    if ((aa - bb) > 1e-12){
        return -1;
    }else{
        return 1;
    }
}

int main(){
    int i;
#pragma omp parallel for
    for(i = 0; i < 100; i++){
        int *index= (int *) malloc(sizeof(int)*10);
        double *tmp_array = (double*) malloc(sizeof(double)*10);
        int j;
        for(j=0; j<10; j++){
            tmp_array[j] = rand();
            index[j] = j;
        }
        // QuickSort the index array based on tmp_array:
        qsort_r(index, 10, sizeof(*index), simcmp, tmp_array);
        free(index);
        free(tmp_array);
    }
    return 0;
}

编译和运行没有问题。但是，它并不完全理想，因为 qsort_r 依赖于平台和编译器。有一个 portable version of qsort_r here 作者很好地总结了我的问题：

If you want to qsort() an array with a comparison operator that takes parameters you need to use global variables to pass those parameters (not possible when writing multithreaded code), or use qsort_r/qsort_s which are not portable (there are separate GNU/BSD/Windows versions and they all take different arguments).

Answer 2

我知道这已经是自我回答，但这里有一些标准的 C 和 OpenMP 选项。 qsort_r 函数是一个很好的经典选择，但值得注意的是 qsort_s 是 c11 标准的一部分，因此在任何提供 c11 的地方都是可移植的（不包括 Windows，它们还不太提供 c99）。

在没有嵌套比较功能的OpenMP中，仍然使用原始的qsort，有两种方法可以想到。首先是结合 OpenMP 使用经典的全局变量 threadprivate:

static int *index = NULL;
static double *tmp_array = NULL;

#pragma omp threadprivate(index, tmp_array)

int simcmp(const void *a, const void *b){
    int ia = *(int *)a;
    int ib = *(int *)b;
    double aa = ((double *)tmp_array)[ia];
    double bb = ((double *)tmp_array)[ib];
    if ((aa - bb) > 1e-12){
        return -1;
    }else{
        return 1;
    }
}

int main(){
    int i;
#pragma omp parallel for
    for(i = 0; i < 100; i++){
        index= (int *) malloc(sizeof(int)*10);
        tmp_array = (double*) malloc(sizeof(double)*10);
        int j;
        for(j=0; j<10; j++){
            tmp_array[j] = rand();
            index[j] = j;
        }
        // QuickSort the index array based on tmp_array:
        qsort_r(index, 10, sizeof(*index), simcmp, tmp_array);
        free(index);
        free(tmp_array);
    }
    return 0;
}

上面的版本导致并行区域中的每个线程都使用全局变量索引和 tmp_array 的私有副本，从而解决了这个问题。这可能是您可以用标准 C 和 OpenMP 编写的最便携的版本，唯一可能不兼容的平台是那些不实现线程本地内存的平台（某些微控制器等）。

如果您想避免使用全局变量并仍然具有可移植性并使用 OpenMP，那么我建议使用 C++11 和带有 lambda 的 std::sort 算法：

std::sort(index, index+10, [=](const int& a,  const int& b){
    if ((tmp_array[a] - tmp_array[b]) > 1e-12){
        return -1;
    }else{
        return 1;
    }
});

使用 C 中的 openmp，如何并行化包含用于 qsort 的嵌套比较函数的 for 循环？

With openmp in C, how can I parallelize a for loop that contains a nested comparison function for qsort?

c

openmp

qsort