Add LP-based blocking analysis for FMLP+

4 files changed, 307 insertions, 6 deletions

diff --git a/native/Makefile b/native/Makefile
index 2df9893..6f1abe2 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_OBJ    = lp_common.o io.o lp_dflp.o lp_dpcp.o lp_mpcp.o lp_fmlp.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 182eff1..998eeb5 100644
--- a/native/include/lp_analysis.h
+++ b/native/include/lp_analysis.h
@@ -3,12 +3,14 @@
 
 #include "sharedres_types.h"
 
-extern BlockingBounds* lp_dpcp_bounds(const ResourceSharingInfo& info,
-                            const ResourceLocality& locality, bool use_RTA = true);
+BlockingBounds* lp_dpcp_bounds(const ResourceSharingInfo& info,
+                    const ResourceLocality& locality, bool use_RTA = true);
 
-extern BlockingBounds* lp_dflp_bounds(const ResourceSharingInfo& info,
-                            const ResourceLocality& locality);
+BlockingBounds* lp_dflp_bounds(const ResourceSharingInfo& info,
+                    const ResourceLocality& locality);
 
-extern BlockingBounds* lp_mpcp_bounds(const ResourceSharingInfo& info);
+BlockingBounds* lp_mpcp_bounds(const ResourceSharingInfo& info);
+
+BlockingBounds* lp_part_fmlp_bounds(const ResourceSharingInfo& info);
 
 #endif /* LP_ANALYSYS_H_ */
diff --git a/native/src/blocking/linprog/lp_fmlp.cpp b/native/src/blocking/linprog/lp_fmlp.cpp
new file mode 100644
index 0000000..75e2186
--- /dev/null
+++ b/native/src/blocking/linprog/lp_fmlp.cpp
@@ -0,0 +1,286 @@
+#include <iostream>
+#include <set>
+#include <algorithm>
+
+#include "lp_common.h"
+#include "blocking.h"
+#include "stl-hashmap.h"
+
+#include "cpu_time.h"
+
+typedef hashmap<unsigned int, unsigned int> BlockingLimits;
+
+// Constraint 14
+static void add_fifo_cluster_constraints(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp)
+{
+        foreach_remote_task(info.get_tasks(), ti, tx)
+        {
+                unsigned int t = tx->get_id();
+
+                // compute direct blocking opportunities, not counting Tx
+                BlockingLimits per_resource_remote;
+
+                foreach(ti.get_requests(), req)
+                        per_resource_remote[req->get_resource_id()] = 0;
+
+                foreach_local_task_except(info.get_tasks(), *tx, ty)
+                {
+                        foreach(ty->get_requests(), req)
+                        {
+                                unsigned int u = req->get_resource_id();
+                                if (per_resource_remote.find(u) !=
+                                    per_resource_remote.end())
+                                        per_resource_remote[u] += req->get_max_num_requests(ti.get_response());
+                        }
+                }
+
+                unsigned int total_limit = 0;
+                foreach(ti.get_requests(), req)
+                {
+                        unsigned int u = req->get_resource_id();
+                        total_limit += std::min(req->get_num_requests(),
+                                                per_resource_remote[u]);
+                }
+
+                LinearExpression *exp = new LinearExpression();
+
+                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_INDIRECT);
+                                exp->add_var(var_id);
+                        }
+                }
+
+                lp.add_inequality(exp, total_limit);
+        }
+}
+
+// Constraint 13
+static void add_total_fifo_constraints(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp,
+        BlockingLimits &per_cluster_counts)
+{
+
+        unsigned int total_num_requests = 0;
+
+        foreach(ti.get_requests(), req)
+                total_num_requests += req->get_num_requests();
+
+        foreach_task_except(info.get_tasks(), ti, tx)
+        {
+                unsigned int t = tx->get_id();
+
+                LinearExpression *exp = new LinearExpression();
+
+                //for all requests accessed by tx
+                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_DIRECT);
+                                exp->add_var(var_id);
+                                var_id = vars.lookup(t, q, v, BLOCKING_INDIRECT);
+                                exp->add_var(var_id);
+                        }
+                }
+
+                lp.add_inequality(exp, per_cluster_counts[tx->get_cluster()]);
+        }
+}
+
+// Constraint 12
+static void add_fifo_resource_constraints(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp)
+{
+        BlockingLimits per_resource_counts;
+
+        foreach(ti.get_requests(), req)
+                per_resource_counts[req->get_resource_id()] = req->get_num_requests();
+
+        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();
+                        LinearExpression *exp = new LinearExpression();
+
+                        foreach_request_instance(*request, ti, v)
+                        {
+                                unsigned int var_id;
+                                var_id = vars.lookup(t, q, v, BLOCKING_DIRECT);
+                                exp->add_var(var_id);
+                        }
+
+                        lp.add_inequality(exp, per_resource_counts[q]);
+                }
+        }
+}
+
+static BlockingLimits count_blocking_opportunities(
+        const ResourceSharingInfo &info,
+        const TaskInfo& ti)
+{
+        BlockingLimits per_cluster_counts;
+
+        foreach_task_except(info.get_tasks(), ti, tx)
+        {
+                unsigned int c = tx->get_cluster();
+
+                if (per_cluster_counts.find(c) == per_cluster_counts.end())
+                {
+                        // compute direct blocking opportunities on Tx's cluster
+                        BlockingLimits per_resource_remote;
+
+                        foreach(ti.get_requests(), req)
+                                per_resource_remote[req->get_resource_id()] = 0;
+
+                        foreach_local_task(info.get_tasks(), *tx, ty)
+                        {
+                                foreach(ty->get_requests(), req)
+                                {
+                                        unsigned int u = req->get_resource_id();
+                                        if (per_resource_remote.find(u) !=
+                                            per_resource_remote.end())
+                                                per_resource_remote[u] += req->get_max_num_requests(ti.get_response());
+                                }
+                        }
+
+                        per_cluster_counts[c] = 0;
+                        foreach(ti.get_requests(), req)
+                        {