OpenMP C - усреднение параллельных циклов дает разные результаты - PullRequest
Новая
       7

OpenMP C - усреднение параллельных циклов дает разные результаты

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

Я пытаюсь распараллелить мою программу на C, которая читает 5000 файлов с данными и усредняет каждую строку по файлам. Например,

Файл 1: 

1
2

Файл 2: 

3
4

Вывод будет: 

2
3

Программа работает нормально, пока я не распараллелю ее, а затем получаю разные ответы при каждом запуске. Программа выглядит так: 

#pragma omp parallel for        
for(int i=0; i<numFiles; i++){
    //Process FILES
    processFile(argv[i+2],alpha,entropySum,entropy2Sum);
}

Где processFiles открывает файл в argv и добавляет данные в строке i в массив entropySum [i], а данные ^ 2 в массив entropy2Sum [i]. После добавления всех данных я вывожу свою информацию, используя 

for(int i=0; i<=TF; i++){
    double avg=0, avg2=0, stdDev=0;
    avg = entropySum[i]/numFiles;
    avg2 = entropy2Sum[i]/numFiles;
    stdDev = sqrt(avg2-pow(avg,2));
    printf("%d\t%.12e\t%.12e\n",i,avg,stdDev);
}

Это пример различных результатов, которые я получаю: 

$ ./calcEntropy 1 data/2019_01_07/L06/p_00/data*
0   0.000000000000e+00  0.000000000000e+00
1   3.805323999338e-01  1.739913615303e-01
2   9.195334281358e-01  1.935111917992e-01
3   1.263129144934e+00  1.592392740809e-01
4   1.437299446640e+00  1.069415304025e-01
**5 1.519477007427e+00  7.899186640180e-02**
6   1.540955646645e+00  8.134009585552e-02
7   1.562133860024e+00  6.672275284387e-02
**8 1.573666031035e+00  7.200051995992e-02**
9   1.577305749778e+00  6.905825416624e-02
10  1.584251429260e+00  7.170811783630e-02
11  1.606099624837e+00  7.026618801497e-02
12  1.587069341648e+00  6.714269884875e-02

$ ./calcEntropy 1 data/2019_01_07/L06/p_00/data*
0   0.000000000000e+00  0.000000000000e+00
1   3.805323999338e-01  1.739913615303e-01
2   9.195334281358e-01  1.935111917992e-01
3   1.263129144934e+00  1.592392740809e-01
4   1.437299446640e+00  1.069415304025e-01
**5 1.519114903273e+00  8.255618715434e-02**
6   1.540955646645e+00  8.134009585553e-02
7   1.562133860024e+00  6.672275284389e-02
**8 1.573666031035e+00  6.715192373223e-02**
9   1.577305749778e+00  6.905825416623e-02
10  1.584251429260e+00  7.170811783631e-02
11  1.606099624837e+00  7.026618801500e-02
12  1.587069341648e+00  6.714269884876e-02

После проверки в Интернете, я чувствую, что мне, вероятно, следует использовать сокращение? Но я не совсем уверен, как реализовать это в этом цикле с двумя переменными, которые увеличиваются (entropySum и entropy2Sum), а также увеличиваются внутри функции processFile.

Пожалуйста, дайте мне знать, если вам нужна дополнительная информация или код. Спасибо.

1 Ответ

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

Я предполагаю, что проблема в том, что математика с плавающей запятой не ассоциативна. Смотри https://en.wikipedia.org/wiki/Associative_property#Nonassociativity_of_floating_point_calculation

Другими словами, если у вас есть числа с плавающей точкой a, b и c, то (a + b) + c не всегда равно a + (b + c). Порядок, который вы делаете, имеет значение. Однако, если вы используете #pragma omp parallel for, вы сообщаете компилятору, что порядок не имеет значения .

Вот несколько подходов к решению этой проблемы:

  1. Сделайте дополнение точно с GMP. Есть библиотека GMP, которая позволяет вам конвертировать двойное число в рациональное число. Затем вы можете сложить рациональные числа вместе, и результат будет одинаковым независимо от того, в каком порядке он выполняется, потому что нет округления. Смотри https://gmplib.org/manual/Rational-Number-Functions.html#Rational-Number-Functions

    После добавления вы можете преобразовать рациональное обратно в двойное, что не является точным, но каждый раз оно является неточным одинаковым образом.

  2. Выполните сложение точно с фиксированной точкой. Преимущество этого заключается в том, что вам не нужно использовать внешнюю библиотеку.

    Преобразовать числа в фиксированную точку следующим образом: 

    #define SCALE_FACTOR 100
// Convert from double to fixed point
// Example: 15.46   becomes 1546
// Example: 3.14159 becomes 314
int convert_d_to_fixed(double d) {
    return (int) d * SCALE_FACTOR
}

    Преобразование в фиксированную точку неточно. Однако после преобразования все сложения и вычитания в фиксированной точке становятся точными, поскольку вы используете целочисленную арифметику. 

    int add_fixed(int a, int b) {
    return a + b;
}

    Как только вы закончите добавление, вы можете конвертировать обратно: 

    double convert_fixed_to_d(int f) {
    return ((double) f) / SCALE_FACTOR;
}

    Этот метод не является точным, но он неточен в точности каждый раз, независимо от того, в каком порядке производится добавление.

  3. Загрузите каждое число в память, затем выполните сложение. Создайте двумерный массив. Каждый столбец представляет один файл. Каждая строка - это строка из каждого файла. В псевдокоде: 

    #pragma omp parallel for        
for(int i=0; i<numFiles; i++){
    load file i into column i
}
#pragma omp parallel for        
for(int j=0; j<numRows; j++){
    sum row j into entropySum[j]
    sum square of elements in row j into entropy2Sum[j]
}

    Это всегда делает сложения в том же порядке, но все же допускает параллелизм при загрузке данных и при добавлении данных.

    Недостаток: весь набор данных должен быть загружен в память одновременно. Это стоит (number of files) * (number of rows) * 8 байтов

...