Page 1 of 1

omp parallel for loop, on map stl c++

PostPosted: Tue Oct 30, 2018 12:20 am
by open_coder
i am trying to apply parallel weight updation in dijsktra algorithms, when a node is choosen as min, update its all neighbours weight in parallel.

But with increasing threads cause increase in execution time, instead of decrease in execution time.
what is wrong in my code ?

##############################################################################################

omp_set_num_threads(2);
#pragma omp parallel private (my_first, my_last, i) shared(size, nth, my_id)
{
my_id = omp_get_thread_num();
nth = omp_get_num_threads();
size = ptr.size();

my_first = my_id*size / nth;
my_last = (my_id+1)*size / nth - 1;

#pragma omp critical
{
for(i=my_first; i<= my_last; i++){
p = ptr.begin();
advance(p,i);
if (mind[p->first] > md + p->second){
mind[p->first] = md + p->second;
Q.push(make_pair(mind[p->first], p->first) );
}
}
}

Re: omp parallel for loop, on map stl c++

PostPosted: Tue Oct 30, 2018 3:28 am
by MarkB
Almost all the work is inside the critical section, which only one thread at a time will execute, so you won't see any speedup.
What are you using the measure the execution time?

Re: omp parallel for loop, on map stl c++

PostPosted: Tue Oct 30, 2018 5:25 am
by open_coder
I am using "time" linux command to measure execution time of my program.

Re: omp parallel for loop, on map stl c++

PostPosted: Tue Oct 30, 2018 5:56 am
by open_coder
Could any one suggest me how i can update map in parallel to speedup execution of my algorithm.

Re: omp parallel for loop, on map stl c++

PostPosted: Wed Nov 07, 2018 12:30 pm
by Oldboy
Take a look at this code:
http://people.sc.fsu.edu/~jburkardt/c_s ... a_openmp.c
It is very hard to win anything with few nodes (in this case 6).
Even with 60 nodes the open mp effect is small.

Re: omp parallel for loop, on map stl c++

PostPosted: Tue Nov 13, 2018 12:15 am
by open_coder
Can i do implement distributed heap in Dijkstra algorithms to speed up in find min element among all nodes.