Exclude untied tasks from checking of task scheduling constraint (TSC)

[AndreyChurbanov]

Summary

This is second attempt to exclude untied tasks from TSC, the first one was rejected because of kastors/trassen-task-dep benchmark hang.
This change works for the benchmark, because task stealing algorithm re-implemented so that the stealing of any task of the victim thread queue allowed, as opposed to only try to steal the head task.

Also added the check if the thief thread spins on a barrier - then any task allowed to be stolen.

[Hahnfeld]

runtime/src/kmp_global.cpp

318 ↗

(On Diff #121527)

Does this need to be global variable? If I understand the current patch correctly, __kmp_task_untied_encountered will be set to true once the first untied task has been encountered, However, it is never reset to zero, potentially degrading performance for later parallel regions in a program that only use tied tasks, right?

Wouldn't it make sense to have this as a property of the current parallel region? (maybe in kmp_taskteam_t?) Or does this cause problems because of the current implementation of barriers where the teams may not be valid anymore for the workers that are in the fork barrier?

[AndreyChurbanov]

runtime/src/kmp_global.cpp

318 ↗

(On Diff #121527)

Thanks for the comment, I will think of making the flag local for a task team. The task team is valid while threads execute tasks, it is the regular team that cannot be accessed safely by worker threads on fork barrier, so this is not a problem.

[AndreyChurbanov]

The flag indicating the presence of untied task in the region made task team local (was global initially).

Thus the presence of untied tasks in one region (part of parallel between barriers) won't affect other regions, that can potentially speed up execution making task stealing a bit faster.

[Hahnfeld]

In D39613#926282, @AndreyChurbanov wrote:

The flag indicating the presence of untied task in the region made task team local (was global initially).

Thus the presence of untied tasks in one region (part of parallel between barriers) won't affect other regions, that can potentially speed up execution making task stealing a bit faster.

Thanks for doing that change! The changes look good to me, but I'll let the others do a proper review.

[jlpeyton]

LGTM

openmp/trunk/runtime/src/kmp.h

typedef enum kmp_tasking_mode {
   tskm_immediate_exec = 0,
   tskm_extra_barrier = 1,
   tskm_task_teams = 2,
   tskm_max = 2
 } kmp_tasking_mode_t;
 
 extern kmp_tasking_mode_t
     __kmp_tasking_mode; /* determines how/when to execute tasks */
-extern kmp_int32 __kmp_task_stealing_constraint;
+extern int __kmp_task_stealing_constraint;
 #if OMP_40_ENABLED
 extern kmp_int32 __kmp_default_device; // Set via OMP_DEFAULT_DEVICE if
 // specified, defaults to 0 otherwise
 #endif
 #if OMP_45_ENABLED
 // Set via OMP_MAX_TASK_PRIORITY if specified, defaults to 0 otherwise
 extern kmp_int32 __kmp_max_task_priority;
 // Set via KMP_TASKLOOP_MIN_TASKS if specified, defaults to 0 otherwise
volatile kmp_int32
       td_incomplete_child_tasks; /* Child tasks not yet complete */
 #if OMP_40_ENABLED
   kmp_taskgroup_t
       *td_taskgroup; // Each task keeps pointer to its current taskgroup
   kmp_dephash_t
       *td_dephash; // Dependencies for children tasks are tracked from here
   kmp_depnode_t
       *td_depnode; // Pointer to graph node if this task has dependencies
-#endif
-#if OMPT_SUPPORT
-  ompt_task_info_t ompt_task_info;
-#endif
+#endif // OMP_40_ENABLED
 #if OMP_45_ENABLED
   kmp_task_team_t *td_task_team;
   kmp_int32 td_size_alloc; // The size of task structure, including shareds etc.
+#endif // OMP_45_ENABLED
+  kmp_taskdata_t *td_last_tied; // keep tied task for task scheduling constraint
+#if OMPT_SUPPORT
+  ompt_task_info_t ompt_task_info;
 #endif
 }; // struct kmp_taskdata
 
 // Make sure padding above worked
 KMP_BUILD_ASSERT(sizeof(kmp_taskdata_t) % sizeof(void *) == 0);
 
 // Data for task team but per thread
 typedef struct kmp_base_thread_data {
typedef struct kmp_base_task_team {
   /* TRUE means tt_threads_data is set up and initialized */
   kmp_int32 tt_nproc; /* #threads in team           */
   kmp_int32
       tt_max_threads; /* number of entries allocated for threads_data array */
 #if OMP_45_ENABLED
   kmp_int32
       tt_found_proxy_tasks; /* Have we found proxy tasks since last barrier */
 #endif
+  kmp_int32 tt_untied_task_encountered;
 
   KMP_ALIGN_CACHE
   volatile kmp_int32 tt_unfinished_threads; /* #threads still active      */
 
   KMP_ALIGN_CACHE
   volatile kmp_uint32
       tt_active; /* is the team still actively executing tasks */
 } kmp_base_task_team_t;

openmp/trunk/runtime/src/kmp_global.cpp

 
 /* This check ensures that the compiler is passing the correct data type for the
    flags formal parameter of the function kmpc_omp_task_alloc(). If the type is
    not a 4-byte type, then give an error message about a non-positive length
    array pointing here.  If that happens, the kmp_tasking_flags_t structure must
    be redefined to have exactly 32 bits. */
 KMP_BUILD_ASSERT(sizeof(kmp_tasking_flags_t) == 4);
 
-kmp_int32 __kmp_task_stealing_constraint =
-    1; /* Constrain task stealing by default */
+int __kmp_task_stealing_constraint = 1; /* Constrain task stealing by default */
 
 #ifdef DEBUG_SUSPEND
 int __kmp_suspend_count = 0;
 #endif
 
 int __kmp_settings = FALSE;
 int __kmp_duplicate_library_ok = 0;
 #if USE_ITT_BUILD

openmp/trunk/runtime/src/kmp_tasking.cpp

#endif // OMP_40_ENABLED
   // GEH - note tasking_ser => task_serial
   KMP_DEBUG_ASSERT(
       (taskdata->td_flags.tasking_ser || taskdata->td_flags.task_serial) ==
       taskdata->td_flags.task_serial);
   if (taskdata->td_flags.task_serial) {
     if (resumed_task == NULL) {
       resumed_task = taskdata->td_parent; // In a serialized task, the resumed
       // task is the parent
-    } else
-#if OMP_45_ENABLED
-        if (!(task_team && task_team->tt.tt_found_proxy_tasks))
-#endif
-    {
-      // verify resumed task passed in points to parent
-      KMP_DEBUG_ASSERT(resumed_task == taskdata->td_parent);
     }
   } else {
     KMP_DEBUG_ASSERT(resumed_task !=
                      NULL); // verify that resumed task is passed as arguemnt
   }
 
   // Free this task and then ancestor tasks if they have no children.
   // Restore th_current_task first as suggested by John:
#endif
   task->td_flags.started = 1;
   task->td_flags.executing = 1;
   task->td_flags.complete = 0;
   task->td_flags.freed = 0;
 
 #if OMP_40_ENABLED
   task->td_depnode = NULL;
 #endif
+  task->td_last_tied = task;
 
   if (set_curr_task) { // only do this init first time thread is created
     task->td_incomplete_child_tasks = 0;
     // Not used: don't need to deallocate implicit task
     task->td_allocated_child_tasks = 0;
 #if OMP_40_ENABLED
     task->td_taskgroup = NULL; // An implicit task does not have taskgroup
     task->td_dephash = NULL;
KA_TRACE(10, ("__kmp_task_alloc(enter): T#%d loc=%p, flags=(0x%x) "
                 gtid, loc_ref, *((kmp_int32 *)flags), sizeof_kmp_task_t,
                 sizeof_shareds, task_entry));
 
   if (parent_task->td_flags.final) {
     if (flags->merged_if0) {
     }
     flags->final = 1;
   }
+  if (flags->tiedness == TASK_UNTIED && !team->t.t_serialized) {
+    // Untied task encountered causes the TSC algorithm to check entire deque of
+    // the victim thread. If no untied task encountered, then checking the head
+    // of the deque should be enough.
+    KMP_CHECK_UPDATE(thread->th.th_task_team->tt.tt_untied_task_encountered, 1);
+  }
 
 #if OMP_45_ENABLED
   if (flags->proxy == TASK_PROXY) {
     flags->tiedness = TASK_UNTIED;
     flags->merged_if0 = 1;
 
     /* are we running in a sequential parallel or tskm_immediate_exec... we need
        tasking support enabled */
#endif
   taskdata->td_allocated_child_tasks = 1; // start at one because counts current
 // task and children
 #if OMP_40_ENABLED
   taskdata->td_taskgroup =
       parent_task->td_taskgroup; // task inherits taskgroup from the parent task
   taskdata->td_dephash = NULL;
   taskdata->td_depnode = NULL;
 #endif
+  if (flags->tiedness == TASK_UNTIED)
+    taskdata->td_last_tied = NULL; // will be set when the task is scheduled
+  else
+    taskdata->td_last_tied = taskdata;
 
 // Only need to keep track of child task counts if team parallel and tasking not
 // serialized or if it is a proxy task
 #if OMP_45_ENABLED
   if (flags->proxy == TASK_PROXY ||
       !(taskdata->td_flags.team_serial || taskdata->td_flags.tasking_ser))
 #else
   if (!(taskdata->td_flags.team_serial || taskdata->td_flags.tasking_ser))
#endif
       // this task belongs to a task group and we need to cancel it
       discard = 1 /* true */;
     }
   }
 
   // Invoke the task routine and pass in relevant data.
   // Thunks generated by gcc take a different argument list.
   if (!discard) {
+    if (taskdata->td_flags.tiedness == TASK_UNTIED) {
+      taskdata->td_last_tied = current_task->td_last_tied;
+      KMP_DEBUG_ASSERT(taskdata->td_last_tied);
+    }
 #if KMP_STATS_ENABLED
     KMP_COUNT_BLOCK(TASK_executed);
     switch (KMP_GET_THREAD_STATE()) {
     case FORK_JOIN_BARRIER:
       KMP_PUSH_PARTITIONED_TIMER(OMP_task_join_bar);
       break;
     case PLAIN_BARRIER:
       KMP_PUSH_PARTITIONED_TIMER(OMP_task_plain_bar);
#if OMPT_SUPPORT && OMPT_OPTIONAL
   }
 #endif
 
   KA_TRACE(10, ("__kmpc_end_taskgroup(enter): T#%d loc=%p\n", gtid, loc));
   KMP_DEBUG_ASSERT(taskgroup != NULL);
   KMP_SET_THREAD_STATE_BLOCK(TASKGROUP);
 
   if (__kmp_tasking_mode != tskm_immediate_exec) {
+    // mark task as waiting not on a barrier
+    taskdata->td_taskwait_counter += 1;
+    taskdata->td_taskwait_ident = loc;
+    taskdata->td_taskwait_thread = gtid + 1;
 #if USE_ITT_BUILD
     // For ITT the taskgroup wait is similar to taskwait until we need to
     // distinguish them
     void *itt_sync_obj = __kmp_itt_taskwait_object(gtid);
     if (itt_sync_obj != NULL)
       __kmp_itt_taskwait_starting(gtid, itt_sync_obj);
 #endif /* USE_ITT_BUILD */
 
#endif
     {
       kmp_flag_32 flag(RCAST(kmp_uint32 *, &taskgroup->count), 0U);
       while (TCR_4(taskgroup->count) != 0) {
         flag.execute_tasks(thread, gtid, FALSE,
                            &thread_finished USE_ITT_BUILD_ARG(itt_sync_obj),
                            __kmp_task_stealing_constraint);
       }
     }
+    taskdata->td_taskwait_thread = -taskdata->td_taskwait_thread; // end waiting
 
 #if OMPT_SUPPORT && OMPT_OPTIONAL
     if (UNLIKELY(ompt_enabled.ompt_callback_sync_region_wait)) {
       ompt_callbacks.ompt_callback(ompt_callback_sync_region_wait)(
           ompt_sync_region_taskgroup, ompt_scope_end, &(my_parallel_data),
           &(my_task_data), codeptr);
     }
 #endif
if (TCR_4(thread_data->td.td_deque_ntasks) == 0) {
     return NULL;
   }
 
   tail = (thread_data->td.td_deque_tail - 1) &
          TASK_DEQUE_MASK(thread_data->td); // Wrap index.
   taskdata = thread_data->td.td_deque[tail];
 
   if (is_constrained && (taskdata->td_flags.tiedness == TASK_TIED)) {
-    // we need to check if the candidate obeys task scheduling constraint:
-    // only child of current task can be scheduled
-    kmp_taskdata_t *current = thread->th.th_current_task;
+    // we need to check if the candidate obeys task scheduling constraint (TSC)
+    // only descendant of all deferred tied tasks can be scheduled, checking
+    // the last one is enough, as it in turn is the descendant of all others
+    kmp_taskdata_t *current = thread->th.th_current_task->td_last_tied;
+    KMP_DEBUG_ASSERT(current != NULL);
+    // check if last tied task is not suspended on barrier
+    if (current->td_flags.tasktype == TASK_EXPLICIT ||
+        current->td_taskwait_thread > 0) { // <= 0 on barrier
       kmp_int32 level = current->td_level;
       kmp_taskdata_t *parent = taskdata->td_parent;
       while (parent != current && parent->td_level > level) {
         parent = parent->td_parent; // check generation up to the level of the
         // current task
         KMP_DEBUG_ASSERT(parent != NULL);
       }
       if (parent != current) {
-      // If the tail task is not a child, then no other child can appear in the
-      // deque.
+        // The TSC does not allow to steal victim task
         __kmp_release_bootstrap_lock(&thread_data->td.td_deque_lock);
-      KA_TRACE(10,
-               ("__kmp_remove_my_task(exit #2): T#%d No tasks to remove: "
+        KA_TRACE(10, ("__kmp_remove_my_task(exit #2): T#%d No tasks to remove: "
                       "ntasks=%d head=%u tail=%u\n",
                       gtid, thread_data->td.td_deque_ntasks,
-                thread_data->td.td_deque_head, thread_data->td.td_deque_tail));
+                      thread_data->td.td_deque_head,
+                      thread_data->td.td_deque_tail));
         return NULL;
       }
     }
+  }
 
   thread_data->td.td_deque_tail = tail;
   TCW_4(thread_data->td.td_deque_ntasks, thread_data->td.td_deque_ntasks - 1);
 
   __kmp_release_bootstrap_lock(&thread_data->td.td_deque_lock);
 
   KA_TRACE(10, ("__kmp_remove_my_task(exit #2): T#%d task %p removed: "
                 "ntasks=%d head=%u tail=%u\n",
                 gtid, taskdata, thread_data->td.td_deque_ntasks,
                 thread_data->td.td_deque_head, thread_data->td.td_deque_tail));
 
   task = KMP_TASKDATA_TO_TASK(taskdata);
   return task;
 }
 
 // __kmp_steal_task: remove a task from another thread's deque
 // Assume that calling thread has already checked existence of
 // task_team thread_data before calling this routine.
-static kmp_task_t *__kmp_steal_task(kmp_info_t *victim, kmp_int32 gtid,
+static kmp_task_t *__kmp_steal_task(kmp_info_t *victim_thr, kmp_int32 gtid,
                                     kmp_task_team_t *task_team,
                                     volatile kmp_int32 *unfinished_threads,
                                     int *thread_finished,
                                     kmp_int32 is_constrained) {
   kmp_task_t *task;
   kmp_taskdata_t *taskdata;
+  kmp_taskdata_t *current;
   kmp_thread_data_t *victim_td, *threads_data;
+  kmp_int32 level, target;
   kmp_int32 victim_tid;
 
   KMP_DEBUG_ASSERT(__kmp_tasking_mode != tskm_immediate_exec);
 
   threads_data = task_team->tt.tt_threads_data;
   KMP_DEBUG_ASSERT(threads_data != NULL); // Caller should check this condition
 
-  victim_tid = victim->th.th_info.ds.ds_tid;
+  victim_tid = victim_thr->th.th_info.ds.ds_tid;
   victim_td = &threads_data[victim_tid];
 
   KA_TRACE(10, ("__kmp_steal_task(enter): T#%d try to steal from T#%d: "
-                "task_team=%p ntasks=%d "
-                "head=%u tail=%u\n",
-                gtid, __kmp_gtid_from_thread(victim), task_team,
+                "task_team=%p ntasks=%d head=%u tail=%u\n",
+                gtid, __kmp_gtid_from_thread(victim_thr), task_team,
                 victim_td->td.td_deque_ntasks, victim_td->td.td_deque_head,
                 victim_td->td.td_deque_tail));
 
-  if ((TCR_4(victim_td->td.td_deque_ntasks) ==
-       0) || // Caller should not check this condition
-      (TCR_PTR(victim->th.th_task_team) !=
-       task_team)) // GEH: why would this happen?
-  {
+  if (TCR_4(victim_td->td.td_deque_ntasks) == 0) {
     KA_TRACE(10, ("__kmp_steal_task(exit #1): T#%d could not steal from T#%d: "
-                  "task_team=%p "
-                  "ntasks=%d head=%u tail=%u\n",
-                  gtid, __kmp_gtid_from_thread(victim), task_team,
+                  "task_team=%p ntasks=%d head=%u tail=%u\n",
+                  gtid, __kmp_gtid_from_thread(victim_thr), task_team,
                   victim_td->td.td_deque_ntasks, victim_td->td.td_deque_head,
                   victim_td->td.td_deque_tail));
     return NULL;
   }
 
   __kmp_acquire_bootstrap_lock(&victim_td->td.td_deque_lock);
 
+  int ntasks = TCR_4(victim_td->td.td_deque_ntasks);
   // Check again after we acquire the lock
-  if ((TCR_4(victim_td->td.td_deque_ntasks) == 0) ||
-      (TCR_PTR(victim->th.th_task_team) !=
-       task_team)) // GEH: why would this happen?
-  {
+  if (ntasks == 0) {
     __kmp_release_bootstrap_lock(&victim_td->td.td_deque_lock);
     KA_TRACE(10, ("__kmp_steal_task(exit #2): T#%d could not steal from T#%d: "
-                  "task_team=%p "
-                  "ntasks=%d head=%u tail=%u\n",
-                  gtid, __kmp_gtid_from_thread(victim), task_team,
-                  victim_td->td.td_deque_ntasks, victim_td->td.td_deque_head,
-                  victim_td->td.td_deque_tail));
+                  "task_team=%p ntasks=%d head=%u tail=%u\n",
+                  gtid, __kmp_gtid_from_thread(victim_thr), task_team, ntasks,
+                  victim_td->td.td_deque_head, victim_td->td.td_deque_tail));
     return NULL;
   }
 
   KMP_DEBUG_ASSERT(victim_td->td.td_deque != NULL);
 
   taskdata = victim_td->td.td_deque[victim_td->td.td_deque_head];
-  if (is_constrained) {
-    // we need to check if the candidate obeys task scheduling constraint:
-    // only descendant of current task can be scheduled
-    kmp_taskdata_t *current = __kmp_threads[gtid]->th.th_current_task;
-    kmp_int32 level = current->td_level;
+  if (is_constrained && (taskdata->td_flags.tiedness == TASK_TIED)) {
+    // we need to check if the candidate obeys task scheduling constraint (TSC)
+    // only descendant of all deferred tied tasks can be scheduled, checking
+    // the last one is enough, as it in turn is the descendant of all others
+    current = __kmp_threads[gtid]->th.th_current_task->td_last_tied;
+    KMP_DEBUG_ASSERT(current != NULL);
+    // check if last tied task is not suspended on barrier
+    if (current->td_flags.tasktype == TASK_EXPLICIT ||
+        current->td_taskwait_thread > 0) { // <= 0 on barrier
+      level = current->td_level;
       kmp_taskdata_t *parent = taskdata->td_parent;
       while (parent != current && parent->td_level > level) {
         parent = parent->td_parent; // check generation up to the level of the
         // current task
         KMP_DEBUG_ASSERT(parent != NULL);
       }
       if (parent != current) {
-      // If the head task is not a descendant of the current task then do not
-      // steal it. No other task in victim's deque can be a descendant of the
-      // current task.
+        if (!task_team->tt.tt_untied_task_encountered) {
+          // The TSC does not allow to steal victim task
           __kmp_release_bootstrap_lock(&victim_td->td.td_deque_lock);
-      KA_TRACE(10, ("__kmp_steal_task(exit #2): T#%d could not steal from "
-                    "T#%d: task_team=%p "
-                    "ntasks=%d head=%u tail=%u\n",
-                    gtid,
-                    __kmp_gtid_from_thread(threads_data[victim_tid].td.td_thr),
-                    task_team, victim_td->td.td_deque_ntasks,
+          KA_TRACE(10,
+                   ("__kmp_steal_task(exit #3): T#%d could not steal from "
+                    "T#%d: task_team=%p ntasks=%d head=%u tail=%u\n",
+                    gtid, __kmp_gtid_from_thread(victim_thr), task_team, ntasks,
                     victim_td->td.td_deque_head, victim_td->td.td_deque_tail));
           return NULL;
         }
+        taskdata = NULL; // will check other tasks in victim's deque
+      }
+    }
   }
+  if (taskdata != NULL) {
     // Bump head pointer and Wrap.
     victim_td->td.td_deque_head =
         (victim_td->td.td_deque_head + 1) & TASK_DEQUE_MASK(victim_td->td);
+  } else {
+    int i;
+    // walk through victim's deque trying to steal any task
+    target = victim_td->td.td_deque_head;
+    for (i = 1; i < ntasks; ++i) {
+      target = (target + 1) & TASK_DEQUE_MASK(victim_td->td);
+      taskdata = victim_td->td.td_deque[target];
+      if (taskdata->td_flags.tiedness == TASK_TIED) {
+        // check if the candidate obeys the TSC
+        kmp_taskdata_t *parent = taskdata->td_parent;
+        // check generation up to the level of the current task
+        while (parent != current && parent->td_level > level) {
+          parent = parent->td_parent;
+          KMP_DEBUG_ASSERT(parent != NULL);
+        }
+        if (parent != current) {
+          // The TSC does not allow to steal the candidate
+          taskdata = NULL;
+          continue;
+        } else {
+          // found victim tied task
+          break;
+        }
+      } else {
+        // found victim untied task
+        break;
+      }
+    }
+    if (taskdata == NULL) {
+      // No appropriate candidate to steal found
+      __kmp_release_bootstrap_lock(&victim_td->td.td_deque_lock);
+      KA_TRACE(10, ("__kmp_steal_task(exit #4): T#%d could not steal from "
+                    "T#%d: task_team=%p ntasks=%d head=%u tail=%u\n",
+                    gtid, __kmp_gtid_from_thread(victim_thr), task_team, ntasks,
+                    victim_td->td.td_deque_head, victim_td->td.td_deque_tail));
+      return NULL;
+    }
+    int prev = target;
+    for (i = i + 1; i < ntasks; ++i) {
+      // shift remaining tasks in the deque left by 1
+      target = (target + 1) & TASK_DEQUE_MASK(victim_td->td);
+      victim_td->td.td_deque[prev] = victim_td->td.td_deque[target];
+      prev = target;
+    }
+    KMP_DEBUG_ASSERT(victim_td->td.td_deque_tail ==
+                     ((target + 1) & TASK_DEQUE_MASK(victim_td->td)));
+    victim_td->td.td_deque_tail = target; // tail -= 1 (wrapped))
+  }
   if (*thread_finished) {
     // We need to un-mark this victim as a finished victim.  This must be done
     // before releasing the lock, or else other threads (starting with the
     // master victim) might be prematurely released from the barrier!!!
     kmp_int32 count;
 
     count = KMP_TEST_THEN_INC32(unfinished_threads);
 
     KA_TRACE(
         20,
         ("__kmp_steal_task: T#%d inc unfinished_threads to %d: task_team=%p\n",
          gtid, count + 1, task_team));
 
     *thread_finished = FALSE;
   }
-  TCW_4(victim_td->td.td_deque_ntasks,
-        TCR_4(victim_td->td.td_deque_ntasks) - 1);
+  TCW_4(victim_td->td.td_deque_ntasks, ntasks - 1);
 
   __kmp_release_bootstrap_lock(&victim_td->td.td_deque_lock);
 
   KMP_COUNT_BLOCK(TASK_stolen);
-  KA_TRACE(
-      10,
-      ("__kmp_steal_task(exit #3): T#%d stole task %p from T#%d: task_team=%p "
-       "ntasks=%d head=%u tail=%u\n",
-       gtid, taskdata, __kmp_gtid_from_thread(victim), task_team,
-       victim_td->td.td_deque_ntasks, victim_td->td.td_deque_head,
-       victim_td->td.td_deque_tail));
+  KA_TRACE(10,
+           ("__kmp_steal_task(exit #5): T#%d stole task %p from T#%d: "
+            "task_team=%p ntasks=%d head=%u tail=%u\n",
+            gtid, taskdata, __kmp_gtid_from_thread(victim_thr), task_team,
+            ntasks, victim_td->td.td_deque_head, victim_td->td.td_deque_tail));
 
   task = KMP_TASKDATA_TO_TASK(taskdata);
   return task;
 }
 
 // __kmp_execute_tasks_template: Choose and execute tasks until either the
 // condition is statisfied (return true) or there are none left (return false).
 //
static inline int __kmp_execute_tasks_template(
     int *thread_finished USE_ITT_BUILD_ARG(void *itt_sync_obj),
     kmp_int32 is_constrained) {
   kmp_task_team_t *task_team = thread->th.th_task_team;
   kmp_thread_data_t *threads_data;
   kmp_task_t *task;
   kmp_info_t *other_thread;
   kmp_taskdata_t *current_task = thread->th.th_current_task;
   volatile kmp_int32 *unfinished_threads;
-  kmp_int32 nthreads, victim = -2, use_own_tasks = 1, new_victim = 0,
+  kmp_int32 nthreads, victim_tid = -2, use_own_tasks = 1, new_victim = 0,
                       tid = thread->th.th_info.ds.ds_tid;
 
   KMP_DEBUG_ASSERT(__kmp_tasking_mode != tskm_immediate_exec);
   KMP_DEBUG_ASSERT(thread == __kmp_threads[gtid]);
 
   if (task_team == NULL)
     return FALSE;
 
while (1) { // Inner loop to find a task and execute it
       task = NULL;
       if (use_own_tasks) { // check on own queue first
         task = __kmp_remove_my_task(thread, gtid, task_team, is_constrained);
       }
       if ((task == NULL) && (nthreads > 1)) { // Steal a task
         int asleep = 1;
         use_own_tasks = 0;
         // Try to steal from the last place I stole from successfully.
-        if (victim == -2) { // haven't stolen anything yet
-          victim = threads_data[tid].td.td_deque_last_stolen;
-          if (victim !=
+        if (victim_tid == -2) { // haven't stolen anything yet
+          victim_tid = threads_data[tid].td.td_deque_last_stolen;
+          if (victim_tid !=
               -1) // if we have a last stolen from victim, get the thread
-            other_thread = threads_data[victim].td.td_thr;
+            other_thread = threads_data[victim_tid].td.td_thr;
         }
-        if (victim != -1) { // found last victim
+        if (victim_tid != -1) { // found last victim
           asleep = 0;
         } else if (!new_victim) { // no recent steals and we haven't already
           // used a new victim; select a random thread
           do { // Find a different thread to steal work from.
             // Pick a random thread. Initial plan was to cycle through all the
             // threads, and only return if we tried to steal from every thread,
             // and failed.  Arch says that's not such a great idea.
-            victim = __kmp_get_random(thread) % (nthreads - 1);
-            if (victim >= tid) {
-              ++victim; // Adjusts random distribution to exclude self
+            victim_tid = __kmp_get_random(thread) % (nthreads - 1);
+            if (victim_tid >= tid) {
+              ++victim_tid; // Adjusts random distribution to exclude self
             }
             // Found a potential victim
-            other_thread = threads_data[victim].td.td_thr;
+            other_thread = threads_data[victim_tid].td.td_thr;
             // There is a slight chance that __kmp_enable_tasking() did not wake
             // up all threads waiting at the barrier.  If victim is sleeping,
             // then wake it up. Since we were going to pay the cache miss
             // penalty for referencing another thread's kmp_info_t struct
             // anyway,
             // the check shouldn't cost too much performance at this point. In
             // extra barrier mode, tasks do not sleep at the separate tasking
             // barrier, so this isn't a problem.
while (1) { // Inner loop to find a task and execute it
 
         if (!asleep) {
           // We have a victim to try to steal from
           task = __kmp_steal_task(other_thread, gtid, task_team,
                                   unfinished_threads, thread_finished,
                                   is_constrained);
         }
         if (task != NULL) { // set last stolen to victim
-          if (threads_data[tid].td.td_deque_last_stolen != victim) {
-            threads_data[tid].td.td_deque_last_stolen = victim;
+          if (threads_data[tid].td.td_deque_last_stolen != victim_tid) {
+            threads_data[tid].td.td_deque_last_stolen = victim_tid;
             // The pre-refactored code did not try more than 1 successful new
             // vicitm, unless the last one generated more local tasks;
             // new_victim keeps track of this
             new_victim = 1;
           }
         } else { // No tasks found; unset last_stolen
           KMP_CHECK_UPDATE(threads_data[tid].td.td_deque_last_stolen, -1);
-          victim = -2; // no successful victim found
+          victim_tid = -2; // no successful victim found
         }
       }
 
       if (task == NULL) // break out of tasking loop
         break;
 
 // Found a task; execute it
 #if USE_ITT_BUILD && USE_ITT_NOTIFY
KA_TRACE(
          __kmp_gtid_from_thread(this_thr), task_team));
 #if OMP_45_ENABLED
     KMP_DEBUG_ASSERT(task_team->tt.tt_nproc > 1 ||
                      task_team->tt.tt_found_proxy_tasks == TRUE);
     TCW_SYNC_4(task_team->tt.tt_found_proxy_tasks, FALSE);
 #else
     KMP_DEBUG_ASSERT(task_team->tt.tt_nproc > 1);
 #endif
+    KMP_CHECK_UPDATE(task_team->tt.tt_untied_task_encountered, 0);
     TCW_SYNC_4(task_team->tt.tt_active, FALSE);
     KMP_MB();
 
     TCW_PTR(this_thr->th.th_task_team, NULL);
   }
 }
 
 // __kmp_tasking_barrier: