Task Scheduling Problem

Discuss the OpenMP 3.0 API Specifications with the OpenMP Arch. Review Board. (Read Only)

Task Scheduling Problem

Postby lpw25 » Fri Aug 21, 2009 4:40 am

It seems that a valid OpenMP implementation could deadlock on the following code:

Code: Select all
#pragma omp parallel
{
    // Task 1
    #pragma omp task
    {
        // Task 2
        #pragma omp task
        {
            doSomething();
        }

        // Taskwait 1
        #pragma omp taskwait
        doSomethingElse();
    }

    // Task 3
    #pragma omp task if(1 == 0)
    {
        // Task 4
        #pragma omp task
        {
            doAnotherThing();
        }

        // Taskwait 2
        #pragma omp taskwait
        doSomethingMore();
    }
}


Each thread decides to execute Task 1 when it is created but then decides to continue with Task 1 when Task 2 is created. When they reach Taskwait 1 each thread then decides to continue executing its implicit task. When each thread creates its Task 3 it must execute it immediately because of task scheduling constraint 1 in the API. Then the threads must create Task 4 and reach Taskwait 2. Each thread is now stuck: Task 1 and Task 3 are stuck at Taskwait 1 and Taskwait 2 respectively, Task 2 and Task 4 cannot be execute because of task scheduling constraint 2 in the API (Task 2 is not descended from Task 3 and Task 4 is not descended from Task 1).

Each of the scheduling decisions described above appear to be valid according to the API and the source code also appears to be valid. Have I misinterpreted the API or is this conforming behaviour?
lpw25
 
Posts: 2
Joined: Fri Aug 21, 2009 4:06 am

Re: Task Scheduling Problem

Postby Federico » Wed Aug 26, 2009 11:21 am

I apologize for taking so long to answer, but I felt the need to check all discussions we had on this issue in the 3.0 Language Committee.

It was the clear intent of the Language Committee that a task switch should happen at the task switching point "immediately following the generation" (3.0 Specs, p. 62, row 5) of Task 3, to get rid of Task 2 before proceeding.
Unfortunately, we used the word "immediately" also to describe the behavior on encounter of an "if(0)ed" task. This is inappropriate in many respects (e.g.: which one is more "immediate", the task switching point or the execution?), and brought to an incorrect wording of Task Scheduling Constraint 2.

Thanks for pointing this out, I'm raising the issue with the Language Committee, to clarify and amend the specifications.

Federico Massaioli
Federico
 
Posts: 22
Joined: Wed Oct 24, 2007 6:39 am

Re: Task Scheduling Problem

Postby lpw25 » Wed Sep 02, 2009 6:18 am

Thank you for your reply.

Just to clarify, are you saying that an implementation should treat Task 3 (and all other "if(0)ed" tasks) as subject to Task Scheduling Constraint 2, and therefore not available for scheduling until after the completion of Task 2 and Task1.

Thanks,

Leo White
lpw25
 
Posts: 2
Joined: Fri Aug 21, 2009 4:06 am

Re: Task Scheduling Problem

Postby Federico » Fri Sep 04, 2009 12:38 am

lpw25 wrote:Just to clarify, are you saying that an implementation should treat Task 3 (and all other "if(0)ed" tasks) as subject to Task Scheduling Constraint 2, and therefore not available for scheduling until after the completion of Task 2 and Task1.


Yes, this is what I'm saying.
The rationale behind Task Scheduling Constraint 2 is to avoid the possibility of a thread deadlocking with hitself. If an implicit task region can be executed from beginning to end without the executing thread going in deadlock with itself, TSC 2 ensures that this will be true even if the implicit task is split into explicit tasks.
Your example clearly shows that, according to current wording, this property doesn't hold for "if(0)ed" tasks: a deadlock could happen even with a team of only one thread.

Federico
Federico
 
Posts: 22
Joined: Wed Oct 24, 2007 6:39 am


Return to OpenMP 3.0 API Specifications

Who is online

Users browsing this forum: No registered users and 0 guests

cron