Second Task Scheduling Constraint

[jakub]

I have trouble understanding the second task scheduling constraint (2.7.1, p59, l29-32):
"Other scheduling of new tied tasks is constrained by the set of task regions that are currently tied to the thread, and that are not suspended in a barrier region. If this set is empty, any new tied task may be scheduled. Otherwise, a new tied task may be scheduled only if it is a descendant of every task in the set."

Does the above talk about just explicit barriers, or implicit barriers too (at the end of worksharing constructs without nowait)? Shouldn't the set also exclude tasks suspended in taskwait regions?
For the latter I'm asking because when a task hits a taskwait construct, but all its descendent tasks are running in other threads (that can happen if the implicit tasks in those threads encountered
barrier region or if the implicit tasks exited), the taskwait will have to be suspended if the only new queued tasks were created by other implicit tasks, while the thread CPU time could be used to work on some new task in the mean time.

[Federico]

Yes, the reference to "barrier region" refers to both explicit and explicit barriers. The only difference between explicit and implicit barriers is that the latter are added automatically.

No, taskwait regions have to be included in the set. And it is immaterial whether tasks were created by implicit or explicit tasks. The purpose of the restriction is to avoid spurious races deriving from task scheduling. Consider the following code snippet:

Code: Select all

#pragma omp task
{
  //...
  omp_set_lock(&alock);

  #pragma omp task
    foo();
  #pragma omp task
    bar();
  #pragma omp taskwait
  //...
  omp_unset_lock(&alock);
}


Imagine that a thread holding the lock reaches the taskwait region. Were it allowed to execute another task like the one it suspended because of the taskwait, it would try to set the lock again, block, and a deadlock would occur. Similar scenarios could happen with critical sections.
Deadlocks like that would be even harder to debug than deadlocks occurring between two different threads.
The restriction avoids those cases, relying on the assumption that the code is correct if executed serially (a safe programming style, given that a parallel region could be inactive for several reasons).
The restriction also helps user to make correct assumptions to safely access threadprivate variables inside tasks, avoiding data races among different tasks tied to the same thread.

You are right: this safety measure could bring to thread starvation and load unbalance. This is one of the reasons for the untied clause, which can be used by the user to tell the implementation which tasks can be safely executed even by a thread in a taskwait region.

I hope this helps.

[jakub]

Thanks, that makes sense.
BTW, would you know answer for viewtopic.php?f=5&t=82 question too? It is not just about reduction, similarly about e.g.
private, firstprivate etc. vars on the parallel. If task has such vars in a shared clause and there is no taskwait, can the implicit task run till the end, running destructors
for private/firstprivate variables and afterwards execute some explicit tasks, or does it need to make sure all explicit tasks finished before it runs private/firstprivate
destructors and computes the reduction operator on all the private reduction vars?
In particular for compilers that implement parallel regions by outlining the region into a function where privatized variables are automatic variables in that new function
and constructors/copy constructors are run at the beginning of the function and at the end destructors (and code to compute reductions), is a call to a function which
acts as an extended barrier, running all encountered explicit tasks, needed before running the destructors (or if there are none, just returning from function when the
automatic variables would be gone)? I'm worried that if that is necessary it would pessimize even parallels which never create any explicit tasks.

Code: Select all

struct A
{
  A();
  ~A();
  A(const A &);
};

int foo (A *, A *, int *);

int
main ()
{
  A a, b;
  int r = 0;
  #pragma omp parallel private (a) firstprivate (b) reduction (+:r)
  {
    foo (a, b, r);
  }
  return r;
}


where foo definition is in another translation unit and not visible to the compiler, could potentially create tasks and so an extra barrier would be needed, if the implicit task must keep its privatized variables live for the duration of all explicit tasks.

Code: Select all

int foo (A *a, A *b, int *r)
{
  #pragma omp master
  for (int i = 0; i < 50; i++)
    #pragma omp task
      do_work (i, a, b, r);
}


[lfm]

The implementation is not required to keep its private variables live until all tasks that might reference those variables complete. The burden is on the task to ensure that it doesn't reference shared variables that have gone out of scope. This could be done with a barrier or (perhaps better) with firstprivate.

-- Larry

[Federico]

Jakub,
I apologize for taking so long to answer, I missed your reply.

I agree with Larry's answer.
We had a long discussion on this issue (it is summarized in a paper at IWOMP '07) but eventually realized that forcing the implementation to keep automatic and private variables alive just in case of a task would be too taxing for performances. We decided the user knows better and has the responsoibility of adding proper, explicit synchronization constructs to this purpose.
However, the points you make are interesting, and some folks on the lang committee think that a more detailed specification of what happens with private variables should be good. The issue is more complex than it appears, so definitely this will not make it in 3.0. Maybe in future specs.