Add GPU affinity tracking.

Adds GPU affinity tracking/prediction routines. Tracking
uses a process-chart method whereby observations over two
standard deviations below or above the average are discarded.

4 files changed, 268 insertions, 4 deletions

diff --git a/include/litmus/gpu_affinity.h b/include/litmus/gpu_affinity.h
new file mode 100644
index 000000000000..de5d1a5ab9e9
--- /dev/null
+++ b/include/litmus/gpu_affinity.h
@@ -0,0 +1,58 @@
+#ifndef LITMUS_GPU_AFFINITY_H
+#define LITMUS_GPU_AFFINITY_H
+
+#include <litmus/rt_param.h>
+#include <litmus/sched_plugin.h>
+#include <litmus/litmus.h>
+
+void update_gpu_estimate(struct task_struct* t, lt_t observed);
+gpu_migration_dist_t gpu_migration_distance(int a, int b);
+
+static inline void reset_gpu_tracker(struct task_struct* t)
+{
+        t->rt_param.accum_gpu_time = 0;
+        t->rt_param.gpu_time_stamp = 0;
+}
+
+static inline void start_gpu_tracker(struct task_struct* t)
+{
+        lt_t now = litmus_clock();
+        if (likely(!t->rt_param.gpu_time_stamp))
+                t->rt_param.gpu_time_stamp = now;
+}
+
+static inline void stop_gpu_tracker(struct task_struct* t)
+{
+        lt_t now = litmus_clock();
+        if (likely(t->rt_param.gpu_time_stamp)) {
+                t->rt_param.accum_gpu_time += (now - t->rt_param.gpu_time_stamp);
+                t->rt_param.gpu_time_stamp = 0;
+        }
+}
+
+static inline lt_t get_gpu_time(struct task_struct* t)
+{
+        lt_t accum = t->rt_param.accum_gpu_time;
+        if (t->rt_param.gpu_time_stamp != 0)
+                accum += (litmus_clock() - t->rt_param.gpu_time_stamp);
+        return accum;
+}
+
+static inline lt_t get_gpu_estimate(struct task_struct* t,
+                                gpu_migration_dist_t dist)
+{
+        int i;
+        lt_t val;
+
+        if(dist == MIG_NONE)
+                dist = MIG_LOCAL;
+
+        val = t->rt_param.gpu_migration_est[dist].avg;
+        for(i = dist-1; i >= 0; --i)
+                if(t->rt_param.gpu_migration_est[i].avg > val)
+                        val = t->rt_param.gpu_migration_est[i].avg;
+
+        return ((val > 0) ? val : dist+1);
+}
+
+#endif
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 3e4a32af1ba7..b5e58b79dfda 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -98,6 +98,14 @@ struct affinity_observer_args
         int lock_od;
 };
 
+struct gpu_affinity_observer_args
+{
+        struct affinity_observer_args obs;
+        unsigned int replica_to_gpu_offset;
+        unsigned int rho;
+        int relaxed_rules;
+};
+
 #define IKGLP_M_IN_FIFOS (0u)
 #define IKGLP_UNLIMITED_IN_FIFOS (~0u)
 #define IKGLP_OPTIMAL_FIFO_LEN (0u)
@@ -154,6 +162,40 @@ struct control_page {
 #include <linux/semaphore.h>
 #include <litmus/binheap.h>
 
+/*** GPU affinity tracking structures ***/
+
+typedef enum gpu_migration_dist
+{
+        MIG_LOCAL       = 0,
+        MIG_NEAR        = 1,
+        MIG_MED         = 2,
+        MIG_FAR         = 3, /* assumes 8 GPU binary tree hierarchy */
+        MIG_NONE        = 4,
+
+        MIG_LAST = MIG_NONE
+} gpu_migration_dist_t;
+
+#if 0
+typedef struct feedback_est
+{
+        fp_t est;
+        fp_t accum_err;
+} feedback_est_t
+#endif
+
+#define AVG_EST_WINDOW_SIZE 20
+typedef int (*notify_rsrc_exit_t)(struct task_struct* tsk);
+
+typedef struct avg_est {
+        lt_t history[AVG_EST_WINDOW_SIZE];
+        uint16_t count;
+        uint16_t idx;
+        lt_t sum;
+        lt_t avg;
+        lt_t std;
+} avg_est_t;
+
+
 struct _rt_domain;
 struct bheap_node;
 struct release_heap;
@@ -217,16 +259,14 @@ struct rt_param {
         gpu_migration_dist_t    gpu_migration;
         int                     last_gpu;
         lt_t                    accum_gpu_time;
-        lt_t                    gpu_time_stamp
+        lt_t                    gpu_time_stamp;
         unsigned int            suspend_gpu_tracker_on_block:1;
 #endif /* end LITMUS_AFFINITY_LOCKING */
 #endif /* end LITMUS_NVIDIA */
 
-#if 0 /* PORT RECHECK */
 #ifdef CONFIG_LITMUS_AFFINITY_LOCKING
         notify_rsrc_exit_t  rsrc_exit_cb;
-        void* rsrc_exit_cb_args
-#endif
+        void* rsrc_exit_cb_args;
 #endif
 
 #ifdef CONFIG_LITMUS_LOCKING
diff --git a/litmus/Makefile b/litmus/Makefile
index c0b0821667be..0bda543ca57c 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -31,6 +31,9 @@ obj-$(CONFIG_LITMUS_LOCKING) += kfmlp_lock.o
 obj-$(CONFIG_LITMUS_NESTED_LOCKING) += fifo_lock.o prioq_lock.o ikglp_lock.o
 obj-$(CONFIG_LITMUS_AFFINITY_LOCKING) += kexclu_affinity.o
 obj-$(CONFIG_LITMUS_NVIDIA) += nvidia_info.o
+ifeq ($(CONFIG_LITMUS_AFFINITY_LOCKING),y)
+        obj-$(CONFIG_LITMUS_NVIDIA) += gpu_affinity.o
+endif
 
 obj-$(CONFIG_FEATHER_TRACE) += ft_event.o ftdev.o
 obj-$(CONFIG_SCHED_TASK_TRACE) += sched_task_trace.o
diff --git a/litmus/gpu_affinity.c b/litmus/gpu_affinity.c
new file mode 100644
index 000000000000..85fa0ffb7328
--- /dev/null
+++ b/litmus/gpu_affinity.c
@@ -0,0 +1,163 @@
+#include <linux/sched.h>
+#include <litmus/litmus.h>
+#include <litmus/gpu_affinity.h>
+
+#include <litmus/sched_trace.h>
+#include <litmus/trace.h>
+
+/* two second cap on crazy observations */
+#define OBSERVATION_CAP ((lt_t)(2e9))
+
+#define NUM_STDEV_NUM   2
+#define NUM_STDEV_DENOM 1
+
+#define MIN(a, b) ((a < b) ? a : b)
+
+#if 0
+/* PID feedback controller */
+static fp_t update_estimate(feedback_est_t* fb, fp_t a, fp_t b, lt_t observed)
+{
+        fp_t relative_err;
+        fp_t err, new;
+        fp_t actual = _integer_to_fp(observed);
+
+        err = _sub(actual, fb->est);
+        new = _add(_mul(a, err), _mul(b, fb->accum_err));
+
+        relative_err = _div(err, actual);
+
+        fb->est = new;
+        fb->accum_err = _add(fb->accum_err, err);
+
+        return relative_err;
+}
+#endif
+
+static lt_t varience(lt_t nums[], const lt_t avg, const uint32_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;
+        uint32_t i;
+        for(i = 0; i < count; ++i) {
+                lt_t temp = (int64_t)nums[i] - (int64_t)avg;
+                sqdeviations += temp * temp;
+        }
+        return sqdeviations/count;
+}
+
+static 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)
+{
+        avg_est_t *est;
+        struct migration_info mig_info;
+
+        BUG_ON(tsk_rt(t)->gpu_migration > MIG_LAST);
+
+        est = &(tsk_rt(t)->gpu_migration_est[tsk_rt(t)->gpu_migration]);
+
+        /* log the migration event */
+        mig_info.observed = observed;
+        mig_info.estimated = est->avg;
+        mig_info.distance = tsk_rt(t)->gpu_migration;
+        sched_trace_migration(t, &mig_info);
+
+        if (unlikely(observed > OBSERVATION_CAP)) {
+                TRACE_TASK(t,
+                        "Crazy observation greater than was dropped: %llu > %llu\n",
+                        observed,
+                        OBSERVATION_CAP);
+                return;
+        }
+
+        /* 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_NUM)/NUM_STDEV_DENOM;
+                lower = est->avg - MIN(range, est->avg); // no underflow.
+
+                if (unlikely(observed < lower)) {
+                        TRACE_TASK(t,
+                                "Observation is too small: %llu < %llu (avg: %llu)\n",
+                                observed, lower, est->avg);
+                        return;
+                }
+
+                upper = est->avg + range;
+                if (unlikely(observed > upper)) {
+                        TRACE_TASK(t,
+                                "Observation is too large: %llu > %llu (avg: %llu)\n",
+                                observed, upper, est->avg);
+                        return;
+                }
+        }
+
+        if (unlikely(est->count < AVG_EST_WINDOW_SIZE))
+                ++est->count;
+        else
+                est->sum -= est->history[est->idx];
+
+        TS_UPDATE_GPU_EST_START;
+        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;
+        TS_UPDATE_GPU_EST_END;
+
+        TRACE_TASK(t,
+                "GPU est update after (dist = %d, obs = %llu): %llu\n",
+                tsk_rt(t)->gpu_migration,
+                observed,
+                est->avg);
+}
+
+gpu_migration_dist_t gpu_migration_distance(int a, int b)
+{
+        /* GPUs organized in a binary hierarchy, no more than 2^MIG_FAR GPUs */
+        int i;
+        int dist;
+
+        if(likely(a >= 0 && b >= 0)) {
+                for(i = 0; i <= MIG_FAR; ++i) {
+                        if(a>>i == b>>i) {
+                                dist = i;
+                                goto out;
+                        }
+                }
+                dist = MIG_NONE; /* hopefully never reached. */
+                TRACE_CUR("WARNING: GPU distance too far! %d -> %d\n", a, b);
+        }
+        else {
+                dist = MIG_NONE;
+        }
+
+out:
+        TRACE_CUR("Distance %d -> %d is %d\n", a, b, dist);
+
+        return dist;
+}