С openmp в C, как я могу распараллелить цикл for, который содержит вложенную функцию сравнения для qsort? - PullRequest
Новая
       17

С openmp в C, как я могу распараллелить цикл for, который содержит вложенную функцию сравнения для qsort?

0 голосов
/ 09 января 2019

Я хочу распараллелить цикл 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 работать с этой вложенной функцией сравнения? Если нет, то есть ли хороший способ достичь аналогичного результата без вложенной функции сравнения?

Edit: Я использую компилятор GNU C, где разрешены вложенные функции. Код компилируется и работает нормально без выражения pragma. Я не могу определить simcmp вне цикла for, потому что тогда tmp_array должна быть глобальной переменной, которая может испортить многопоточность. Однако, если у кого-то есть предложение достичь того же результата без вложенной функции, это будет приветствоваться.

Ответы [ 2 ]

0 голосов
/ 12 января 2019

Я понимаю, что это был ответ сам, но вот некоторые стандартные опции 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 и алгоритм 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;
    }
});
0 голосов
/ 10 января 2019

Я решил свою проблему с помощью 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 зависит от платформы и компилятора. Здесь есть переносимая версия qsort_r , где автор хорошо описывает мою проблему:

Если вы хотите qsort () массив с оператором сравнения, который принимает параметры вам нужно использовать глобальные переменные для передачи этих параметров (невозможно при написании многопоточного кода) или использовать qsort_r / qsort_s которые не являются переносимыми (существуют отдельные версии GNU / BSD / Windows и все они принимают разные аргументы).

...