From 308ff37a60a61e158bfe108bfcea0bf3b71e942d Mon Sep 17 00:00:00 2001 From: Bjoern Brandenburg Date: Sun, 9 Dec 2012 12:39:41 -0400 Subject: Add LP-based blocking analysis for FMLP+ --- native/src/blocking/linprog/lp_fmlp.cpp | 286 ++++++++++++++++++++++++++++++++ 1 file changed, 286 insertions(+) create mode 100644 native/src/blocking/linprog/lp_fmlp.cpp (limited to 'native/src/blocking') 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 +#include +#include + +#include "lp_common.h" +#include "blocking.h" +#include "stl-hashmap.h" + +#include "cpu_time.h" + +typedef hashmap 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; +} -- cgit v1.2.2