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.

6 files changed, 871 insertions, 3 deletions

diff --git a/native/Makefile b/native/Makefile
index 71a6835..c2a08e5 100644
--- a/native/Makefile
+++ b/native/Makefile
@@ -81,7 +81,7 @@ LDFLAGS   = $(LIBS)
 SWIGFLAGS = -python -c++ -outdir . -includeall -Iinclude
 
 vpath %.cc interface
-vpath %.cpp src src/edf src/blocking src/linprog
+vpath %.cpp src src/edf src/blocking src/blocking/linprog src/linprog
 
 # #### Common C++ source files ####
 
@@ -100,7 +100,8 @@ ALL = testmain _sched.so _locking.so _sim.so
 
 # Compile LP-based code only if we have a solver.
 ifneq ($(CPLEX),)
-LP_OBJ    = cplex.o io.o
+LP_OBJ    = lp_common.o lp_dflp.o lp_dpcp.o
+LP_OBJ   += cplex.o io.o
 endif
 
 .PHONY: all clean
diff --git a/native/include/linprog/model.h b/native/include/linprog/model.h
index 27729dd..22f96e4 100644
--- a/native/include/linprog/model.h
+++ b/native/include/linprog/model.h
@@ -53,7 +53,7 @@ class LinearProgram
         Constraints inequalities;
 
 public:
-        LinearProgram() : objective(0) {};
+        LinearProgram() : objective(new LinearExpression()) {};
 
         ~LinearProgram()
         {
@@ -91,6 +91,11 @@ public:
                 return objective;
         }
 
+        LinearExpression *get_objective()
+        {
+                return objective;
+        }
+
         const Constraints& get_equalities() const
         {
                 return equalities;
diff --git a/native/include/lp_common.h b/native/include/lp_common.h
new file mode 100644
index 0000000..06519d1
--- /dev/null
+++ b/native/include/lp_common.h
@@ -0,0 +1,159 @@
+#ifndef LP_COMMON_H_
+#define LP_COMMON_H_
+
+#include <stdint.h>
+
+#include "sharedres_types.h"
+#include "blocking.h"
+
+#include "stl-helper.h"
+#include "stl-hashmap.h"
+
+#include "linprog/model.h"
+#include "linprog/cplex.h"
+
+enum blocking_type
+{
+        BLOCKING_DIRECT,
+        BLOCKING_INDIRECT,
+        BLOCKING_PREEMPT
+};
+
+class VarMapper {
+private:
+        hashmap<uint64_t, unsigned int> map;
+
+        void insert(uint64_t key)
+        {
+                unsigned int idx = map.size();
+                map[key] = idx;
+        }
+
+        static uint64_t encode_request(uint64_t task_id, uint64_t res_id, uint64_t req_id,
+                                       uint64_t blocking_type)
+        {
+                assert(task_id < (1 << 30));
+                assert(res_id < (1 << 10));
+                assert(req_id < (1 << 22));
+                assert(blocking_type < (1 << 2));
+
+                return (blocking_type << 62) | (task_id << 30) | (req_id << 10) | res_id;
+        }
+
+public:
+
+        unsigned int lookup(unsigned int task_id, unsigned int res_id, unsigned int req_id,
+                            blocking_type type)
+        {
+                uint64_t key = encode_request(task_id, res_id, req_id, type);
+                if (!map.count(key))
+                        insert(key);
+                return map[key];
+        }
+
+        void clear()
+        {
+                map.clear();
+        }
+
+        unsigned int get_num_vars()
+        {
+                return map.size();
+        }
+};
+
+void set_blocking_objective(
+        VarMapper& vars,
+        const ResourceSharingInfo& info, const ResourceLocality&,
+        const TaskInfo& ti,
+        LinearProgram& lp,
+        LinearExpression *local_obj = 0,
+        LinearExpression *remote_obj = 0);
+
+void add_mutex_constraints(VarMapper& vars,
+                const ResourceSharingInfo& info,
+                const TaskInfo& ti,  LinearProgram& lp);
+
+void add_topology_constraints(VarMapper& vars,
+                const ResourceSharingInfo& info, const ResourceLocality& locality,
+                const TaskInfo& ti, LinearProgram& lp);
+
+void add_local_lower_priority_constraints(
+        VarMapper& vars,
+        const ResourceSharingInfo& info,
+        const ResourceLocality& locality,
+        const TaskInfo& ti,
+        LinearProgram& lp);
+
+// A generic for loop that iterates 'request_index_variable' from 0 to the
+// maximum number of requests issued by task tx while ti is pending. 'tx_request'
+// should be of type RequestBound&.
+#define foreach_request_instance(tx_request, task_ti, request_index_variable) \
+        for (                                                           \
+                unsigned int __max_num_requests = (tx_request).get_max_num_requests((task_ti).get_response()), \
+                                 request_index_variable = 0;            \
+                request_index_variable < __max_num_requests;            \
+                request_index_variable++                                \
+                )
+
+// iterate over each task using 'task_iter', skipping 'excluded_task'
+#define foreach_task_except(tasks, excluded_task, task_iter)    \
+        foreach(tasks, task_iter)                               \
+        if (task_iter->get_id() != (excluded_task).get_id())
+
+// iterate only over tasks with equal or lower priority
+#define foreach_lowereq_priority_task(tasks, reference_task, task_iter) \
+        foreach(tasks, task_iter)                                     \
+        if (task_iter->get_priority() >= (reference_task).get_priority())
+
+// iterate only over tasks with equal or lower priority, excluding 'reference_task'
+#define foreach_lowereq_priority_task_except(tasks, reference_task, task_iter) \
+        foreach(tasks, task_iter)                                     \
+        if (task_iter->get_priority() >= (reference_task).get_priority() &&    \
+                task_iter->get_id() != (reference_task).get_id())
+
+
+// iterate only over tasks with higher priority
+#define foreach_higher_priority_task(tasks, reference_task, task_iter) \
+        foreach(tasks, task_iter)                                      \
+        if (task_iter->get_priority() < (reference_task).get_priority())
+
+// iterate over requests not in the local cluster
+#define foreach_remote_request(requests, locality, task_ti, request_iter) \
+        foreach(requests, request_iter)                                 \
+        if ((locality)[request_iter->get_resource_id()]                 \
+            != (int) (task_ti).get_cluster())
+
+// iterate over requests for resources in a specific cluster
+#define foreach_request_in_cluster(requests, locality, cluster, request_iter) \
+        foreach(requests, request_iter)                                 \
+        if ((locality)[request_iter->get_resource_id()]                 \
+            == (int) (cluster))
+
+// iterate over each task using 'task_iter', skipping tasks in the same
+// cluster as 'local_task'
+#define foreach_remote_task(tasks, local_task, task_iter)       \
+        foreach(tasks, task_iter)                               \
+        if (task_iter->get_cluster() != (local_task).get_cluster())
+
+#define foreach_local_task(tasks, local_task, task_iter)        \
+        foreach(tasks, task_iter)                               \
+        if (task_iter->get_cluster() == (local_task).get_cluster())
+
+#define foreach_local_task_except(tasks, local_task, task_iter) \
+        foreach(tasks, task_iter)                               \
+        if (task_iter->get_cluster() == (local_task).get_cluster() && \
+            task_iter->get_id() != (local_task).get_id())
+
+#define foreach_local_lowereq_priority_task_except(tasks, local_task, task_iter)        \
+        foreach(tasks, task_iter)                               \
+        if (task_iter->get_cluster() == (local_task).get_cluster() && \
+            task_iter->get_id() != (local_task).get_id() && \
+            task_iter->get_priority() >= (local_task).get_priority())
+
+#define foreach_request_for(requests, res_id, req_iter) \
+        foreach(requests, req_iter)                             \
+        if (req_iter->get_resource_id() == res_id)
+
+
+#endif /* LP_COMMON_H_ */
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 <iostream>
+
+#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<unsigned int, unsigned int> 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<unsigned int, LinearExpression *> 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<unsigned int, unsigned int> 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 <iostream>
+#include <set>
+#include <algorithm>
+
+#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<unsigned int, long> 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<unsigned int>& _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<int> 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<unsigned int, unsigned int> 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<unsigned int, LinearExpression *> 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;
+}