Re: [GSoC'19] First Evaluations: Implementing OpenMP Work Stealing Scheduling

[Jakub Jelinek <jakub at redhat dot com>]

On Thu, Jun 27, 2019 at 05:20:56AM +0900, 김규래 wrote:
> I'll share my status for GSoC first evaluation.
>  
> Current status of libgomp task system:
> I'll first summarize my understanding of libgomp.
> Please correct me if I'm wrong.
> Currently libgomp has 3 different queues: children_queue, taskloop_queue and team_queue.
> These three queues are protected using a big lock (team->task_lock).

Indeed.  That lock protects those queues, and the task dependencies
(task->{depend_hash,depend_count,dependers}), *task->taskwait, *taskgroup
etc.

> The current 3 queue setup makes the implementation of work-stealing hard because they must be inter-synchronized.
>  
> Implementation of competing systems:
> The intel OpenMP implementation [1] is simpler.
> It uses a single queue for each thread and a single subroutine for dequeuing and executing the tasks  [2, 3].
> The taskgroup tasks and childen tasks are only counted (not queued) [4, 5, 6].
> So the taskwait or barrier like constructs only have to check whether all the tasks of interest were computed.
> This unifies the task queuing system and makes scheduling much simpler.

I see the per-thread locks td_deque_lock in there, does it have anything
like the per team lock (or per taskgroup lock) for some cases or not?
What kind of locking does it use for task dependencies?  E.g. a task could
depend on tasks running in multiple threads and some further tasks still
queued in various threads' queues (plus some not yet satisfied tasks), for
the dependencies certainly in libgomp data structures all the bookkeeping
can't be done just with atomic accesses, so some mutex is needed.

> What to do on libgomp:
> I think we should follow a similar path to libomp.
> Instead of using 3 different queues, we could simply use one and only count the tasks of interest.

We already do have such counts at least in some cases, e.g.
taskgroup->num_children and sure, new ones can be added.
The replacement of the 3 queues with either a single one or
a per implicit task is the easy part.

> This should also reduce the synchronization overhead between the queues (such as in gomp_task_run_post_remove_taskgroup). 
> Then the big task_lock lock could be split into one lock for each thread.

This is the hard part, we need to figure out the right locking scheme for
all the data accesses that need protection or use atomic accesses otherwise
where possible, or say __atomic_load outside of mutex protected area and
if it indicates there might be something of interest, take a lock and retry
under lock.
Where will a new task be placed when created?  Pick a random thread, take
that thread's lock and put it into that queue?  What about threads that are
currently sleeping and need to be woken up using gomp_sem_post, do we somehow
prefer them for the new task placement?  Do we consider priorities just
within each thread's queue and not globally?  I'm afraid if we want to avoid
the team->task_lock altogether or as much as possible, we have to and in the
standard, priority is just a best effort, so it might be fine.
For the work-stealing, if the current thread doesn't have anything in its
own queue, will it pick a random other thread (or say remember what it tried
last or similar)?  And as said earlier, if there is no work to do by the
current thread, but it needs to wait for some other tasks to complete,
it shouldn't busy wait forever, but needs to sleep and needs to be awaken if
there is further work for it or if the condition it is waiting on is finally
met (gomp_team_barrier_wake, taskwait->taskwait_sem,
taskgroup->taskgroup_sem).
Do we need any other locks to protect some state (say, do we need a
per-taskgroup lock, or can we get away with only atomic accesses)?

	Jakub