## 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

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

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

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: 675
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

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

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

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: 675
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

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

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

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: 675
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh