openmp shared array

General OpenMP discussion

openmp shared array

Postby puwkin » Tue Apr 02, 2013 11:43 pm

i have two nasted for(s) that work with shared arrays and shared boolean flag, i know that it might be a collisions while trying to write into array but if i make thoose sections critical i will lose all benefits of paralleling this. Is there any options how can i avoid this and still work in parallel? thanks

Code: Select all
#pragma omp parallel
{
#pragma omp for schedule (guided)
            for(int i=0;i<N-1;i++)
            {
                for(int j=i+1;j<N;j++)
                {
                    if(cluster[i*N+j]!=0)
                    {
                        inner_set[i]=1;// Critical???
                        inner_set[j]=1;
                    }
                    else
                    {
                        outter_set[i]=1;
                    }
                }
            }
}

do
{
    isChanged=false;
#pragma omp parallel for schedule (guided)     
            for(int i=0; i<N; i++)
            {
                if(inner_set[i]!=0)
                {
                    for (int j=0; j<N;j++)
                    {
                        if(i!=j && outter_set[j]!=0)
                        {
                            if(dis[i*N+j]<Dis)
                            {
                                isChanged=true;
                                inner_set[i]=0;//critical???
                                outter_set[i]=1;
                            }
                        }

                    }
                }


        }
}while(isChanged);
puwkin
 
Posts: 1
Joined: Tue Apr 02, 2013 11:04 pm

Re: openmp shared array

Postby MarkB » Wed Apr 03, 2013 4:25 am

Hi there,

Let's consider the first loop to begin with. There are two possible techniques you could use: atomic writes or an array reduction.
Which is faster will depend on the OpenMP implementation, and on the frequency with which the if test succeeds.

The atomic write version is simple to implement (though it requires a 3.1 compliant compiler). This is better that critical because the OpenMP implementation
can update different elements of the array at the same time.

Code: Select all
#pragma omp for schedule (guided)
            for(int i=0;i<N-1;i++)
            {
                for(int j=i+1;j<N;j++)
                {
                    if(cluster[i*N+j]!=0)
                    {
#pragma omp atomic write
                        inner_set[i]=1;
#pragma omp atomic write
                        inner_set[j]=1;
                    }
                    else
                    {
                        outter_set[i]=1;
                    }
                }
            }


The array reduction version is a bit messier and requires a temporary array of size N * no. of threads:

Code: Select all
#pragma omp parallel private(myid, nthreads)
{
      myid = omp_get_thread_num();
      nthreads= omp_get_num_threads();
      for(int i=0;i<N;i++) {
          inner_set_tmp[myid][i]=0;
      }

#pragma omp for schedule (guided)
            for(int i=0;i<N-1;i++)
            {
                for(int j=i+1;j<N;j++)
                {
                    if(cluster[i*N+j]!=0)
                    {
                        inner_set_tmp[myid][i]=1;
                        inner_set_tmp[myid][j]=1;
                    }
                    else
                    {
                        outter_set[i]=1;
                    }
                }
            }
#pragma omp for
            for(int i=0;i<N;i++) {
                 for (int id=0; id<nthreads; id++) {
                       inner_set[i] |= inner_set_tmp[id][i];
                 {
            }
}


In the second loop, I'm having a bit of trouble convincing myself that the result is independent of the order in which the i loop is executed, since a write
to outter_set[i] can affect the outcome of the test outter_set[j]!=0 for later i iterations. Assuming this doesn't matter:

There are no possible races on inner_set, since it is only ever indexed by the parallel loop iterator.
The possible collisions are between the reads and writes of outter_set. The shared flag can be handled with a reduction clause.
We can use atomics:

Code: Select all
#pragma omp parallel for schedule (guided)  reduction(|:isChanged) private (tmp)
            for(int i=0; i<N; i++)
            {
                if(inner_set[i]!=0)
                {
                    for (int j=0; j<N;j++)
                    {
#pragma omp atomic read
                        tmp = outter_set[j];
                        if(i!=j && tmp!=0)
                        {
                            if(dis[i*N+j]<Dis)
                            {
                                isChanged=true;
                                inner_set[i]=0;
#pragma omp atomic write
                                outter_set[i]=1;
                            }
                        }

                    }
                }


        }


Another option might be to use a temporary copy of outter_set. Do you get the right result if you do this?:

Code: Select all
#pragma omp parallel
{
#pragma omp for schedule (guided)  reduction(|:isChanged) 
            for(int i=0; i<N; i++)
            {
                if(inner_set[i]!=0)
                {
                    for (int j=0; j<N;j++)
                    {
                        if(i!=j && outter_set[j]!=0)
                        {
                            if(dis[i*N+j]<Dis)
                            {
                                isChanged=true;
                                inner_set[i]=0;
                                outter_set_tmp[i]=1;
                            }
                        }

                    }
                }


        }

#pragma omp for
            for(int i=0; i<N; i++) {
                outter_set[i] = outter_set_tmp[i];
            }

}


Hope this helps: please forgive any coding errors, but I hope you get the ideas!

Mark.
MarkB
 
Posts: 428
Joined: Thu Jan 08, 2009 10:12 am


Return to Using OpenMP

Who is online

Users browsing this forum: Google [Bot] and 12 guests