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

[김규래<msca8h at naver dot com>]

Hi everyone,
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).
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.

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.
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.
I'm currently implementing this but not yet have testable results.
I'll share results as soon as they become available.

Any feedback would be much appreciated.

Ray Kim


[1] https://github.com/llvm-mirror/openmp
[2] https://github.com/llvm-mirror/openmp/blob/3f381f546ec9b065f9133d1fcd5d2711affb646a/runtime/src/kmp_tasking.cpp#L2889
[3] Each thread's dedicated queue. https://github.com/llvm-mirror/openmp/blob/bbb6f0170731679d690cee002be712f2d703b8fe/runtime/src/kmp.h#L2384
[4] The task executing part of taskwait. https://github.com/llvm-mirror/openmp/blob/bbb6f0170731679d690cee002be712f2d703b8fe/runtime/src/kmp.h#L2187
[5] Atomic variable holding number of uncompleted children. https://github.com/llvm-mirror/openmp/blob/bbb6f0170731679d690cee002be712f2d703b8fe/runtime/src/kmp.h#L2352
[6] Atomic variable hodling number of uncompleted tasks in taskgroup. https://github.com/llvm-mirror/openmp/blob/bbb6f0170731679d690cee002be712f2d703b8fe/runtime/src/kmp.h#L2188