Create a runtime option to disable task throttling

[viroulep]

Summary

By default a task execution is serialized when a task queue is full, the one exception being when its dependencies are not met, then the task queue is extended.

This behavior may cripple the application performance in some specific task graph scenarios, like the ones detailed in section 4.2 from this paper published at IWOMP 2018 (the full text can be found here).
In such cases not having the full task graph prevent some opportunities for cache reuse between successive tasks of the stencil algorithm.

After the paper Thierry Gautier (whom I work with) was contacted by Jim Cownie who seemed to think some of the improvements described in the paper may be interesting enough to be merged upstream.

While the changes in the paper were made against an earlier version of the runtime, it's actually easier to integrate now, as the mechanism to resize task queues already exists.
So my suggestion would be to add an option to make sure the task queues are always resized if it's full and task throttling is disabled.

Please let me know what you think.

[viroulep]

Hi there,

by any chance did anyone had the time to take a look at this?

[AndreyChurbanov]

LGTM,

sorry for the delay.

[viroulep]

Thank you very much for the review Andrey!
I don't have commit access to the repository, would you mind committing these changes on my behalf or pointing me to someone who can please?

[lebedev.ri]

Isn't this missing test coverage?

[AndreyChurbanov]

Yes, adding tests would be great. Simplest thing to do is to extend existing tests with throttling on/off, I think.

Philippe,
If you don't mind, could you please update the patch adding tests. I'd suggest to use two existing tests with big number of created tasks (all others use small number of tasks and thus are not relevant to this patch). Possible additional change is:

Index: runtime/test/tasking/omp_taskloop_grainsize.c
===================================================================
--- runtime/test/tasking/omp_taskloop_grainsize.c       (revision 364425)
+++ runtime/test/tasking/omp_taskloop_grainsize.c       (working copy)
@@ -1,5 +1,7 @@
 // RUN: %libomp-compile-and-run
 // RUN: %libomp-compile && env KMP_TASKLOOP_MIN_TASKS=1 %libomp-run
+// RUN: %libomp-compile && env KMP_ENABLE_TASK_THROTTLING=0 %libomp-run
+// RUN: %libomp-compile && env KMP_ENABLE_TASK_THROTTLING=1 %libomp-run
 // REQUIRES: openmp-4.5

 // These compilers don't support the taskloop construct
Index: runtime/test/tasking/omp_taskloop_num_tasks.c
===================================================================
--- runtime/test/tasking/omp_taskloop_num_tasks.c       (revision 364425)
+++ runtime/test/tasking/omp_taskloop_num_tasks.c       (working copy)
@@ -2,6 +2,8 @@
 // UNSUPPORTED: netbsd
 // RUN: %libomp-compile-and-run
 // RUN: %libomp-compile && env KMP_TASKLOOP_MIN_TASKS=1 %libomp-run
+// RUN: %libomp-compile && env KMP_ENABLE_TASK_THROTTLING=0 %libomp-run
+// RUN: %libomp-compile && env KMP_ENABLE_TASK_THROTTLING=1 %libomp-run
 // REQUIRES: openmp-4.5

 // These compilers don't support the taskloop construct

[AndreyChurbanov]

Of cause you are free to choose your own test, or simply extend existing test(s).

[viroulep]

This adds a specific test for the task throttling behavior.

[viroulep]

Thanks Roman and Andrey for the additional comments!
Sorry for not including tests right away, and thanks for the detailed suggestions, I really appreciate it.

I ended up adding an extra test: I didn't want to mess around the grain size in the taskloop test (as the number of tasks created is not high enough), and I also wanted to explicitly test the task throttling behavior.
I did this by creating a lot of tasks and checking the number of tasks enqueued when the master thread starts executing tasks.
I've made a (hopefully) comprehensive explanation at the beginning of the test.

[AndreyChurbanov]

LGTM

[viroulep]

Thanks for the merge!

openmp/trunk/runtime/src/kmp.h

typedef enum kmp_tasking_mode {
   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 int __kmp_task_stealing_constraint;
+extern int __kmp_enable_task_throttling;
 #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

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);
 
 int __kmp_task_stealing_constraint = 1; /* Constrain task stealing by default */
+int __kmp_enable_task_throttling = 1;
 
 #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_settings.cpp

 
 static void __kmp_stg_print_forkjoin_frames_mode(kmp_str_buf_t *buffer,
                                                  char const *name, void *data) {
   __kmp_stg_print_int(buffer, name, __kmp_forkjoin_frames_mode);
 } // __kmp_stg_print_forkjoin_frames
 #endif /* USE_ITT_BUILD */
 
 // -----------------------------------------------------------------------------
+// KMP_ENABLE_TASK_THROTTLING
+
+static void __kmp_stg_parse_task_throttling(char const *name,
+                                            char const *value, void *data) {
+  __kmp_stg_parse_bool(name, value, &__kmp_enable_task_throttling);
+} // __kmp_stg_parse_task_throttling
+
+
+static void __kmp_stg_print_task_throttling(kmp_str_buf_t *buffer,
+                                            char const *name, void *data) {
+  __kmp_stg_print_bool(buffer, name, __kmp_enable_task_throttling);
+} // __kmp_stg_print_task_throttling
+
+// -----------------------------------------------------------------------------
 // OMP_DISPLAY_ENV
 
 #if OMP_40_ENABLED
 
 static void __kmp_stg_parse_omp_display_env(char const *name, char const *value,
                                             void *data) {
   if (__kmp_str_match("VERBOSE", 1, value)) {
     __kmp_display_env_verbose = TRUE;
#endif // KMP_USE_ADAPTIVE_LOCKS
     {"KMP_HW_SUBSET", __kmp_stg_parse_hw_subset, __kmp_stg_print_hw_subset,
      NULL, 0, 0},
 #if USE_ITT_BUILD
     {"KMP_FORKJOIN_FRAMES", __kmp_stg_parse_forkjoin_frames,
      __kmp_stg_print_forkjoin_frames, NULL, 0, 0},
     {"KMP_FORKJOIN_FRAMES_MODE", __kmp_stg_parse_forkjoin_frames_mode,
      __kmp_stg_print_forkjoin_frames_mode, NULL, 0, 0},
 #endif
+    {"KMP_ENABLE_TASK_THROTTLING", __kmp_stg_parse_task_throttling,
+     __kmp_stg_print_task_throttling, NULL, 0, 0},
 
 #if OMP_40_ENABLED
     {"OMP_DISPLAY_ENV", __kmp_stg_parse_omp_display_env,
      __kmp_stg_print_omp_display_env, NULL, 0, 0},
     {"OMP_CANCELLATION", __kmp_stg_parse_omp_cancellation,
      __kmp_stg_print_omp_cancellation, NULL, 0, 0},
 #endif
 

openmp/trunk/runtime/src/kmp_tasking.cpp

static kmp_int32 __kmp_push_task(kmp_int32 gtid, kmp_task_t *task) {
   if (thread_data->td.td_deque == NULL) {
     __kmp_alloc_task_deque(thread, thread_data);
   }
 
   int locked = 0;
   // Check if deque is full
   if (TCR_4(thread_data->td.td_deque_ntasks) >=
       TASK_DEQUE_SIZE(thread_data->td)) {
-    if (__kmp_task_is_allowed(gtid, __kmp_task_stealing_constraint, taskdata,
+    if (__kmp_enable_task_throttling &&
+        __kmp_task_is_allowed(gtid, __kmp_task_stealing_constraint, taskdata,
                               thread->th.th_current_task)) {
       KA_TRACE(20, ("__kmp_push_task: T#%d deque is full; returning "
                     "TASK_NOT_PUSHED for task %p\n",
                     gtid, taskdata));
       return TASK_NOT_PUSHED;
     } else {
       __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
       locked = 1;
       // expand deque to push the task which is not allowed to execute
       __kmp_realloc_task_deque(thread, thread_data);
     }
   }
   // Lock the deque for the task push operation
   if (!locked) {
     __kmp_acquire_bootstrap_lock(&thread_data->td.td_deque_lock);
 #if OMP_45_ENABLED
     // Need to recheck as we can get a proxy task from thread outside of OpenMP
     if (TCR_4(thread_data->td.td_deque_ntasks) >=
         TASK_DEQUE_SIZE(thread_data->td)) {
-      if (__kmp_task_is_allowed(gtid, __kmp_task_stealing_constraint, taskdata,
+      if (__kmp_enable_task_throttling &&
+          __kmp_task_is_allowed(gtid, __kmp_task_stealing_constraint, taskdata,
                                 thread->th.th_current_task)) {
         __kmp_release_bootstrap_lock(&thread_data->td.td_deque_lock);
         KA_TRACE(20, ("__kmp_push_task: T#%d deque is full on 2nd check; "
                       "returning TASK_NOT_PUSHED for task %p\n",
                       gtid, taskdata));
         return TASK_NOT_PUSHED;
       } else {
         // expand deque to push the task which is not allowed to execute

openmp/trunk/runtime/test/tasking/omp_fill_taskqueue.c

+// RUN: %libomp-compile && env KMP_ENABLE_TASK_THROTTLING=0 %libomp-run
+// RUN: %libomp-compile && env KMP_ENABLE_TASK_THROTTLING=1 %libomp-run
+
+#include<omp.h>
+#include<stdlib.h>
+#include<string.h>
+
+/**
+ * Test the task throttling behavior of the runtime.
+ * Unless OMP_NUM_THREADS is 1, the master thread pushes tasks to its own tasks
+ * queue until either of the following happens:
+ *   - the task queue is full, and it starts serializing tasks
+ *   - all tasks have been pushed, and it can begin execution
+ * The idea is to create a huge number of tasks which execution are blocked
+ * until the master thread comes to execute tasks (they need to be blocking,
+ * otherwise the second thread will start emptying the queue).
+ * At this point we can check the number of enqueued tasks: iff all tasks have
+ * been enqueued, then there was no task throttling.
+ * Otherwise there has been some sort of task throttling.
+ * If what we detect doesn't match the value of the environment variable, the
+ * test is failed.
+ */
+
+
+#define NUM_TASKS 2000
+
+
+int main()
+{
+  int i;
+  int block = 1;
+  int tid;
+  int throttling = strcmp(getenv("KMP_ENABLE_TASK_THROTTLING"), "1") == 0;
+  int enqueued = 0;
+  int failed = -1;
+
+  #pragma omp parallel num_threads(2)
+  #pragma omp master
+  {
+    for (i = 0; i < NUM_TASKS; i++) {
+      enqueued++;
+      #pragma omp task
+      {
+        tid = omp_get_thread_num();
+        if (tid == 0) {
+          // As soon as the master thread starts executing task we should unlock
+          // all tasks, and detect the test failure if it has not been done yet.
+          if (failed < 0)
+            failed = throttling ? enqueued == NUM_TASKS : enqueued < NUM_TASKS;
+          block = 0;
+        }
+        while (block)
+          ;
+      }
+    }
+    block = 0;
+  }
+
+  return failed;
+}