[OpenMP] libomp: fix dynamic loop dispatcher

[AndreyChurbanov]

Summary

Restructured dynamic loop dispatcher code.
Fixed work with dispatch buffers for nonmonotonic dynamic (static_steal) schedule:

• eliminated possibility of stealing iterations of the wrong loop when victim thread changed its buffer to work on another loop;
• fixed race when victim thread changed its buffer to work in nested parallel.
• eliminated "static" property of the schedule, that is now a single thread can execute whole loop.

[AndreyChurbanov]

Enable one more test fixed by this patch.

[jlpeyton]

Can you elaborate in the summary what your fixing about the static_steal schedule?

openmp/runtime/src/kmp_dispatch.cpp

1252–1254

Can we get rid of these commented lines?

1395–1397

Can we get rid of these commented lines?

[AndreyChurbanov]

Some comments removed.

[jlpeyton]

LGTM

[hoy]

Hello, I was seeing an assert firing in kmp_dispatch.cpp when running the omp_parallel_reduction.c test with a -DLLVM_ENABLE_ASSERTIONS enabled toolset. Would you mind taking a look? Thanks.

******************** TEST 'libomp :: parallel/omp_parallel_reduction.c' FAILED ********************
Script:
... omitted 

Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
OMP: Error #13: Assertion failure at kmp_dispatch.cpp(1453).
OMP: Hint Please submit a bug report with this message, compile and run commands used, and machine configuration info including native compiler and operating system versions. Faster response will be obtained by including all program sources. For information on submitting this issue, please see https://bugs.llvm.org/.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.

[AndreyChurbanov]

In D103648#2839482, @hoy wrote:

Hello, I was seeing an assert firing in kmp_dispatch.cpp when running the omp_parallel_reduction.c test with a -DLLVM_ENABLE_ASSERTIONS enabled toolset. Would you mind taking a look? Thanks.

• TEST 'libomp :: parallel/omp_parallel_reduction.c' FAILED ****

Script:
... omitted

Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
OMP: Error #13: Assertion failure at kmp_dispatch.cpp(1453).
OMP: Hint Please submit a bug report with this message, compile and run commands used, and machine configuration info including native compiler and operating system versions. Faster response will be obtained by including all program sources. For information on submitting this issue, please see https://bugs.llvm.org/.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.

Thanks for reporting.
Actually the wrong assertion existed before this patch, which apparently increased the probability of its triggering.
I've fixed the assertion in https://reviews.llvm.org/D104880.

[hoy]

In D103648#2839789, @AndreyChurbanov wrote:

In D103648#2839482, @hoy wrote:

Hello, I was seeing an assert firing in kmp_dispatch.cpp when running the omp_parallel_reduction.c test with a -DLLVM_ENABLE_ASSERTIONS enabled toolset. Would you mind taking a look? Thanks.

• TEST 'libomp :: parallel/omp_parallel_reduction.c' FAILED ****

Script:
... omitted

Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.
OMP: Error #13: Assertion failure at kmp_dispatch.cpp(1453).
OMP: Hint Please submit a bug report with this message, compile and run commands used, and machine configuration info including native compiler and operating system versions. Faster response will be obtained by including all program sources. For information on submitting this issue, please see https://bugs.llvm.org/.
Assertion failure at kmp_dispatch.cpp(1453): (vnew.p.ub - 1) * (UT)chunk <= trip.

Thanks for reporting.
Actually the wrong assertion existed before this patch, which apparently increased the probability of its triggering.
I've fixed the assertion in https://reviews.llvm.org/D104880.

Thanks for the fast turnaround!

[rogfer01]

openmp/runtime/src/kmp_dispatch.cpp

911

Sometimes (not always, so it seems a data race) running this test in an Arm 64-bit machine with 46 cores (and in a Power9 machine with 40 cores) all the threads end waiting here, so the test doesn't progress anymore.

All the cases I've seen happen with KMP_DISP_NUM_BUFFERS=3 and -DMY_SCHEDULE=guided.

Any idea how I could debug this further?

A quick look about sh->buffer_index shows it is a volatile and it is updated in

sh->buffer_index += __kmp_dispatch_num_buffers;
KD_TRACE(100, ("__kmp_dispatch_next: T#%d change buffer_index:%d\n",
               gtid, sh->buffer_index));

KMP_MB(); /* Flush all pending memory write invalidates.  */

Given that this is not an atomic operation (yet it goes followed by a memory barrier) my only hypothesis is that the original load of sh->buffer_index might have read an old value but that would suggest KMP_MB() is not effective in these targets? So I am at loss here.

Thanks!

[AndreyChurbanov]

openmp/runtime/src/kmp_dispatch.cpp

911

Which test(s) you see hanging?

There indeed may be a data race somewhere in the code, I will try to take a look. Still better to know the exact test case.

[rogfer01]

openmp/runtime/src/kmp_dispatch.cpp

911

Hi Andrey,

apologies I forgot to mention that in the comment above

env/kmp_set_dispatch_buf.c was easy to cause a deadlock with KMP_DISP_NUM_BUFFERS=3 and -DMY_SCHEDULE=guided.

Kind regards,

openmp/runtime/src/kmp.h

 #if KMP_STATIC_STEAL_ENABLED
 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 )
+  kmp_lock_t *steal_lock; // lock used for chunk stealing
+  // 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.
+  //    b) all parm1-4 are on 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).
+  // if they are on the same cache 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
     kmp_int32 parm2; //     make no real change at least while padding is off.
     kmp_int32 parm3;
     kmp_int32 parm4;
   };
 
   kmp_uint32 ordered_lower;
   kmp_uint32 ordered_upper;
 #if KMP_OS_WINDOWS
-  // This var can be placed in the hole between 'tc' and 'parm1', instead of
-  // 'static_steal_counter'. It would be nice to measure execution times.
-  // Conditional if/endif can be removed at all.
   kmp_int32 last_upper;
 #endif /* KMP_OS_WINDOWS */
 } dispatch_private_info32_t;
 
 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
+  kmp_lock_t *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).
 
   struct KMP_ALIGN(32) {
     kmp_int64 parm1;
     kmp_int64 parm2;
     kmp_int64 parm3;
     kmp_int64 parm4;
   };
 
   kmp_uint64 ordered_lower;
   kmp_uint64 ordered_upper;
 #if KMP_OS_WINDOWS
-  // This var can be placed in the hole between 'tc' and 'parm1', instead of
-  // 'static_steal_counter'. It would be nice to measure execution times.
-  // Conditional if/endif can be removed at all.
   kmp_int64 last_upper;
 #endif /* KMP_OS_WINDOWS */
 } dispatch_private_info64_t;
 #else /* KMP_STATIC_STEAL_ENABLED */
 typedef struct KMP_ALIGN_CACHE dispatch_private_info32 {
   kmp_int32 lb;
   kmp_int32 ub;
   kmp_int32 st;

 
 typedef struct KMP_ALIGN_CACHE dispatch_private_info {
   union private_info {
     dispatch_private_info32_t p32;
     dispatch_private_info64_t p64;
   } u;
   enum sched_type schedule; /* scheduling algorithm */
   kmp_sched_flags_t flags; /* flags (e.g., ordered, nomerge, etc.) */
+  std::atomic<kmp_uint32> steal_flag; // static_steal only, state of a buffer
   kmp_int32 ordered_bumped;
-  // To retain the structure size after making ordered_iteration scalar
-  kmp_int32 ordered_dummy[KMP_MAX_ORDERED - 3];
   // Stack of buffers for nest of serial regions
   struct dispatch_private_info *next;
   kmp_int32 type_size; /* the size of types in private_info */
 #if KMP_USE_HIER_SCHED
   kmp_int32 hier_id;
   void *parent; /* hierarchical scheduling parent pointer */
 #endif
   enum cons_type pushed_ws;
 } dispatch_private_info_t;
 
 typedef struct dispatch_shared_info32 {
   /* chunk index under dynamic, number of idle threads under static-steal;
      iteration index otherwise */
   volatile kmp_uint32 iteration;
-  volatile kmp_uint32 num_done;
+  volatile kmp_int32 num_done;
   volatile kmp_uint32 ordered_iteration;
   // Dummy to retain the structure size after making ordered_iteration scalar
   kmp_int32 ordered_dummy[KMP_MAX_ORDERED - 1];
 } dispatch_shared_info32_t;
 
 typedef struct dispatch_shared_info64 {
   /* chunk index under dynamic, number of idle threads under static-steal;
      iteration index otherwise */
   volatile kmp_uint64 iteration;
-  volatile kmp_uint64 num_done;
+  volatile kmp_int64 num_done;
   volatile kmp_uint64 ordered_iteration;
   // Dummy to retain the structure size after making ordered_iteration scalar
   kmp_int64 ordered_dummy[KMP_MAX_ORDERED - 3];
 } dispatch_shared_info64_t;
 
 typedef struct dispatch_shared_info {
   union shared_info {
     dispatch_shared_info32_t s32;
typedef struct kmp_disp {
   void (*th_deo_fcn)(int *gtid, int *cid, ident_t *);
   /* Vector for END ORDERED SECTION */
   void (*th_dxo_fcn)(int *gtid, int *cid, ident_t *);
 
   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_uint32 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
   kmp_int64 *th_doacross_info; // info on loop bounds
 #if KMP_USE_INTERNODE_ALIGNMENT
   char more_padding[INTERNODE_CACHE_LINE];
 #endif
 } kmp_disp_t;
 

openmp/runtime/src/kmp_dispatch.h

template <typename T> struct dispatch_private_infoXX_template {
   typedef typename traits_t<T>::unsigned_t UT;
   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
+  kmp_lock_t *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).
 
template <typename T> struct KMP_ALIGN_CACHE dispatch_private_info_template {
   // duplicate alignment here, otherwise size of structure is not correct in our
   // compiler
   union KMP_ALIGN_CACHE private_info_tmpl {
     dispatch_private_infoXX_template<T> p;
     dispatch_private_info64_t p64;
   } u;
   enum sched_type schedule; /* scheduling algorithm */
   kmp_sched_flags_t flags; /* flags (e.g., ordered, nomerge, etc.) */
+  std::atomic<kmp_uint32> steal_flag; // static_steal only, state of a buffer
   kmp_uint32 ordered_bumped;
-  // to retain the structure size after making order
-  kmp_int32 ordered_dummy[KMP_MAX_ORDERED - 3];
   dispatch_private_info *next; /* stack of buffers for nest of serial regions */
   kmp_uint32 type_size;
 #if KMP_USE_HIER_SCHED
   kmp_int32 hier_id;
   kmp_hier_top_unit_t<T> *hier_parent;
   // member functions
   kmp_int32 get_hier_id() const { return hier_id; }
   kmp_hier_top_unit_t<T> *get_parent() { return hier_parent; }
 #endif
   enum cons_type pushed_ws;
 };
 
 // replaces dispatch_shared_info{32,64} structures and
 // dispatch_shared_info{32,64}_t types
 template <typename T> struct dispatch_shared_infoXX_template {
   typedef typename traits_t<T>::unsigned_t UT;
+  typedef typename traits_t<T>::signed_t ST;
   /* chunk index under dynamic, number of idle threads under static-steal;
      iteration index otherwise */
   volatile UT iteration;
-  volatile UT num_done;
+  volatile ST num_done;
   volatile UT ordered_iteration;
   // to retain the structure size making ordered_iteration scalar
   UT ordered_dummy[KMP_MAX_ORDERED - 3];
 };
 
 // replaces dispatch_shared_info structure and dispatch_shared_info_t type
 template <typename T> struct dispatch_shared_info_template {
   typedef typename traits_t<T>::unsigned_t UT;

openmp/runtime/src/kmp_dispatch.cpp

static inline int __kmp_get_monotonicity(ident_t *loc, enum sched_type schedule,
   else if (SCHEDULE_HAS_NONMONOTONIC(schedule))
     monotonicity = SCHEDULE_NONMONOTONIC;
   else if (SCHEDULE_HAS_MONOTONIC(schedule))
     monotonicity = SCHEDULE_MONOTONIC;
 
   return monotonicity;
 }
 
+#if KMP_STATIC_STEAL_ENABLED
+enum { // values for steal_flag (possible states of private per-loop buffer)
+  UNUSED = 0,
+  CLAIMED = 1, // owner thread started initialization
+  READY = 2, // available for stealing
+  THIEF = 3 // finished by owner, or claimed by thief
+  // possible state changes:
+  // 0 -> 1 owner only, sync
+  // 0 -> 3 thief only, sync
+  // 1 -> 2 owner only, async
+  // 2 -> 3 owner only, async
+  // 3 -> 2 owner only, async
+  // 3 -> 0 last thread finishing the loop, async
+};
+#endif
+
 // 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
 // to the scheduling (often the number of threads in a team, but not always if
 // hierarchical scheduling is used).  tid is the id of the thread calling
 // the function within the group of nproc threads.  It will have a value
 // between 0 and nproc - 1.  This is often just the thread id within a team, but
 // is not necessarily the case when using hierarchical scheduling.
if (schedule == kmp_sch_static) {
     schedule = __kmp_static;
   } else {
     if (schedule == kmp_sch_runtime) {
       // 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(loc, schedule, use_hier);
       schedule = SCHEDULE_WITHOUT_MODIFIERS(schedule);
+      if (pr->flags.ordered) // correct monotonicity for ordered loop if needed
+        monotonicity = SCHEDULE_MONOTONIC;
       // Detail the schedule if needed (global controls are differentiated
       // appropriately)
       if (schedule == kmp_sch_guided_chunked) {
         schedule = __kmp_guided;
       } else if (schedule == kmp_sch_static) {
         schedule = __kmp_static;
       }
       // Use the chunk size specified by OMP_SCHEDULE (or default if not
if (active) {
     if (pr->flags.ordered) {
       pr->ordered_bumped = 0;
       pr->u.p.ordered_lower = 1;
       pr->u.p.ordered_upper = 0;
     }
   }
 
   switch (schedule) {
-#if (KMP_STATIC_STEAL_ENABLED)
+#if KMP_STATIC_STEAL_ENABLED
   case kmp_sch_static_steal: {
     T ntc, init;
 
     KD_TRACE(100,
              ("__kmp_dispatch_init_algorithm: T#%d kmp_sch_static_steal case\n",
               gtid));
 
     ntc = (tc % chunk ? 1 : 0) + tc / chunk;
     if (nproc > 1 && ntc >= nproc) {
       KMP_COUNT_BLOCK(OMP_LOOP_STATIC_STEAL);
       T id = tid;
       T small_chunk, extras;
-
+      kmp_uint32 old = UNUSED;
+      int claimed = pr->steal_flag.compare_exchange_strong(old, CLAIMED);
+      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-private-buffer lock,
+        // free memory in __kmp_dispatch_next when status==0.
+        pr->u.p.steal_lock = (kmp_lock_t *)__kmp_allocate(sizeof(kmp_lock_t));
+        __kmp_init_lock(pr->u.p.steal_lock);
+      }
       small_chunk = ntc / nproc;
       extras = ntc % nproc;
 
       init = id * small_chunk + (id < extras ? id : extras);
       pr->u.p.count = init;
+      if (claimed) { // are we succeeded in claiming own buffer?
         pr->u.p.ub = init + small_chunk + (id < extras ? 1 : 0);
-
-      pr->u.p.parm2 = lb;
+        // Other threads will inspect steal_flag when searching for a victim.
+        // READY means other threads may steal from this thread from now on.
+        KMP_ATOMIC_ST_REL(&pr->steal_flag, READY);
+      } else {
+        // other thread has stolen whole our range
+        KMP_DEBUG_ASSERT(pr->steal_flag == THIEF);
+        pr->u.p.ub = init; // mark there is no iterations to work on
+      }
+      pr->u.p.parm2 = ntc; // save number of chunks
       // 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);
+      // nproc (just a heuristics, could be optimized later on).
+      pr->u.p.parm3 = 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(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(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));
       goto dynamic_init;
if (!active) {
     /* What happens when number of threads changes, need to resize buffer? */
     pr = reinterpret_cast<dispatch_private_info_template<T> *>(
         &th->th.th_dispatch
              ->th_disp_buffer[my_buffer_index % __kmp_dispatch_num_buffers]);
     sh = reinterpret_cast<dispatch_shared_info_template<T> volatile *>(
         &team->t.t_disp_buffer[my_buffer_index % __kmp_dispatch_num_buffers]);
     KD_TRACE(10, ("__kmp_dispatch_init: T#%d my_buffer_index:%d\n", gtid,
                   my_buffer_index));
+    if (sh->buffer_index != my_buffer_index) { // too many loops in progress?
+      KD_TRACE(100, ("__kmp_dispatch_init: T#%d before wait: my_buffer_index:%d"
+                     " sh->buffer_index:%d\n",
+                     gtid, my_buffer_index, sh->buffer_index));
+      __kmp_wait<kmp_uint32>(&sh->buffer_index, my_buffer_index,
+                             __kmp_eq<kmp_uint32> USE_ITT_BUILD_ARG(NULL));
+      // Note: KMP_WAIT() cannot be used there: buffer index and
+      // my_buffer_index are *always* 32-bit integers.
+      KD_TRACE(100, ("__kmp_dispatch_init: T#%d after wait: my_buffer_index:%d "
+                     "sh->buffer_index:%d\n",
+                     gtid, my_buffer_index, sh->buffer_index));
+    }
   }
 
   __kmp_dispatch_init_algorithm(loc, gtid, pr, schedule, lb, ub, st,
 #if USE_ITT_BUILD
                                 &cur_chunk,
 #endif
                                 chunk, (T)th->th.th_team_nproc,
                                 (T)th->th.th_info.ds.ds_tid);
   if (active) {
     if (pr->flags.ordered == 0) {
       th->th.th_dispatch->th_deo_fcn = __kmp_dispatch_deo_error;
       th->th.th_dispatch->th_dxo_fcn = __kmp_dispatch_dxo_error;
     } else {
       th->th.th_dispatch->th_deo_fcn = __kmp_dispatch_deo<UT>;
       th->th.th_dispatch->th_dxo_fcn = __kmp_dispatch_dxo<UT>;
     }
-  }
-
-  if (active) {
-    /* The name of this buffer should be my_buffer_index when it's free to use
-     * it */
-
-    KD_TRACE(100, ("__kmp_dispatch_init: T#%d before wait: my_buffer_index:%d "
-                   "sh->buffer_index:%d\n",
-                   gtid, my_buffer_index, sh->buffer_index));
-    __kmp_wait<kmp_uint32>(&sh->buffer_index, my_buffer_index,
-                           __kmp_eq<kmp_uint32> USE_ITT_BUILD_ARG(NULL));
-    // Note: KMP_WAIT() cannot be used there: buffer index and
-    // my_buffer_index are *always* 32-bit integers.
-    KMP_MB(); /* is this necessary? */
-    KD_TRACE(100, ("__kmp_dispatch_init: T#%d after wait: my_buffer_index:%d "
-                   "sh->buffer_index:%d\n",
-                   gtid, my_buffer_index, sh->buffer_index));
-
     th->th.th_dispatch->th_dispatch_pr_current = (dispatch_private_info_t *)pr;
     th->th.th_dispatch->th_dispatch_sh_current =
         CCAST(dispatch_shared_info_t *, (volatile dispatch_shared_info_t *)sh);
 #if USE_ITT_BUILD
     if (pr->flags.ordered) {
       __kmp_itt_ordered_init(gtid);
     }
     // Report loop metadata
buff = __kmp_str_format(
         traits_t<T>::spec, traits_t<T>::spec, traits_t<T>::spec);
     KD_TRACE(10, (buff, gtid, pr->schedule, pr->flags.ordered, pr->u.p.lb,
                   pr->u.p.ub, pr->u.p.st, pr->u.p.tc, pr->u.p.count,
                   pr->u.p.ordered_lower, pr->u.p.ordered_upper, pr->u.p.parm1,
                   pr->u.p.parm2, pr->u.p.parm3, pr->u.p.parm4));
     __kmp_str_free(&buff);
   }
 #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 (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 )
-
 #if OMPT_SUPPORT && OMPT_OPTIONAL
   if (ompt_enabled.ompt_callback_work) {
     ompt_team_info_t *team_info = __ompt_get_teaminfo(0, NULL);
     ompt_task_info_t *task_info = __ompt_get_task_info_object(0);
     ompt_callbacks.ompt_callback(ompt_callback_work)(
         ompt_work_loop, ompt_scope_begin, &(team_info->parallel_data),
         &(task_info->task_data), pr->u.p.tc, OMPT_LOAD_RETURN_ADDRESS(gtid));
   }

 template <typename UT>
 static void __kmp_dispatch_finish_chunk(int gtid, ident_t *loc) {
   typedef typename traits_t<UT>::signed_t ST;
   __kmp_assert_valid_gtid(gtid);
   kmp_info_t *th = __kmp_threads[gtid];
 
   KD_TRACE(100, ("__kmp_dispatch_finish_chunk: T#%d called\n", gtid));
   if (!th->th.th_team->t.t_serialized) {
-    //        int cid;
     dispatch_private_info_template<UT> *pr =
         reinterpret_cast<dispatch_private_info_template<UT> *>(
             th->th.th_dispatch->th_dispatch_pr_current);
     dispatch_shared_info_template<UT> volatile *sh =
         reinterpret_cast<dispatch_shared_info_template<UT> volatile *>(
             th->th.th_dispatch->th_dispatch_sh_current);
     KMP_DEBUG_ASSERT(pr);
     KMP_DEBUG_ASSERT(sh);
     KMP_DEBUG_ASSERT(th->th.th_dispatch ==
                      &th->th.th_team->t.t_dispatch[th->th.th_info.ds.ds_tid]);
 
-    //        for (cid = 0; cid < KMP_MAX_ORDERED; ++cid) {
     UT lower = pr->u.p.ordered_lower;
     UT upper = pr->u.p.ordered_upper;
     UT inc = upper - lower + 1;
 
     if (pr->ordered_bumped == inc) {
       KD_TRACE(
           1000,
           ("__kmp_dispatch_finish: T#%d resetting ordered_bumped to zero\n",
if (pr->u.p.tc == 0) {
     KD_TRACE(10,
              ("__kmp_dispatch_next_algorithm: T#%d early exit trip count is "
               "zero status:%d\n",
               gtid, status));
     return 0;
   }
 
   switch (pr->schedule) {
-#if (KMP_STATIC_STEAL_ENABLED)
+#if KMP_STATIC_STEAL_ENABLED
   case kmp_sch_static_steal: {
     T chunk = pr->u.p.parm1;
-
+    UT nchunks = pr->u.p.parm2;
     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 = pr->u.p.th_steal_lock;
+      // use lock for 8-byte induction variable.
+      // TODO (optional): check presence and use 16-byte CAS
+      kmp_lock_t *lck = pr->u.p.steal_lock;
       KMP_DEBUG_ASSERT(lck != NULL);
       if (pr->u.p.count < (UT)pr->u.p.ub) {
+        KMP_DEBUG_ASSERT(pr->steal_flag == READY);
         __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;
+        kmp_lock_t *lckv; // victim buffer's lock
         T while_limit = pr->u.p.parm3;
         T 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
+        KMP_ATOMIC_ST_REL(&pr->steal_flag, THIEF); // mark self buffer inactive
         while ((!status) && (while_limit != ++while_index)) {
-          dispatch_private_info_template<T> *victim;
+          dispatch_private_info_template<T> *v;
           T remaining;
-          T victimIdx = pr->u.p.parm4;
-          T oldVictimIdx = victimIdx ? victimIdx - 1 : nproc - 1;
-          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_disp_buffer[idx]);
-            KMP_DEBUG_ASSERT(victim);
+          T victimId = pr->u.p.parm4;
+          T oldVictimId = victimId ? victimId - 1 : nproc - 1;
+          v = reinterpret_cast<dispatch_private_info_template<T> *>(
+              &team->t.t_dispatch[victimId].th_disp_buffer[idx]);
+          KMP_DEBUG_ASSERT(v);
+          while ((v == pr || KMP_ATOMIC_LD_RLX(&v->steal_flag) == THIEF) &&
+                 oldVictimId != victimId) {
+            victimId = (victimId + 1) % nproc;
+            v = reinterpret_cast<dispatch_private_info_template<T> *>(
+                &team->t.t_dispatch[victimId].th_disp_buffer[idx]);
+            KMP_DEBUG_ASSERT(v);
           }
-          if (victim == pr || id != victim->u.p.static_steal_counter) {
+          if (v == pr || KMP_ATOMIC_LD_RLX(&v->steal_flag) == THIEF) {
             continue; // try once more (nproc attempts in total)
-            // no victim is ready yet to participate in stealing
-            // 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 = victim->u.p.th_steal_lock;
-          KMP_ASSERT(lck != NULL);
+          if (KMP_ATOMIC_LD_RLX(&v->steal_flag) == UNUSED) {
+            kmp_uint32 old = UNUSED;
+            // try to steal whole range from inactive victim
+            status = v->steal_flag.compare_exchange_strong(old, THIEF);
+            if (status) {
+              // initialize self buffer with victim's whole range of chunks
+              T id = victimId;
+              T small_chunk, extras;
+              small_chunk = nchunks / nproc; // chunks per thread
+              extras = nchunks % nproc;
+              init = id * small_chunk + (id < extras ? id : extras);
               __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) {
+              pr->u.p.count = init + 1; // exclude one we execute immediately
+              pr->u.p.ub = init + small_chunk + (id < extras ? 1 : 0);
               __kmp_release_lock(lck, gtid);
-            pr->u.p.parm4 = (victimIdx + 1) % nproc; // next victim
-            continue; // not enough chunks to steal
+              pr->u.p.parm4 = (id + 1) % nproc; // remember neighbour tid
+              // no need to reinitialize other thread invariants: lb, st, etc.
+#ifdef KMP_DEBUG
+              {
+                char *buff;
+                // create format specifiers before the debug output
+                buff = __kmp_str_format(
+                    "__kmp_dispatch_next: T#%%d stolen chunks from T#%%d, "
+                    "count:%%%s ub:%%%s\n",
+                    traits_t<UT>::spec, traits_t<T>::spec);
+                KD_TRACE(10, (buff, gtid, id, pr->u.p.count, pr->u.p.ub));
+                __kmp_str_free(&buff);
               }
-          // stealing succeeded, reduce victim's ub by 1/4 of undone chunks or
-          // by 1
-          if (remaining > 3) {
+#endif
+              // activate non-empty buffer and let others steal from us
+              if (pr->u.p.count < (UT)pr->u.p.ub)
+                KMP_ATOMIC_ST_REL(&pr->steal_flag, READY);
+              break;
+            }
+          }
+          if (KMP_ATOMIC_LD_RLX(&v->steal_flag) != READY ||
+              v->u.p.count >= (UT)v->u.p.ub) {
+            pr->u.p.parm4 = (victimId + 1) % nproc; // shift start victim tid
+            continue; // no chunks to steal, try next victim
+          }
+          lckv = v->u.p.steal_lock;
+          KMP_ASSERT(lckv != NULL);
+          __kmp_acquire_lock(lckv, gtid);
+          limit = v->u.p.ub; // keep initial ub
+          if (v->u.p.count >= limit) {
+            __kmp_release_lock(lckv, gtid);
+            pr->u.p.parm4 = (victimId + 1) % nproc; // shift start victim tid
+            continue; // no chunks to steal, try next victim
+          }
+
+          // stealing succeded, reduce victim's ub by 1/4 of undone chunks
+          // TODO: is this heuristics good enough??
+          remaining = limit - v->u.p.count;
+          if (remaining > 7) {
             // steal 1/4 of remaining
             KMP_COUNT_DEVELOPER_VALUE(FOR_static_steal_stolen, remaining >> 2);
-            init = (victim->u.p.ub -= (remaining >> 2));
+            init = (v->u.p.ub -= (remaining >> 2));
           } else {
-            // steal 1 chunk of 2 or 3 remaining
+            // steal 1 chunk of 1..7 remaining
             KMP_COUNT_DEVELOPER_VALUE(FOR_static_steal_stolen, 1);
-            init = (victim->u.p.ub -= 1);
+            init = (v->u.p.ub -= 1);
           }
-          __kmp_release_lock(lck, gtid);
-
+          __kmp_release_lock(lckv, gtid);
+#ifdef KMP_DEBUG
+          {
+            char *buff;
+            // create format specifiers before the debug output
+            buff = __kmp_str_format(
+                "__kmp_dispatch_next: T#%%d stolen chunks from T#%%d, "
+                "count:%%%s ub:%%%s\n",
+                traits_t<UT>::spec, traits_t<UT>::spec);
+            KD_TRACE(10, (buff, gtid, victimId, init, limit));
+            __kmp_str_free(&buff);
+          }
+#endif
           KMP_DEBUG_ASSERT(init + 1 <= limit);
-          pr->u.p.parm4 = victimIdx; // remember victim to steal from
+          pr->u.p.parm4 = victimId; // 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(pr->u.p.th_steal_lock, gtid);
+          // now update own count and ub with stolen range excluding init chunk
+          __kmp_acquire_lock(lck, gtid);
           pr->u.p.count = init + 1;
           pr->u.p.ub = limit;
-          __kmp_release_lock(pr->u.p.th_steal_lock, gtid);
+          __kmp_release_lock(lck, gtid);
+          // activate non-empty buffer and let others steal from us
+          if (init + 1 < limit)
+            KMP_ATOMIC_ST_REL(&pr->steal_flag, READY);
         } // while (search for victim)
       } // if (try to find victim and steal)
     } else {
       // 4-byte induction variable, use 8-byte CAS for pair (count, ub)
+      // as all operations on pair (count, ub) must be done atomically
       typedef union {
         struct {
           UT count;
           T ub;
         } p;
         kmp_int64 b;
       } union_i4;
-      // All operations on 'count' or 'ub' must be combined atomically
-      // together.
-      {
-        union_i4 vold, vnew;
+      if (pr->u.p.count < (UT)pr->u.p.ub) {
+        KMP_DEBUG_ASSERT(pr->steal_flag == READY);
         vold.b = *(volatile kmp_int64 *)(&pr->u.p.count);
-        vnew = vold;
-        vnew.p.count++;
-        while (!KMP_COMPARE_AND_STORE_ACQ64(
+        vnew.b = vold.b;
+        vnew.p.count++; // get chunk from head of self range
+        while (!KMP_COMPARE_AND_STORE_REL64(
             (volatile kmp_int64 *)&pr->u.p.count,
             *VOLATILE_CAST(kmp_int64 *) & vold.b,
             *VOLATILE_CAST(kmp_int64 *) & vnew.b)) {
           KMP_CPU_PAUSE();
           vold.b = *(volatile kmp_int64 *)(&pr->u.p.count);
-          vnew = vold;
+          vnew.b = vold.b;
           vnew.p.count++;
         }
-        vnew = vold;
-        init = vnew.p.count;
-        status = (init < (UT)vnew.p.ub);
+        init = vold.p.count;
+        status = (init < (UT)vold.p.ub);
+      } else {
+        status = 0; // no own chunks
       }
-
-      if (!status) {
-        kmp_info_t **other_threads = team->t.t_threads;
+      if (!status) { // try to steal
         T while_limit = pr->u.p.parm3;
         T 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
+        KMP_ATOMIC_ST_REL(&pr->steal_flag, THIEF); // mark self buffer inactive
         while ((!status) && (while_limit != ++while_index)) {
-          dispatch_private_info_template<T> *victim;
-          union_i4 vold, vnew;
+          dispatch_private_info_template<T> *v;
           T remaining;
-          T victimIdx = pr->u.p.parm4;
-          T oldVictimIdx = victimIdx ? victimIdx - 1 : nproc - 1;
-          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_disp_buffer[idx]);
-            KMP_DEBUG_ASSERT(victim);
+          T victimId = pr->u.p.parm4;
+          T oldVictimId = victimId ? victimId - 1 : nproc - 1;
+          v = reinterpret_cast<dispatch_private_info_template<T> *>(
+              &team->t.t_dispatch[victimId].th_disp_buffer[idx]);
+          KMP_DEBUG_ASSERT(v);
+          while ((v == pr || KMP_ATOMIC_LD_RLX(&v->steal_flag) == THIEF) &&
+                 oldVictimId != victimId) {
+            victimId = (victimId + 1) % nproc;
+            v = reinterpret_cast<dispatch_private_info_template<T> *>(
+                &team->t.t_dispatch[victimId].th_disp_buffer[idx]);
+            KMP_DEBUG_ASSERT(v);
           }
-          if (victim == pr || id != victim->u.p.static_steal_counter) {
+          if (v == pr || KMP_ATOMIC_LD_RLX(&v->steal_flag) == THIEF) {
             continue; // try once more (nproc attempts in total)
-            // no victim is ready yet to participate in stealing
-            // 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 ||
-                (remaining = vnew.p.ub - vnew.p.count) < 2) {
-              pr->u.p.parm4 = (victimIdx + 1) % nproc; // shift start victim id
-              break; // not enough chunks to steal, goto next victim
-            }
-            if (remaining > 3) {
-              // try to steal 1/4 of remaining
-              vnew.p.ub -= remaining >> 2;
+          if (KMP_ATOMIC_LD_RLX(&v->steal_flag) == UNUSED) {
+            kmp_uint32 old = UNUSED;
+            // try to steal whole range from inactive victim
+            status = v->steal_flag.compare_exchange_strong(old, THIEF);
+            if (status) {
+              // initialize self buffer with victim's whole range of chunks
+              T id = victimId;
+              T small_chunk, extras;
+              small_chunk = nchunks / nproc; // chunks per thread
+              extras = nchunks % nproc;
+              init = id * small_chunk + (id < extras ? id : extras);
+              vnew.p.count = init + 1;
+              vnew.p.ub = init + small_chunk + (id < extras ? 1 : 0);
+              // write pair (count, ub) at once atomically
+#if KMP_ARCH_X86
+              KMP_XCHG_FIXED64((volatile kmp_int64 *)(&pr->u.p.count), vnew.b);
+#else
+              *(volatile kmp_int64 *)(&pr->u.p.count) = vnew.b;
+#endif
+              pr->u.p.parm4 = (id + 1) % nproc; // remember neighbour tid
+              // no need to initialize other thread invariants: lb, st, etc.
+#ifdef KMP_DEBUG
+              {
+                char *buff;
+                // create format specifiers before the debug output
+                buff = __kmp_str_format(
+                    "__kmp_dispatch_next: T#%%d stolen chunks from T#%%d, "
+                    "count:%%%s ub:%%%s\n",
+                    traits_t<UT>::spec, traits_t<T>::spec);
+                KD_TRACE(10, (buff, gtid, id, pr->u.p.count, pr->u.p.ub));
+                __kmp_str_free(&buff);
+              }
+#endif
+              // activate non-empty buffer and let others steal from us
+              if (pr->u.p.count < (UT)pr->u.p.ub)
+                KMP_ATOMIC_ST_REL(&pr->steal_flag, READY);
+              break;
+            }
+          while (1) { // CAS loop with check if victim still has enough chunks
+            // many threads may be stealing concurrently from same victim
+            vold.b = *(volatile kmp_int64 *)(&v->u.p.count);
+            if (KMP_ATOMIC_LD_ACQ(&v->steal_flag) != READY ||
+                vold.p.count >= (UT)vold.p.ub) {
+              pr->u.p.parm4 = (victimId + 1) % nproc; // shift start victim id
+              break; // no chunks to steal, try next victim
+            }
+            vnew.b = vold.b;
+            remaining = vold.p.ub - vold.p.count;
+            // TODO: is this heuristics good enough??
+            if (remaining > 7) {
+              vnew.p.ub -= remaining >> 2; // steal from tail of victim's range
             } else {
-              vnew.p.ub -= 1; // steal 1 chunk of 2 or 3 remaining
+              vnew.p.ub -= 1; // steal 1 chunk of 1..7 remaining
             }
             KMP_DEBUG_ASSERT((vnew.p.ub - 1) * (UT)chunk <= trip);
-            // TODO: Should this be acquire or release?
-            if (KMP_COMPARE_AND_STORE_ACQ64(
-                    (volatile kmp_int64 *)&victim->u.p.count,
+            if (KMP_COMPARE_AND_STORE_REL64(
+                    (volatile kmp_int64 *)&v->u.p.count,
                     *VOLATILE_CAST(kmp_int64 *) & vold.b,
                     *VOLATILE_CAST(kmp_int64 *) & vnew.b)) {
-              // stealing succeeded
+              // stealing succedded
+#ifdef KMP_DEBUG
+              {
+                char *buff;
+                // create format specifiers before the debug output
+                buff = __kmp_str_format(
+                    "__kmp_dispatch_next: T#%%d stolen chunks from T#%%d, "
+                    "count:%%%s ub:%%%s\n",
+                    traits_t<T>::spec, traits_t<T>::spec);
+                KD_TRACE(10, (buff, gtid, victimId, vnew.p.ub, vold.p.ub));
+                __kmp_str_free(&buff);
+              }
+#endif
               KMP_COUNT_DEVELOPER_VALUE(FOR_static_steal_stolen,
                                         vold.p.ub - vnew.p.ub);
               status = 1;
-              while_index = 0;
+              pr->u.p.parm4 = victimId; // keep victim id
               // now update own count and ub
               init = vnew.p.ub;
               vold.p.count = init + 1;
 #if KMP_ARCH_X86
               KMP_XCHG_FIXED64((volatile kmp_int64 *)(&pr->u.p.count), vold.b);
 #else
               *(volatile kmp_int64 *)(&pr->u.p.count) = vold.b;
 #endif
+              // activate non-empty buffer and let others steal from us
+              if (vold.p.count < (UT)vold.p.ub)
+                KMP_ATOMIC_ST_REL(&pr->steal_flag, READY);
               break;
             } // if (check CAS result)
             KMP_CPU_PAUSE(); // CAS failed, repeatedly attempt
           } // while (try to steal from particular victim)
         } // while (search for victim)
       } // if (try to find victim and steal)
     } // if (4-byte induction variable)
     if (!status) {
       *p_lb = 0;
       *p_ub = 0;
       if (p_st != NULL)
         *p_st = 0;
     } else {
-      start = pr->u.p.parm2;
+      start = pr->u.p.lb;
       init *= chunk;
       limit = chunk + init - 1;
       incr = pr->u.p.st;
       KMP_COUNT_DEVELOPER_VALUE(FOR_static_steal_chunks, 1);
 
       KMP_DEBUG_ASSERT(init <= trip);
+      // keep track of done chunks for possible early exit from stealing
+      // TODO: count executed chunks locally with rare update of shared location
+      // test_then_inc<ST>((volatile ST *)&sh->u.s.iteration);
       if ((last = (limit >= trip)) != 0)
         limit = trip;
       if (p_st != NULL)
         *p_st = incr;
 
       if (incr == 1) {
         *p_lb = start + init;
         *p_ub = start + limit;
       } else {
         *p_lb = start + init * incr;
         *p_ub = start + limit * incr;
       }
-
-      if (pr->flags.ordered) {
-        pr->u.p.ordered_lower = init;
-        pr->u.p.ordered_upper = limit;
-      } // if
     } // if
     break;
   } // case
-#endif // ( KMP_STATIC_STEAL_ENABLED )
+#endif // KMP_STATIC_STEAL_ENABLED
   case kmp_sch_static_balanced: {
     KD_TRACE(
         10,
         ("__kmp_dispatch_next_algorithm: T#%d kmp_sch_static_balanced case\n",
          gtid));
     /* check if thread has any iteration to do */
     if ((status = !pr->u.p.count) != 0) {
       pr->u.p.count = 1;
if (pr->flags.use_hier)
       status = sh->hier->next(loc, gtid, pr, &last, p_lb, p_ub, p_st);
     else
 #endif // KMP_USE_HIER_SCHED
       status = __kmp_dispatch_next_algorithm<T>(gtid, pr, sh, &last, p_lb, p_ub,
                                                 p_st, th->th.th_team_nproc,
                                                 th->th.th_info.ds.ds_tid);
     // status == 0: no more iterations to execute
     if (status == 0) {
-      UT num_done;
-
-      num_done = test_then_inc<ST>((volatile ST *)&sh->u.s.num_done);
+      ST num_done;
+      num_done = test_then_inc<ST>(&sh->u.s.num_done);
 #ifdef KMP_DEBUG
       {
         char *buff;
         // create format specifiers before the debug output
         buff = __kmp_str_format(
             "__kmp_dispatch_next: T#%%d increment num_done:%%%s\n",
-            traits_t<UT>::spec);
+            traits_t<ST>::spec);
         KD_TRACE(10, (buff, gtid, sh->u.s.num_done));
         __kmp_str_free(&buff);
       }
 #endif
 
 #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) {
+      if (num_done == th->th.th_team_nproc - 1) {
+#if KMP_STATIC_STEAL_ENABLED
+        if (pr->schedule == kmp_sch_static_steal) {
           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) {
             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;
+                    &team->t.t_dispatch[i].th_disp_buffer[idx]);
+            KMP_ASSERT(buf->steal_flag == THIEF); // buffer must be inactive
+            KMP_ATOMIC_ST_RLX(&buf->steal_flag, UNUSED);
+            if (traits_t<T>::type_size > 4) {
+              // destroy locks used for stealing
+              kmp_lock_t *lck = buf->u.p.steal_lock;
               KMP_ASSERT(lck != NULL);
               __kmp_destroy_lock(lck);
               __kmp_free(lck);
-            buf->u.p.th_steal_lock = NULL;
+              buf->u.p.steal_lock = NULL;
+            }
           }
         }
 #endif
-        /* NOTE: release this buffer to be reused */
+        /* NOTE: release shared buffer to be reused */
 
         KMP_MB(); /* Flush all pending memory write invalidates.  */
 
         sh->u.s.num_done = 0;
         sh->u.s.iteration = 0;
 
         /* TODO replace with general release procedure? */
         if (pr->flags.ordered) {
           sh->u.s.ordered_iteration = 0;
         }
 
-        KMP_MB(); /* Flush all pending memory write invalidates.  */
-
         sh->buffer_index += __kmp_dispatch_num_buffers;
         KD_TRACE(100, ("__kmp_dispatch_next: T#%d change buffer_index:%d\n",
                        gtid, sh->buffer_index));
 
         KMP_MB(); /* Flush all pending memory write invalidates.  */
 
       } // if
       if (__kmp_env_consistency_check) {

openmp/runtime/src/kmp_dispatch_hier.h

default:
       // don't use the core_barrier_impl for more than 8 threads
       KMP_ASSERT(0);
     }
     return wait_val;
   }
 
 public:
   static void reset_private(kmp_int32 num_active,
                             kmp_hier_private_bdata_t *tdata);
   static void reset_shared(kmp_int32 num_active,
                            kmp_hier_shared_bdata_t<T> *bdata);
   static void barrier(kmp_int32 id, kmp_hier_shared_bdata_t<T> *bdata,
                       kmp_hier_private_bdata_t *tdata);
 };
 
 template <typename T>
 void core_barrier_impl<T>::reset_private(kmp_int32 num_active,
                                          kmp_hier_private_bdata_t *tdata) {
   tdata->num_active = num_active;
   tdata->index = 0;
   tdata->wait_val[0] = tdata->wait_val[1] = get_wait_val(num_active);
 }
 template <typename T>
 void core_barrier_impl<T>::reset_shared(kmp_int32 num_active,
                                         kmp_hier_shared_bdata_t<T> *bdata) {
   bdata->val[0] = bdata->val[1] = 0LL;
   bdata->status[0] = bdata->status[1] = 0LL;
 }
 template <typename T>
 void core_barrier_impl<T>::barrier(kmp_int32 id,
                                    kmp_hier_shared_bdata_t<T> *bdata,
                                    kmp_hier_private_bdata_t *tdata) {
   kmp_uint64 current_index = tdata->index;
   kmp_uint64 next_index = 1 - current_index;
   kmp_uint64 current_wait_value = tdata->wait_val[current_index];
   kmp_uint64 next_wait_value =
       (current_wait_value ? 0 : get_wait_val(tdata->num_active));
   KD_TRACE(10, ("core_barrier_impl::barrier(): T#%d current_index:%llu "
                 "next_index:%llu curr_wait:%llu next_wait:%llu\n",
                 __kmp_get_gtid(), current_index, next_index, current_wait_value,
                 next_wait_value));
   char v = (current_wait_value ? '\1' : '\0');
   (RCAST(volatile char *, &(bdata->val[current_index])))[id] = v;
   __kmp_wait<kmp_uint64>(&(bdata->val[current_index]), current_wait_value,
                          __kmp_eq<kmp_uint64> USE_ITT_BUILD_ARG(NULL));
   tdata->wait_val[current_index] = next_wait_value;
   tdata->index = next_index;
 }
 
 // Counter barrier implementation
 // Can be used in a unit with arbitrary number of active threads
 template <typename T> class counter_barrier_impl {
 public:
   static void reset_private(kmp_int32 num_active,
                             kmp_hier_private_bdata_t *tdata);
   static void reset_shared(kmp_int32 num_active,
                            kmp_hier_shared_bdata_t<T> *bdata);
   static void barrier(kmp_int32 id, kmp_hier_shared_bdata_t<T> *bdata,
                       kmp_hier_private_bdata_t *tdata);
 };
 
 template <typename T>
 void counter_barrier_impl<T>::reset_private(kmp_int32 num_active,
                                             kmp_hier_private_bdata_t *tdata) {
   tdata->num_active = num_active;
   tdata->index = 0;
   tdata->wait_val[0] = tdata->wait_val[1] = (kmp_uint64)num_active;
 }
 template <typename T>
 void counter_barrier_impl<T>::reset_shared(kmp_int32 num_active,
                                            kmp_hier_shared_bdata_t<T> *bdata) {
   bdata->val[0] = bdata->val[1] = 0LL;
   bdata->status[0] = bdata->status[1] = 0LL;
 }
 template <typename T>
 void counter_barrier_impl<T>::barrier(kmp_int32 id,
                                       kmp_hier_shared_bdata_t<T> *bdata,
                                       kmp_hier_private_bdata_t *tdata) {
   volatile kmp_int64 *val;
   kmp_uint64 current_index = tdata->index;
   kmp_uint64 next_index = 1 - current_index;
   kmp_uint64 current_wait_value = tdata->wait_val[current_index];
   kmp_uint64 next_wait_value = current_wait_value + tdata->num_active;
 
   KD_TRACE(10, ("counter_barrier_impl::barrier(): T#%d current_index:%llu "
                 "next_index:%llu curr_wait:%llu next_wait:%llu\n",
if (active == 1)
       return;
     hier_barrier.zero();
     if (active >= 2 && active <= 8) {
       core_barrier_impl<T>::reset_shared(active, &hier_barrier);
     } else {
       counter_barrier_impl<T>::reset_shared(active, &hier_barrier);
     }
   }
   void reset_private_barrier(kmp_hier_private_bdata_t *tdata) {
     KMP_DEBUG_ASSERT(tdata);
     KMP_DEBUG_ASSERT(active > 0);
     if (active == 1)
       return;
     if (active >= 2 && active <= 8) {
       core_barrier_impl<T>::reset_private(active, tdata);
     } else {
       counter_barrier_impl<T>::reset_private(active, tdata);
     }
   }
   void barrier(kmp_int32 id, kmp_hier_private_bdata_t *tdata) {
     KMP_DEBUG_ASSERT(tdata);
     KMP_DEBUG_ASSERT(active > 0);
     KMP_DEBUG_ASSERT(id >= 0 && id < active);
     if (active == 1) {
       tdata->index = 1 - tdata->index;
       return;
     }
     if (active >= 2 && active <= 8) {
private:
   int next_recurse(ident_t *loc, int gtid, kmp_hier_top_unit_t<T> *current,
                    kmp_int32 *p_last, T *p_lb, T *p_ub, ST *p_st,
                    kmp_int32 previous_id, int hier_level) {
     int status;
     kmp_info_t *th = __kmp_threads[gtid];
     auto parent = current->get_parent();
     bool last_layer = (hier_level == get_num_layers() - 1);
     KMP_DEBUG_ASSERT(th);
     kmp_hier_private_bdata_t *tdata = &(th->th.th_hier_bar_data[hier_level]);
     KMP_DEBUG_ASSERT(current);
     KMP_DEBUG_ASSERT(hier_level >= 0);
     KMP_DEBUG_ASSERT(hier_level < get_num_layers());
     KMP_DEBUG_ASSERT(tdata);
     KMP_DEBUG_ASSERT(parent || last_layer);
 
     KD_TRACE(
         1, ("kmp_hier_t.next_recurse(): T#%d (%d) called\n", gtid, hier_level));
if (previous_id == 0) {
             th->th.th_dispatch->th_dispatch_sh_current);
         nproc = (T)get_top_level_nproc();
       } else {
         // middle layers use the shared buffer inside the kmp_hier_top_unit_t
         // structure
         KD_TRACE(10, ("kmp_hier_t.next_recurse(): T#%d (%d) using hier sh\n",
                       gtid, hier_level));
         my_sh =
             parent->get_curr_sh(th->th.th_hier_bar_data[hier_level + 1].index);
         nproc = (T)parent->get_num_active();
       }
       my_pr = current->get_my_pr();
       KMP_DEBUG_ASSERT(my_sh);
       KMP_DEBUG_ASSERT(my_pr);
       enum sched_type schedule = get_sched(hier_level);
       ST chunk = (ST)get_chunk(hier_level);
       status = __kmp_dispatch_next_algorithm<T>(gtid, my_pr, my_sh,
if (previous_id == 0) {
         __kmp_type_convert(hier_id, &hid);
         status = next_recurse(loc, gtid, parent, &contains_last, &my_lb, &my_ub,
                               &my_st, hid, hier_level + 1);
         KD_TRACE(
             10,
             ("kmp_hier_t.next_recurse(): T#%d (%d) hier_next() returned %d\n",
              gtid, hier_level, status));
         if (status == 1) {
           kmp_hier_private_bdata_t *upper_tdata =
               &(th->th.th_hier_bar_data[hier_level + 1]);
           my_sh = parent->get_curr_sh(upper_tdata->index);
           KD_TRACE(10, ("kmp_hier_t.next_recurse(): T#%d (%d) about to init\n",
                         gtid, hier_level));
           __kmp_dispatch_init_algorithm(loc, gtid, my_pr, schedule,
                                         parent->get_curr_lb(upper_tdata->index),
                                         parent->get_curr_ub(upper_tdata->index),
                                         parent->get_curr_st(upper_tdata->index),
 #if USE_ITT_BUILD

 template <typename T>
 void __kmp_dispatch_init_hierarchy(ident_t *loc, int n,
                                    kmp_hier_layer_e *new_layers,
                                    enum sched_type *new_scheds,
                                    typename traits_t<T>::signed_t *new_chunks,
                                    T lb, T ub,
                                    typename traits_t<T>::signed_t st) {
   int tid, gtid, num_hw_threads, num_threads_per_layer1, active;
-  int my_buffer_index;
+  unsigned int my_buffer_index;
   kmp_info_t *th;
   kmp_team_t *team;
   dispatch_private_info_template<T> *pr;
   dispatch_shared_info_template<T> volatile *sh;
   gtid = __kmp_entry_gtid();
   tid = __kmp_tid_from_gtid(gtid);
 #ifdef KMP_DEBUG
   KD_TRACE(10, ("__kmp_dispatch_init_hierarchy: T#%d called: %d layer(s)\n",

openmp/runtime/src/kmp_settings.cpp

#endif // KMP_USE_HIER_SCHED
   // AC: TODO: probably remove TRAPEZOIDAL (OMP 3.0 does not allow it)
   else if (!__kmp_strcasecmp_with_sentinel("auto", ptr, *delim))
     sched = kmp_sch_auto;
   else if (!__kmp_strcasecmp_with_sentinel("trapezoidal", ptr, *delim))
     sched = kmp_sch_trapezoidal;
   else if (!__kmp_strcasecmp_with_sentinel("static", ptr, *delim))
     sched = kmp_sch_static;
 #if KMP_STATIC_STEAL_ENABLED
-  else if (!__kmp_strcasecmp_with_sentinel("static_steal", ptr, *delim))
-    sched = kmp_sch_static_steal;
+  else if (!__kmp_strcasecmp_with_sentinel("static_steal", ptr, *delim)) {
+    // replace static_steal with dynamic to better cope with ordered loops
+    sched = kmp_sch_dynamic_chunked;
+    sched_modifier = sched_type::kmp_sch_modifier_nonmonotonic;
+  }
 #endif
   else {
     // If there is no proper schedule kind, then this schedule is invalid
     KMP_WARNING(StgInvalidValue, name, value);
     __kmp_omp_schedule_restore();
     return NULL;
   }
 

openmp/runtime/test/env/kmp_set_dispatch_buf.c

 // RUN: %libomp-compile
 // RUN: env KMP_DISP_NUM_BUFFERS=0 %libomp-run
 // RUN: env KMP_DISP_NUM_BUFFERS=1 %libomp-run
 // RUN: env KMP_DISP_NUM_BUFFERS=3 %libomp-run
 // RUN: env KMP_DISP_NUM_BUFFERS=4 %libomp-run
 // RUN: env KMP_DISP_NUM_BUFFERS=7 %libomp-run
 // RUN: %libomp-compile -DMY_SCHEDULE=guided
 // RUN: env KMP_DISP_NUM_BUFFERS=1 %libomp-run
 // RUN: env KMP_DISP_NUM_BUFFERS=3 %libomp-run
 // RUN: env KMP_DISP_NUM_BUFFERS=4 %libomp-run
 // RUN: env KMP_DISP_NUM_BUFFERS=7 %libomp-run
-// UNSUPPORTED: clang-11, clang-12, clang-13
+// UNSUPPORTED: clang-11, clang-12
 #include <stdio.h>
 #include <omp.h>
 #include <stdlib.h>
 #include <limits.h>
 #include "omp_testsuite.h"
 
 #define INCR 7
 #define MY_MAX 200
for (i = MY_MAX; i >= MY_MIN; i-=INCR)
       b_known_value++;
   }
 
   for(i = 0; i < REPETITIONS; i++) {
     if(!test_kmp_set_disp_num_buffers()) {
       num_failed++;
     }
   }
+  if (num_failed == 0)
+    printf("passed\n");
+  else
+    printf("failed %d\n", num_failed);
   return num_failed;
 }

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

 // RUN: %libomp-compile && %libomp-run 7
 // RUN: %libomp-run 0 && %libomp-run -1
 // RUN: %libomp-run 1 && %libomp-run 2 && %libomp-run 5
 // RUN: %libomp-compile -DMY_SCHEDULE=guided && %libomp-run 7
 // RUN: %libomp-run 1 && %libomp-run 2 && %libomp-run 5
-// UNSUPPORTED: clang-11, clang-12, clang-13
+// UNSUPPORTED: clang-11, clang-12
 #include <stdio.h>
 #include <omp.h>
 #include <stdlib.h>
 #include <limits.h>
 #include "omp_testsuite.h"
 
 #define INCR 7
 #define MY_MAX 200
for (i = MY_MAX; i >= MY_MIN; i-=INCR)
       b_known_value++;
   }
 
   for(i = 0; i < REPETITIONS; i++) {
     if(!test_kmp_set_disp_num_buffers()) {
       num_failed++;
     }
   }
+  if (num_failed == 0)
+    printf("passed\n");
+  else
+    printf("failed %d\n", num_failed);
   return num_failed;
 }

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

 // RUN: %libomp-compile
 // RUN: env OMP_SCHEDULE=static %libomp-run 1 0
 // RUN: env OMP_SCHEDULE=static,10 %libomp-run 1 10
 // RUN: env OMP_SCHEDULE=dynamic %libomp-run 2 1
 // RUN: env OMP_SCHEDULE=dynamic,11 %libomp-run 2 11
 // RUN: env OMP_SCHEDULE=guided %libomp-run 3 1
 // RUN: env OMP_SCHEDULE=guided,12 %libomp-run 3 12
 // RUN: env OMP_SCHEDULE=auto %libomp-run 4 1
 // RUN: env OMP_SCHEDULE=trapezoidal %libomp-run 101 1
 // RUN: env OMP_SCHEDULE=trapezoidal,13 %libomp-run 101 13
-// RUN: env OMP_SCHEDULE=static_steal %libomp-run 102 1
-// RUN: env OMP_SCHEDULE=static_steal,14 %libomp-run 102 14
+// RUN: env OMP_SCHEDULE=static_steal %libomp-run 2 1
+// RUN: env OMP_SCHEDULE=static_steal,14 %libomp-run 2 14
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <math.h>
 #include "omp_testsuite.h"
 
 int sum;
 char* correct_kind_string;

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

+// RUN: %libomp-compile-and-run
+//
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include <omp.h>
+
+#define TYPE long
+#define MAX_ITER (TYPE)((TYPE)1000000)
+#define EVERY (TYPE)((TYPE)100000)
+
+int main(int argc, char* argv[]) {
+  TYPE x = MAX_ITER;
+  omp_set_max_active_levels(2);
+  omp_set_num_threads(2);
+  #pragma omp parallel for schedule(nonmonotonic:dynamic,1)
+  for (TYPE i = 0; i < x; i++) {
+    int tid = omp_get_thread_num();
+    omp_set_num_threads(1);
+    #pragma omp parallel proc_bind(spread)
+    {
+      if (i % EVERY == (TYPE)0)
+        printf("Outer thread %d at iter %ld\n", tid, i);
+    }
+  }
+  printf("passed\n");
+  return 0;
+}