Skip to content

Commit 377aa40

Browse files
jpeyton52jpeyton52
committedApr 14, 2016
Exponential back off logic for test-and-set lock
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 to 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. Differential Revision: http://reviews.llvm.org/D19020 llvm-svn: 266329
1 parent c1c14a2 commit 377aa40

File tree

6 files changed

+165
-3
lines changed

6 files changed

+165
-3
lines changed
 

‎openmp/runtime/src/kmp_csupport.c

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -957,8 +957,10 @@ __kmp_init_indirect_csptr(kmp_critical_name * crit, ident_t const * loc, kmp_int
957957
} else { \
958958
KMP_YIELD_SPIN(spins); \
959959
} \
960+
kmp_backoff_t backoff = __kmp_spin_backoff_params; \
960961
while (l->lk.poll != KMP_LOCK_FREE(tas) || \
961962
! KMP_COMPARE_AND_STORE_ACQ32(&(l->lk.poll), KMP_LOCK_FREE(tas), KMP_LOCK_BUSY(gtid+1, tas))) { \
963+
__kmp_spin_backoff(&backoff); \
962964
if (TCR_4(__kmp_nth) > (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) { \
963965
KMP_YIELD(TRUE); \
964966
} else { \

‎openmp/runtime/src/kmp_lock.cpp

Lines changed: 43 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -113,11 +113,11 @@ __kmp_acquire_tas_lock_timed_template( kmp_tas_lock_t *lck, kmp_int32 gtid )
113113
KMP_YIELD_SPIN( spins );
114114
}
115115

116+
kmp_backoff_t backoff = __kmp_spin_backoff_params;
116117
while ( ( lck->lk.poll != KMP_LOCK_FREE(tas) ) ||
117118
( ! KMP_COMPARE_AND_STORE_ACQ32( & ( lck->lk.poll ), KMP_LOCK_FREE(tas), KMP_LOCK_BUSY(gtid+1, tas) ) ) ) {
118-
//
119-
// FIXME - use exponential backoff here
120-
//
119+
120+
__kmp_spin_backoff(&backoff);
121121
if ( TCR_4( __kmp_nth ) > ( __kmp_avail_proc ? __kmp_avail_proc :
122122
__kmp_xproc ) ) {
123123
KMP_YIELD( TRUE );
@@ -3008,6 +3008,46 @@ __kmp_set_drdpa_lock_flags( kmp_drdpa_lock_t *lck, kmp_lock_flags_t flags )
30083008
lck->lk.flags = flags;
30093009
}
30103010

3011+
// Time stamp counter
3012+
#if KMP_ARCH_X86 || KMP_ARCH_X86_64
3013+
# define __kmp_tsc() __kmp_hardware_timestamp()
3014+
// Runtime's default backoff parameters
3015+
kmp_backoff_t __kmp_spin_backoff_params = { 1, 4096, 100 };
3016+
#else
3017+
// Use nanoseconds for other platforms
3018+
extern kmp_uint64 __kmp_now_nsec();
3019+
kmp_backoff_t __kmp_spin_backoff_params = { 1, 256, 100 };
3020+
# define __kmp_tsc() __kmp_now_nsec()
3021+
#endif
3022+
3023+
// A useful predicate for dealing with timestamps that may wrap.
3024+
// Is a before b?
3025+
// Since the timestamps may wrap, this is asking whether it's
3026+
// shorter to go clockwise from a to b around the clock-face, or anti-clockwise.
3027+
// Times where going clockwise is less distance than going anti-clockwise
3028+
// are in the future, others are in the past.
3029+
// e.g.) a = MAX-1, b = MAX+1 (=0), then a > b (true) does not mean a reached b
3030+
// whereas signed(a) = -2, signed(b) = 0 captures the actual difference
3031+
static inline bool before(kmp_uint64 a, kmp_uint64 b)
3032+
{
3033+
return ((kmp_int64)b - (kmp_int64)a) > 0;
3034+
}
3035+
3036+
// Truncated binary exponential backoff function
3037+
void
3038+
__kmp_spin_backoff(kmp_backoff_t *boff)
3039+
{
3040+
// We could flatten this loop, but making it a nested loop gives better result.
3041+
kmp_uint32 i;
3042+
for (i = boff->step; i > 0; i--) {
3043+
kmp_uint64 goal = __kmp_tsc() + boff->min_tick;
3044+
do {
3045+
KMP_CPU_PAUSE();
3046+
} while (before(__kmp_tsc(), goal));
3047+
}
3048+
boff->step = (boff->step<<1 | 1) & (boff->max_backoff-1);
3049+
}
3050+
30113051
#if KMP_USE_DYNAMIC_LOCK
30123052

30133053
// Direct lock initializers. It simply writes a tag to the low 8 bits of the lock word.

‎openmp/runtime/src/kmp_lock.h

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1265,6 +1265,19 @@ __kmp_get_user_lock_owner(kmp_user_lock_p, kmp_uint32);
12651265

12661266
#endif // KMP_USE_DYNAMIC_LOCK
12671267

1268+
// data structure for using backoff within spin locks.
1269+
typedef struct {
1270+
kmp_uint32 step; // current step
1271+
kmp_uint32 max_backoff; // upper bound of outer delay loop
1272+
kmp_uint32 min_tick; // size of inner delay loop in ticks (machine-dependent)
1273+
} kmp_backoff_t;
1274+
1275+
// Runtime's default backoff parameters
1276+
extern kmp_backoff_t __kmp_spin_backoff_params;
1277+
1278+
// Backoff function
1279+
extern void __kmp_spin_backoff(kmp_backoff_t *);
1280+
12681281
#ifdef __cplusplus
12691282
} // extern "C"
12701283
#endif // __cplusplus

‎openmp/runtime/src/kmp_settings.c

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4037,6 +4037,102 @@ __kmp_stg_print_lock_kind( kmp_str_buf_t * buffer, char const * name, void * dat
40374037
}
40384038
}
40394039

4040+
// -------------------------------------------------------------------------------------------------
4041+
// KMP_SPIN_BACKOFF_PARAMS
4042+
// -------------------------------------------------------------------------------------------------
4043+
4044+
// KMP_SPIN_BACKOFF_PARAMS=max_backoff[,min_tick] (max backoff size, min tick for machine pause)
4045+
static void
4046+
__kmp_stg_parse_spin_backoff_params(const char* name, const char* value, void* data)
4047+
{
4048+
const char *next = value;
4049+
4050+
int total = 0; // Count elements that were set. It'll be used as an array size
4051+
int prev_comma = FALSE; // For correct processing sequential commas
4052+
int i;
4053+
4054+
kmp_uint32 max_backoff = __kmp_spin_backoff_params.max_backoff;
4055+
kmp_uint32 min_tick = __kmp_spin_backoff_params.min_tick;
4056+
4057+
// Run only 3 iterations because it is enough to read two values or find a syntax error
4058+
for ( i = 0; i < 3 ; i++) {
4059+
SKIP_WS( next );
4060+
4061+
if ( *next == '\0' ) {
4062+
break;
4063+
}
4064+
// Next character is not an integer or not a comma OR number of values > 2 => end of list
4065+
if ( ( ( *next < '0' || *next > '9' ) && *next !=',' ) || total > 2 ) {
4066+
KMP_WARNING( EnvSyntaxError, name, value );
4067+
return;
4068+
}
4069+
// The next character is ','
4070+
if ( *next == ',' ) {
4071+
// ',' is the fisrt character
4072+
if ( total == 0 || prev_comma ) {
4073+
total++;
4074+
}
4075+
prev_comma = TRUE;
4076+
next++; //skip ','
4077+
SKIP_WS( next );
4078+
}
4079+
// Next character is a digit
4080+
if ( *next >= '0' && *next <= '9' ) {
4081+
int num;
4082+
const char *buf = next;
4083+
char const * msg = NULL;
4084+
prev_comma = FALSE;
4085+
SKIP_DIGITS( next );
4086+
total++;
4087+
4088+
const char *tmp = next;
4089+
SKIP_WS( tmp );
4090+
if ( ( *next == ' ' || *next == '\t' ) && ( *tmp >= '0' && *tmp <= '9' ) ) {
4091+
KMP_WARNING( EnvSpacesNotAllowed, name, value );
4092+
return;
4093+
}
4094+
4095+
num = __kmp_str_to_int( buf, *next );
4096+
if ( num <= 0 ) { // The number of retries should be > 0
4097+
msg = KMP_I18N_STR( ValueTooSmall );
4098+
num = 1;
4099+
} else if ( num > KMP_INT_MAX ) {
4100+
msg = KMP_I18N_STR( ValueTooLarge );
4101+
num = KMP_INT_MAX;
4102+
}
4103+
if ( msg != NULL ) {
4104+
// Message is not empty. Print warning.
4105+
KMP_WARNING( ParseSizeIntWarn, name, value, msg );
4106+
KMP_INFORM( Using_int_Value, name, num );
4107+
}
4108+
if( total == 1 ) {
4109+
max_backoff = num;
4110+
} else if( total == 2 ) {
4111+
min_tick = num;
4112+
}
4113+
}
4114+
}
4115+
KMP_DEBUG_ASSERT( total > 0 );
4116+
if( total <= 0 ) {
4117+
KMP_WARNING( EnvSyntaxError, name, value );
4118+
return;
4119+
}
4120+
__kmp_spin_backoff_params.max_backoff = max_backoff;
4121+
__kmp_spin_backoff_params.min_tick = min_tick;
4122+
}
4123+
4124+
static void
4125+
__kmp_stg_print_spin_backoff_params(kmp_str_buf_t *buffer, char const* name, void* data)
4126+
{
4127+
if( __kmp_env_format ) {
4128+
KMP_STR_BUF_PRINT_NAME_EX(name);
4129+
} else {
4130+
__kmp_str_buf_print( buffer, " %s='", name );
4131+
}
4132+
__kmp_str_buf_print( buffer, "%d,%d'\n", __kmp_spin_backoff_params.max_backoff,
4133+
__kmp_spin_backoff_params.min_tick );
4134+
}
4135+
40404136
#if KMP_USE_ADAPTIVE_LOCKS
40414137

40424138
// -------------------------------------------------------------------------------------------------
@@ -4653,6 +4749,7 @@ static kmp_setting_t __kmp_stg_table[] = {
46534749

46544750
{ "KMP_NUM_LOCKS_IN_BLOCK", __kmp_stg_parse_lock_block, __kmp_stg_print_lock_block, NULL, 0, 0 },
46554751
{ "KMP_LOCK_KIND", __kmp_stg_parse_lock_kind, __kmp_stg_print_lock_kind, NULL, 0, 0 },
4752+
{ "KMP_SPIN_BACKOFF_PARAMS", __kmp_stg_parse_spin_backoff_params, __kmp_stg_print_spin_backoff_params, NULL, 0, 0 },
46564753
#if KMP_USE_ADAPTIVE_LOCKS
46574754
{ "KMP_ADAPTIVE_LOCK_PROPS", __kmp_stg_parse_adaptive_lock_props,__kmp_stg_print_adaptive_lock_props, NULL, 0, 0 },
46584755
#if KMP_DEBUG_ADAPTIVE_LOCKS

‎openmp/runtime/src/z_Linux_util.c

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2211,6 +2211,15 @@ __kmp_elapsed_tick( double *t )
22112211
*t = 1 / (double) CLOCKS_PER_SEC;
22122212
}
22132213

2214+
/* Return the current time stamp in nsec */
2215+
kmp_uint64
2216+
__kmp_now_nsec()
2217+
{
2218+
struct timeval t;
2219+
gettimeofday(&t, NULL);
2220+
return KMP_NSEC_PER_SEC*t.tv_sec + 1000*t.tv_usec;
2221+
}
2222+
22142223
/*
22152224
Determine whether the given address is mapped into the current address space.
22162225
*/

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
// RUN: %libomp-compile-and-run
2+
// RUN: %libomp-compile && env KMP_LOCK_KIND=tas KMP_SPIN_BACKOFF_PARAMS=2048,200 %libomp-run
23
#include <stdio.h>
34
#include "omp_testsuite.h"
45

0 commit comments

Comments
 (0)