Вычислить алгоритм Пи из учебника с использованием OpenMP - PullRequest
Новая
       8

Вычислить алгоритм Пи из учебника с использованием OpenMP

0 голосов
/ 11 ноября 2018

Я изучаю это руководство по OpenMP, и я наткнулся на это упражнение на странице 19. Это алгоритм вычисления числа Пи, который я должен распараллелить: 

static long num_steps = 100000;
double step;
void main ()
{
  int i;
  double x, pi
  double sum = 0.0;
  step = 1.0 / (double)num_steps;

  for(i = 0; i < num_steps; i++)
  {
     x = (I + 0.5) * step;
     sum = sum + 4.0 / (1.0 + x*x);
  }

  pi = step * sum;
}

Я не могу использовать, до этого момента, параллельную для #pragma. Я могу использовать только: 

#pragma omp parallel {}
omp_get_thread_num();
omp_set_num_threads(int);
omp_get_num_threads();

Моя реализация выглядит так: 

#define NUM_STEPS 800

int main(int argc, char **argv)
{
   int num_steps = NUM_STEPS;
   int i;
  double x;
  double pi;
  double step = 1.0 / (double)num_steps;

  double sum[num_steps];

  for(i = 0; i < num_steps; i++)
  {
      sum[i] = 0;
  }

  omp_set_num_threads(num_steps);
  #pragma omp parallel
  {
    x = (omp_get_thread_num() + 0.5) * step;
    sum[omp_get_thread_num()] += 4.0 / (1.0 + x * x);
  }

  double totalSum = 0;

  for(i = 0; i < num_steps; i++)
  {
    totalSum += sum[i];
  }

  pi = step * totalSum;

  printf("Pi: %.5f", pi);
}

Игнорирование проблемы с использованием массива суммы (позже объясняется, что необходимо определить критический раздел для значения суммы с помощью #pragma omp критического или #pragma omp atomic), вышеупомянутое импелентация работает только для ограниченного числа потоков (800 в моем случае), где последовательный код использует 100000 шагов. Есть ли способ достичь этого только с помощью вышеупомянутых команд OpenMP, или я обязан использовать параллельный для #pragma omp, который еще не был упомянут в учебнике?

Большое спасибо за ваше время, я действительно пытаюсь понять концепцию распараллеливания в C с использованием OpenMP.

1 Ответ

0 голосов
/ 11 ноября 2018

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

Самый простой способ - сделать что-то вроде: 

int tid = omp_get_thread_num();
int n_threads = omp_get_num_threads();

for (int i = tid; i < num_steps; i += n_threads) {
    // ...
}

Таким образом, работа распределяется по всем потокам независимо от количества потоков.

Если было 3 темы и 9 шагов:

  • Поток 0 будет выполнять шаги 0, 3, 6
  • Поток 1 будет выполнять шаги 1, 4, 7
  • Поток 2 будет выполнять шаги 2, 5, 8

Это работает, но не идеально, если каждый поток обращается к данным из некоторого общего массива. Лучше, если потоки обращаются к разделам данных поблизости для locality целей.

В этом случае вы можете разделить количество шагов на количество потоков и дать каждому потоку непрерывный набор задач, например: 

int tid = omp_get_thread_num();
int n_threads = omp_get_num_threads();

int steps_per_thread = num_steps / n_threads;
int start = tid * steps_per_thread;
int end = start + steps_per_thread;

for (int i = start; i < end; i++) {
    // ...
}

Теперь 3 потока, выполняющие 9 шагов, выглядят так:

  • Тема 0 выполняет шаги 0, 1, 2
  • Тема 1 выполняет шаги 3, 4, 5
  • Нить 2 выполняет шаги 6, 7, 8

Этот подход на самом деле наиболее вероятен при использовании #pragma omp for. В большинстве случаев компилятор просто делит задачи в соответствии с количеством потоков и назначает каждому потоку раздел.

Таким образом, учитывая набор из 2 потоков и 100 итераций для цикла, компилятор, скорее всего, даст итерации 0-49 для потока 0 и итерации 50-99 для потока 1.

Обратите внимание, что если число итераций не делится поровну на количество потоков, остаток необходимо обработать явно.

...