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 даст правильные результаты.

Answer 1

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

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

$ a.out 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

$ a.out 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() в ваш цикл.