Как на C++ выполнить параллельные математические вычисления?

Question

[Максим Иванов]

У меня есть числа от 1 до 18446744073709551615. И для каждого числа вычисляется остаток от деления. Но вычисления получаются бесконечными, мне сказали, что нужно делать в несколько потоков и тогда будет все параллельно, но я не понимаю как это.

Получение простого числа 100%. Первые 500 простых чисел по таблице прогонял, ответ тоже 100%. Исходя из готовых алгоритмов (так как вероятностные использовать нельзя).

#include <iostream>
#include <biginteger.cpp>
using namespace std;

int main(int argc, char *argv[]) {
    char *text = "274876858367";
    BigInteger n(text), k, q;

    if (n % 2 == 0 || n == 1) {
        cout << "число не является простым" << endl;
        return 0;
    }

    q = n.sqrt() + 1;

    BigInteger m;
    bool prm = true;

    // простые делители
    // начинаются с тройки

    for(k = 3; k <= q; ) {

        // все четные делители и все делители,
        // кратные простым числам, могут быть опущены
        if ((k % 2 == 0) || (k % 3 == 0)) { k++; continue; }

        //m = n%k;
        //cout << "n = " << n << " k = " << k << ", n % k = " << m <<endl;

        if (n % k == 0) {
            prm = false;
            break;
        }

        k++;
    }

    if (prm) cout << "число является простым" << endl;
    else cout << "число не является простым" << endl;

    return 0;
}

Можете привести примеры, пожалуйста?

Comments

[Vitaliy]

В принципе параллельные вычисления делаются на gpu (cuda,opencl)

[Максим Иванов]

а программно? типо fork

[Максим Мосейчук]

splincodewd: проще тогда OpenMP использовать. Если коротко - пишете такой же цикл, только снабдив его директивами. А компилятор распределит всё между потоками.

[MiiNiPaa]

А если OpenMP по какой-то непонятной причине использовать не получается, тогда С++11 и std::thread/std::async. Хотя это для вашего случая похоже на закат солнца вручную.

Answer 1

[Максим Мосейчук]

OpenMP

#include <iostream>

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

	#pragma omp parallel for
	for (size_t i = 0; i < 1000000; ++i)
	{
		std::cout << i << std::endl;
	}
}

Конкретно этот пример работает медленнее на нескольких потоках из-за синхронизации ввода-вывода. Для эффективного использования результат нужно накапливать в памяти, затем выводить.

Comments

[Максим Иванов]

то есть вся суть в #pragma omp parallel for ?

[Максим Мосейчук]

splincodewd: и флаги компилятору передать соответствующие. Для g++ это -fopenmp

[Максим Иванов]

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

[Максим Мосейчук]

splincodewd: Я же говорю, ввод-вывод нежелательно использовать внутри цикла.

[Максим Иванов]

ввод-вывод не использую, а как его подрубить этот Open MP, флаг только передать?

[Максим Иванов]

я вот прописал в pro файле флаг, но не уверен, что правильно, просто считает также долго

.pro
TEMPLATE = app
CONFIG += console c++11
CONFIG -= app_bundle
CONFIG -= qt

SOURCES += main.cpp \
biginteger.cpp

HEADERS += \
biginteger.h

QMAKE_CXXFLAGS += -fopenmp

[Максим Иванов]

вот, теперь OpenMP ругается, на break и на

: ошибка: missing increment expression
for(k = 3; k <= q; ){
^

: ошибка: break statement used with OpenMP for loop
break;
^

[Максим Мосейчук]

splincodewd: цикл for должен быть представлен в каконичном виде, со всеми параметрами, что бы OpenMP смог разбить его.

[Максим Иванов]

но у меня его параметры совсем другого типа данных, BigInteger

[Максим Иванов]

а есть что-нибудь другое кроме как omp?

[Максим Мосейчук]

splincodewd: Cuda, OpenCL. Но там довольно примитивные типы, всякие BigInteger придётся городить самому.

[Максим Мосейчук]

splincodewd: вы бы показали код, мы бы помогли. А гадать на кофейной гуще, где у вас проблема я не умею.

[Максим Мосейчук]

splincodewd: если c++ не критично, то можете глянуть на Haskell. Там и biginteger встроенный есть, и parMap (параллельный map)

[Максим Иванов]

задача немного модифицирована, но смысл тот же, там слишком много вычислений, а нужно как-то моментально получать ответ

[Максим Мосейчук]

splincodewd: Как вы хотите получить моментально ответ, если на проверку одного большого числа уйдет часы вычислений?

[Максим Иванов]

В том и дело, что мой алгоритм видимо очень ужасен, и я не знаю как правильно поступить, вот я и думал, что можно как-то распараллелить вычисления?

[AtomKrieg]

splincodewd: в таблицу сохранить нужные значения. Как вы ещё моментально миллиард чисел переберете?

[Максим Иванов]

в таблицу? то есть базу иметь специальную?

[Максим Мосейчук]

splincodewd: вы ему ответьте, иначе ему не придет уведомление.

[Максим Иванов]

AtomKrieg: ps: в таблицу? то есть базу иметь специальную?

[AtomKrieg]

splincodewd: все равно что

Answer 2

[Alexander Movchan]

Способов распаралелить много, но хочу заметить, что ваши вычисления получаются бесконечными отчасти благодаря следующей строке:
cout << sqrt(n) << endl;
А именно, из-за endl. После каждого вычисления вы зачем-то сбрасываете поток вместо того, чтоб просто вывести символ перевода на новую строку '\n'.

P.S. В С пишите math.h, а в C++ - cmath. И зачем вы используете while вместо for?

#include <cstdint>
...
for (uint64_t i = 0; i < UINT64_MAX; ++i)

P.P.S. Вот пример на чистом C++. Не забудьте подключить библиотеку pthread.

Код

#include <iostream>
#include <sstream>
#include <string>
#include <thread>
#include <mutex>
#include <chrono>
#include <cmath>
#include <cstdint>


using namespace std;


mutex ios_mutex;


void compute(int b, int e)
{
    stringstream buffer;
    for (uint64_t i = b; i < e; ++i)
    {
        buffer << sqrt(i) << '\n';
    }

    ios_mutex.lock();
    cout << buffer.str();
    ios_mutex.unlock();
}


int main(int argc, char** argv)
{
    thread t0(compute,   0,  99);
    thread t1(compute, 100, 199);
    thread t2(compute, 200, 299);
    thread t3(compute, 300, 399);
    thread t4(compute, 400, 499);
    thread t5(compute, 500, 599);
    thread t6(compute, 600, 699);
    thread t7(compute, 700, 799);

    t0.join();
    t1.join();
    t2.join();
    t3.join();
    t4.join();
    t5.join();
    t6.join();
    t7.join();

    return 0;
}

Comments

[Максим Иванов]

задача немного модифицирована, но смысл тот же, там слишком много вычислений, а нужно как-то моментально получать ответ