Найти простые числа из заданного диапазона чисел параллельная программа

Я попытался реализовать метод решета Эратосфена для поиска простых чисел.

Это мой блок кода

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<omp.h>


char isPrime[1000];     

// odd-only sieve
int eratosthenesOdd(int N, int useOpenMP)
{
        /* enable/disable OpenMP */
        omp_set_num_threads(useOpenMP ? omp_get_num_procs() : 1);

        /* instead of i*i <= N we write i <= sqr(N) to help OpenMP */
        const int NSqrt = (int)sqrt((double)N);
        int memorySize = (N-1)/2;


        int i, j;
        /* Let all numbers be prime initially */
        #pragma omp parallel for
        for (i = 0; i <= memorySize; i++){
                isPrime[i] = 1;
        }


        /* find all odd non-primes */
        #pragma omp parallel for schedule(dynamic)
        for (i = 3; i <= NSqrt; i += 2){
                if (isPrime[i/2]){
                        for (j = i*i; j <= N; j += 2*i){
                                isPrime[j/2] = 0;
                        }
                }
        }

        printf("2\n")   
        for(int k=3;k<=N;k+=2){
                if(isPrime[k/2]==1){
                        printf("%d ", k);
                }
        }

        /* sieve is complete, count primes */
        int total = N >= 2 ? 1 : 0;
        #pragma omp parallel for reduction(+:total)
        for (i = 1; i <= memorySize; i++){
                total += isPrime[i];
        }

        return total;
}

int main()
{
        double start, finish;
        start =  omp_get_wtime();
        int total = eratosthenesOdd(100, 1);
        finish = omp_get_wtime();
        printf("\n %d", total);
        printf("\n Elapsed time=%e seconds", finish-start);
        return 0;
}

Я получил ссылку от здесь. Код работает хорошо, и я могу найти, сколько простых чисел находится в заданном диапазоне.

Я скептически отношусь к прошедшему времени, которое я получил после нескольких испытаний с одинаковым количеством сроков.

Предположим, я хочу увидеть простые числа от 1 до 100. Я также хочу узнать прошедшее время для различных потоков.

1st trial
N=100
Number of Thread  1, elapsed time = 5.008094e-04
Number of Thread  8, elapsed time = 4.649349e-04
Number of Thread 16, elapsed time = 4.652534e-04

2nd trial
N=100
Number of Thread  1, elapsed time = 4.668552e-04sec
Number of Thread  8, elapsed time = 5.837623e-04sec
Number of Thread 16, elapsed time = 5.835127e-04sec

 3rd trial
 N=100
Number of Thread  1, elapsed time = 4.530195e-04 sec
Number of Thread  8, elapsed time = 4.66317e-04sec
Number of Thread 16, elapsed time = 6.141420e-04 sec

Интересно, эта программа действительно реализует параллельную программу? Если да, то как я могу получить эту вариацию во времени? Кроме того, когда задача делится между потоками, время должно уменьшаться по сравнению с последовательным временем. Но здесь этого не произошло.

Вы можете просмотреть массив isPrime после завершения сита; если isPrime[i] — это 1, то i — простое число. Переберите любой диапазон в пределах массива, чтобы получить список простых чисел.

Jonathan Leffler 09.04.2022 20:20

Обратите внимание, что у вас есть гонка данных при доступе к isPrime и j. Я предлагаю вам прочитать достойную книгу об OpenMP и всегда определять ваши переменные в минимально необходимой области видимости. Я также предлагаю вам использовать предложение default(none), поэтому вы должны явно определить общие атрибуты ваших переменных.

Laci 09.04.2022 20:22
const int NSqrt = (int)sqrt((double)N); склонен к проблемам, когда sqrt(N) возвращает xxx.999999999999, а не ожидаемое xxx.0. const int NSqrt = lround(sqrt((double)N)); лучше.
chux - Reinstate Monica 09.04.2022 22:13

@JonathanLeffler Я изменил блок кода в соответствии с вашим предложением. Я считаю, что я не правильно понял ваш комментарий, так что я получил результат, который представляет собой миксер простого и не простого числа. Не могли бы вы объяснить мне, как я могу получить правильный вывод.

Encipher 09.04.2022 23:02

@chux-ReinstateMonica В блоке кода есть и другие проблемы, не могли бы вы отредактировать его? Спасибо.

Encipher 09.04.2022 23:03

@Encipher Лучше всего, чтобы автор вопроса отредактировал вопрос.

chux - Reinstate Monica 09.04.2022 23:05

Когда операция сита завершена, каждый элемент массива isPrime должен содержать либо 0, что указывает на то, что индекс является составным числом, либо 1, что указывает на то, что индекс является простым числом. Следовательно, цикл по строкам for (int i = 2; i < 1000; i++) { if (isPrime[i]) printf("%d\n", i); } должен печатать простые числа, по одному в строке. Если на выходе появляются составные числа, в вашем алгоритме сита есть ошибка, возможно, вызванная гонками данных. Если запустить однопоточный, вы должны получить правильный вывод. Если вы запустите его в многопоточном режиме и получите другой ответ, это ошибка.

Jonathan Leffler 09.04.2022 23:30

Я пропустил, что код оптимизирует хранилище, индексируя по i/2. Он знает, что 2 простое, а все остальные четные числа составные. Тип данных char для уменьшения использования памяти (вероятно, в 4 раза) по сравнению с использованием int. Вы можете пойти дальше и использовать массив битов — это позволяет вам иметь дело с в 8 раз большим количеством значений в том же пространстве памяти, что и массив char.

Jonathan Leffler 10.04.2022 00:17

Как я уже упоминал, у вас есть гонки данных. Чтобы исправить это, вам просто нужно сделать то же самое, что обсуждалось в ваших прошлых 2-3 вопросах о нахождении простых чисел. Например. этот код (3-я версия) подходит с точки зрения OpenMP. Обратите внимание на разницу: он содержит атомарные операции чтения/записи, и вы использовали for (int i = ...) вместо for (j = ...) (вы объявили переменную внутри параллельного региона, что делает ее частной переменной)

Laci 10.04.2022 08:24

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

Encipher 10.04.2022 08:30

Пока ваш код дает неверные результаты и имеет неопределенное поведение, вам не стоит беспокоиться о его скорости. Обратите внимание, что если N=1000000 вы увидите ускорение, если N=100 вам вообще не нужно ускорение. В последнем случае параллельные накладные расходы намного превышают выигрыш от распараллеливания.

Laci 10.04.2022 08:51
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
0
11
65
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

У меня не установлено программное обеспечение OMP, поэтому мне пришлось удалить распараллеливание. Однако код работает после того, как цикл «распечатать простые числа» настроен на то, что алгоритм знает, что 2 — единственное четное простое число, и что он сохраняет простоту нечетного числа X в isPrime[X / 2].

Это приводит к этому коду:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//#include <omp.h>

static char isPrime[1000];

// odd-only sieve
//static int eratosthenesOdd(int N, int useOpenMP)
static int eratosthenesOdd(int N)
{
    /* enable/disable OpenMP */
    //omp_set_num_threads(useOpenMP ? omp_get_num_procs() : 1);

    /* instead of i*i <= N we write i <= sqr(N) to help OpenMP */
    const int NSqrt = (int)sqrt((double)N);
    int memorySize = (N - 1) / 2;

    int i, j;
    /* Let all numbers be prime initially */
    //#pragma omp parallel for
    for (i = 0; i <= memorySize; i++)
    {
        isPrime[i] = 1;
    }


    /* find all odd non-primes */
    //#pragma omp parallel for schedule(dynamic)
    for (i = 3; i <= NSqrt; i += 2)
    {
        if (isPrime[i / 2])
        {
            for (j = i * i; j <= N; j += 2 * i)
            {
                isPrime[j / 2] = 0;
            }
        }
    }


    printf("2\n");
    for (int k = 3; k <= N; k += 2)
    {
        if (isPrime[k / 2] == 1)
        {
            printf("%d\n", k);
        }
    }

    /* sieve is complete, count primes */
    int total = N >= 2 ? 1 : 0;
    //#pragma omp parallel for reduction(+:total)
    for (i = 1; i <= memorySize; i++)
    {
        total += isPrime[i];
    }

    return total;
}

int main(void)
{
    //int total = eratosthenesOdd(100, 1);
    int total = eratosthenesOdd(100);
    printf("Number of primes: %d\n", total);
    return 0;
}

И этот вывод:

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
Number of primes: 25

Судя по проверке, это правильно для простых чисел до 100.

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

Encipher 10.04.2022 06:09

Добавление параллелизма не обязательно ускоряет процесс. Это зависит от затрат на синхронизацию и преимуществ параллельной работы.

Jonathan Leffler 10.04.2022 06:43

Но не странно ли, что одно и то же количество терминов с одинаковым количеством потоков показывает разные результаты в разных трейлах.

Encipher 10.04.2022 06:50

Это зависит от того, как код OMP синхронизирует и распараллеливает вещи. Решето Эратосфена (по крайней мере, в наивных реализациях) предполагает, что пока оно обрабатывает простое число P, все меньшие простые числа уже идентифицированы, а их (нечетные) кратные помечены как непростые (составные). Поэтому не совсем ясно, что параллелизм может купить вам какое-то ускорение. И если это предположение нарушается, вы можете легко получить неверные результаты. Обеспечивает ли синхронизация OMP это предположение?

Jonathan Leffler 10.04.2022 06:53

@Encipher - вам может понравиться этот инструмент с живым графическим интерфейсом desmos.com/calculator/zfrrlfeiji, чтобы увидеть, сколько мы можем заплатить, чтобы не потерять больше, чем получить от параллельного выполнения кода. Другими словами, для крошечных проблем (не так много для обработки) дополнительные накладные расходы на параллельное выполнение кода могут (и часто становятся) расти намного больше, чем ожидаемое (теоретическое + принципиально ограниченное) ускорение. Если кто-то платит намного больше, чем получает обратно, такие инвестиции были чистой потерей. Также никогда не тестируйте на весах ниже 1E9, если вы пытаетесь действительно опираться на неопровержимые факты, а не на шум и совпадения.

user3666197 10.04.2022 15:18

Другие вопросы по теме