Всем привет.
UPD2: добавлены реализации boost и OpenMP, почищен код, добавлены комменты в код, немного переформулировано ТЗ (суть не поменялась).
Признаюсь: первый опыт с многопоточной программой, так что прошу ногами сильно не бить.
Решил написать простую программу генерации простых чисел по методу вычеркивания. В развитии этой темы, написал 6 алгоритмов, 4 из которых многопоточные, близнецы, но используют std:thread (метод Initiate3), std:async (Initiate4), boost (Initiate5), OpenMP (Initiate6). Изначально ожидал, что многопоточные алгоритмы загрузят все ядра процессора на 100% и дадут увеличение скорости работы программы. Результаты удивили:
- Все реализации выполняются примерно за одно время (даже OpenMP).
- Многопоточные реализации не быстрее однопоточной, а иногда даже медленнее!!!
std:thread - грузит одно ядро на 100%
std:async - грузит два ядра, общая нагрузка не более 100% одного ядра.
boost - грузит одно ядро
OpenMP - грузит два ядра (суммарная нагрузка 200%), но при этом выполняется не быстрее (обогреватель воздуха помещения)!
Вопрос 1: почему Initiate3,4,5 не грузит все ядра на полную мощность?
Вопрос 2: почему Initiate6 (OpneMP) грузит все ядра, но пи этом не быстрее?
Вопрос 3: Как получить профит от многопоточности в данной конкретной задаче?
Для тех, кто решится помочь - заранее спасибо, и вот инфа в помощь:
Краткое представление алгоритма. Создается массив, элементы которого соответствует числам 3, 5, 7... (ведь четные числа не простые априори). Если соотв. число простое, то значение элемента массива 1, если не простое - 0 (для чистоты эксперимента специально заменил bool на unsigned char). Заполняет массив функция Initiate, в параметрах которой - максимальное число до которого искать. Initiate1 втупую проверяет каждое число, Initiate2 - при нахождении простого числа проходит массив вперед и убирает (помечает не-простыми) соотв. числа, Initiate3,4,5,6 - то же, но с многопоточностью. MarkNonPrime2 и MarkNonPrime3 - близнецы, но вторая предназначена для запуска в отдельном потоке. Остальное, думаю, будет понятно из кода.
Запускать так:
$ g++ -std=c++11 -lpthread -L/usr/lib -lboost_thread prime.cpp -fopenmp -O0 -o prime && time ./prime
Выбор реализации - в main() вызвать нужный метод InitiateX.
Длительность выполнения программы регулировать изменяя параметр InitiateX в main.
Собственно код (prime.cpp):
#include <iostream>
#include <iomanip>
#include <vector>
#include <thread>
#include <future>
#include <boost/thread/thread.hpp>
using namespace std;
// Maximum threads that could be spawned (except OpenMP)
#define MAX_THREAD 100
class CPrimeNumbers{
public:
vector<unsigned char> numbers; // Array starts with 3 and has a step of 2: 3, 5, 7, 9 ...
inline uint NumberToIndex(const uint number) {return (number-3)/2;}; // BUG: check whether number is < 3
inline uint IndexToNumber(const uint index) {return index*2+3;};
void MarkNonPrime2(const uint v,const uint max); // Single thread version: mark all N*v numbers (N - integer, N*v<=max) as non-prime
static void MarkNonPrime3(CPrimeNumbers *sno, const uint v,const uint max); // Multithreading version: mark all N*v numbers (N - integer, N*v<=max) as non-prime
public:
// Find all prime numbers - different realizations
void Initiate1(const uint max=6); // Simple algorithm - checking each number
void Initiate2(const uint max=6); // Marking-forward algorithm, single thread
void Initiate3(const uint max=6); // Marking-forward algorithm, multithreading using C++11, std::thread
void Initiate4(const uint max=6); // Marking-forward algorithm, multithreading using C++11, std::async
void Initiate5(const uint max=6); // Marking-forward algorithm, multithreading using Boost
void Initiate6(const uint max=6); // Marking-forward algorithm, multithreading using OpenMP
void Print(); // Outhput prime numbers found
bool IsPrime(uint number); // Check whether given number is prime
};
bool CPrimeNumbers::IsPrime(uint number)
{
uint i;
// BUG: check whether number is =0
if (number<4)
return true;
if (number%2==0)
return false;
for (i=0;i<NumberToIndex(number);i++)
if ( numbers[i]==1 && number%IndexToNumber(i) == 0 )
return false;
return true;
};
/*static*/ void CPrimeNumbers::MarkNonPrime3(CPrimeNumbers *sno, const uint v,const uint max)
{
uint n;
n=v*3;
while (n<=max) {
sno->numbers[sno->NumberToIndex(n)]=0;
n+=v*2;
}
};
void CPrimeNumbers::MarkNonPrime2(const uint v,const uint max)
{
uint n;
n=v*3;
while (n<=max) {
numbers[NumberToIndex(n)]=0;
n+=v*2;
}
};
void CPrimeNumbers::Initiate6(const uint max)
{
uint head,i;
numbers.assign(NumberToIndex(max)+1,1);
for (head=3;head<=max;head+=2) {
if ( numbers[NumberToIndex(head)]==1 ) { // Is prime/unchecked yet
if (!IsPrime(head)) { // Is not prime
numbers[NumberToIndex(head)]=0;
}
else{ // Is prime
/*********** Multithreading using OpenMP ***********/
#pragma omp parallel
{
MarkNonPrime3(this,head,max);
}
}
}
};
};
void CPrimeNumbers::Initiate5(const uint max)
{
uint head,i;
vector<boost::thread> threads;
numbers.assign(NumberToIndex(max)+1,1);
for (head=3;head<=max;head+=2) {
if ( numbers[NumberToIndex(head)]==1 ) { // Is prime/unchecked yet
if (!IsPrime(head)) { // Is not prime
numbers[NumberToIndex(head)]=0;
}
else{ // Is prime
/*********** Multithreading using Boost ***********/
if ( threads.size()==MAX_THREAD) {
threads[0].join();
threads.erase(threads.begin());
}
threads.push_back( boost::thread(MarkNonPrime3,this,head,max) );
}
}
};
for (auto t=threads.begin();t!=threads.end();t++)
t->join();
};
void CPrimeNumbers::Initiate4(const uint max)
{
uint head,i;
numbers.assign(NumberToIndex(max)+1,1);
for (head=3;head<=max;head+=2) {
if ( numbers[NumberToIndex(head)]==1 ) { // Is prime/unchecked yet
if (!IsPrime(head)) { // Is not prime
numbers[NumberToIndex(head)]=0;
}
else{ // Is prime
/*********** multithreading using C++11, std::async ***********/
async(launch::async, MarkNonPrime3,this,head,max );
}
}
};
};
void CPrimeNumbers::Initiate3(const uint max)
{
uint head,i;
vector<thread> threads;
numbers.assign(NumberToIndex(max)+1,1);
for (head=3;head<=max;head+=2) {
if ( numbers[NumberToIndex(head)]==1 ) { // Is prime/unchecked yet
if (!IsPrime(head)) { // Is not prime
numbers[NumberToIndex(head)]=0;
}
else{ // Is prime
/*********** Multithreading using C++11, std::thread ***********/
if ( threads.size()==MAX_THREAD) {
threads[0].join();
threads.erase(threads.begin());
}
threads.push_back( thread(MarkNonPrime3,this,head,max) );
}
}
};
for (auto t=threads.begin();t!=threads.end();t++)
t->join();
};
void CPrimeNumbers::Initiate2(const uint max)
{
uint head,i;
numbers.assign(NumberToIndex(max)+1,1);
for (head=3;head<=max;head+=2) {
if ( numbers[NumberToIndex(head)]==1 ) { // Is prime/unchecked yet
if (!IsPrime(head)) { // Is not prime
numbers[NumberToIndex(head)]=0;
}
else{ // Is prime
/*********** Single thread ***********/
MarkNonPrime2 (head,max);
}
}
};
};
void CPrimeNumbers::Initiate1(const uint max)
{
uint i;
uint head;
numbers.assign(NumberToIndex(max)+1,1);
for (head=3;head<=max;head+=2) {
if (! IsPrime(head) )
numbers[NumberToIndex(head)]=0;
};
};
void CPrimeNumbers::Print()
{
uint n;
n=3;
for (auto i:numbers) {
if (i) cout << n << " ";
n+=2;
}
cout << endl;
}
int main()
{
CPrimeNumbers s;
/*********** Choose the algorithm ***********/
s.Initiate1(100000);
s.Print();
return 0;
}
