2 files changed, 697 insertions, 0 deletions

diff --git a/native/src/blocking/linprog/lp_common.cpp b/native/src/blocking/linprog/lp_common.cpp
index a7bb1b5..1715d3b 100644
--- a/native/src/blocking/linprog/lp_common.cpp
+++ b/native/src/blocking/linprog/lp_common.cpp
@@ -234,6 +234,7 @@ void add_local_lower_priority_constraints(
 }
 
 
+// Constraint 10 in [Brandenburg 2013]
 // For shared-memory protocols.
 // Remote tasks cannot preempt Ti since they are not scheduled
 // on Ti's assigned task; therefore force BLOCKING_PREEMPT to zero.
@@ -261,3 +262,110 @@ void add_topology_constraints_shm(
         }
         lp.add_equality(exp, 0);
 }
+
+// Constraint 9 in [Brandenburg 2013]
+// local higher-priority tasks never cause blocking under SHM protocols
+void add_local_higher_priority_constraints_shm(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp)
+{
+        LinearExpression *exp = new LinearExpression();
+
+        foreach_local_task(info.get_tasks(), ti, tx)
+        {
+                if (tx->get_priority() < ti.get_priority())
+                {
+                        unsigned int t = tx->get_id();
+                        foreach(tx->get_requests(), request)
+                        {
+                                unsigned int q = request->get_resource_id();
+                                foreach_request_instance(*request, ti, v)
+                                {
+                                        unsigned int var_id;
+                                        var_id = vars.lookup(t, q, v,
+                                                             BLOCKING_PREEMPT);
+                                        exp->add_var(var_id);
+
+                                        var_id = vars.lookup(t, q, v,
+                                                             BLOCKING_INDIRECT);
+                                        exp->add_var(var_id);
+
+                                        var_id = vars.lookup(t, q, v,
+                                                             BLOCKING_DIRECT);
+                                        exp->add_var(var_id);
+                                }
+                        }
+                }
+        }
+        lp.add_equality(exp, 0);
+}
+
+static unsigned int max_num_arrivals_shm(
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti)
+{
+        hashmap<unsigned int, unsigned int> request_counts;
+
+        foreach(ti.get_requests(), req)
+                request_counts[req->get_resource_id()] = 0;
+
+        // count how often each resource is accessed on remote cores
+        foreach_remote_task(info.get_tasks(), ti, tx)
+        {
+                foreach(tx->get_requests(), req)
+                {
+                        unsigned int q = req->get_resource_id();
+                        if (request_counts.find(q) != request_counts.end())
+                                request_counts[q] += req->get_max_num_requests(ti.get_response());
+                }
+        }
+
+        // initialize to 1 to account for job release
+        unsigned int total = 1;
+
+        foreach(ti.get_requests(), req)
+                total += std::min(request_counts[req->get_resource_id()],
+                                  req->get_num_requests());
+
+        return total;
+}
+
+// Constraint 11 in [Brandenburg 2013]
+// Local lower-priority tasks block at most once each time
+// that Ti suspends (and once after release).
+void add_local_lower_priority_constraints_shm(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp)
+{
+        unsigned int num_arrivals = max_num_arrivals_shm(info, ti);
+
+        foreach_local_lowereq_priority_task_except(info.get_tasks(), ti, tx)
+        {
+                LinearExpression *exp = new LinearExpression();
+                unsigned int t = tx->get_id();
+                foreach(tx->get_requests(), request)
+                {
+                        unsigned int q = request->get_resource_id();
+                        foreach_request_instance(*request, ti, v)
+                        {
+                                unsigned int var_id;
+                                var_id = vars.lookup(t, q, v,
+                                                     BLOCKING_PREEMPT);
+                                exp->add_var(var_id);
+
+                                var_id = vars.lookup(t, q, v,
+                                                     BLOCKING_INDIRECT);
+                                exp->add_var(var_id);
+
+                                var_id = vars.lookup(t, q, v,
+                                                     BLOCKING_DIRECT);
+                                exp->add_var(var_id);
+                        }
+                }
+                lp.add_equality(exp, num_arrivals);
+        }
+}
diff --git a/native/src/blocking/linprog/lp_mpcp.cpp b/native/src/blocking/linprog/lp_mpcp.cpp
new file mode 100644
index 0000000..bccea5d
--- /dev/null
+++ b/native/src/blocking/linprog/lp_mpcp.cpp
@@ -0,0 +1,589 @@
+#include <iostream>
+#include <set>
+#include <algorithm>
+
+#include "lp_common.h"
+#include "blocking.h"
+#include "stl-hashmap.h"
+
+#include "cpu_time.h"
+
+#include "mpcp.h"
+
+#define NO_BOUND (-1)
+
+typedef hashmap<unsigned int, unsigned int> PerResourceCounts;
+typedef hashmap<unsigned int, hashmap<unsigned int, unsigned int> > PerTaskPerRequestDirectBlockingBound;
+typedef hashmap<unsigned int, unsigned int> PerTaskIndirectBlockingBound;
+
+class GcsResponseTimes
+{
+private:
+        // per each task, and per each global critical section (gcs),
+        // the maximum wait time bound
+        hashmap< unsigned long, hashmap< unsigned int, long> > remote_delay;
+
+        hashmap< unsigned long, hashmap< unsigned int, unsigned long> > gcs_response;
+
+        const ResourceSharingInfo &info;
+        const MPCPCeilings &prio_ceilings;
+
+        long bound_remote_delay(const TaskInfo &tsk,
+                                unsigned int res_id);
+
+        void bound_gcs_response_times(void);
+
+
+public:
+        GcsResponseTimes(const ResourceSharingInfo &i,
+                         const MPCPCeilings &pc)
+                         : info(i), prio_ceilings(pc)
+        {
+                bound_gcs_response_times();
+        }
+
+
+        long get_max_remote_delay(const TaskInfo &ti, unsigned int res_id)
+        {
+                if (remote_delay.find(ti.get_id()) == remote_delay.end())
+                        remote_delay[ti.get_id()] = hashmap<unsigned int, long>();
+
+                hashmap<unsigned int, long> &tmap = remote_delay[ti.get_id()];
+
+                if (tmap.find(res_id) == tmap.end())
+                        tmap[res_id] = bound_remote_delay(ti, res_id);
+
+                return tmap[res_id];
+        }
+
+        long get_gcs_response(const TaskInfo &ti, unsigned int res_id)
+        {
+                // look up the task
+                if (gcs_response.find(ti.get_id()) == gcs_response.end())
+                        return NO_BOUND;
+
+                hashmap<unsigned int, unsigned long> &tmap = gcs_response[ti.get_id()];
+
+                // look up the resource
+                if (tmap.find(res_id) == tmap.end())
+                        return NO_BOUND;
+
+                return tmap[res_id];
+        }
+};
+
+
+void GcsResponseTimes::bound_gcs_response_times()
+{
+        Clusters clusters;
+        split_by_cluster(info, clusters);
+
+        ClusterResponseTimes responses;
+        determine_gcs_response_times(clusters, prio_ceilings, responses);
+
+        for (unsigned int c = 0; c < clusters.size(); c++)