LINUX.ORG.RU

Распараллеливание с помощью openmp

 , , , ,


1

5

Вообщем пытаюсь использовать Openmp, чтобы распараллелить задачу вычисления экспоненты с помощью ряда Тейлора. Программа работает, но при сравнении времени выполнения последовательного кода и с Openmp, нет прироста скорости, а даже наоборот выполняется дольше с Openmp. В чем может быть причина?

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <omp.h>
int fact(int c);
double taylor(double x, int n);
 
int main(int argc, char *argv[]) {
  double x=0;
  int n=0;
  int n_max = 32;
  if (argc != 3) {
  printf("Input three parametrs!\n");
  return 1;
}
  sscanf(argv[1], "%lf", &x);
  sscanf(argv[2], "%d", &n);

 if((n>n_max)||(n<0)) {
 printf("Invalid parameter n, enter n from 0..10\n");
 return 1;
 }
    
 int i; 
 double sum=0 ;
 double t = omp_get_wtime();
 
  #pragma omp parallel for private(i) reduction(+: sum)
   for (i=1; i<=n; i++) {
	  double taylor = pow(x,i)/fact(i);
	  sum+=taylor;
  }
  
  double diff = omp_get_wtime() - t; 
  printf("e^x = %lf\n Time: \t %lf\n", ++sum, diff);
  return 0;
}

int fact(int c) {
   int fact=1;
   int i;
   for (i = 1; i <= c; i++ ) {
      fact *=i;
   }
   return fact;
}


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

annulen ★★★★★
()

Но еще ускорить программу можно, достаточно заменить функцию fact на константный массив и прирост будет ощутимый

Silerus ★★★★
()

Факториал целиком лучше не считать, из-за переполнения плохая точность. Лучше так: 1+(1+(1+(1+(1+...)*x/4.0)*x/3.0)*x/2.0)*x

anonymous
()

Не надо так считать экспоненту, в особенности для отрицательного аргумента. «Правильный способ», гарантирующий все верные значащие цифры в рамках допустимого представления такой (псевдокод):

if (x < 0) 
  return 1/e(-x);

if (x > 1) 
  return e(x/2)^2
else
  return <формула от анонимуса: 1+(1+(1+(1+(1+...)*x/4.0)*x/3.0)*x/2.0)*x с *фиксированным* числом сомножителей -- 18 для чисел размера double>
endif

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

как то так

 const int fact[32]={1, 2, 6, 24, 120 ... };
ну и потом вызывать элемент массива по номеру факториала.
 taylor = pow(x,i)/fact[i]; 
- тем самым мы избежим многократных перевычислений и выиграем время. Кроме того совсем немного времени можно выиграть если изменить это:
  double taylor = pow(x,i)/fact[i];
  sum+=taylor;
на это:
sum+=pow(x,i)/fact[i];
но здесь на какие-то наносекунды буквально,хотя скорее всего умный компилятор - это сделает за тебя.

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

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

shonny
() автор топика

С OpenMP не знаком, но только замечу, что параллельный алгоритм совсем не значит, что будет всегда быстрее последовательного. Это надо очень постараться еще, чтобы получилось быстрее

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

я тебе пишу об общем способе ускорения вычислений, то что я убрал - это замена сложного вычисления на доступ по индексу - это огромный прирост производительности (мы выигрываем время за счет траты ресурсов памяти). На распараллеливание ты будешь всегда проигрывать в данной задаче, почему тебе описали в первом посте. Т.е распараллеливание - это не панацея, а наоборот при ненужном использовании она будет затормаживать. Вот если б ты решал задачу перемножения матриц - то там бы ты выиграл, при грамотном использовании конечно, т.к все элементы новой матрицы могут вычисляться независимо.

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

Смотря какие матрицы. Если огромные, то лучше специльными библиотеками воспользоваться, там уже все распараллелили оптимально с трюками вроде divide and conquer. Если умножать матрицы 3х3 или 4х4 - то никакой выгоды от параллелизма не будет

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

Ну почему, для омп перемножение матриц 3х3 - это их классический пример (есть в их документации), и прирост они там как раз показывают, но там же они показывают, как можно на этом же примере все испортить. Так же этот пример используют в своих видео лекцииях на коусере преподаватели Томского университета в курсе «Введение в параллельное программирование с использованием OpenMP и MPI».

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

Ну почему, для омп перемножение матриц 3х3 - это их классический пример (есть в их документации)

Где? Я не нашёл — может там не #pragma omp parallel, а #pragma omp simd ? Иначе не представляю, как многопоточная версия может быть быстрее, разве что совсем стрёмной однопоточной версии.

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

они и сравнивают, лобовое решение однопоточное, и #pragma omp parallel на главный цикл перебора


for(i = 0; i < N; i++)
    for(j = 0; j < N; j++)
    {
        C[i][j] = 0;
        for(k = 0; k < N; k++)
        C[i][j] += A[i][k] * B[k][j];
    }

#pragma omp parallel for shared(A, B, C) private(i, j, k)
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            C[i][j] = 0;
            for (k = 0; k < N; k++) {
                C[i][j] += (A[i][k] * B[k][j]);
            }
        }
    }
Silerus ★★★★
()
Ответ на: комментарий от Silerus

Нашёл такой код в этой книжке и ещё в паре мест, там везде огромные матрицы — конкретно там 4096 на 4096. Для 3x3 никакого ускорения от параллельности нет, я проверил на своей машине.

tim239 ★★
()

На всякий случай замечу, для поддержания академической беседы, что производительность параллельной программы можно загнать в нулину кривой работой с кешем. Гуглить false sharing. Как раз не плохо стреляет на всяких матрицах, СЛАУ и пр.

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

Для совсем конских неразреженных(!) матриц можно упороться алгоритмом Штрассена, который также можно положить на OpenMP.

DarkAmateur ★★★★
()
Последнее исправление: DarkAmateur (всего исправлений: 1)
Ответ на: комментарий от tim239

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

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