Change task stealing to always get task from head of victim's deque.

[AndreyChurbanov]

Summary

Stealing bigger tasks is preferable strategy in theory. Testing showed some improvements in such tasking tests as kdtree, floorplan, fibonacci.
No performance regressions detected.

[Hahnfeld]

runtime/src/kmp_tasking.c

1797 ↗

(On Diff #76549)

Does this still hold then? I think currently a thread will add tasks to the tail so we have previously stolen the last generated task. However we are now going to take a task from the head.

If that is a problem, should we first try to steal from the head and afterwards check the tail if it's not a descendant task?

[AndreyChurbanov]

Updated diff: (1) merged recent commits, and (2) updated one comment.

[AndreyChurbanov]

Jonas,

If the head of victim's deque is not a descendant of the current task, then no other task in the deque can be a descendant. This should not be hard to prove mathematically, at least for simple cases without target tasks involved and without dependencies. Dependencies can bring complexity, but I am pretty sure the theory should still hold.

• Andrey

[Hahnfeld]

If I didn't get it wrong, a thread A won't steal another task until all new local tasks are finished. So if A stole one task from B, all tasks in its local queue will be descendants of B's current task when B does as taskwait, right?

[AndreyChurbanov]

Basically you are correct, but I'll try to re-phrase or detail your statement(s):

until all new local tasks are finished.

I'd say until its queue is empty. Its tasks can be stolen (not finished), or can wait for dependencies.

all tasks in its local queue will be descendants of B's current task when B does as taskwait, right?

Maybe, if B hasn't yet got anything to execute. Or, more likely, they will be descendants of one of ancestors of B's current task, if B got some task for execution after generating the task stolen by A. E.g.

#pragma omp task { // task T1 executed by `B`
  #pragma omp task // task T11 stolen by `A`
    {/* more tasks T11* generated */}
  #pragma omp task // task T12 may or may not be stolen
    {/* more tasks T12* */}
  #pragma omp taskwait
}

Tasks in A's queue - T11* - will be descendants of T1 that can be current task of B, if B has not yet started to execute task T12. Then B may change its current task by executing T12 or later its descendants. And if both T11 and T12 were stolen, then B can steal some of T11* or T12* tasks, as they are all descendants of its current task T1.

openmp/trunk/runtime/src/kmp_tasking.c

if ( (TCR_4(victim_td -> td.td_deque_ntasks) == 0) ||
                       "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) );
         return NULL;
     }
 
     KMP_DEBUG_ASSERT( victim_td -> td.td_deque != NULL );
 
-    if ( !is_constrained ) {
-        taskdata = victim_td -> td.td_deque[ victim_td -> td.td_deque_head ];
-        KMP_ASSERT(taskdata);
-        // 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 {
-        // While we have postponed tasks let's steal from tail of the deque (smaller tasks)
-        kmp_int32 tail = ( victim_td -> td.td_deque_tail - 1 ) & TASK_DEQUE_MASK(victim_td->td);  // Wrap index.
-        taskdata = victim_td -> td.td_deque[ tail ];
-        KMP_ASSERT(taskdata);
+    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 child of current task can be scheduled
+        // 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;
         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 descendant of the current task then do not steal it.
+            // 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.
             __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,
                           victim_td->td.td_deque_head, victim_td->td.td_deque_tail) );
             return NULL;
         }
-        victim_td -> td.td_deque_tail = tail;
     }
+    // Bump head pointer and Wrap.
+    victim_td->td.td_deque_head = (victim_td->td.td_deque_head + 1) & TASK_DEQUE_MASK(victim_td->td);
     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_uint32 count;
 
         count = KMP_TEST_THEN_INC32( (kmp_int32 *)unfinished_threads );