[openmp] Fixed nonmonotonic schedule implementation.

[AndreyChurbanov]

Summary

Threads may work on different loops concurrently, thus iterations stealing algorithm should check that thief and victim work on the same loop.
The changes are:

• th_steal_lock moved from thread-private to thread-loop-private buffer;
• fixed dispatch_init to check possibly corrected in dispatch_init_algorithm schedule;
• fixed stealing process and stealing finalization to work with thread-loop-private buffers of the same index, instead of th_dispatch_pr_current which might point to different loops in different threads.

[hbae]

LGTM.

openmp/runtime/src/kmp.h

typedef struct KMP_ALIGN_CACHE dispatch_private_info32 {
   kmp_int32 count;
   kmp_int32 ub;
   /* Adding KMP_ALIGN_CACHE here doesn't help / can hurt performance */
   kmp_int32 lb;
   kmp_int32 st;
   kmp_int32 tc;
   kmp_int32 static_steal_counter; /* for static_steal only; maybe better to put
                                      after ub */
-
+  kmp_lock_t *th_steal_lock; // lock used for chunk stealing
   // KMP_ALIGN( 16 ) ensures ( if the KMP_ALIGN macro is turned on )
   //    a) parm3 is properly aligned and
   //    b) all parm1-4 are in the same cache line.
   // Because of parm1-4 are used together, performance seems to be better
   // if they are in the same line (not measured though).
 
   struct KMP_ALIGN(32) { // AC: changed 16 to 32 in order to simplify template
     kmp_int32 parm1; //     structures in kmp_dispatch.cpp. This should
typedef struct KMP_ALIGN_CACHE dispatch_private_info64 {
   kmp_int64 count; // current chunk number for static & static-steal scheduling
   kmp_int64 ub; /* upper-bound */
   /* Adding KMP_ALIGN_CACHE here doesn't help / can hurt performance */
   kmp_int64 lb; /* lower-bound */
   kmp_int64 st; /* stride */
   kmp_int64 tc; /* trip count (number of iterations) */
   kmp_int64 static_steal_counter; /* for static_steal only; maybe better to put
                                      after ub */
-
+  kmp_lock_t *th_steal_lock; // lock used for chunk stealing
   /* parm[1-4] are used in different ways by different scheduling algorithms */
 
   // KMP_ALIGN( 32 ) ensures ( if the KMP_ALIGN macro is turned on )
   //    a) parm3 is properly aligned and
   //    b) all parm1-4 are in the same cache line.
   // Because of parm1-4 are used together, performance seems to be better
   // if they are in the same line (not measured though).
 
typedef struct kmp_disp {
 
   dispatch_shared_info_t *th_dispatch_sh_current;
   dispatch_private_info_t *th_dispatch_pr_current;
 
   dispatch_private_info_t *th_disp_buffer;
   kmp_int32 th_disp_index;
   kmp_int32 th_doacross_buf_idx; // thread's doacross buffer index
   volatile kmp_uint32 *th_doacross_flags; // pointer to shared array of flags
-  union { // we can use union here because doacross cannot be used in
-    // nonmonotonic loops
-    kmp_int64 *th_doacross_info; // info on loop bounds
-    kmp_lock_t *th_steal_lock; // lock used for chunk stealing (8-byte variable)
-  };
 #if KMP_USE_INTERNODE_ALIGNMENT
   char more_padding[INTERNODE_CACHE_LINE];
 #endif
 } kmp_disp_t;
 
 /* ------------------------------------------------------------------------ */
 /* Barrier stuff */
 

openmp/runtime/src/kmp_dispatch.h

template <typename T> struct dispatch_private_infoXX_template {
   typedef typename traits_t<T>::signed_t ST;
   UT count; // unsigned
   T ub;
   /* Adding KMP_ALIGN_CACHE here doesn't help / can hurt performance */
   T lb;
   ST st; // signed
   UT tc; // unsigned
   T static_steal_counter; // for static_steal only; maybe better to put after ub
-
+  kmp_lock_t *th_steal_lock; // lock used for chunk stealing
   /* parm[1-4] are used in different ways by different scheduling algorithms */
 
   // KMP_ALIGN( 32 ) ensures ( if the KMP_ALIGN macro is turned on )
   //    a) parm3 is properly aligned and
   //    b) all parm1-4 are in the same cache line.
   // Because of parm1-4 are used together, performance seems to be better
   // if they are in the same line (not measured though).
 

openmp/runtime/src/kmp_dispatch.cpp

if (nproc > 1 && ntc >= nproc) {
       pr->u.p.parm4 = (id + 1) % nproc; // remember neighbour tid
       pr->u.p.st = st;
       if (traits_t<T>::type_size > 4) {
         // AC: TODO: check if 16-byte CAS available and use it to
         // improve performance (probably wait for explicit request
         // before spending time on this).
         // For now use dynamically allocated per-thread lock,
         // free memory in __kmp_dispatch_next when status==0.
-        KMP_DEBUG_ASSERT(th->th.th_dispatch->th_steal_lock == NULL);
-        th->th.th_dispatch->th_steal_lock =
+        KMP_DEBUG_ASSERT(pr->u.p.th_steal_lock == NULL);
+        pr->u.p.th_steal_lock =
             (kmp_lock_t *)__kmp_allocate(sizeof(kmp_lock_t));
-        __kmp_init_lock(th->th.th_dispatch->th_steal_lock);
+        __kmp_init_lock(pr->u.p.th_steal_lock);
       }
       break;
     } else {
       /* too few chunks: switching to kmp_sch_dynamic_chunked */
       schedule = kmp_sch_dynamic_chunked;
       KD_TRACE(100, ("__kmp_dispatch_init_algorithm: T#%d switching to "
                      "kmp_sch_dynamic_chunked\n",
                       gtid));
#ifdef KMP_DEBUG
   }
 #endif
 #if (KMP_STATIC_STEAL_ENABLED)
   // It cannot be guaranteed that after execution of a loop with some other
   // schedule kind all the parm3 variables will contain the same value. Even if
   // all parm3 will be the same, it still exists a bad case like using 0 and 1
   // rather than program life-time increment. So the dedicated variable is
   // required. The 'static_steal_counter' is used.
-  if (schedule == kmp_sch_static_steal) {
+  if (pr->schedule == kmp_sch_static_steal) {
     // Other threads will inspect this variable when searching for a victim.
     // This is a flag showing that other threads may steal from this thread
     // since then.
     volatile T *p = &pr->u.p.static_steal_counter;
     *p = *p + 1;
   }
 #endif // ( KMP_STATIC_STEAL_ENABLED )
 
KD_TRACE(100,
              ("__kmp_dispatch_next_algorithm: T#%d kmp_sch_static_steal case\n",
               gtid));
 
     trip = pr->u.p.tc - 1;
 
     if (traits_t<T>::type_size > 4) {
       // use lock for 8-byte and CAS for 4-byte induction
       // variable. TODO (optional): check and use 16-byte CAS
-      kmp_lock_t *lck = th->th.th_dispatch->th_steal_lock;
+      kmp_lock_t *lck = pr->u.p.th_steal_lock;
       KMP_DEBUG_ASSERT(lck != NULL);
       if (pr->u.p.count < (UT)pr->u.p.ub) {
         __kmp_acquire_lock(lck, gtid);
         // try to get own chunk of iterations
         init = (pr->u.p.count)++;
         status = (init < (UT)pr->u.p.ub);
         __kmp_release_lock(lck, gtid);
       } else {
         status = 0; // no own chunks
       }
       if (!status) { // try to steal
         kmp_info_t **other_threads = team->t.t_threads;
         int while_limit = pr->u.p.parm3;
         int while_index = 0;
+        T id = pr->u.p.static_steal_counter; // loop id
+        int idx = (th->th.th_dispatch->th_disp_index - 1) %
+                  __kmp_dispatch_num_buffers; // current loop index
+        // note: victim thread can potentially execute another loop
         // TODO: algorithm of searching for a victim
         // should be cleaned up and measured
         while ((!status) && (while_limit != ++while_index)) {
+          dispatch_private_info_template<T> *victim;
           T remaining;
           T victimIdx = pr->u.p.parm4;
           T oldVictimIdx = victimIdx ? victimIdx - 1 : nproc - 1;
-          dispatch_private_info_template<T> *victim =
-              reinterpret_cast<dispatch_private_info_template<T> *>(
-                  other_threads[victimIdx]
-                      ->th.th_dispatch->th_dispatch_pr_current);
-          while ((victim == NULL || victim == pr ||
-                  (*(volatile T *)&victim->u.p.static_steal_counter !=
-                   *(volatile T *)&pr->u.p.static_steal_counter)) &&
+          victim = reinterpret_cast<dispatch_private_info_template<T> *>(
+              &other_threads[victimIdx]->th.th_dispatch->th_disp_buffer[idx]);
+          KMP_DEBUG_ASSERT(victim);
+          while ((victim == pr || id != victim->u.p.static_steal_counter) &&
                  oldVictimIdx != victimIdx) {
             victimIdx = (victimIdx + 1) % nproc;
             victim = reinterpret_cast<dispatch_private_info_template<T> *>(
-                other_threads[victimIdx]
-                    ->th.th_dispatch->th_dispatch_pr_current);
+                &other_threads[victimIdx]->th.th_dispatch->th_disp_buffer[idx]);
+            KMP_DEBUG_ASSERT(victim);
           }
-          if (!victim || (*(volatile T *)&victim->u.p.static_steal_counter !=
-                          *(volatile T *)&pr->u.p.static_steal_counter)) {
+          if (victim == pr || id != victim->u.p.static_steal_counter) {
             continue; // try once more (nproc attempts in total)
             // no victim is ready yet to participate in stealing
-            // because all victims are still in kmp_init_dispatch
+            // because no victim passed kmp_init_dispatch yet
           }
           if (victim->u.p.count + 2 > (UT)victim->u.p.ub) {
             pr->u.p.parm4 = (victimIdx + 1) % nproc; // shift start tid
             continue; // not enough chunks to steal, goto next victim
           }
 
-          lck = other_threads[victimIdx]->th.th_dispatch->th_steal_lock;
+          lck = victim->u.p.th_steal_lock;
           KMP_ASSERT(lck != NULL);
           __kmp_acquire_lock(lck, gtid);
           limit = victim->u.p.ub; // keep initial ub
           if (victim->u.p.count >= limit ||
               (remaining = limit - victim->u.p.count) < 2) {
             __kmp_release_lock(lck, gtid);
             pr->u.p.parm4 = (victimIdx + 1) % nproc; // next victim
             continue; // not enough chunks to steal
if (traits_t<T>::type_size > 4) {
           }
           __kmp_release_lock(lck, gtid);
 
           KMP_DEBUG_ASSERT(init + 1 <= limit);
           pr->u.p.parm4 = victimIdx; // remember victim to steal from
           status = 1;
           while_index = 0;
           // now update own count and ub with stolen range but init chunk
-          __kmp_acquire_lock(th->th.th_dispatch->th_steal_lock, gtid);
+          __kmp_acquire_lock(pr->u.p.th_steal_lock, gtid);
           pr->u.p.count = init + 1;
           pr->u.p.ub = limit;
-          __kmp_release_lock(th->th.th_dispatch->th_steal_lock, gtid);
+          __kmp_release_lock(pr->u.p.th_steal_lock, gtid);
         } // while (search for victim)
       } // if (try to find victim and steal)
     } else {
       // 4-byte induction variable, use 8-byte CAS for pair (count, ub)
       typedef union {
         struct {
           UT count;
           T ub;
if (traits_t<T>::type_size > 4) {
         init = vnew.p.count;
         status = (init < (UT)vnew.p.ub);
       }
 
       if (!status) {
         kmp_info_t **other_threads = team->t.t_threads;
         int while_limit = pr->u.p.parm3;
         int while_index = 0;
-
+        T id = pr->u.p.static_steal_counter; // loop id
+        int idx = (th->th.th_dispatch->th_disp_index - 1) %
+                  __kmp_dispatch_num_buffers; // current loop index
+        // note: victim thread can potentially execute another loop
         // TODO: algorithm of searching for a victim
         // should be cleaned up and measured
         while ((!status) && (while_limit != ++while_index)) {
+          dispatch_private_info_template<T> *victim;
           union_i4 vold, vnew;
           kmp_int32 remaining;
           T victimIdx = pr->u.p.parm4;
           T oldVictimIdx = victimIdx ? victimIdx - 1 : nproc - 1;
-          dispatch_private_info_template<T> *victim =
-              reinterpret_cast<dispatch_private_info_template<T> *>(
-                  other_threads[victimIdx]
-                      ->th.th_dispatch->th_dispatch_pr_current);
-          while ((victim == NULL || victim == pr ||
-                  (*(volatile T *)&victim->u.p.static_steal_counter !=
-                   *(volatile T *)&pr->u.p.static_steal_counter)) &&
+          victim = reinterpret_cast<dispatch_private_info_template<T> *>(
+              &other_threads[victimIdx]->th.th_dispatch->th_disp_buffer[idx]);
+          KMP_DEBUG_ASSERT(victim);
+          while ((victim == pr || id != victim->u.p.static_steal_counter) &&
                  oldVictimIdx != victimIdx) {
             victimIdx = (victimIdx + 1) % nproc;
             victim = reinterpret_cast<dispatch_private_info_template<T> *>(
-                other_threads[victimIdx]
-                    ->th.th_dispatch->th_dispatch_pr_current);
+                &other_threads[victimIdx]->th.th_dispatch->th_disp_buffer[idx]);
+            KMP_DEBUG_ASSERT(victim);
           }
-          if (!victim || (*(volatile T *)&victim->u.p.static_steal_counter !=
-                          *(volatile T *)&pr->u.p.static_steal_counter)) {
+          if (victim == pr || id != victim->u.p.static_steal_counter) {
             continue; // try once more (nproc attempts in total)
             // no victim is ready yet to participate in stealing
-            // because all victims are still in kmp_init_dispatch
+            // because no victim passed kmp_init_dispatch yet
           }
           pr->u.p.parm4 = victimIdx; // new victim found
           while (1) { // CAS loop if victim has enough chunks to steal
             vold.b = *(volatile kmp_int64 *)(&victim->u.p.count);
             vnew = vold;
 
             KMP_DEBUG_ASSERT((vnew.p.ub - 1) * (UT)chunk <= trip);
             if (vnew.p.count >= (UT)vnew.p.ub ||

 #if KMP_USE_HIER_SCHED
       pr->flags.use_hier = FALSE;
 #endif
       if ((ST)num_done == th->th.th_team_nproc - 1) {
 #if (KMP_STATIC_STEAL_ENABLED)
         if (pr->schedule == kmp_sch_static_steal &&
             traits_t<T>::type_size > 4) {
           int i;
+          int idx = (th->th.th_dispatch->th_disp_index - 1) %
+                    __kmp_dispatch_num_buffers; // current loop index
           kmp_info_t **other_threads = team->t.t_threads;
           // loop complete, safe to destroy locks used for stealing
           for (i = 0; i < th->th.th_team_nproc; ++i) {
-            kmp_lock_t *lck = other_threads[i]->th.th_dispatch->th_steal_lock;
+            dispatch_private_info_template<T> *buf =
+                reinterpret_cast<dispatch_private_info_template<T> *>(
+                    &other_threads[i]->th.th_dispatch->th_disp_buffer[idx]);
+            kmp_lock_t *lck = buf->u.p.th_steal_lock;
             KMP_ASSERT(lck != NULL);
             __kmp_destroy_lock(lck);
             __kmp_free(lck);
-            other_threads[i]->th.th_dispatch->th_steal_lock = NULL;
+            buf->u.p.th_steal_lock = NULL;
           }
         }
 #endif
         /* NOTE: release this buffer to be reused */
 
         KMP_MB(); /* Flush all pending memory write invalidates.  */
 
         sh->u.s.num_done = 0;

openmp/runtime/test/worksharing/for/omp_nonmonotonic_nowait.c

+// RUN: %libomp-compile-and-run
+
+// The test checks nonmonotonic scheduling works correctly when threads
+// may execute different loops concurrently.
+
+#include <stdio.h>
+#include <omp.h>
+
+#define N 200
+#define C 20
+int main()
+{
+  int i, l0 = 0, l1 = 0;
+  #pragma omp parallel num_threads(8)
+  {
+    #pragma omp for schedule(nonmonotonic:dynamic,C) nowait
+    for (i = 0; i < N; ++i) {
+      #pragma omp atomic
+        l0++;
+    }
+    #pragma omp for schedule(nonmonotonic:dynamic,C) nowait
+    for (i = 0; i < N * N; ++i) {
+      #pragma omp atomic
+        l1++;
+    }
+  }
+  if (l0 != N || l1 != N * N) {
+    printf("failed l0 = %d, l1 = %d, should be %d %d\n", l0, l1, N, N * N);
+    return 1;
+  } else {
+    printf("passed\n");
+    return 0;
+  }
+}