OpenMP базовое распараллеливание

Question

Я застрял в написании некоторого параллельного кода c с использованием OpenMP для курса параллелизма.

Вот фрагмент

#include <stdio.h>
#include <time.h>
#include <math.h>

#define FALSE 0
#define TRUE 1

int count_primes_0(int);
int count_primes_1(int);
int count_primes_2(int);

int main(int argc, char *argv[]){
    int n;

    if (argc != 2){
        printf("Incorrect Invocation, use: \nq1 N");
        return 0;
    } else {
        n = atoi(argv[1]);  
    }

    if (n < 0){
        printf("N cannot be negative");
        return 0;
    }

    printf("N = %d\n", n);

    //omp_set_num_threads(1);
    time_it(count_primes_0, n, "Method 0");
    time_it(count_primes_1, n, "Method 1");
    time_it(count_primes_2, n, "Method 2");

    return 0;
}

int is_prime(int n){
    for(int i = 2; i <= (int)(sqrt((double) n)); i++){
        if ((n % i) == 0){
            return FALSE;
        }
    }

    return n > 1;
}

void time_it( int (*f)(int), int n, char *string){
    clock_t start_clock;
    clock_t end_clock;
    double calc_time;
    int nprimes;

    struct timeval start_val;
    struct timeval end_val;

    start_clock = clock();
    nprimes = (*f)(n);
    end_clock = clock();
    calc_time = ((double)end_clock - (double)start_clock) / CLOCKS_PER_SEC;
    printf("\tNumber of primes: %d \t Time taken: %fs\n\n", nprimes, calc_time);
}

// METHOD 0
// Base Case no parallelization
int count_primes_0(int n){
    int nprimes = 0;

    for(int i = 1; i <= n; i++){
        if (is_prime(i)) {
            nprimes++;
        }
    }

    return nprimes;
}

//METHOD 1
// Use only For and Critical Constructs
int count_primes_1(int n){
    int nprimes = 0;

    #pragma omp parallel for
    for(int i = 1; i <= n; i++){
        if (is_prime(i)) {
            #pragma omp critical
            nprimes++;
        }
    }

    return nprimes;
}

//METHOD 2
// Use Reduction
int count_primes_2(int n){
    int nprimes = 0;

    #pragma omp parallel for reduction(+:nprimes)
    for(int i = 1; i <= n; i++){
        if (is_prime(i)) {
           nprimes++;
        }
    }

    return nprimes;
}

Проблема, с которой я сталкиваюсь, заключается в том, что когда я использую omp_set_num_threads(), чем меньше потоков я использую, тем быстрее выполняются мои функции - или становится ближе к времени выполнения базового непараллельного случая

Результаты по времени: они запускаются на 8-ядерном компьютере

8 потоков: метод 0: 0,07 с; Метод 1: 1,63 с; Метод 2: 1.4 с

4 потока: метод 0: 0,07 с; Метод 1: 0,16 с; Метод 2: 0,16 с

2 потока: метод 0: 0,07 с; Метод 1: 0,10; Метод 2: 0,09

1 поток: метод 0: 0,07 с; Метод 1: 0,08 с; Метод 2: 0,07 с

Я попытался отключить оптимизацию и использовать другую версию GCC без разницы

Любая помощь приветствуется.

РЕДАКТИРОВАТЬ: использование часов в Linux возвращает "неправильное" время, настенные часы - это то, что мне нужно, поэтому использование ether omp_get_wtime() или функции Linux timeit даст правильные результаты.

Answer 1

Я удивлен, что вы видели какой-либо успех с программой, как это указано выше. Если вы посмотрите на справочную страницу RedHat Linux для clock (), вы увидите, что она "возвращает приблизительное время процессора, используемое программой". Добавление директив OpenMP приводит к дополнительным издержкам, и, следовательно, вы должны видеть больше общего процессорного времени, используемого при запуске OpenMP. То, на что вам нужно обратить внимание - это время истечения (или время настенных часов). Когда вы работаете параллельно (и у вас есть программа, которая может извлечь выгоду из параллели), вы увидите, что время истечения уменьшается. Спецификация OpenMP определяет подпрограмму (omp_get_wtime()) для предоставления этой информации.

Изменение вашей программы для создания отчетов с использованием clock () и omp_get_wtime():

1000000 долларов США (1 000 000)

2 процессора:

часы (): 0,23 времени (): 0,23 времени (): 0,96 времени (): 0,16 часов (): 0,59 времени (): 0,09

4 процессора:

часы (): 0,24 времени (): 0,24 часов (): 0,97 времени (): 0,16 часов (): 0,57 времени (): 0,09

8 процессоров:

часы (): 0,24 времени (): 0,24 часов (): 2,60 времени (): 0,26 часов (): 0,64 времени (): 0,09

$ 10000000 (10 000 000)

2 процессора:

часы (): 6,07 времени (): 6,07 часов (): 10,4 времени (): 1,78 часов (): 11,3 времени (): 1,65

4 процессора:

часы (): 6,07 времени (): 6,07 часов (): 11,5 времени (): 1,71 часов (): 10,7 времени (): 1,72

8 процессоров:

часы (): 6,07 времени (): 6,07 часов (): 9,92 времени (): 1,83 часов (): 11,9 времени (): 1,86

Answer 2

OpenMP не распараллеливает циклы с вызовами функций внутри него, если аргументы не являются частными. Решение было бы встроить is_prime() в вашей петле.