From 4d45e06a55ad463247edd949e6d0c98a69fcf332 Mon Sep 17 00:00:00 2001 From: Bjoern Brandenburg Date: Tue, 7 Aug 2012 20:28:29 +0200 Subject: Add DPCP and DFLP linear program generation These files implement the generation and evaluation of linear programs that bound maximum s-aware pi-blocking under the DPCP and the DFLP. --- native/src/blocking/linprog/lp_common.cpp | 177 ++++++++++++++ native/src/blocking/linprog/lp_dflp.cpp | 152 ++++++++++++ native/src/blocking/linprog/lp_dpcp.cpp | 374 ++++++++++++++++++++++++++++++ 3 files changed, 703 insertions(+) create mode 100644 native/src/blocking/linprog/lp_common.cpp create mode 100644 native/src/blocking/linprog/lp_dflp.cpp create mode 100644 native/src/blocking/linprog/lp_dpcp.cpp (limited to 'native/src') diff --git a/native/src/blocking/linprog/lp_common.cpp b/native/src/blocking/linprog/lp_common.cpp new file mode 100644 index 0000000..808ff28 --- /dev/null +++ b/native/src/blocking/linprog/lp_common.cpp @@ -0,0 +1,177 @@ +#include "lp_common.h" + +// LP-based analysis of semaphore protocols. +// Based on the paper: +// B. Brandenburg, "Improved Analysis and Evaluation of Real-Time Semaphore +// Protocols for P-FP Scheduling", Proceedings of the 19th IEEE Real-Time and +// Embedded Technology and Applications Symposium (RTAS 2013), April 2013. + +void set_blocking_objective( + VarMapper& vars, + const ResourceSharingInfo& info, const ResourceLocality& locality, + const TaskInfo& ti, + LinearProgram& lp, + LinearExpression *local_obj, + LinearExpression *remote_obj) +{ + 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(); + bool local = locality[q] == (int) ti.get_cluster(); + double length; + + // Sanity check topology info in debug mode. + assert(locality[q] != NO_CPU); + + length = request->get_request_length(); + + foreach_request_instance(*request, ti, v) + { + unsigned int var_id; + + var_id = vars.lookup(t, q, v, BLOCKING_DIRECT); + obj->add_term(length, var_id); + if (local && local_obj) + local_obj->add_term(length, var_id); + else if (!local && remote_obj) + remote_obj->add_term(length, var_id); + + var_id = vars.lookup(t, q, v, BLOCKING_INDIRECT); + obj->add_term(length, var_id); + if (local && local_obj) + local_obj->add_term(length, var_id); + else if (!local && remote_obj) + remote_obj->add_term(length, var_id); + + var_id = vars.lookup(t, q, v, BLOCKING_PREEMPT); + obj->add_term(length, var_id); + if (local && local_obj) + local_obj->add_term(length, var_id); + else if (!local && remote_obj) + remote_obj->add_term(length, var_id); + } + } + } +} + +// Constraint 1 in [Brandenburg 2013] +void add_mutex_constraints( + VarMapper& vars, + const ResourceSharingInfo& info, + const TaskInfo& ti, + LinearProgram& lp) +{ + + 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(); + foreach_request_instance(*request, ti, v) + { + LinearExpression *exp = new LinearExpression(); + 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); + + var_id = vars.lookup(t, q, v, BLOCKING_PREEMPT); + exp->add_var(var_id); + + lp.add_inequality(exp, 1); + } + } + } +} + +// Constraint 2 in [Brandenburg 2013] +void add_topology_constraints( + VarMapper& vars, + const ResourceSharingInfo& info, + const ResourceLocality& locality, + const TaskInfo& ti, + LinearProgram& lp) +{ + LinearExpression *exp = new LinearExpression(); + + foreach_task_except(info.get_tasks(), ti, tx) + { + unsigned int t = tx->get_id(); + foreach_remote_request(tx->get_requests(), locality, ti, 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); + } + } + } + lp.add_equality(exp, 0); +} + +static unsigned int max_num_arrivals_remote( + const ResourceLocality& locality, + const TaskInfo& ti) +{ + // initialize to 1 to account for job release + unsigned int count = 1; + + // count how often resources on remote cores are accessed + foreach(ti.get_requests(), req) + if (locality[req->get_resource_id()] != (int) ti.get_cluster()) + count += req->get_num_requests(); + + return count; +} + + +// Constraint 3 in [Brandenburg 2013] +// One priority-boosting-related preemption per local task +// each time that Ji arrives (is released or resumed) +void add_local_lower_priority_constraints( + VarMapper& vars, + const ResourceSharingInfo& info, + const ResourceLocality& locality, + const TaskInfo& ti, + LinearProgram& lp) +{ + unsigned int num_arrivals = max_num_arrivals_remote(locality, 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(); + + // is it a resource local to Ti? + if (locality[q] == (int) ti.get_cluster()) + { + foreach_request_instance(*request, ti, v) + { + unsigned int var_id; + var_id = vars.lookup(t, q, v, + BLOCKING_PREEMPT); + exp->add_var(var_id); + } + } + } + lp.add_equality(exp, num_arrivals); + } +} + diff --git a/native/src/blocking/linprog/lp_dflp.cpp b/native/src/blocking/linprog/lp_dflp.cpp new file mode 100644 index 0000000..6b416be --- /dev/null +++ b/native/src/blocking/linprog/lp_dflp.cpp @@ -0,0 +1,152 @@ +#include + +#include "lp_common.h" +#include "stl-hashmap.h" + +// Constraint 5 +// only one blocking request each time a job of T_i +// issues a request, with regard to each cluster and each task. +static void add_fifo_cluster_constraints( + VarMapper& vars, + const ResourceSharingInfo& info, + const ResourceLocality& locality, + const TaskInfo& ti, + LinearProgram& lp) +{ + hashmap per_cluster_counts; + + foreach(ti.get_requests(), req) + per_cluster_counts[locality[req->get_resource_id()]] += req->get_num_requests(); + + foreach_task_except(info.get_tasks(), ti, tx) + { + unsigned int t = tx->get_id(); + + // one constraint for each cluster accessed by tx + hashmap constraints; + + foreach(tx->get_requests(), request) + { + unsigned int q = request->get_resource_id(); + unsigned int c = locality[q]; + LinearExpression *exp; + + if (constraints.find(c) == constraints.end()) + constraints[c] = new LinearExpression(); + + exp = constraints[c]; + + 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); + } + } + + // add each per-cluster constraint + foreach(constraints, it) + lp.add_inequality(it->second, per_cluster_counts[it->first]); + } +} + +// Constraint 4 +// only one *directly* blocking request each time a job of T_i +// issues a request, with regard to each resource and each task. +static void add_fifo_resource_constraints( + VarMapper& vars, + const ResourceSharingInfo& info, + const ResourceLocality& locality, + const TaskInfo& ti, + LinearProgram& lp) +{ + hashmap 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]); + } + } +} + +void add_dflp_constraints( + VarMapper& vars, + const ResourceSharingInfo& info, + const ResourceLocality& locality, + const TaskInfo& ti, + LinearProgram& lp) +{ + // Constraint 1 + add_mutex_constraints(vars, info, ti, lp); + // Constraint 2 + add_topology_constraints(vars, info, locality, ti, lp); + // Constraint 3 + add_local_lower_priority_constraints(vars, info, locality, ti, lp); + // Constraint 4 + add_fifo_resource_constraints(vars, info, locality, ti, lp); + // Constraint 5 + add_fifo_cluster_constraints(vars, info, locality, ti, lp); +} + +static void apply_dflp_bounds_for_task( + unsigned int i, + BlockingBounds& bounds, + const ResourceSharingInfo& info, + const ResourceLocality& locality) +{ + LinearProgram lp; + VarMapper vars; + const TaskInfo& ti = info.get_tasks()[i]; + LinearExpression *local_obj = new LinearExpression(); + + set_blocking_objective(vars, info, locality, ti, lp, local_obj); + + add_dflp_constraints(vars, info, locality, ti, lp); + + Solution *sol = cplex_solve(lp, vars.get_num_vars()); + + 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; +} + +BlockingBounds* lp_dflp_bounds(const ResourceSharingInfo& info, + const ResourceLocality& locality) +{ + BlockingBounds *results = new BlockingBounds(info); + + for (unsigned int i = 0; i < info.get_tasks().size(); i++) + apply_dflp_bounds_for_task(i, *results, info, locality); + + return results; +} diff --git a/native/src/blocking/linprog/lp_dpcp.cpp b/native/src/blocking/linprog/lp_dpcp.cpp new file mode 100644 index 0000000..fbd0cd5 --- /dev/null +++ b/native/src/blocking/linprog/lp_dpcp.cpp @@ -0,0 +1,374 @@ +#include +#include +#include + +#include "lp_common.h" +#include "blocking.h" +#include "stl-hashmap.h" + +#define NO_WAIT_TIME_BOUND (-1) + +class MaxWaitTimes +{ +private: + // mapping of resource id to previously computed maximum wait time + hashmap max_wait_time; + + // parameters for wait time calculation + const ResourceSharingInfo& info; + const ResourceLocality& locality; + const TaskInfo& ti; + const PriorityCeilings& prio_ceiling; + + void bound_wait_time(unsigned int res_id); + +public: + MaxWaitTimes(const ResourceSharingInfo& _info, const ResourceLocality& _loc, + const TaskInfo& _ti, const std::vector& _pc) + : info(_info), locality(_loc), ti(_ti), prio_ceiling(_pc) + {}; + + long operator[](unsigned int res_id) + { + if (!max_wait_time.count(res_id)) + bound_wait_time(res_id); + return max_wait_time[res_id]; + } +}; + +void MaxWaitTimes::bound_wait_time(unsigned int res_id) +{ + unsigned int own_length = 0, delay_by_lower = 0, delay_by_higher = 0; + + unsigned int c = locality[res_id]; + + // find ti's maximum request length + foreach(ti.get_requests(), ti_req) + if (ti_req->get_resource_id() == res_id) + own_length = std::max(own_length, + ti_req->get_request_length()); + + // find maximum lower-priority request length that blocks + foreach_lowereq_priority_task(info.get_tasks(), ti, tx) + { + // on the cluster in which res_id is located + foreach_request_in_cluster(tx->get_requests(), locality, + c, request) + { + unsigned int q = request->get_resource_id(); + // can block? + if (prio_ceiling[q] <= ti.get_priority()) + delay_by_lower = std::max(delay_by_lower, + request->get_request_length()); + } + } + + // response-time analysis to find final maximum wait time + + unsigned long next_estimate = own_length + delay_by_lower; + unsigned long estimate = 0; + + while (next_estimate <= ti.get_response() && next_estimate != estimate) + { + delay_by_higher = 0; + estimate = next_estimate; + + foreach_higher_priority_task(info.get_tasks(), ti, tx) + { + foreach_request_in_cluster(tx->get_requests(), locality, + c, request) + { + unsigned int nreqs = request->get_max_num_requests(estimate); + unsigned long rlen = request->get_request_length(); + + delay_by_higher += nreqs * rlen; + } + } + + next_estimate = own_length + delay_by_lower + delay_by_higher; + } + + if (estimate <= ti.get_response()) + max_wait_time[res_id] = estimate; + else + max_wait_time[res_id] = NO_WAIT_TIME_BOUND; +} + +// Constraint 8 +// Ti's maximum wait times limit the maximum number of times +// that higher-priority tasks can directly and indirectly delay Ti. +static void add_max_wait_time_constraints( + VarMapper& vars, + const ResourceSharingInfo& info, + const ResourceLocality& locality, + const TaskInfo& ti, + const PriorityCeilings& prio_ceilings, + LinearProgram& lp) +{ + MaxWaitTimes max_wait_time = MaxWaitTimes(info, locality, ti, prio_ceilings); + + foreach_higher_priority_task(info.get_tasks(), ti, tx) + { + unsigned int t = tx->get_id(); + foreach(tx->get_requests(), request) + { + unsigned int q = request->get_resource_id(); + unsigned int c = locality[q]; + + unsigned int max_num_reqs = 0; + bool bounded = true; + + // Figure out how often and how long ti is waiting in + // total in cluster c. To do so, look at each of ti's + // requests for a resource located in cluster c. + + foreach_request_in_cluster(ti.get_requests(), locality, + c, ti_req) + { + unsigned int y = ti_req->get_resource_id(); + long wait = max_wait_time[y]; + + if (wait == NO_WAIT_TIME_BOUND) + { + bounded = false; + break; + } + + unsigned int nreqs = request->get_max_num_requests(wait); + max_num_reqs += nreqs * ti_req->get_num_requests(); + } + + + if (bounded) + { + 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); + var_id = vars.lookup(t, q, v, BLOCKING_INDIRECT); + exp->add_var(var_id); + } + lp.add_inequality(exp, max_num_reqs); + } + } + } +} + +// Substitute for Constraint 8 +// no direct or indirect blocking due to resources +// on clusters that ti doesn't even access. +static void add_independent_cluster_constraints( + VarMapper& vars, + const ResourceSharingInfo& info, + const ResourceLocality& locality, + const TaskInfo& ti, + LinearProgram& lp) +{ + + //find all clusters that ti accesses + std::set accessed_clusters; + foreach(ti.get_requests(), req) + { + int c = locality[req->get_resource_id()]; + accessed_clusters.insert(c); + } + + LinearExpression *exp = new LinearExpression(); + + 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(); + if (accessed_clusters.count(locality[q]) == 0) + { + 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_equality(exp, 0); +} + +// Constraint 6 +static void add_conflict_set_constraints( + VarMapper& vars, + const ResourceSharingInfo& info, + const ResourceLocality& locality, + const TaskInfo& ti, + const PriorityCeilings& prio_ceiling, + LinearProgram& lp) +{ + LinearExpression *exp = new LinearExpression(); + + 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(); + if (prio_ceiling[q] > ti.get_priority()) + { + // smaller ID <=> higher priority + // Priority ceiling is lower than ti's priority, + // so it cannot block ti. + 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); + } + } + } + } + + // force blocking fractions to zero + lp.add_equality(exp, 0); +} + +// Constraint 7 +// Each request can be directly delayed at most +// once by a lower-priority task. +static void add_atmostonce_lower_prio_constraints( + VarMapper& vars, + const ResourceSharingInfo& info, + const ResourceLocality& locality, + const TaskInfo& ti, + const PriorityCeilings& priority_ceiling, + LinearProgram& lp) +{ + // Count the number of times that each cluster is accessed by ti. + hashmap per_cluster_counts; + foreach(ti.get_requests(), req) + per_cluster_counts[locality[req->get_resource_id()]] += req->get_num_requests(); + + // build one constraint for each cluster + hashmap constraints; + + foreach_lowereq_priority_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(); + + if (priority_ceiling[q] <= ti.get_priority()) + { + // yes, can block us + unsigned int c = locality[q]; + LinearExpression *exp; + + if (constraints.find(c) == constraints.end()) + constraints[c] = new LinearExpression(); + + exp = constraints[c]; + + foreach_request_instance(*request, ti, v) + { + unsigned int var_id; + var_id = vars.lookup(t, q, v, BLOCKING_DIRECT); + exp->add_var(var_id); + } + } + } + } + + // add each per-cluster constraint + foreach(constraints, it) + lp.add_inequality(it->second, per_cluster_counts[it->first]); +} + +void add_dpcp_constraints( + VarMapper& vars, + const ResourceSharingInfo& info, + const ResourceLocality& locality, + const TaskInfo& ti, + const PriorityCeilings& prio_ceilings, + LinearProgram& lp, + bool use_rta) +{ + // Constraint 1 + add_mutex_constraints(vars, info, ti, lp); + // Constraint 2 + add_topology_constraints(vars, info, locality, ti, lp); + // Constraint 3 + add_local_lower_priority_constraints(vars, info, locality, ti, lp); + // Constraint 7 + add_atmostonce_lower_prio_constraints(vars, info, locality, + ti, prio_ceilings, lp); + // Constraint 6 + add_conflict_set_constraints(vars, info, locality, ti, + prio_ceilings, lp); + + if (use_rta) + // Constraint 8 + add_max_wait_time_constraints(vars, info, locality, ti, prio_ceilings, + lp); + else + add_independent_cluster_constraints(vars, info, locality, ti, lp); +} + +static void apply_dpcp_bounds_for_task( + unsigned int i, + BlockingBounds& bounds, + const ResourceSharingInfo& info, + const ResourceLocality& locality, + const PriorityCeilings& prio_ceilings, + bool use_rta) +{ + LinearProgram lp; + VarMapper vars; + const TaskInfo& ti = info.get_tasks()[i]; + LinearExpression *local_obj = new LinearExpression(); + + set_blocking_objective(vars, info, locality, ti, lp, local_obj); + + add_dpcp_constraints(vars, info, locality, ti, + prio_ceilings, lp, use_rta); + + Solution *sol = cplex_solve(lp, vars.get_num_vars()); + + 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; +} + + +BlockingBounds* lp_dpcp_bounds(const ResourceSharingInfo& info, + const ResourceLocality& locality, + bool use_rta) +{ + BlockingBounds* results = new BlockingBounds(info); + + PriorityCeilings prio_ceilings = get_priority_ceilings(info); + + for (unsigned int i = 0; i < info.get_tasks().size(); i++) + apply_dpcp_bounds_for_task(i, *results, info, + locality, prio_ceilings, use_rta); + + return results; +} -- cgit v1.2.2