standard devation-based gpu affinity predictor

2 files changed, 65 insertions, 3 deletions

diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index a441badd30cc..04239c747f06 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -152,6 +152,7 @@ typedef struct avg_est{
         uint16_t count;
         uint16_t idx;
         lt_t sum;
+        lt_t std;
         lt_t avg;
 } avg_est_t;
 
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;