openmp для l oop не распараллеливается - PullRequest
Новая
       118

openmp для l oop не распараллеливается

1 голос
/ 21 июня 2020

Я пытаюсь измерить время работы параллельной версии и последовательной.

У меня есть такая программа: 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <omp.h>
#include <time.h>
#include <unistd.h>
#include <sys/types.h>
#include <errno.h>
#include <sys/resource.h>
#include <sys/times.h>

#define ARRAY_SIZE 1024 * 20

long time_delta = 0;

struct rusage rusage_start;
struct rusage rusage_finish;

void bubble_sort(unsigned int* array) {
    unsigned int tmp = 0;
    bool no_swap = 0;
    for (unsigned int i = ARRAY_SIZE - 1; i >= 0; --i)
    {
        no_swap = 1;
        {
            #pragma omp parallel for num_threads(4)
            for (unsigned int j = 0; j < i; j++)
            {
                if (array[j] > array[j + 1])
                {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    no_swap = 0;
                }
            }
        }
        if (no_swap)
            break;
    }
}

int main(int argc, char* argv[]) {
    (void)argc;
    (void)argv;
    srand(time(NULL));
    unsigned int* array = malloc(sizeof(unsigned int) * ARRAY_SIZE);
    if(!array) { return -1; }
    for(unsigned int i = 0; i < ARRAY_SIZE; ++i) {
        array[i] = rand() % ARRAY_SIZE;
    }
    getrusage(RUSAGE_SELF, &rusage_start);
    
    //sort
    bubble_sort(array);

    getrusage(RUSAGE_SELF, &rusage_finish);
    time_delta = (1000000 * (rusage_finish.ru_utime.tv_sec - rusage_start.ru_utime.tv_sec)) + (rusage_finish.ru_utime.tv_usec - rusage_start.ru_utime.tv_usec);
    printf("Time: %li microseconds\n", time_delta);
    free(array);
    return 0;
}

Я компилирую и измеряю время вот так: 

gcc -openmp main.c -o prog && for n in {1..10}; do ./prog; done

Проблема в том, что если я изменю количество потоков в функции до или вообще удалю директиву, ничего не изменится.

Что я делаю не так?

Вроде все правильно. (Я запускаю код на ВМ с 4 ядрами; lscpu их видит.)

1 Ответ

1 голос
/ 21 июня 2020

Ваш for l oop не может (или не должен ) быть распараллелен, потому что переменная, объявленная вне его области (tmp), изменяется внутри. В вашем случае эту конкретную проблему можно исправить, удалив текущее объявление, которое у вас есть для tmp, и поместив его в блок if: 

    if (array[j] > array[j + 1])
    {
        unsigned int tmp = array[j]; // Now a LOCAL variable (one for each loop).
        array[j] = array[j + 1];
        array[j + 1] = tmp;
        no_swap = 0;
    }

В вашем коде как это стоит, существует (высокая) вероятность гонки данных, если циклы, выполняющиеся параллельно, пытаются одновременно прочитать или записать single tmp переменную.

Однако у вас также есть похожая проблема с переменной no_swap и, что более важно, с самими данными array: если один l oop s j совпадает с другим l oop s j + 1, то попытка замена элементов вызовет гонку данных (конфликт доступа).

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

...