Exponential back off logic for test-and-set lock.

[jlpeyton]

Summary

This change adds back off logic in the test and set lock for better contended lock performance. It uses a simple truncated binary exponential back off function. The default back off parameters are tuned for x86.

The main back off logic has a two loop structure where each is controlled by a user-level parameter:
max_backoff - limits the outer loop number of iterations. This parameter should be a power of 2.
min_ticks - the inner spin wait loop number of "ticks" which is system dependent and should be tuned for your system if you so choose. The "ticks" on x86 correspond the the time stamp counter, but on other architectures ticks is a timestamp derived from gettimeofday().

The user can modify these via the environment variable KMP_SPIN_BACKOFF_PARAMS=max_backoff[,min_ticks]

Currently, since the default user lock is a queuing lock, one would have to also specify KMP_LOCK_KIND=tas to use the test-and-set locks.

[hbae]

LGTM.

openmp/trunk/runtime/src/kmp_csupport.c

if (l->lk.poll != KMP_LOCK_FREE(tas) ||                                                                      \
         kmp_uint32 spins;                                                                                        \
         KMP_FSYNC_PREPARE(l);                                                                                    \
         KMP_INIT_YIELD(spins);                                                                                   \
         if (TCR_4(__kmp_nth) > (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) {                            \
             KMP_YIELD(TRUE);                                                                                     \
         } else {                                                                                                 \
             KMP_YIELD_SPIN(spins);                                                                               \
         }                                                                                                        \
+        kmp_backoff_t backoff = __kmp_spin_backoff_params;                                                       \
         while (l->lk.poll != KMP_LOCK_FREE(tas) ||                                                               \
                ! KMP_COMPARE_AND_STORE_ACQ32(&(l->lk.poll), KMP_LOCK_FREE(tas), KMP_LOCK_BUSY(gtid+1, tas))) {   \
+            __kmp_spin_backoff(&backoff);                                                                        \
             if (TCR_4(__kmp_nth) > (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) {                        \
                 KMP_YIELD(TRUE);                                                                                 \
             } else {                                                                                             \
                 KMP_YIELD_SPIN(spins);                                                                           \
             }                                                                                                    \
         }                                                                                                        \
     }                                                                                                            \
     KMP_FSYNC_ACQUIRED(l);                                                                                       \

openmp/trunk/runtime/src/kmp_lock.h

 #else // KMP_USE_DYNAMIC_LOCK
 
 # define KMP_LOCK_BUSY(v, type)    (v)
 # define KMP_LOCK_FREE(type)       0
 # define KMP_LOCK_STRIP(v)         (v)
 
 #endif // KMP_USE_DYNAMIC_LOCK
 
+// data structure for using backoff within spin locks.
+typedef struct {
+    kmp_uint32 step;        // current step
+    kmp_uint32 max_backoff; // upper bound of outer delay loop
+    kmp_uint32 min_tick;    // size of inner delay loop in ticks (machine-dependent)
+} kmp_backoff_t;
+
+// Runtime's default backoff parameters
+extern kmp_backoff_t __kmp_spin_backoff_params;
+
+// Backoff function
+extern void __kmp_spin_backoff(kmp_backoff_t *);
+
 #ifdef __cplusplus
 } // extern "C"
 #endif // __cplusplus
 
 #endif /* KMP_LOCK_H */
 

openmp/trunk/runtime/src/kmp_lock.cpp

#endif /* USE_LOCK_PROFILE */
     if ( TCR_4( __kmp_nth ) > ( __kmp_avail_proc ? __kmp_avail_proc :
       __kmp_xproc ) ) {
         KMP_YIELD( TRUE );
     }
     else {
         KMP_YIELD_SPIN( spins );
     }
 
+    kmp_backoff_t backoff = __kmp_spin_backoff_params;
     while ( ( lck->lk.poll != KMP_LOCK_FREE(tas) ) ||
       ( ! KMP_COMPARE_AND_STORE_ACQ32( & ( lck->lk.poll ), KMP_LOCK_FREE(tas), KMP_LOCK_BUSY(gtid+1, tas) ) ) ) {
-        //
-        // FIXME - use exponential backoff here
-        //
+
+        __kmp_spin_backoff(&backoff);
         if ( TCR_4( __kmp_nth ) > ( __kmp_avail_proc ? __kmp_avail_proc :
           __kmp_xproc ) ) {
             KMP_YIELD( TRUE );
         }
         else {
             KMP_YIELD_SPIN( spins );
         }
     }

 }
 
 static void
 __kmp_set_drdpa_lock_flags( kmp_drdpa_lock_t *lck, kmp_lock_flags_t flags )
 {
     lck->lk.flags = flags;
 }
 
+// Time stamp counter
+#if KMP_ARCH_X86 || KMP_ARCH_X86_64
+# define __kmp_tsc() __kmp_hardware_timestamp()
+// Runtime's default backoff parameters
+kmp_backoff_t __kmp_spin_backoff_params = { 1, 4096, 100 };
+#else
+// Use nanoseconds for other platforms
+extern kmp_uint64 __kmp_now_nsec();
+kmp_backoff_t __kmp_spin_backoff_params = { 1, 256, 100 };
+# define __kmp_tsc() __kmp_now_nsec()
+#endif
+
+// A useful predicate for dealing with timestamps that may wrap.
+// Is a before b?
+// Since the timestamps may wrap, this is asking whether it's
+// shorter to go clockwise from a to b around the clock-face, or anti-clockwise.
+// Times where going clockwise is less distance than going anti-clockwise
+// are in the future, others are in the past.
+// e.g.) a = MAX-1, b = MAX+1 (=0), then a > b (true) does not mean a reached b
+//       whereas signed(a) = -2, signed(b) = 0 captures the actual difference
+static inline bool before(kmp_uint64 a, kmp_uint64 b)
+{
+    return ((kmp_int64)b - (kmp_int64)a) > 0;
+}
+
+// Truncated binary exponential backoff function
+void
+__kmp_spin_backoff(kmp_backoff_t *boff)
+{
+    // We could flatten this loop, but making it a nested loop gives better result.
+    kmp_uint32 i;
+    for (i = boff->step; i > 0; i--) {
+        kmp_uint64 goal = __kmp_tsc() + boff->min_tick;
+        do {
+            KMP_CPU_PAUSE();
+        } while (before(__kmp_tsc(), goal));
+    }
+    boff->step = (boff->step<<1 | 1) & (boff->max_backoff-1);
+}
+
 #if KMP_USE_DYNAMIC_LOCK
 
 // Direct lock initializers. It simply writes a tag to the low 8 bits of the lock word.
 static void __kmp_init_direct_lock(kmp_dyna_lock_t *lck, kmp_dyna_lockseq_t seq)
 {
     TCW_4(*lck, KMP_GET_D_TAG(seq));
     KA_TRACE(20, ("__kmp_init_direct_lock: initialized direct lock with type#%d\n", seq));
 }

openmp/trunk/runtime/src/kmp_settings.c

 #endif
     }
 
     if ( value != NULL ) {
         __kmp_stg_print_str( buffer, name, value );
     }
 }
 
+// -------------------------------------------------------------------------------------------------
+// KMP_SPIN_BACKOFF_PARAMS
+// -------------------------------------------------------------------------------------------------
+
+// KMP_SPIN_BACKOFF_PARAMS=max_backoff[,min_tick] (max backoff size, min tick for machine pause)
+static void
+__kmp_stg_parse_spin_backoff_params(const char* name, const char* value, void* data)
+{
+    const char *next = value;
+
+    int total = 0;          // Count elements that were set. It'll be used as an array size
+    int prev_comma = FALSE; // For correct processing sequential commas
+    int i;
+
+    kmp_uint32 max_backoff = __kmp_spin_backoff_params.max_backoff;
+    kmp_uint32 min_tick = __kmp_spin_backoff_params.min_tick;
+
+    // Run only 3 iterations because it is enough to read two values or find a syntax error
+    for ( i = 0; i < 3 ; i++) {
+        SKIP_WS( next );
+
+        if ( *next == '\0' ) {
+            break;
+        }
+        // Next character is not an integer or not a comma OR number of values > 2 => end of list
+        if ( ( ( *next < '0' || *next > '9' ) && *next !=',' ) || total > 2 ) {
+            KMP_WARNING( EnvSyntaxError, name, value );
+            return;
+        }
+        // The next character is ','
+        if ( *next == ',' ) {
+            // ',' is the fisrt character
+            if ( total == 0 || prev_comma ) {
+                total++;
+            }
+            prev_comma = TRUE;
+            next++; //skip ','
+            SKIP_WS( next );
+        }
+        // Next character is a digit
+        if ( *next >= '0' && *next <= '9' ) {
+            int num;
+            const char *buf = next;
+            char const * msg  = NULL;
+            prev_comma = FALSE;
+            SKIP_DIGITS( next );
+            total++;
+
+            const char *tmp = next;
+            SKIP_WS( tmp );
+            if ( ( *next == ' ' || *next == '\t' ) && ( *tmp >= '0' && *tmp <= '9' ) ) {
+                KMP_WARNING( EnvSpacesNotAllowed, name, value );
+                return;
+            }
+
+            num = __kmp_str_to_int( buf, *next );
+            if ( num <= 0 ) { // The number of retries should be > 0
+                msg = KMP_I18N_STR( ValueTooSmall );
+                num = 1;
+            } else if ( num > KMP_INT_MAX ) {
+                msg = KMP_I18N_STR( ValueTooLarge );
+                num = KMP_INT_MAX;
+            }
+            if ( msg != NULL ) {
+                // Message is not empty. Print warning.
+                KMP_WARNING( ParseSizeIntWarn, name, value, msg );
+                KMP_INFORM( Using_int_Value, name, num );
+            }
+            if( total == 1 ) {
+                max_backoff = num;
+            } else if( total == 2 ) {
+                min_tick = num;
+            }
+        }
+    }
+    KMP_DEBUG_ASSERT( total > 0 );
+    if( total <= 0 ) {
+        KMP_WARNING( EnvSyntaxError, name, value );
+        return;
+    }
+    __kmp_spin_backoff_params.max_backoff = max_backoff;
+    __kmp_spin_backoff_params.min_tick    = min_tick;
+}
+
+static void
+__kmp_stg_print_spin_backoff_params(kmp_str_buf_t *buffer, char const* name, void* data)
+{
+    if( __kmp_env_format ) {
+        KMP_STR_BUF_PRINT_NAME_EX(name);
+    } else {
+        __kmp_str_buf_print( buffer, "   %s='", name );
+    }
+    __kmp_str_buf_print( buffer, "%d,%d'\n", __kmp_spin_backoff_params.max_backoff,
+                         __kmp_spin_backoff_params.min_tick );
+}
+
 #if KMP_USE_ADAPTIVE_LOCKS
 
 // -------------------------------------------------------------------------------------------------
 // KMP_ADAPTIVE_LOCK_PROPS, KMP_SPECULATIVE_STATSFILE
 // -------------------------------------------------------------------------------------------------
 
 // Parse out values for the tunable parameters from a string of the form
 // KMP_ADAPTIVE_LOCK_PROPS=max_soft_retries[,max_badness]
#endif /* USE_ITT_BUILD && USE_ITT_NOTIFY */
     { "KMP_DYNAMIC_MODE",                  __kmp_stg_parse_kmp_dynamic_mode,   __kmp_stg_print_kmp_dynamic_mode,   NULL, 0, 0 },
 
 #ifdef USE_LOAD_BALANCE
     { "KMP_LOAD_BALANCE_INTERVAL",         __kmp_stg_parse_ld_balance_interval,__kmp_stg_print_ld_balance_interval,NULL, 0, 0 },
 #endif
 
     { "KMP_NUM_LOCKS_IN_BLOCK",            __kmp_stg_parse_lock_block,         __kmp_stg_print_lock_block,         NULL, 0, 0 },
     { "KMP_LOCK_KIND",                     __kmp_stg_parse_lock_kind,          __kmp_stg_print_lock_kind,          NULL, 0, 0 },
+    { "KMP_SPIN_BACKOFF_PARAMS",           __kmp_stg_parse_spin_backoff_params, __kmp_stg_print_spin_backoff_params, NULL, 0, 0 },
 #if KMP_USE_ADAPTIVE_LOCKS
     { "KMP_ADAPTIVE_LOCK_PROPS",           __kmp_stg_parse_adaptive_lock_props,__kmp_stg_print_adaptive_lock_props,  NULL, 0, 0 },
 #if KMP_DEBUG_ADAPTIVE_LOCKS
     { "KMP_SPECULATIVE_STATSFILE",         __kmp_stg_parse_speculative_statsfile,__kmp_stg_print_speculative_statsfile,  NULL, 0, 0 },
 #endif
 #endif // KMP_USE_ADAPTIVE_LOCKS
     { "KMP_PLACE_THREADS",                 __kmp_stg_parse_place_threads,      __kmp_stg_print_place_threads,      NULL, 0, 0 },
 #if USE_ITT_BUILD

openmp/trunk/runtime/src/z_Linux_util.c

 
 /* Calculate the elapsed wall clock tick for the user */
 void
 __kmp_elapsed_tick( double *t )
 {
     *t = 1 / (double) CLOCKS_PER_SEC;
 }
 
+/* Return the current time stamp in nsec */
+kmp_uint64
+__kmp_now_nsec()
+{
+    struct timeval t;
+    gettimeofday(&t, NULL);
+    return KMP_NSEC_PER_SEC*t.tv_sec + 1000*t.tv_usec;
+}
+
 /*
     Determine whether the given address is mapped into the current address space.
 */
 
 int
 __kmp_is_address_mapped( void * addr ) {
 
     int found = 0;

openmp/trunk/runtime/test/lock/omp_lock.c

 // RUN: %libomp-compile-and-run
+// RUN: %libomp-compile && env KMP_LOCK_KIND=tas KMP_SPIN_BACKOFF_PARAMS=2048,200 %libomp-run
 #include <stdio.h>
 #include "omp_testsuite.h"
 
 omp_lock_t lck;
 
 int test_omp_lock()
 {
   int nr_threads_in_single = 0;