[OpenMP] Add OpenMP 5.0 nonmonotonic code

This patch adds:
* New omp_sched_monotonic flag to omp_sched_t which is handled within the runtime
* Parsing of monotonic/nonmonotonic in OMP_SCHEDULE
* Tests for the monotonic flag and envirable parsing
* Logic to force monotonic when hierarchical scheduling is used

Differential Revision: https://reviews.llvm.org/D60979

llvm-svn: 359601

1 files changed, 50 insertions, 13 deletions

diff --git a/openmp/runtime/src/kmp_dispatch.cpp b/openmp/runtime/src/kmp_dispatch.cpp
index ee786ae9fc9..6ae8234d5ff 100644
--- a/openmp/runtime/src/kmp_dispatch.cpp
+++ b/openmp/runtime/src/kmp_dispatch.cpp
@@ -68,6 +68,20 @@ void __kmp_dispatch_dxo_error(int *gtid_ref, int *cid_ref, ident_t *loc_ref) {
   }
 }
 
+// Returns either SCHEDULE_MONOTONIC or SCHEDULE_NONMONOTONIC
+static inline int __kmp_get_monotonicity(enum sched_type schedule,
+                                         bool use_hier = false) {
+  // Pick up the nonmonotonic/monotonic bits from the scheduling type
+  int monotonicity;
+  // default to monotonic
+  monotonicity = SCHEDULE_MONOTONIC;
+  if (SCHEDULE_HAS_NONMONOTONIC(schedule))
+    monotonicity = SCHEDULE_NONMONOTONIC;
+  else if (SCHEDULE_HAS_MONOTONIC(schedule))
+    monotonicity = SCHEDULE_MONOTONIC;
+  return monotonicity;
+}
+
 // Initialize a dispatch_private_info_template<T> buffer for a particular
 // type of schedule,chunk.  The loop description is found in lb (lower bound),
 // ub (upper bound), and st (stride).  nproc is the number of threads relevant
@@ -95,6 +109,8 @@ void __kmp_dispatch_init_algorithm(ident_t *loc, int gtid,
   T tc;
   kmp_info_t *th;
   kmp_team_t *team;
+  int monotonicity;
+  bool use_hier;
 
 #ifdef KMP_DEBUG
   typedef typename traits_t<T>::signed_t ST;
@@ -125,13 +141,16 @@ void __kmp_dispatch_init_algorithm(ident_t *loc, int gtid,
 #endif
                                     team->t.t_active_level == 1;
 #endif
-#if (KMP_STATIC_STEAL_ENABLED)
-  if (SCHEDULE_HAS_NONMONOTONIC(schedule))
-    // AC: we now have only one implementation of stealing, so use it
-    schedule = kmp_sch_static_steal;
-  else
+
+#if KMP_USE_HIER_SCHED
+  use_hier = pr->flags.use_hier;
+#else
+  use_hier = false;
 #endif
-    schedule = SCHEDULE_WITHOUT_MODIFIERS(schedule);
+
+  /* Pick up the nonmonotonic/monotonic bits from the scheduling type */
+  monotonicity = __kmp_get_monotonicity(schedule, use_hier);
+  schedule = SCHEDULE_WITHOUT_MODIFIERS(schedule);
 
   /* Pick up the nomerge/ordered bits from the scheduling type */
   if ((schedule >= kmp_nm_lower) && (schedule < kmp_nm_upper)) {
@@ -149,6 +168,10 @@ void __kmp_dispatch_init_algorithm(ident_t *loc, int gtid,
   } else {
     pr->flags.ordered = FALSE;
   }
+  // Ordered overrides nonmonotonic
+  if (pr->flags.ordered) {
+    monotonicity = SCHEDULE_MONOTONIC;
+  }
 
   if (schedule == kmp_sch_static) {
     schedule = __kmp_static;
@@ -157,6 +180,8 @@ void __kmp_dispatch_init_algorithm(ident_t *loc, int gtid,
       // Use the scheduling specified by OMP_SCHEDULE (or __kmp_sch_default if
       // not specified)
       schedule = team->t.t_sched.r_sched_type;
+      monotonicity = __kmp_get_monotonicity(schedule, use_hier);
+      schedule = SCHEDULE_WITHOUT_MODIFIERS(schedule);
       // Detail the schedule if needed (global controls are differentiated
       // appropriately)
       if (schedule == kmp_sch_guided_chunked) {
@@ -207,7 +232,13 @@ void __kmp_dispatch_init_algorithm(ident_t *loc, int gtid,
       }
 #endif
     }
-
+#if KMP_STATIC_STEAL_ENABLED
+    // map nonmonotonic:dynamic to static steal
+    if (schedule == kmp_sch_dynamic_chunked) {
+      if (monotonicity == SCHEDULE_NONMONOTONIC)
+        schedule = kmp_sch_static_steal;
+    }
+#endif
     /* guided analytical not safe for too many threads */
     if (schedule == kmp_sch_guided_analytical_chunked && nproc > 1 << 20) {
       schedule = kmp_sch_guided_iterative_chunked;
@@ -217,6 +248,8 @@ void __kmp_dispatch_init_algorithm(ident_t *loc, int gtid,
     if (schedule == kmp_sch_runtime_simd) {
       // compiler provides simd_width in the chunk parameter
       schedule = team->t.t_sched.r_sched_type;
+      monotonicity = __kmp_get_monotonicity(schedule, use_hier);
+      schedule = SCHEDULE_WITHOUT_MODIFIERS(schedule);
       // Detail the schedule if needed (global controls are differentiated
       // appropriately)
       if (schedule == kmp_sch_static || schedule == kmp_sch_auto ||
@@ -236,9 +269,10 @@ void __kmp_dispatch_init_algorithm(ident_t *loc, int gtid,
       {
         char *buff;
         // create format specifiers before the debug output
-        buff = __kmp_str_format("__kmp_dispatch_init: T#%%d new: schedule:%%d"
-                                " chunk:%%%s\n",
-                                traits_t<ST>::spec);
+        buff = __kmp_str_format(
+            "__kmp_dispatch_init_algorithm: T#%%d new: schedule:%%d"
+            " chunk:%%%s\n",
+            traits_t<ST>::spec);
         KD_TRACE(10, (buff, gtid, schedule, chunk));
         __kmp_str_free(&buff);
       }
@@ -331,7 +365,10 @@ void __kmp_dispatch_init_algorithm(ident_t *loc, int gtid,
       pr->u.p.ub = init + small_chunk + (id < extras ? 1 : 0);
 
       pr->u.p.parm2 = lb;
-      // pr->pfields.parm3 = 0; // it's not used in static_steal
+      // parm3 is the number of times to attempt stealing which is
+      // proportional to the number of chunks per thread up until
+      // the maximum value of nproc.
+      pr->u.p.parm3 = KMP_MIN(small_chunk + extras, nproc);
       pr->u.p.parm4 = (id + 1) % nproc; // remember neighbour tid
       pr->u.p.st = st;
       if (traits_t<T>::type_size > 4) {
@@ -1184,7 +1221,7 @@ int __kmp_dispatch_next_algorithm(int gtid,
       }
       if (!status) { // try to steal
         kmp_info_t **other_threads = team->t.t_threads;
-        int while_limit = nproc; // nproc attempts to find a victim
+        int while_limit = pr->u.p.parm3;
         int while_index = 0;
         // TODO: algorithm of searching for a victim
         // should be cleaned up and measured
@@ -1282,7 +1319,7 @@ int __kmp_dispatch_next_algorithm(int gtid,
 
       if (!status) {
         kmp_info_t **other_threads = team->t.t_threads;
-        int while_limit = nproc; // nproc attempts to find a victim
+        int while_limit = pr->u.p.parm3;
         int while_index = 0;
 
         // TODO: algorithm of searching for a victim