C ++ OpenMP Фибоначчи: 1 поток работает намного быстрее, чем 4 потока

Question

Я пытаюсь понять, почему следующее выполняется намного быстрее в 1 потоке, чем в 4 потоках в OpenMP. Следующий код на самом деле основан на похожем вопросе: Рекурсивные задачи OpenMP , но при попытке реализовать один из предложенных ответов я не получаю предполагаемое ускорение, которое предполагает, что я сделал что-то не так (и Не уверен, что это). Получают ли люди лучшую скорость при запуске ниже на 4 потока, чем на 1 поток? Я получаю 10-кратное замедление при работе на 4 ядрах (я должен получить умеренное ускорение, а не значительное замедление).

int fib(int n)
  {
    if(n == 0 || n == 1)
        return n;
    if (n < 20) //EDITED CODE TO INCLUDE CUTOFF
        return fib(n-1)+fib(n-2); 
    int res, a, b;
    #pragma omp task shared(a)
    a = fib(n-1);
    #pragma omp task shared(b)
    b = fib(n-2);
    #pragma omp taskwait
    res = a+b;
    return res;
  }

int main(){
  omp_set_nested(1);
  omp_set_num_threads(4);
  double start_time = omp_get_wtime();
  #pragma omp parallel
  {
    #pragma omp single
    {
      cout << fib(25) << endl;
    }
  }
  double time = omp_get_wtime() - start_time;
  std::cout << "Time(ms): " << time*1000 << std::endl;
  return 0;
}

Answer 1

Вы пробовали это с большим числом?

В многопоточности инициализация работы на ядрах процессора занимает некоторое время. Для небольших заданий, которые выполняются очень быстро на одном ядре, из-за этого многопоточность замедляет работу.

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

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

На этой OpenMP / Tasks вики-странице она упоминается, и предлагается ручное отключение. Должно быть две версии функции, и когда поток идет слишком глубоко, он продолжает рекурсию с помощью одного потока.

EDIT: переменная отсечки должна быть увеличена перед входом в зону OMP.

---

следующий код предназначен для целей тестирования для OP, чтобы проверить

#define CUTOFF 5
int fib_s(int n)
{
    if (n == 0 || n == 1)
        return n;
    int res, a, b;
    a = fib_s(n - 1);
    b = fib_s(n - 2);
    res = a + b;
    return res;
}
int fib_m(int n,int co)
{
    if (co >= CUTOFF) return fib_s(n);
    if (n == 0 || n == 1)
        return n;
    int res, a, b;
    co++;
#pragma omp task shared(a)
    a = fib_m(n - 1,co);
#pragma omp task shared(b)
    b = fib_m(n - 2,co);
#pragma omp taskwait
    res = a + b;
    return res;
}

int main()
{
    omp_set_nested(1);
    omp_set_num_threads(4);
    double start_time = omp_get_wtime();
#pragma omp parallel
    {
#pragma omp single
        {
            cout << fib_m(25,1) << endl;
        }
    }
    double time = omp_get_wtime() - start_time;
    std::cout << "Time(ms): " << time * 1000 << std::endl;
    return 0;
}

---

РЕЗУЛЬТАТ: При значении CUTOFF, равном 10, вычисление 45-го члена заняло менее 8 секунд.

co=1   14.5s
co=2    9.5s
co=3    6.4s
co=10   7.5s
co=15   7.0s 
co=20   8.5s
co=21 >18.0s
co=22 >40.0s