diff --git a/openmp/runtime/src/kmp_taskdeps.h b/openmp/runtime/src/kmp_taskdeps.h
--- a/openmp/runtime/src/kmp_taskdeps.h
+++ b/openmp/runtime/src/kmp_taskdeps.h
@@ -85,6 +85,8 @@
 #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;
@@ -143,7 +145,9 @@
           // 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);
           }
diff --git a/openmp/runtime/src/kmp_tasking.cpp b/openmp/runtime/src/kmp_tasking.cpp
--- a/openmp/runtime/src/kmp_tasking.cpp
+++ b/openmp/runtime/src/kmp_tasking.cpp
@@ -3920,26 +3920,10 @@
             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;
@@ -3948,7 +3932,7 @@
 
   // 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;
 
@@ -3962,6 +3946,29 @@
       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);