C++: Break out the DPCP code into own file

Part of refactoring sharedres.cpp.

4 files changed, 218 insertions, 198 deletions

diff --git a/native/Makefile b/native/Makefile
index 997cfce..2204788 100644
--- a/native/Makefile
+++ b/native/Makefile
@@ -47,14 +47,14 @@ CXXFLAGS += -O2 -DNDEBUG
 endif
 
 vpath %.cc interface
-vpath %.cpp src src/edf
+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
 SCHED_OBJ = sim.o schedule_sim.o
 CORE_OBJ  = tasks.o
-SYNC_OBJ  = sharedres.o
+SYNC_OBJ  = sharedres.o dpcp.o
 
 # #### Targets ####
 
diff --git a/native/include/blocking.h b/native/include/blocking.h
new file mode 100644
index 0000000..80b4973
--- /dev/null
+++ b/native/include/blocking.h
@@ -0,0 +1,32 @@
+#ifndef BLOCKING_H
+#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 {
+        LimitedRequestBound(const RequestBound *rqb, unsigned int l) :
+                request_bound(rqb), limit(l) {};
+        LimitedRequestBound() : request_bound(NULL), limit(0) {};
+
+        const RequestBound  *request_bound;
+        unsigned int        limit;
+};
+
+typedef std::vector<LimitedRequestBound> LimitedContentionSet;
+
+void sort_by_request_length(LimitedContentionSet &lcs);
+void sort_by_request_length(Resources& resources);
+void sort_by_request_length(ClusterResources& resources);
+void sort_by_request_length(ContentionSet& cs);
+
+#endif
diff --git a/native/src/blocking/dpcp.cpp b/native/src/blocking/dpcp.cpp
new file mode 100644
index 0000000..6e194aa
--- /dev/null
+++ b/native/src/blocking/dpcp.cpp
@@ -0,0 +1,178 @@
+#include "sharedres.h"
+#include "blocking.h"
+
+#include "stl-helper.h"
+
+// ************************************************** DPCP **************
+/*
+
+  DPCP blocking terms (Rajkumar, 1991, page 87):
+
+  1) Local PCP blocking => does not apply here, we only care about global
+  resources.
+
+  2) A lower-priority gcs on a remote proc each time that Ji issues a request.
+
+  3) All requests of all higher-priority tasks on all remote processors that Ji
+  accesses.
+
+  4) Global critical sections on Ji's CPU. Since gcs are not part of the job
+  execution time in our model, it does not matter whether the local gcs's
+  belong to lower or higher-priority tasks.
+ */
+
+
+static void split_by_locality(const ResourceSharingInfo& info,
+                              const ResourceLocality& locality,
+                              AllPerCluster& per_cluster)
+{
+        foreach(info.get_tasks(), it)
+        {
+                while (it->get_cluster()  >= per_cluster.size())
+                        per_cluster.push_back(ContentionSet());
+
+                foreach(it->get_requests(), jt)
+                {
+                        const RequestBound &req = *jt;
+                        int cpu = locality[req.get_resource_id()];
+
+                        if (cpu == NO_CPU)
+                                // NO_CPU => dedicated synchronization processor
+                                continue;
+
+                        while ((unsigned int) cpu  >= per_cluster.size())
+                                per_cluster.push_back(ContentionSet());
+
+                        per_cluster[cpu].push_back(&req);
+                }
+        }
+}
+
+static unsigned int count_requests_to_cpu(
+        const TaskInfo& tsk,
+        const ResourceLocality& locality,
+        int cpu)
+{
+        unsigned int count = 0;
+
+        foreach(tsk.get_requests(), req)
+                if (locality[req->get_resource_id()] == cpu)
+                        count += req->get_num_requests();
+
+        return count;
+}
+
+static Interference bound_blocking_dpcp(
+        const TaskInfo* tsk,
+        const ContentionSet& cont,
+        unsigned int max_lower_prio)
+{
+        Interference inter;
+        const unsigned int interval = tsk->get_response();
+
+        // assumption: cont is ordered by request length
+        foreach(cont, it)
+        {
+                const RequestBound* req = *it;
+
+                // can't block itself
+                if (req->get_task() != tsk)
+                {
+                        unsigned int num;
+                        if (req->get_task()->get_priority() < tsk->get_priority())
+                        {
+                                // higher prio => all of them
+                                num = req->get_max_num_requests(interval);
+                                inter.count += num;
+                                inter.total_length += num * req->get_request_length();
+                        }
+                        else if (max_lower_prio)
+                        {
+                                // lower prio => only remaining
+                                num = std::min(req->get_max_num_requests(interval), max_lower_prio);
+                                inter.count += num;
+                                inter.total_length += num * req->get_request_length();
+                                max_lower_prio -= num;
+                        }
+                }
+        }
+
+        return inter;
+}
+
+static Interference dpcp_remote_bound(
+        const TaskInfo& tsk,
+        const ResourceLocality& locality,
+        const AllPerCluster& per_cpu)
+{
+        Interference blocking;
+        unsigned int cpu = 0;
+
+        foreach(per_cpu, it)
+        {
+                // this is about remote delays
+                if (cpu != tsk.get_cluster())
+                {
+                        const ContentionSet &cs = *it;
+                        unsigned int reqs;
+                        reqs = count_requests_to_cpu(tsk, locality, cpu);
+
+                        if (reqs > 0)
+                                blocking += bound_blocking_dpcp(&tsk, cs, reqs);
+                }
+                cpu++;
+        }
+
+        return blocking;
+}
+
+
+static Interference dpcp_local_bound(
+        const TaskInfo* tsk,
+        const ContentionSet& local)
+{
+        Interference blocking;
+        const unsigned int interval = tsk->get_response();
+
+        foreach(local, it)
+        {
+                const RequestBound* req = *it;
+                if (req->get_task() != tsk)
+                {
+                        unsigned int num;
+                        num = req->get_max_num_requests(interval);
+                        blocking.count += num;
+                        blocking.total_length += num * req->get_request_length();
+                }
+        }
+
+        return blocking;
+}
+
+
+BlockingBounds* dpcp_bounds(const ResourceSharingInfo& info,
+                            const ResourceLocality& locality)
+{
+        AllPerCluster per_cpu;
+
+        split_by_locality(info, locality, per_cpu);
+        sort_by_request_length(per_cpu);
+
+        BlockingBounds* _results = new BlockingBounds(info);