openmp problem to parallelize a cycle in which there are cha

General OpenMP discussion

openmp problem to parallelize a cycle in which there are cha

Postby nivaldo » Sat May 11, 2013 11:39 am

hello, I am a student of engineering in computer information sciences and for some days I'm trying to figure out how to parallelize this code, maybe someone can help me

// n is the number of nodes of a graph
// calculateValue returns a node weight
// all values ​​of variables and arrays are positive integers



array= new int[n+1];
array[n]=0;
for(int i=n-1 ; i>=0 ; i--)
{

array[i]=calculateValue(i)+array[i+1];


}
nivaldo
 
Posts: 5
Joined: Fri May 10, 2013 1:20 am

Re: openmp problem to parallelize a cycle in which there are

Postby hjnln » Sun May 12, 2013 11:09 pm

try this !!

array= new int[n+1];
array[n]=0;
#pragma omp parallel for num_threads(the number of core)
for(int i=n-1 ; i>=0 ; i--)
{

array[i]=calculateValue(i)+array[i+1];


}
hjnln
 
Posts: 5
Joined: Sun May 12, 2013 10:11 pm

Re: openmp problem to parallelize a cycle in which there are

Postby MarkB » Mon May 13, 2013 2:16 am

nivaldo wrote:hello, I am a student of engineering in computer information sciences and for some days I'm trying to figure out how to parallelize this code, maybe someone can help me


Please don't post generic requests for people to do your homework assignment for you on this forum. If you make a genuine attempt, and have a specific question to ask, then that's fine!

hjnln wrote:try this !!

array= new int[n+1];
array[n]=0;
#pragma omp parallel for num_threads(the number of core)
for(int i=n-1 ; i>=0 ; i--)
{

array[i]=calculateValue(i)+array[i+1];


}


That doesn't work, due to the dependency on array[]!
MarkB
 
Posts: 428
Joined: Thu Jan 08, 2009 10:12 am

Re: openmp problem to parallelize a cycle in which there are

Postby nivaldo » Mon May 13, 2013 1:05 pm

sorry, I'm learning OpenMP on my own, and wanted to see an example.
nivaldo
 
Posts: 5
Joined: Fri May 10, 2013 1:20 am

Re: openmp problem to parallelize a cycle in which there are

Postby MarkB » Tue May 14, 2013 2:35 am

nivaldo wrote:sorry, I'm learning OpenMP on my own, and wanted to see an example.


There's no way to do this directly without modifying the code. A simple solution would be to split the loop into two, the first loop calling calculateValue() and storing the results in a temporary array, and a second loop using these values to compute array[]. The first loop can then be parallelised easily with a #pragma omp parallel for directive. The second loop has to remain sequential. This would be a reasonable solution if calculateValue() is expensive and n is not too large. A more sophisticated solution would be to implement a parallel prefix sum algorithm.
MarkB
 
Posts: 428
Joined: Thu Jan 08, 2009 10:12 am

Re: openmp problem to parallelize a cycle in which there are

Postby nivaldo » Tue May 14, 2013 6:22 am

Thanks for the help, I'm new to openmp and at my university do not know anyone who can parallel programming. I'm working on an application that identifies the faces of a figure from a 2D sketch to take to 3d. The identification algorithm that implements faces a maximum weight clique but the execution time of some cases is very large. So I want to parallelize the code using openmp, and I have a part of code that is similar to that cycle, when using openmp considerably low time, but since there is no data dependency executes the code correctly. I was reading about the prefix sum algorithm, but do not really understand, you believe that with this algorithm can lower the execution time of this cycle although n is a value big enough?
nivaldo
 
Posts: 5
Joined: Fri May 10, 2013 1:20 am

Re: openmp problem to parallelize a cycle in which there are

Postby MarkB » Tue May 14, 2013 8:53 am

For sufficiently large N, the parallel prefix algorithm will be faster that the sequential version. The benefit of parallelism has to outweigh the overheads of starting a parallel region and synchronising the threads: a very rough estimate suggests that sufficiently large probably means N > 10^6 for a typical OpenMP implementation.
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 8 guests