Index: openmp/trunk/runtime/src/kmp_csupport.c =================================================================== --- openmp/trunk/runtime/src/kmp_csupport.c +++ openmp/trunk/runtime/src/kmp_csupport.c @@ -957,8 +957,10 @@ } 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 { \ Index: openmp/trunk/runtime/src/kmp_lock.h =================================================================== --- openmp/trunk/runtime/src/kmp_lock.h +++ openmp/trunk/runtime/src/kmp_lock.h @@ -1265,6 +1265,19 @@ #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 Index: openmp/trunk/runtime/src/kmp_lock.cpp =================================================================== --- openmp/trunk/runtime/src/kmp_lock.cpp +++ openmp/trunk/runtime/src/kmp_lock.cpp @@ -113,11 +113,11 @@ 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 ); @@ -3008,6 +3008,46 @@ 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. Index: openmp/trunk/runtime/src/kmp_settings.c =================================================================== --- openmp/trunk/runtime/src/kmp_settings.c +++ openmp/trunk/runtime/src/kmp_settings.c @@ -4037,6 +4037,102 @@ } } +// ------------------------------------------------------------------------------------------------- +// 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 // ------------------------------------------------------------------------------------------------- @@ -4653,6 +4749,7 @@ { "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 Index: openmp/trunk/runtime/src/z_Linux_util.c =================================================================== --- openmp/trunk/runtime/src/z_Linux_util.c +++ openmp/trunk/runtime/src/z_Linux_util.c @@ -2211,6 +2211,15 @@ *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. */ Index: openmp/trunk/runtime/test/lock/omp_lock.c =================================================================== --- openmp/trunk/runtime/test/lock/omp_lock.c +++ openmp/trunk/runtime/test/lock/omp_lock.c @@ -1,4 +1,5 @@ // RUN: %libomp-compile-and-run +// RUN: %libomp-compile && env KMP_LOCK_KIND=tas KMP_SPIN_BACKOFF_PARAMS=2048,200 %libomp-run #include #include "omp_testsuite.h"