Page MenuHomePhabricator

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

Authored by AndreyChurbanov on Nov 1 2016, 7:01 AM.

Details

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.

Diff Detail

Event Timeline

AndreyChurbanov retitled this revision from to Change task stealing to always get task from head of victim's deque..
AndreyChurbanov updated this object.
AndreyChurbanov set the repository for this revision to rL LLVM.
AndreyChurbanov added a subscriber: openmp-commits.
Hahnfeld added inline comments.
runtime/src/kmp_tasking.c
1796–1799 ↗(On Diff #76690)

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?

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

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 accepted this revision.Nov 2 2016, 8:45 AM
Hahnfeld added a reviewer: 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?

This revision is now accepted and ready to land.Nov 2 2016, 8:45 AM

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.

This revision was automatically updated to reflect the committed changes.