C pragma omp parallel

Question

I'm just started with OpenMP and I need help.

I have a program and I need to parallelize it. This is what I have:

#include <stdio.h>
#include <sys/time.h>
#include <omp.h>

#define N1 3000000      
#define it 5

struct timeval  t0, t1;

int i, itera_kop;

int A[N1], B[N1];

void Exe_Denbora(char * pTestu, struct timeval *pt0, struct timeval *pt1)
{
  double tej;

  tej = (pt1->tv_sec - pt0->tv_sec) + (pt1->tv_usec - pt0->tv_usec) / 1e6;
  printf("%s = %10.3f ms (%d hari)\n",pTestu, tej*1000, omp_get_max_threads());
}

void sum(char * pTestu, int *b, int n)
{
  double bat=0;
  int i;

  for (i=0; i<n; i++) bat+=b[i];
  printf ("sum: %.1f\n",bat);
}

main ()  
{
  for (itera_kop=1;itera_kop<it;itera_kop++)
  {
    for(i=0; i<N1; i++)
    {
     A[i] = 1;
     B[i] = 3;
    }
    gettimeofday(&t0, 0);
    #pragma omp parallel for private(i)
    for(i=2; i<N1; i++)
    { 
      A[i] = 35 / (7/B[i-1] + 2/A[i]);
      B[i] = B[i] / (A[i-1]+2) + 3 / B[i];
    }
    gettimeofday(&t1, 0);
    Exe_Denbora("T1",&t0,&t1);
    printf ("\n");
  } 

  printf("\n\n");
  sum("A",A,N1);
  sum("B",B,N1);

}

If I execute the code without using #pragma omp parallel for I get:

A sum: 9000005.5

B sum: 3000005.5

But if I try to parallelize the code I get:

A sum: 9000284.0

B sum: 3000036.0

using 32 threads.

I would like to know why I can't parallelize the code that way

A[i] depends on B[i-1] and B[i] depends on A[i-1] so you have a dependency of your i iteration on your i-1 iteration. Therefore, you cannot parallelize the loop as it is. Just split the loop in two with the A[i] line and the B[i] one. Then parallelize both, and that should work. — Gilles
@Gilles why don't you provide an answer you people can give you credit for it — dreamcrash

Michael Riess Michael Riess · Accepted Answer · 2017-11-15T07:48:15

As you are likely aware, your problem is in this for loop. You have dependency between the two lines in the loop.

for(i=2; i<N1; i++)
{ 
  A[i] = 35 / (7/B[i-1] + 2/A[i]);
  B[i] = B[i] / (A[i-1]+2) + 3 / B[i];
}

We cannot know the order in which any given thread reaches one of those two lines. Therefore, as an example, when the second line executes, the value in B[i] will be different depending on if A[i-1] has already been changed or not by another thread. The same can be said of A[i]'s dependency on the value of B[i-1]. A short and clear explanation of dependencies can be found at the following link. I would recommend you take a look if this still is not clear. https://scs.senecac.on.ca/~gpu621/pages/content/omp_2.html

C pragma omp parallel

1 Answers