From 901fdd9c22790039a76c1d3ee01828a2f124f6f3 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Mon, 10 Sep 2012 11:27:08 -0400 Subject: standard devation-based gpu affinity predictor --- litmus/gpu_affinity.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 64 insertions(+), 3 deletions(-) (limited to 'litmus') diff --git a/litmus/gpu_affinity.c b/litmus/gpu_affinity.c index 2cdf18bc7dd6..896f3248b8a2 100644 --- a/litmus/gpu_affinity.c +++ b/litmus/gpu_affinity.c @@ -11,8 +11,10 @@ // reason for skew: high outliers are less // frequent and way out of bounds -#define HI_THRESHOLD 2 -#define LO_THRESHOLD 4 +//#define HI_THRESHOLD 2 +//#define LO_THRESHOLD 4 + +#define NUM_STDEV 2 #define MIN(a, b) ((a < b) ? a : b) @@ -33,6 +35,44 @@ static fp_t update_estimate(feedback_est_t* fb, fp_t a, fp_t b, lt_t observed) return relative_err; } +lt_t varience(lt_t nums[], const lt_t avg, const uint16_t count) +{ + /* brute force: takes about as much time as incremental running methods when + * count < 50 (on Bonham). Brute force also less prone to overflow. + */ + lt_t sqdeviations = 0; + uint16_t i; + for(i = 0; i < count; ++i) + { + lt_t temp = (int64_t)nums[i] - (int64_t)avg; + sqdeviations += temp * temp; + } + return sqdeviations/count; +} + +lt_t isqrt(lt_t n) +{ + /* integer square root using babylonian method + * (algo taken from wikipedia */ + lt_t res = 0; + lt_t bit = ((lt_t)1) << (sizeof(n)*8-2); + while (bit > n) { + bit >>= 2; + } + + while (bit != 0) { + if (n >= res + bit) { + n -= res + bit; + res = (res >> 1) + bit; + } + else { + res >>= 1; + } + bit >>= 2; + } + return res; +} + void update_gpu_estimate(struct task_struct *t, lt_t observed) { //feedback_est_t *fb = &(tsk_rt(t)->gpu_migration_est[tsk_rt(t)->gpu_migration]); @@ -65,8 +105,28 @@ void update_gpu_estimate(struct task_struct *t, lt_t observed) observed); return; } - } #endif + // filter values outside NUM_STDEVx the standard deviation, + // but only filter if enough samples have been taken. + if (likely((est->count > MIN(10, AVG_EST_WINDOW_SIZE/2)))) { + lt_t lower, upper; + + lt_t range = est->std*NUM_STDEV; + lower = est->avg - MIN(range, est->avg); // no underflow. + + if (unlikely(observed < lower)) { + TRACE_TASK(t, "Observation is too small: %llu\n", observed); + return; + } + + upper = est->avg + range; + if (unlikely(observed > upper)) { + TRACE_TASK(t, "Observation is too large: %llu\n", observed); + return; + } + } + + if (unlikely(est->count < AVG_EST_WINDOW_SIZE)) { ++est->count; @@ -84,6 +144,7 @@ void update_gpu_estimate(struct task_struct *t, lt_t observed) est->history[est->idx] = observed; est->sum += observed; est->avg = est->sum/est->count; + est->std = isqrt(varience(est->history, est->avg, est->count)); est->idx = (est->idx + 1) % AVG_EST_WINDOW_SIZE; -- cgit v1.2.2