Initial GEL Piecewise Linear implementation

4 files changed, 289 insertions, 1 deletions

diff --git a/native/Makefile b/native/Makefile
index d9c5cbd..f9fbb75 100644
--- a/native/Makefile
+++ b/native/Makefile
@@ -51,7 +51,7 @@ vpath %.cpp src src/edf src/blocking
 
 # #### Common C++ source files ####
 
-EDF_OBJ   = baker.o baruah.o gfb.o bcl.o bcl_iterative.o rta.o ffdbf.o gedf.o load.o cpu_time.o
+EDF_OBJ   = baker.o baruah.o gfb.o bcl.o bcl_iterative.o rta.o ffdbf.o gedf.o gel_pl.o load.o cpu_time.o
 SCHED_OBJ = sim.o schedule_sim.o
 CORE_OBJ  = tasks.o
 SYNC_OBJ  = sharedres.o dpcp.o mpcp.o
diff --git a/native/include/edf/gel_pl.h b/native/include/edf/gel_pl.h
new file mode 100644
index 0000000..4093d95
--- /dev/null
+++ b/native/include/edf/gel_pl.h
@@ -0,0 +1,80 @@
+#ifndef GEL_PL_H
+#define GEL_PL_H
+
+#ifndef SWIG
+#include <vector>
+#endif
+
+class GELPl
+{
+
+ private:
+    std::vector<unsigned long> bounds;
+    int no_cpus;
+    const TaskSet& tasks;
+    int rounds;
+    std::vector<double> S_i;
+    std::vector<double> G_i;
+
+    // For faster lookups, to avoid too many conversions.
+    std::vector<double> utilizations;
+
+    double compute_exact_s(double S, const std::vector<double>& Y_ints);
+    double compute_binsearch_s(double S, const std::vector<double>& Y_ints);
+
+    inline double compute_M(double s, double S,
+                                   const std::vector<double>& Y_ints);
+
+    // These are basically just structs that override operator< to allow
+    // sort algorithms to work.
+    class ReplacementType {
+     public:
+        unsigned int old_task;
+        unsigned int new_task;
+        double location;
+        double old_task_utilization;
+
+        bool operator<(const ReplacementType& other) const {
+            return (location < other.location)
+                   || ((location == other.location)
+                       && (old_task_utilization < other.old_task_utilization));
+        }
+    };
+
+    class TaggedValue {
+     public:
+        unsigned int task;
+        double value;
+
+        //Order is reversed - we are going to want the largest, rather than the
+        //smallest, values.
+        bool operator<(const TaggedValue& other) const {
+            return other.value < value;
+        }
+    };
+
+ public:
+   enum Scheduler {
+     GEDF,
+     GFL
+   };
+
+   GELPl(Scheduler sched,
+         unsigned int num_processors,
+         const TaskSet& tasks,
+         unsigned int rounds);
+
+   unsigned long get_bound(unsigned int index) {
+        return bounds[index];
+   }
+
+   double get_Si(unsigned int index) {
+        return S_i[index];
+   }
+
+   double get_Gi(unsigned int index) {
+        return G_i[index];
+   }
+};
+
+#endif
diff --git a/native/interface/sched.i b/native/interface/sched.i
index 255531a..d0809b6 100644
--- a/native/interface/sched.i
+++ b/native/interface/sched.i
@@ -12,6 +12,7 @@
 #include "edf/ffdbf.h"
 #include "edf/load.h"
 #include "edf/gedf.h"
+#include "edf/gel_pl.h"
 #include "sharedres.h"
 %}
 
@@ -39,3 +40,4 @@
 #include "edf/ffdbf.h"
 #include "edf/load.h"
 #include "edf/gedf.h"
+#include "edf/gel_pl.h"
diff --git a/native/src/edf/gel_pl.cpp b/native/src/edf/gel_pl.cpp
new file mode 100644
index 0000000..53ae575
--- /dev/null
+++ b/native/src/edf/gel_pl.cpp
@@ -0,0 +1,206 @@
+#include "tasks.h"
+
+#include "edf/gel_pl.h"
+
+#include <vector>
+#include <limits>
+#include <algorithm>
+#include <cmath>
+
+static bool reversed_order(double first, double second) {
+    return second < first;
+}
+
+GELPl::GELPl(Scheduler sched, unsigned int num_processors, const TaskSet& ts,
+             unsigned int num_rounds)
+:no_cpus(num_processors), tasks(ts), rounds(num_rounds)
+{
+    std::vector<unsigned long> pps;
+    double S;
+    std::vector<double> Y_ints;
+
+    int task_count = tasks.get_task_count();
+    // Reserve capacity in all vectors to minimize allocation costs.
+    pps.reserve(task_count);
+    Y_ints.reserve(task_count);
+    S_i.reserve(task_count);
+    G_i.reserve(task_count);
+
+    // For faster lookups
+    utilizations.reserve(task_count);
+    for (int i = 0; i < task_count; i++) {
+        utilizations.push_back(double(tasks[i].get_wcet())
+                               / double(tasks[i].get_period()));
+    }
+    
+    unsigned long min_pp = std::numeric_limits<unsigned long>::max();
+
+    // Compute initial priority points, including minimum.
+    for (int i = 0; i < task_count; i++) {
+        const Task& task = tasks[i];
+        unsigned long new_pp = task.get_deadline();
+        if (sched == GFL) {
+            new_pp -= ((num_processors - 1) * task.get_wcet()) / num_processors;
+        }
+        pps.push_back(new_pp);
+        if (new_pp < min_pp) {
+            min_pp = new_pp;
+        }
+    }
+
+    // Reduce to compute minimum.  Also compute Y intercepts, S_i values, and
+    // S.
+    S = 0.0;
+    for (int i = 0; i < task_count; i++) {
+        pps[i] -= min_pp;
+        const Task& task = tasks[i];
+        double wcet = double(task.get_wcet());
+        double period = double(task.get_period());
+        S_i[i] = std::max(0.0, wcet * (1.0 -  double(pps[i])/ period));
+        S += S_i[i];
+        Y_ints.push_back((0.0 - wcet/no_cpus) * (wcet / period)
+                         + task.get_wcet() - S_i[i]);
+    }
+
+    double s;
+    if (rounds == 0) {
+        s = compute_exact_s(S, Y_ints);
+    }
+    else {
+        s = compute_binsearch_s(S, Y_ints);
+    }
+
+    for (int i = 0; i < task_count; i++) {
+        bounds.push_back(pps[i]
+                         + tasks[i].get_wcet()
+                         + (unsigned long)std::ceil(
+                         s - (double(tasks[i].get_wcet() / double(no_cpus)))));
+        G_i.push_back(Y_ints[i] + s * utilizations[i]);
+    }
+}
+
+double GELPl::compute_exact_s(double S, const std::vector<double>& Y_ints) {
+    int task_count = tasks.get_task_count();
+
+    std::vector<ReplacementType> replacements;
+    for (int i = 0; i < task_count; i++) {
+        for (int j = i + 1; j < task_count; j++) {
+            // We can ignore parallel and identical lines - either don't
+            // intersect or we don't care which is picked.
+            if (utilizations[i] != utilizations[j]) {
+                double intersect = (Y_ints[j] - Y_ints[i])
+                                   / (utilizations[i] - utilizations[j]);
+                ReplacementType replacement;
+                replacement.location = intersect;
+                if (intersect >= 0.0) {
+                    if (utilizations[i] < utilizations[j]) {
+                        replacement.old_task = i;
+                        replacement.old_task_utilization = utilizations[i];
+                        replacement.new_task = j;
+                    }
+                    else {
+                        replacement.old_task = j;
+                        replacement.old_task_utilization = utilizations[j];
+                        replacement.new_task = i;
+                    }
+                    replacements.push_back(replacement);
+                }
+            }
+        }
+    }
+    std::sort(replacements.begin(), replacements.end());
+
+    std::vector<bool> task_pres;
+    task_pres.assign(task_count, false);
+    
+    double current_value = S;
+    double current_slope = -1 * no_cpus;
+
+    std::vector<TaggedValue> init_pairs;
+    init_pairs.reserve(task_count);
+    for (int i = 0; i < task_count; i++) {
+        TaggedValue new_pair;
+        new_pair.task = i;
+        new_pair.value = Y_ints[i];
+        init_pairs.push_back(new_pair);
+    }
+    
+    // Allows us to efficiently compute sum of top m-1 elements.  They may not
+    // be in order but must be the correct choices.
+    std::nth_element(init_pairs.begin(), init_pairs.begin() + no_cpus - 2,
+                     init_pairs.end());
+
+    for (int i = 0; i < no_cpus - 1; i++) {
+        unsigned int task_index = init_pairs[i].task;
+        task_pres[task_index] = true;
+        current_value += init_pairs[i].value;
+        current_slope += utilizations[task_index];
+    }
+    
+    unsigned int rindex = 0;
+    double next_s = 0.0;
+    double zero = std::numeric_limits<double>::infinity();
+    while (zero > next_s) {
+        double current_s = next_s;
+        zero = current_s - current_value / current_slope;
+        if (rindex < replacements.size()) {
+            ReplacementType replacement = replacements[rindex];
+            next_s = replacement.location;
+            current_value += (next_s - current_s) * current_slope;
+            // Apply replacement, if appropriate
+            if (task_pres[replacement.old_task]
+                    && !task_pres[replacement.new_task]) {
+                task_pres[replacement.old_task] = false;
+                current_slope -= utilizations[replacement.old_task];
+                task_pres[replacement.new_task] = true;
+                current_slope += utilizations[replacement.new_task];
+            }
+            rindex++;
+        }
+        else {
+            next_s = std::numeric_limits<double>::infinity();
+        }
+    }
+    return zero;
+}
+
+double GELPl::compute_binsearch_s(double S, const std::vector<double>& Y_ints) {
+    double min_s = 0.0;
+    double max_s = 1.0;
+    while (compute_M(max_s, S, Y_ints) > 0) {
+        min_s = max_s;
+        max_s *= 2.0;
+    }
+    
+    for (int i = 0; i < rounds; i++) {
+        double middle = (min_s + max_s) / 2.0;
+        if (compute_M(middle, S, Y_ints) < 0) {
+            max_s = middle;
+        }
+        else {
+            min_s = middle;
+        }
+    }
+
+    // max_s is guaranteed to be a legal bound.
+    return max_s;
+}
+
+double GELPl::compute_M(double s, double S, const std::vector<double>& Y_ints) {
+    std::vector<double> Gvals;
+    int task_count = tasks.get_task_count();
+    for (int i = 0; i < task_count; i++) {
+        Gvals.push_back(Y_ints[i] + utilizations[i] * s);
+    }
+
+    // Again, more efficient computation by not totally sorting.
+    std::nth_element(Gvals.begin(), Gvals.begin() + no_cpus - 2, Gvals.end(),
+                     reversed_order);
+    double to_return = S - no_cpus * s;
+    
+    for (int i = 0; i < no_cpus - 1; i++) {
+        to_return += Gvals[i];
+    }
+
+    return to_return;
+}