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)
+                        {
+                                unsigned int u = req->get_resource_id();
+                                per_cluster_counts[c] += std::min(req->get_num_requests(),
+                                                         per_resource_remote[u]);
+                        }
+                }
+        }
+
+        return per_cluster_counts;
+}
+
+static void add_fmlp_constraints(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const TaskInfo& ti,
+        LinearProgram& lp)
+{
+        // Constraint 1
+        add_mutex_constraints(vars, info, ti, lp);
+        // Constraint  9
+        add_local_higher_priority_constraints_shm(vars, info, ti, lp);
+        // Constraint 10
+        add_topology_constraints_shm(vars, info, ti, lp);
+        // Constraint 11
+        add_local_lower_priority_constraints_shm(vars, info, ti, lp);
+
+        BlockingLimits per_cluster_counts;
+        per_cluster_counts = count_blocking_opportunities(info, ti);
+
+        // Constraint 12
+        add_fifo_resource_constraints(vars, info, ti, lp);
+        // Constraint 13
+        add_total_fifo_constraints(vars, info, ti, lp, per_cluster_counts);
+        // Constraint 14
+        add_fifo_cluster_constraints(vars, info, ti, lp);
+}
+
+static void apply_fmlp_bounds_for_task(
+        unsigned int i,
+        BlockingBounds& bounds,
+        const ResourceSharingInfo& info)
+{
+        LinearProgram lp;
+        VarMapper vars;
+        const TaskInfo& ti = info.get_tasks()[i];
+        LinearExpression *local_obj = new LinearExpression();
+
+#if DEBUG_LP_OVERHEADS >= 2
+        static DEFINE_CPU_CLOCK(model_gen_cost);
+        static DEFINE_CPU_CLOCK(solver_cost);
+
+        std::cout << "---- " << __FUNCTION__ << " ----" << std::endl;
+
+        model_gen_cost.start();
+#endif
+
+        set_blocking_objective_part_shm(vars, info, ti, lp, local_obj);
+        vars.seal();
+
+        add_fmlp_constraints(vars, info, ti, lp);
+
+#if DEBUG_LP_OVERHEADS >= 2
+        model_gen_cost.stop();
+        std::cout << model_gen_cost << std::endl;
+        solver_cost.start();
+#endif
+
+        Solution *sol = linprog_solve(lp, vars.get_num_vars());
+
+#if DEBUG_LP_OVERHEADS >= 2
+        solver_cost.stop();
+        std::cout << solver_cost << std::endl;
+#endif
+        assert(sol != NULL);
+
+        Interference total, remote, local;
+
+        total.total_length = sol->evaluate(*lp.get_objective());
+        local.total_length = sol->evaluate(*local_obj);
+        remote.total_length = total.total_length - local.total_length;
+
+        bounds[i] = total;
+        bounds.set_remote_blocking(i, remote);
+        bounds.set_local_blocking(i, local);
+
+        delete local_obj;
+        delete sol;
+}
+
+
+static BlockingBounds* _lp_fmlp_bounds(const ResourceSharingInfo& info)
+{
+        BlockingBounds* results = new BlockingBounds(info);
+
+        for (unsigned int i = 0; i < info.get_tasks().size(); i++)
+                apply_fmlp_bounds_for_task(i, *results, info);
+
+        return results;
+}
+
+BlockingBounds* lp_part_fmlp_bounds(const ResourceSharingInfo& info)
+{
+#if DEBUG_LP_OVERHEADS >= 1
+        static DEFINE_CPU_CLOCK(cpu_costs);
+
+        cpu_costs.start();
+#endif
+
+        BlockingBounds *results = _lp_fmlp_bounds(info);
+
+#if DEBUG_LP_OVERHEADS >= 1
+        cpu_costs.stop();
+        std::cout << cpu_costs << std::endl;
+#endif
+
+        return results;
+}
diff --git a/schedcat/locking/bounds.py b/schedcat/locking/bounds.py
index dc20241..9e7601c 100644
--- a/schedcat/locking/bounds.py
+++ b/schedcat/locking/bounds.py
@@ -234,3 +234,16 @@ def apply_lp_mpcp_bounds(all_tasks):
         # all blocking, including local blocking
         t.blocked   = res.get_blocking_term(i)
         t.locally_blocked = res.get_local_blocking(i)
+
+def apply_lp_part_fmlp_bounds(all_tasks):
+    # LP-based analysis of the partitioned, preemptive FMLP+
+    model = get_cpp_model(all_tasks)
+    res = lp_cpp.lp_part_fmlp_bounds(model)
+
+    for i,t in enumerate(all_tasks):
+        # remote blocking <=> self-suspension time
+        t.suspended = res.get_remote_blocking(i)
+        # all blocking, including local blocking
+        t.blocked   = res.get_blocking_term(i)
+        t.locally_blocked = res.get_local_blocking(i)
+