[OpenMP] Fix task wait doesn't work as expected in serialized team

[tianshilei1992]

Summary

As discussed in D107121, task wait doesn't work when a regular task T depends on
a detached task or a hidden helper task T' in a serialized team. The root cause is,
since the team is serialized, the last task will not be tracked by
td_incomplete_child_tasks. When T' is finished, it first releases its
dependences, and then decrements its parent counter. So far so good. For the thread
that is running task wait, if at the moment it is still spinning and trying to
execute tasks, it is fine because it can detect the new task and execute it.
However, if it happends to finish the function flag.execute_tasks(...), it will
be broken because td_incomplete_child_tasks is 0 now.

In this patch, we update the rule to track children tasks a little bit. If the
task team encounters a proxy task or a hidden helper task, all following tasks
will be tracked.

[protze.joachim]

It's not just the last task, but any task after a detached/hidden task that has the issue to not be synchronized with the taskwait.

Instead of looking for the values in task_team, you could also just add || taskdata->td_parent->td_incomplete_child_tasks>0 and avoid a branch.

[tianshilei1992]

In D107496#2926713, @protze.joachim wrote:

It's not just the last task, but any task after a detached/hidden task that has the issue to not be synchronized with the taskwait.

Thanks for pointing out. I've updated the description.

Instead of looking for the values in task_team, you could also just add || taskdata->td_parent->td_incomplete_child_tasks>0 and avoid a branch.

They're not equivalent I think, especially when decrementing the counter. We should not decrement the counter if only td_incomplete_child_tasks > 0. I prefer to make increment and decrement "symmetric" such that we know they can be paired.

[protze.joachim]

You are right with your statement, that the two are not completely equivalent. But I still prefer my approach.

Consider the following sequence:

#pragma omp task detach(e) depend(out:a)
{}
#pragma omp taskwait depend(in:a)
#pragma omp task
{}

Your approach will enforce reference counting of child tasks until the end of the parallel region (remember that also main has an implicit inactive parallel region!). So, you will in/decrement the counter also for the last task.

My approach will stop reference counting, as soon as no other task is alive in the team and the task is really serialized. The race condition for at td_allocated_child_tasks>0 and then possibly incrementing from td_allocated_child_tasks=0 is actually harmless, because the same task will decrement the value at the end of it's execution.

For a really serialized task (which does no reference counting), no other task can be created during it's execution, so that td_allocated_child_tasks cannot be >0 at the end of execution.
Similar reasoning holds for your approach: for a serialized task, neither of the two flags in task_team can be set while the task executes and they are never set back to 0, aren't they?

The only requirement is, that the same set of flags is checked for the creation and end of task execution; and it is also important, that the values cannot change between the two encountering. I think, we should collect the flags into a macro/function to make sure we keep them symmetric.

With more and more conditions to this "fast path" for serialized tasks: when does the number of conditions and checks become more expensive than the operations we try to avoid - atomic writes to some variable with no contention?

openmp/runtime/src/kmp_tasking.cpp

1406

Btw: How can this be valid? From my understanding, task_serial marks the task as undeferred. Execution cannot continue before the task finished execution.

[tianshilei1992]

In D107496#2927620, @protze.joachim wrote:

You are right with your statement, that the two are not completely equivalent. But I still prefer my approach.

Consider the following sequence:

#pragma omp task detach(e) depend(out:a)
{}
#pragma omp taskwait depend(in:a)
#pragma omp task
{}

Your approach will enforce reference counting of child tasks until the end of the parallel region (remember that also main has an implicit inactive parallel region!). So, you will in/decrement the counter also for the last task.

My approach will stop reference counting, as soon as no other task is alive in the team and the task is really serialized. The race condition for at td_allocated_child_tasks>0 and then possibly incrementing from td_allocated_child_tasks=0 is actually harmless, because the same task will decrement the value at the end of it's execution.

Yes, you're right. Mine will start the counting as long as there is a detached task or hidden helper task found. I'm just thinking if it is possible there is a task that doesn't increment the count when it is allocated but decrements the counter by mistake.

For a really serialized task (which does no reference counting), no other task can be created during it's execution, so that td_allocated_child_tasks cannot be >0 at the end of execution.
Similar reasoning holds for your approach: for a serialized task, neither of the two flags in task_team can be set while the task executes and they are never set back to 0, aren't they?

Tasks can still be created but whether they are able to deferred, it depends. No?

The only requirement is, that the same set of flags is checked for the creation and end of task execution; and it is also important, that the values cannot change between the two encountering. I think, we should collect the flags into a macro/function to make sure we keep them symmetric.

I'll wrap them into a function.

With more and more conditions to this "fast path" for serialized tasks: when does the number of conditions and checks become more expensive than the operations we try to avoid - atomic writes to some variable with no contention?

That's a good point. It might worth a try to see which path is better.

[tianshilei1992]

rebase and fix comments

[tianshilei1992]

openmp/runtime/src/kmp_tasking.cpp

1406

Hidden helper task must be deferred task, right?

[tianshilei1992]

I think this patch can also fix the flaky failure of openmp/libomptarget/test/offloading/bug50022.cpp.

[AndreyChurbanov]

LGTM with one nit.

openmp/runtime/src/kmp_tasking.cpp

821

Why not use flags here instead of taskdata->td_flags?

[tianshilei1992]

rebase and fix comments

openmp/runtime/src/kmp_tasking.cpp

static void __kmp_free_task_and_ancestors(kmp_int32 gtid,
   }
 
   KA_TRACE(
       20, ("__kmp_free_task_and_ancestors(exit): T#%d task %p has %d children; "
            "not freeing it yet\n",
            gtid, taskdata, children));
 }
 
+// Only need to keep track of child task counts if any of the following:
+// 1. team parallel and tasking not serialized;
+// 2. it is a proxy or detachable or hidden helper task
+// 3. the children counter of its parent task is greater than 0.
+// The reason for the 3rd one is for serialized team that found detached task,
+// hidden helper task, T. In this case, the execution of T is still deferred,
+// and it is also possible that a regular task depends on T. In this case, if we
+// don't track the children, task synchronization will be broken.
+static bool __kmp_track_children_task(kmp_taskdata_t *taskdata) {
+  kmp_tasking_flags_t flags = taskdata->td_flags;
+  bool ret = !(flags.team_serial || flags.tasking_ser);
+  ret = ret || flags.proxy == TASK_PROXY ||
+        flags.detachable == TASK_DETACHABLE || flags.hidden_helper;
+  ret = ret ||
+        KMP_ATOMIC_LD_ACQ(&taskdata->td_parent->td_incomplete_child_tasks) > 0;
+  return ret;
+}
+
 // __kmp_task_finish: bookkeeping to do when a task finishes execution
 //
 // gtid: global thread ID for calling thread
 // task: task to be finished
 // resumed_task: task to be resumed.  (may be NULL if task is serialized)
 //
 // template<ompt>: effectively ompt_enabled.enabled!=0
 // the version with ompt=false is inlined, allowing to optimize away all ompt
#endif
   if (!detach) {
     taskdata->td_flags.complete = 1; // mark the task as completed
 
 #if OMPT_SUPPORT
     // This is not a detached task, we are done here
     if (ompt)
       __ompt_task_finish(task, resumed_task, ompt_task_complete);
 #endif
-
-    // Only need to keep track of count if team parallel and tasking not
-    // serialized, or task is detachable and event has already been fulfilled
-    if (!(taskdata->td_flags.team_serial || taskdata->td_flags.tasking_ser) ||
-        taskdata->td_flags.detachable == TASK_DETACHABLE ||
-        taskdata->td_flags.hidden_helper) {
+    // TODO: What would be the balance between the conditions in the function
+    // and an atomic operation?
+    if (__kmp_track_children_task(taskdata)) {
       __kmp_release_deps(gtid, taskdata);
       // Predecrement simulated by "- 1" calculation
 #if KMP_DEBUG
       children = -1 +
 #endif
           KMP_ATOMIC_DEC(&taskdata->td_parent->td_incomplete_child_tasks);
       KMP_DEBUG_ASSERT(children >= 0);
       if (taskdata->td_taskgroup)
if (flags->tiedness == TASK_UNTIED)
     taskdata->td_last_tied = NULL; // will be set when the task is scheduled
   else
     taskdata->td_last_tied = taskdata;
   taskdata->td_allow_completion_event.type = KMP_EVENT_UNINITIALIZED;
 #if OMPT_SUPPORT
   if (UNLIKELY(ompt_enabled.enabled))
     __ompt_task_init(taskdata, gtid);
 #endif
-  // Only need to keep track of child task counts if team parallel and tasking
-  // not serialized or if it is a proxy or detachable or hidden helper task
-  if (flags->proxy == TASK_PROXY || flags->detachable == TASK_DETACHABLE ||
-      flags->hidden_helper ||
-      !(taskdata->td_flags.team_serial || taskdata->td_flags.tasking_ser)) {
+  // TODO: What would be the balance between the conditions in the function and
+  // an atomic operation?
+  if (__kmp_track_children_task(taskdata)) {
     KMP_ATOMIC_INC(&parent_task->td_incomplete_child_tasks);
     if (parent_task->td_taskgroup)
       KMP_ATOMIC_INC(&parent_task->td_taskgroup->count);
     // Only need to keep track of allocated child tasks for explicit tasks since
     // implicit not deallocated
     if (taskdata->td_parent->td_flags.tasktype == TASK_EXPLICIT) {
       KMP_ATOMIC_INC(&taskdata->td_parent->td_allocated_child_tasks);
     }
     if (flags->hidden_helper) {
       taskdata->td_flags.task_serial = FALSE;
       // Increment the number of hidden helper tasks to be executed
       KMP_ATOMIC_INC(&__kmp_unexecuted_hidden_helper_tasks);
     }
   }
 
   KA_TRACE(20, ("__kmp_task_alloc(exit): T#%d created task %p parent=%p\n",
                 gtid, taskdata, taskdata->td_parent));
 

openmp/runtime/test/tasking/hidden_helper_task/depend.cpp

 // RUN: %libomp-cxx-compile-and-run
+// RUN: %libomp-cxx-compile && env OMP_NUM_THREADS=1 %libomp-run
 
 /*
  * This test aims to check whether hidden helper task can work with regular task
  * in terms of dependences. It is equivalent to the following code:
  *
  * #pragma omp parallel
  * for (int i = 0; i < N; ++i) {
  *   int data = -1;

openmp/runtime/test/tasking/hidden_helper_task/gtid.cpp

 // RUN: %libomp-cxx-compile-and-run
+// RUN: %libomp-cxx-compile && env OMP_NUM_THREADS=1 %libomp-run
 
 /*
  * This test aims to check whether hidden helper thread has right gtid. We also
  * test if there is mixed dependences between regular tasks and hidden helper
  * tasks, the tasks are executed by right set of threads. It is equivalent to
  * the following code:
  *
  * #pragma omp parallel for