时间戳

首页 > 解决方案 > 使用 C 中的 openmp，如何并行化包含 qsort 的嵌套比较函数的 for 循环？

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

问题描述

我想并行化一个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 必须是一个全局变量，这会弄乱多线程。但是，如果有人建议在没有嵌套函数的情况下实现相同的结果，那将是最受欢迎的。

标签： copenmpqsort

解决方案

我意识到这是自我回答的，但这里有一些标准的 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;
}

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

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

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

推荐阅读