Maciek Gaweł
Maciek Gaweł

Reputation: 27

Nested for loops in OMP C

I've got a program that multiplies 2 big numbers provided as char vectors. Now I've got to make sure it uses OpenMP. I've got problem with nested loops, if I use them the result is not what I'm expecting. I would very very appreciate your help. Here's the code

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<omp.h>
#include<time.h>
#define MAX 100000

char * multiply(char [],char[], int manyThreads);
int main(){   
    //omp_set_dynamic(1);
    omp_set_nested(1);
    omp_set_num_threads(8);
    char a[MAX];
    char b[MAX];
    char *c;    

    printf("First number : ");
    scanf("%s",a);
    printf("Second number : ");
    scanf("%s",b);
    printf("Result : ");
    double start = omp_get_wtime( );

    c = multiply(a,b,1);
    printf("%s\n",c);
    double end = omp_get_wtime( );
    printf("Calculation time = %.16g\n", end - start);

    return 0;
}

char * multiply(char a[],char b[], int manyThreads){
    static char result[MAX];
    char tempResult[MAX];
    char temp[MAX];
    int aLength,bLength;
    int i,j,k=0,x=0,y;
    long int r=0;
    long sum = 0;
    aLength=strlen(a)-1;
    bLength=strlen(b)-1;

    #pragma omp parallel if(manyThreads == 1)
    {
        #pragma omp for schedule(dynamic) nowait
        for(i=0;i<=aLength;i++) 
        {
            a[i] = a[i] - 48;
        }

        #pragma omp for schedule(dynamic) nowait
        for(i=0;i<=bLength;i++) 
        {
            b[i] = b[i] - 48;
        }
    }

    #pragma omp parallel if(manyThreads == 1) 
    {       
        #pragma omp for schedule(dynamic) 
        for(i=bLength;i>=0;i--) 
        {
             r=0;

             #pragma omp parallel
             {
               #pragma omp for schedule(dynamic)
               for(j=aLength;j>=0;j--) 
               {
                  temp[k++] = (b[i]*a[j] + r)%10;
                 r = (b[i]*a[j]+r)/10;
               }
             }
             temp[k++] = r;
             x++;
             #pragma omp parallel
             {
               #pragma omp for schedule(dynamic)            
               for(y = 0;y<x;y++)
               {
                  temp[k++] = 0;
               }    
             }                   
        }
    }  

    k=0;
    r=0;
    #pragma omp parallel if(manyThreads == 1)
    {
        #pragma omp for schedule(dynamic) 
        for(i=0;i<aLength+bLength+2;i++)
        {
             sum =0;
             y=0;
             #pragma omp parallel
             {
               #pragma omp for schedule(dynamic)
               for(j=1;j<=bLength+1;j++)
               {
                  if(i <= aLength+j)
                  {
                      sum = sum + temp[y+i];
                  }
                  y += j + aLength + 1;
               }
             }

             tempResult[k++] = (sum+r) %10;
             r = (sum+r)/10;            
        }
    }
    tempResult[k] = r;
    j=0;

    #pragma omp parallel if(manyThreads == 1)
    {
        #pragma omp for schedule(dynamic) 
        for(i=k-1;i>=0;i--)
        {
             result[j++]=tempResult[i] + 48;
        }
    }

    result[j]='\0';

    if(result[0]==48)
    {
        result[0]=255;
    }

    return result;
}

Upvotes: 0

Views: 1336

Answers (1)

alexbuisson
alexbuisson

Reputation: 8509

I can confirm, you have some data-race error.
Without OpenMP:

First number : 123456
Second number : 654321
Result :  08563613376
Calculation time = 0.005543371655221563

With OpenMP:

First number : 123456
Second number : 654321
Result :  00000000825
Calculation time = 0.007188999978097854

And I don't solve the whole problem, but based on i saw, i have some remark.
First i would say that you should specify the for variable in the for construct

#pragma omp for schedule(dynamic) nowait
        for(int i=0;i<=aLength;i++) 
        {
            a[i] = a[i] - 48;
        }

And an example of the main error you made (every time) ... when you enter a parallel region you MUST take care of your variable. what is shared, what is private to each thread ? In your end loop, you don't use nested parallelism but you do a j++in each thread so you should protect j like below.

#pragma omp parallel if(manyThreads == 1) shared(j) 
    {
        int pos;
#pragma omp for schedule(dynamic) 
        for(int i=k-1;i>=0;i--)
        {
#pragma omp atomic capture
            pos = j++;

            result[pos]=(tempResult[i] + 48);
        }
    }

Note that you also forget that OpenMP for construct has the reduction clause

so your for loop to compute sum += temp[y+i] can be rewrite with

#pragma omp for schedule(dynamic) reduction(+:sum)

And you have to follow all your algorithm logic to use sharedand privateclause on each of your surrounding and nested parallel region.

Upvotes: 2

Related Questions