LINUX.ORG.RU

Мне всегда казалось, что несколько потоков должны грузить все ядра процессора...

 , , ,


1

5

Всем привет.

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;
}

★★★★★

Последнее исправление: Kroz (всего исправлений: 5)
Ответ на: комментарий от Kroz

если есть на то веские аргументы

Аргумент простой: сейчас у тебя 50 строк кода и компилируешь ты его по каждому чиху и только у себя. А когда у тебя будет уже несколько тысяч строк кода, при том, что хуже, у тебе придётся кому-то дать свою программу потестировать, и у тебя не будет возможности всячески включать-выключать логи перекомпилированием, да и само перекомпилирование будет занимать не пол секукнды, а пару минут... В общем, ты тогда поймёшь что проще сам :) Но, в любом случае, говорю сразу, перекомпилияция по каждому чиху - не метод.

пс решать естессно тебе, чё уж там, наше дело предложить :)

invy ★★★★★
()
Ответ на: комментарий от invy

не пол секукнды, а пару минут...

пока пару жить ещё можно и с такой «системой». а вот когда по пол часа компилируется, тут уже хоть вешайся..

AndreyKl ★★★★★
()
Ответ на: комментарий от invy

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

На велосипеды машины не ставят катапульты как на реактивные самолеты. Сложность логов, комментариев и т. п. соответствует ТЗ: код не вырастет до тех размеров, чтобы он компилился минуты, да и давать я ему никому не буду.

И, да (с точки зрения расширения кругозора), контр-примеров не увидел.

Kroz ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.