Add LP-based blocking analysis for MPCP

6 files changed, 734 insertions, 2 deletions

diff --git a/native/Makefile b/native/Makefile
index d722fcd..2df9893 100644
--- a/native/Makefile
+++ b/native/Makefile
@@ -118,7 +118,7 @@ ALL = testmain _sched.so _locking.so _sim.so
 
 # Compile LP-based code only if we have a solver.
 ifneq ($(CPLEX_PATH)$(GLPK_PATH),)
-LP_OBJ    = lp_common.o io.o lp_dflp.o lp_dpcp.o
+LP_OBJ    = lp_common.o io.o lp_dflp.o lp_dpcp.o lp_mpcp.o
 
 ifneq ($(CPLEX_PATH),)
 LP_OBJ   += cplex.o cpx.o
@@ -159,5 +159,5 @@ _locking.so: ${SYNC_OBJ} interface/locking_wrap.o
 _sim.so: ${CORE_OBJ} ${SCHED_OBJ} interface/sim_wrap.o
         $(CXX) $(SOFLAGS) $(PYTHON_LIB) -o $@ $+ $(LDFLAGS)
 
-_lp_analysis.so: ${LP_OBJ} sharedres.o cpu_time.o interface/lp_analysis_wrap.o
+_lp_analysis.so: ${LP_OBJ} sharedres.o mpcp.o cpu_time.o interface/lp_analysis_wrap.o
         $(CXX) $(SOFLAGS) $(PYTHON_LIB) -o $@ $+ $(LDFLAGS)
diff --git a/native/include/lp_analysis.h b/native/include/lp_analysis.h
index c33be61..182eff1 100644
--- a/native/include/lp_analysis.h
+++ b/native/include/lp_analysis.h
@@ -9,4 +9,6 @@ extern BlockingBounds* lp_dpcp_bounds(const ResourceSharingInfo& info,
 extern BlockingBounds* lp_dflp_bounds(const ResourceSharingInfo& info,
                             const ResourceLocality& locality);
 
+extern BlockingBounds* lp_mpcp_bounds(const ResourceSharingInfo& info);
+
 #endif /* LP_ANALYSYS_H_ */
diff --git a/native/include/lp_common.h b/native/include/lp_common.h
index 06c5e78..b459664 100644
--- a/native/include/lp_common.h
+++ b/native/include/lp_common.h
@@ -118,6 +118,18 @@ void add_topology_constraints_shm(
         const TaskInfo& ti,
         LinearProgram& lp);
 
+void add_local_lower_priority_constraints_shm(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp);
+
+void add_local_higher_priority_constraints_shm(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp);
+
 // A generic for loop that iterates 'request_index_variable' from 0 to the
 // maximum number of requests issued by task tx while ti is pending. 'tx_request'
 // should be of type RequestBound&.
@@ -169,6 +181,16 @@ void add_topology_constraints_shm(
         foreach(tasks, task_iter)                               \
         if (task_iter->get_cluster() != (local_task).get_cluster())
 
+// iterate only over tasks with equal or lower priority, excluding local tasks
+#define foreach_remote_lowereq_priority_task(tasks, reference_task, task_iter) \
+        foreach_remote_task(tasks, reference_task, task_iter)                      \
+        if (task_iter->get_priority() >= (reference_task).get_priority())
+
+// iterate only over tasks with higher priority, excluding local tasks
+#define foreach_remote_higher_priority_task(tasks, reference_task, task_iter) \
+        foreach_remote_task(tasks, reference_task, task_iter)              \
+        if (task_iter->get_priority() < (reference_task).get_priority())
+
 #define foreach_local_task(tasks, local_task, task_iter)        \
         foreach(tasks, task_iter)                               \
         if (task_iter->get_cluster() == (local_task).get_cluster())
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/