Implement LP-based OMIP blocking analysis

8 files changed, 334 insertions, 1 deletions

diff --git a/native/Makefile b/native/Makefile
index 6f1abe2..54c75d8 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_mpcp.o lp_fmlp.o
+LP_OBJ    = lp_common.o io.o lp_dflp.o lp_dpcp.o lp_mpcp.o lp_fmlp.o lp_omip.o
 
 ifneq ($(CPLEX_PATH),)
 LP_OBJ   += cplex.o cpx.o
diff --git a/native/include/lp_analysis.h b/native/include/lp_analysis.h
index 998eeb5..862c09e 100644
--- a/native/include/lp_analysis.h
+++ b/native/include/lp_analysis.h
@@ -13,4 +13,9 @@ BlockingBounds* lp_mpcp_bounds(const ResourceSharingInfo& info);
 
 BlockingBounds* lp_part_fmlp_bounds(const ResourceSharingInfo& info);
 
+BlockingBounds* lp_omip_bounds(
+        const ResourceSharingInfo& info,
+        unsigned int num_procs,
+        unsigned int cluster_size);
+
 #endif /* LP_ANALYSYS_H_ */
diff --git a/native/include/lp_common.h b/native/include/lp_common.h
index b459664..8f612ea 100644
--- a/native/include/lp_common.h
+++ b/native/include/lp_common.h
@@ -19,6 +19,9 @@ enum blocking_type
         BLOCKING_PREEMPT
 };
 
+// s-oblivious analysis reuses BLOCKING_DIRECT as a catch-all blocking type.
+#define BLOCKING_SOB BLOCKING_DIRECT
+
 class VarMapper {
 private:
         hashmap<uint64_t, unsigned int> map;
@@ -97,6 +100,12 @@ void set_blocking_objective_part_shm(
         LinearExpression *local_obj = 0,
         LinearExpression *remote_obj = 0);
 
+void set_blocking_objective_sob(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp);
+
 void add_mutex_constraints(VarMapper& vars,
                 const ResourceSharingInfo& info,
                 const TaskInfo& ti,  LinearProgram& lp);
diff --git a/native/include/sharedres_types.h b/native/include/sharedres_types.h
index 898434c..fbe8f72 100644
--- a/native/include/sharedres_types.h
+++ b/native/include/sharedres_types.h
@@ -119,6 +119,13 @@ public:
                 return len;
         }
 
+        unsigned int get_num_requests(unsigned int res_id) const
+        {
+                foreach(requests, it)
+                        if (it->get_resource_id() == res_id)
+                                return it->get_num_requests();
+                return 0;
+        }
 };
 
 typedef std::vector<TaskInfo> TaskInfos;
diff --git a/native/src/blocking/linprog/lp_common.cpp b/native/src/blocking/linprog/lp_common.cpp
index 1715d3b..2df1284 100644
--- a/native/src/blocking/linprog/lp_common.cpp
+++ b/native/src/blocking/linprog/lp_common.cpp
@@ -119,6 +119,40 @@ void set_blocking_objective_part_shm(
         }
 }
 
+// This version is for suspension-oblivious shared-memory protocols,
+// where the analysis does not differentiate among the different kinds
+// of blocking (since they are all just added to the execution time anyway).
+void set_blocking_objective_sob(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp)
+{
+        LinearExpression *obj;
+
+        obj = lp.get_objective();
+
+        foreach_task_except(info.get_tasks(), ti, tx)
+        {
+                unsigned int t = tx->get_id();
+
+                foreach(tx->get_requests(), request)
+                {
+                        unsigned int q = request->get_resource_id();
+                        double length = request->get_request_length();;
+
+                        foreach_request_instance(*request, ti, v)
+                        {
+                                unsigned int var_id;
+
+                                var_id = vars.lookup(t, q, v, BLOCKING_SOB);
+                                obj->add_term(length, var_id);
+                        }
+                }
+        }
+}
+
+
 // Constraint 1 in [Brandenburg 2013]
 void add_mutex_constraints(
         VarMapper& vars,
diff --git a/native/src/blocking/linprog/lp_omip.cpp b/native/src/blocking/linprog/lp_omip.cpp
new file mode 100644
index 0000000..0e5d864
--- /dev/null
+++ b/native/src/blocking/linprog/lp_omip.cpp
@@ -0,0 +1,268 @@
+#include <iostream>
+#include <set>
+#include <algorithm>
+#include <cmath>
+
+#include "lp_common.h"
+#include "blocking.h"
+#include "stl-hashmap.h"
+
+#include "cpu_time.h"
+
+// Per-cluster, per-resource access counts.
+typedef hashmap<unsigned int, unsigned int> AccessCounts;
+typedef hashmap<unsigned int, AccessCounts> PerClusterACounts;
+
+static AccessCounts count_accesses(
+        const ResourceSharingInfo& info,
+        unsigned int cluster)
+{
+        AccessCounts acount;
+
+        foreach(info.get_tasks(), tx) {
+                if (tx->get_cluster() == cluster) {
+                        foreach(tx->get_requests(), request)
+                        {
+                                unsigned int q = request->get_resource_id();
+                                // count that q is being accessed by tx
+                                acount[q] += 1;
+                        }
+                }
+        }
+        return acount;
+}
+
+static void add_total_constraints(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp,
+        unsigned int num_procs)
+{
+        // one constraint for each resource
+        hashmap<unsigned int, LinearExpression *> constraints;
+        LinearExpression *exp;
+
+        foreach_task_except(info.get_tasks(), ti, tx)
+        {
+                unsigned int t = tx->get_id();
+
+                //for all requests accessed by tx
+                foreach(tx->get_requests(), request)
+                {
+                        unsigned int q = request->get_resource_id();
+
+                        if (constraints.find(q) == constraints.end())
+                                constraints[q] = new LinearExpression();
+                        exp = constraints[q];
+                        foreach_request_instance(*request, ti, v)
+                        {
+                                unsigned int var_id;
+                                var_id = vars.lookup(t, q, v, BLOCKING_SOB);
+                                exp->add_var(var_id);
+                        }
+                }
+        }
+
+        // add each per-resource constraint
+        foreach(constraints, it) {
+                unsigned int bound = ti.get_num_requests(it->first);
+                bound *= (2 * num_procs - 1);
+                lp.add_inequality(it->second, bound);
+        }
+}
+
+
+static void add_remote_cluster_constraints(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp,
+        AccessCounts& acount,
+        unsigned int num_procs,
+        unsigned int cl