Move MPPC++: Break out the MPCP code into own file

Part of refactoring sharedres.cpp.

4 files changed, 335 insertions, 325 deletions

diff --git a/native/Makefile b/native/Makefile
index 2204788..ec6da1c 100644
--- a/native/Makefile
+++ b/native/Makefile
@@ -54,7 +54,7 @@ vpath %.cpp src src/edf src/blocking
 EDF_OBJ   = baker.o baruah.o gfb.o bcl.o bcl_iterative.o rta.o ffdbf.o gedf.o load.o cpu_time.o
 SCHED_OBJ = sim.o schedule_sim.o
 CORE_OBJ  = tasks.o
-SYNC_OBJ  = sharedres.o dpcp.o
+SYNC_OBJ  = sharedres.o dpcp.o mpcp.o
 
 # #### Targets ####
 
diff --git a/native/include/blocking.h b/native/include/blocking.h
index 80b4973..9930aa2 100644
--- a/native/include/blocking.h
+++ b/native/include/blocking.h
@@ -2,15 +2,10 @@
 #define BLOCKING_H
 
 typedef std::vector<const RequestBound*> ContentionSet;
-
 typedef std::vector<ContentionSet> Resources;
-
 typedef std::vector<Resources> ClusterResources;
-
 typedef std::vector<ContentionSet> AllPerCluster;
-
 typedef std::vector<ContentionSet> TaskContention;
-
 typedef std::vector<TaskContention> ClusterContention;
 
 struct LimitedRequestBound {
@@ -29,4 +24,15 @@ void sort_by_request_length(Resources& resources);
 void sort_by_request_length(ClusterResources& resources);
 void sort_by_request_length(ContentionSet& cs);
 
+
+typedef std::vector<const TaskInfo*> Cluster;
+typedef std::vector<Cluster> Clusters;
+
+void split_by_cluster(const ResourceSharingInfo& info, Clusters& clusters);
+void split_by_resource(const ResourceSharingInfo& info, Resources& resources);
+
+
+
+extern const unsigned int UNLIMITED;
+
 #endif
diff --git a/native/src/blocking/mpcp.cpp b/native/src/blocking/mpcp.cpp
new file mode 100644
index 0000000..8b87556
--- /dev/null
+++ b/native/src/blocking/mpcp.cpp
@@ -0,0 +1,320 @@
+#include "sharedres.h"
+#include "blocking.h"
+
+#include "stl-helper.h"
+#include "math-helper.h"
+
+// ***************************  MPCP ******************************************
+
+
+typedef std::vector<unsigned int> PriorityCeilings;
+
+static void determine_priority_ceilings(const Resources& resources,
+                                        PriorityCeilings& ceilings)
+{
+        ceilings.reserve(resources.size());
+
+        foreach(resources, it)
+        {
+                unsigned int ceiling = UINT_MAX;
+                const ContentionSet& cs = *it;
+
+                foreach(cs, jt)
+                {
+                        const RequestBound* req = *jt;
+                        ceiling = std::min(ceiling, req->get_task()->get_priority());
+                }
+
+                ceilings.push_back(ceiling);
+        }
+}
+
+typedef std::vector<unsigned long> ResponseTimes;
+typedef std::vector<ResponseTimes> TaskResponseTimes;
+typedef std::vector<TaskResponseTimes> ClusterResponseTimes;
+
+static unsigned long get_max_gcs_length(const TaskInfo* tsk,
+                                        const PriorityCeilings& ceilings,
+                                        unsigned int preempted_ceiling)
+{
+        unsigned long gcs_length = 0;
+
+        foreach(tsk->get_requests(), it)
+        {
+                unsigned int prio  = ceilings[it->get_resource_id()];
+                if (prio < preempted_ceiling)
+                        gcs_length = std::max(gcs_length,
+                                              (unsigned long) it->get_request_length());
+        }
+
+        return gcs_length;
+}
+
+static void determine_gcs_response_times(const TaskInfo* tsk,
+                                         const Cluster& cluster,
+                                         const PriorityCeilings& ceilings,
+                                         ResponseTimes& times)
+{
+        times.reserve(tsk->get_requests().size());
+
+        foreach(tsk->get_requests(), it)
+        {
+                unsigned long resp = it->get_request_length();
+                unsigned int prio  = ceilings[it->get_resource_id()];
+
+                // Equation (2) in LNR:09.
+                // One request of each local gcs that can preempt our ceiling,
+                // but at most one per task (since tasks are sequential).
+
+                foreach(cluster, jt)
+                {
+                        const TaskInfo* t = *jt;
+
+                        if (t != tsk)
+                                resp += get_max_gcs_length(t, ceilings, prio);
+                }
+
+                times.push_back(resp);
+        }
+}
+
+static void determine_gcs_response_times(const Cluster& cluster,
+                                         const PriorityCeilings& ceilings,
+                                         TaskResponseTimes& times)
+{
+        times.reserve(cluster.size());
+        foreach(cluster, it)
+        {
+                times.push_back(ResponseTimes());
+                determine_gcs_response_times(*it, cluster, ceilings,
+                                             times.back());
+        }
+}
+
+static void determine_gcs_response_times(const Clusters& clusters,
+                                         const PriorityCeilings& ceilings,
+                                         ClusterResponseTimes& times)
+{
+        times.reserve(clusters.size());
+        foreach(clusters, it)
+        {
+                times.push_back(TaskResponseTimes());
+                determine_gcs_response_times(*it, ceilings, times.back());
+        }
+}
+
+static unsigned long response_time_for(unsigned int res_id,
+                                       unsigned long interval,
+                                       const TaskInfo* tsk,
+                                       const ResponseTimes& resp,
+                                       bool multiple)
+{
+        const Requests& requests = tsk->get_requests();
+        unsigned int i = 0;
+
+        for (i = 0; i < requests.size(); i++)
+                if (requests[i].get_resource_id() == res_id)
+                {
+                        if (multiple)
+                        {
+                                // Equation (3) in LNR:09.
+                                // How many jobs?
+                                unsigned long num_jobs;
+                                num_jobs  = divide_with_ceil(interval, tsk->get_period());
+                                num_jobs += 1;
+
+                                // Note: this may represent multiple gcs, so multiply.
+                                return num_jobs * resp[i] * requests[i].get_num_requests();
+                        }
+                        else
+                                // Just one request.
+                                return resp[i];
+                }
+        // if we get here, then the task does not access res_id
+        return 0;
+}
+
+static unsigned long  mpcp_remote_blocking(unsigned int res_id,
+                                           unsigned long interval,
+                                           const TaskInfo* tsk,
+                                           const Cluster& cluster,
+                                           const TaskResponseTimes times,
+                                           unsigned long& max_lower)
+{
+        unsigned int i;
+        unsigned long blocking = 0;
+
+        // consider each task in cluster
+        for (i = 0; i < cluster.size(); i++)
+        {
+                const TaskInfo* t = cluster[i];
+                if (t != tsk)
+                {
+                        if (t->get_priority() < tsk->get_priority())
+                                // This is a higher-priority task;
+                                // it can block multiple times.
+                                blocking += response_time_for(res_id, interval,
+                                                              t, times[i], true);
+                        else
+                                // This is a lower-priority task;