[OpenMP] Refined the logic to give a regular task from a hidden helper task

[tianshilei1992]

Summary

In current implementation, if a regular task depends on a hidden helper task,
and when the hidden helper task is releasing its dependences, it directly calls
__kmp_omp_task. This could cause a problem that if __kmp_push_task returns
TASK_NOT_PUSHED, the task will be executed immediately. However, the hidden
helper threads are assumed to only execute hidden helper tasks. This could cause
problems because when calling __kmp_omp_task, the encountering gtid, which is
not the real one of the thread, is passed.

This patch uses __kmp_give_task, but because it is a static function, a new
wrapper __kmpc_give_task is added.

[jdoerfert]

Looks sensible, @AndreyChurbanov wdyt?

[tianshilei1992]

openmp/runtime/src/kmp_taskdeps.h

150

I found an interesting thing. If the encountering tid is not passed as a start point, the start point will be 0. In this case, it can happen that thread 0 tries to steal from thread 1, meanwhile thread 1 tries to steal from thread 0. Dead lock. @AndreyChurbanov Is it expected?

[AndreyChurbanov]

LGTM

(Though I didn't test it. Hope it won't break testing.)

openmp/runtime/src/kmp_taskdeps.h

150

Stealing from different queues cannot deadlock because each queue uses its own lock while stealing from it or putting a task into it.

[tianshilei1992]

openmp/runtime/src/kmp_taskdeps.h

150

Yeah, what I thought is not right. In fact, it is dead lock because all regular threads are waiting for the lock of a task queue (actually it is the thread with gtid 1 (tid 1), whom all tasks are given to), but all helper threads have already done their jobs.

openmp/runtime/src/kmp_taskdeps.h

static inline void __kmp_dephash_free(kmp_info_t *thread, kmp_dephash_t *h) {
   __kmp_dephash_free_entries(thread, h);
 #if USE_FAST_MEMORY
   __kmp_fast_free(thread, h);
 #else
   __kmp_thread_free(thread, h);
 #endif
 }
 
+extern void __kmpc_give_task(kmp_task_t *ptask, kmp_int32 start);
+
 static inline void __kmp_release_deps(kmp_int32 gtid, kmp_taskdata_t *task) {
   kmp_info_t *thread = __kmp_threads[gtid];
   kmp_depnode_t *node = task->td_depnode;
 
   // Check mutexinoutset dependencies, release locks
   if (UNLIKELY(node && (node->dn.mtx_num_locks < 0))) {
     // negative num_locks means all locks were acquired
     node->dn.mtx_num_locks = -node->dn.mtx_num_locks;
if (npredecessors == 0) {
         if (KMP_HIDDEN_HELPER_THREAD(gtid)) {
           // Hidden helper thread can only execute hidden helper tasks
           KMP_ASSERT(task->td_flags.hidden_helper);
           next_taskdata = KMP_TASK_TO_TASKDATA(successor->dn.task);
           // If the dependent task is a regular task, we need to push to its
           // encountering thread's queue; otherwise, it can be pushed to its own
           // queue.
           if (!next_taskdata->td_flags.hidden_helper) {
-            __kmp_omp_task(task->encountering_gtid, successor->dn.task, false);
+            __kmpc_give_task(
+                successor->dn.task,
+                __kmp_tid_from_gtid(next_taskdata->encountering_gtid));
           } else {
             __kmp_omp_task(gtid, successor->dn.task, false);
           }
         } else {
           __kmp_omp_task(gtid, successor->dn.task, false);
         }
       }
     }

openmp/runtime/src/kmp_tasking.cpp

void __kmpc_proxy_task_completed(kmp_int32 gtid, kmp_task_t *ptask) {
   __kmp_second_top_half_finish_proxy(taskdata);
   __kmp_bottom_half_finish_proxy(gtid, ptask);
 
   KA_TRACE(10,
            ("__kmp_proxy_task_completed(exit): T#%d proxy task %p completing\n",
             gtid, taskdata));
 }
 
-/*!
-@ingroup TASKING
-@param ptask Task which execution is completed
-
-Execute the completion of a proxy task from a thread that could not belong to
-the team.
-*/
-void __kmpc_proxy_task_completed_ooo(kmp_task_t *ptask) {
+void __kmpc_give_task(kmp_task_t *ptask, kmp_int32 start = 0) {
   KMP_DEBUG_ASSERT(ptask != NULL);
   kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(ptask);
 
-  KA_TRACE(
-      10,
-      ("__kmp_proxy_task_completed_ooo(enter): proxy task completing ooo %p\n",
-       taskdata));
-
-  KMP_DEBUG_ASSERT(taskdata->td_flags.proxy == TASK_PROXY);
-
-  __kmp_first_top_half_finish_proxy(taskdata);
-
   // Enqueue task to complete bottom half completion from a thread within the
   // corresponding team
   kmp_team_t *team = taskdata->td_team;
   kmp_int32 nthreads = team->t.t_nproc;
   kmp_info_t *thread;
 
   // This should be similar to start_k = __kmp_get_random( thread ) % nthreads
   // but we cannot use __kmp_get_random here
-  kmp_int32 start_k = 0;
+  kmp_int32 start_k = start;
   kmp_int32 pass = 1;
   kmp_int32 k = start_k;
 
   do {
     // For now we're just linearly trying to find a thread
     thread = team->t.t_threads[k];
     k = (k + 1) % nthreads;
 
     // we did a full pass through all the threads
     if (k == start_k)
       pass = pass << 1;
 
   } while (!__kmp_give_task(thread, k, ptask, pass));
+}
+
+/*!
+@ingroup TASKING
+@param ptask Task which execution is completed
+
+Execute the completion of a proxy task from a thread that could not belong to
+the team.
+*/
+void __kmpc_proxy_task_completed_ooo(kmp_task_t *ptask) {
+  KMP_DEBUG_ASSERT(ptask != NULL);
+  kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(ptask);
+
+  KA_TRACE(
+      10,
+      ("__kmp_proxy_task_completed_ooo(enter): proxy task completing ooo %p\n",
+       taskdata));
+
+  KMP_DEBUG_ASSERT(taskdata->td_flags.proxy == TASK_PROXY);
+
+  __kmp_first_top_half_finish_proxy(taskdata);
+
+  __kmpc_give_task(ptask);
 
   __kmp_second_top_half_finish_proxy(taskdata);
 
   KA_TRACE(
       10,
       ("__kmp_proxy_task_completed_ooo(exit): proxy task completing ooo %p\n",
        taskdata));
 }