Speed down problem

General OpenMP discussion

Speed down problem

Postby misuzu » Sun Aug 31, 2008 10:36 pm

I've parallelized some algorithm with OpenMP 2.0. (for some reason I can't use newer version now) The algorithm has a recursive charactersitic and each recursive step has no dependency, so I tried to make a task queue model like below.

add(&taskq, main_tree);
#pragma omp parallel
{
next_task = get(&taskq);
while(next_task != NULL)
{
task(next_task);
next_task = get(&taskq);
}
}

Each task creates multiple tasks (like tree structure) and adds them to the single task queue, and every function which accesses to the task queue are protected by critical section.

This model seems to work well in simple example but when I applied it to the algorithm, I got a speed down problem. The result was logically correct, but when the processor number is increased, running time also increased. (ex. 17 secs with 1 thread, 33 secs with 2 threads, 61 secs with 4 threads) CPU usage was 100% and there was no idle thread (at least printf confirmation). So it doesn't look like dead lock or memory bandwidth problem.

I'm new to OpenMP, so I'll appreciate any of advice.
misuzu
 
Posts: 1
Joined: Sun Aug 31, 2008 9:56 pm

Re: Speed down problem

Postby ejd » Tue Sep 02, 2008 6:23 am

You say that you can only use OpenMP 2.0 right now. You might want to try getting to a newer version that supports the OpenMP 3.0 spec that has tasking. That would most likely help you a lot. My guess is that the locking you are having to do to add tasks and remove tasks is what is slowing you down. Unless you are using a lock free algorithm, every thread that is trying to access your task queue has to wait until the task queue is available. As you add more threads this is going to cause more and more delays. I have to say though, that I am surprised by the amount of time that you are showing it increases by as you add threads. Without looking at the routines you are using for adding and removing tasks, there isn't much more I can say.
ejd
 
Posts: 1025
Joined: Wed Jan 16, 2008 7:21 am


Return to Using OpenMP

Who is online

Users browsing this forum: No registered users and 3 guests