From c2c3126de5fc548db5821081af265bb8cf69cebd Mon Sep 17 00:00:00 2001 From: Bjoern Brandenburg Date: Wed, 8 Aug 2012 08:43:11 +0200 Subject: Add support for tracking total LP generation / solving cost Interestingly, this shows that generating huge LPs is not necessarily any faster than creating and solving many small LPs. Further investigation required. --- native/src/blocking/linprog/lp_dflp.cpp | 80 +++++++++++++++++++++++++++++-- native/src/blocking/linprog/lp_dpcp.cpp | 84 ++++++++++++++++++++++++++++++--- 2 files changed, 154 insertions(+), 10 deletions(-) (limited to 'native/src/blocking') diff --git a/native/src/blocking/linprog/lp_dflp.cpp b/native/src/blocking/linprog/lp_dflp.cpp index 8d5fec4..6198825 100644 --- a/native/src/blocking/linprog/lp_dflp.cpp +++ b/native/src/blocking/linprog/lp_dflp.cpp @@ -3,6 +3,8 @@ #include "lp_common.h" #include "stl-hashmap.h" +#include "cpu_time.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. @@ -109,8 +111,8 @@ void add_dflp_constraints( #ifdef CONFIG_MERGED_LINPROGS -BlockingBounds* lp_dflp_bounds(const ResourceSharingInfo& info, - const ResourceLocality& locality) +static BlockingBounds* _lp_dflp_bounds(const ResourceSharingInfo& info, + const ResourceLocality& locality) { BlockingBounds *results = new BlockingBounds(info); const unsigned int num_tasks = info.get_tasks().size(); @@ -120,6 +122,18 @@ BlockingBounds* lp_dflp_bounds(const ResourceSharingInfo& info, LinearProgram lp; unsigned int var_idx = 0; +#if DEBUG_LP_OVERHEADS >= 2 + static DEFINE_CPU_CLOCK(model_gen_cost); + static DEFINE_CPU_CLOCK(solver_cost); + static DEFINE_CPU_CLOCK(extract_cost); + static DEFINE_CPU_CLOCK(total_cost); + + std::cout << "---- " << __FUNCTION__ << " ----" << std::endl; + + model_gen_cost.start(); + total_cost.start(); +#endif + // Generate a "merged" LP. for (unsigned int i = 0; i < num_tasks; i++) { @@ -133,11 +147,21 @@ BlockingBounds* lp_dflp_bounds(const ResourceSharingInfo& info, var_idx = vars.get_next_var(); } +#if DEBUG_LP_OVERHEADS >= 2 + model_gen_cost.stop(); + solver_cost.start(); +#endif + // Solve the big, combined LP. Solution *sol = cplex_solve(lp, var_idx); assert(sol != NULL); +#if DEBUG_LP_OVERHEADS >= 2 + solver_cost.stop(); + extract_cost.start(); +#endif + // Extract each task's solution. for (unsigned int i = 0; i < num_tasks; i++) { @@ -152,6 +176,15 @@ BlockingBounds* lp_dflp_bounds(const ResourceSharingInfo& info, results->set_local_blocking(i, local); } +#if DEBUG_LP_OVERHEADS >= 2 + extract_cost.stop(); + total_cost.stop(); + std::cout << model_gen_cost << std::endl; + std::cout << solver_cost << std::endl; + std::cout << extract_cost << std::endl; + std::cout << total_cost << std::endl; +#endif + delete sol; delete[] local_obj; delete[] remote_obj; @@ -173,12 +206,32 @@ static void apply_dflp_bounds_for_task( 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(vars, info, locality, ti, lp, local_obj); add_dflp_constraints(vars, info, locality, ti, lp); +#if DEBUG_LP_OVERHEADS >=2 + model_gen_cost.stop(); + std::cout << model_gen_cost << std::endl; + solver_cost.start(); +#endif + Solution *sol = cplex_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; @@ -195,8 +248,8 @@ static void apply_dflp_bounds_for_task( delete sol; } -BlockingBounds* lp_dflp_bounds(const ResourceSharingInfo& info, - const ResourceLocality& locality) +static BlockingBounds* _lp_dflp_bounds(const ResourceSharingInfo& info, + const ResourceLocality& locality) { BlockingBounds *results = new BlockingBounds(info); @@ -207,3 +260,22 @@ BlockingBounds* lp_dflp_bounds(const ResourceSharingInfo& info, } #endif + +BlockingBounds* lp_dflp_bounds(const ResourceSharingInfo& info, + const ResourceLocality& locality) +{ +#if DEBUG_LP_OVERHEADS >= 1 + static DEFINE_CPU_CLOCK(cpu_costs); + + cpu_costs.start(); +#endif + + BlockingBounds *results = _lp_dflp_bounds(info, locality); + +#if DEBUG_LP_OVERHEADS >=1 + cpu_costs.stop(); + std::cout << cpu_costs << std::endl; +#endif + + return results; +} diff --git a/native/src/blocking/linprog/lp_dpcp.cpp b/native/src/blocking/linprog/lp_dpcp.cpp index 52ecd0c..1b1cf32 100644 --- a/native/src/blocking/linprog/lp_dpcp.cpp +++ b/native/src/blocking/linprog/lp_dpcp.cpp @@ -6,6 +6,8 @@ #include "blocking.h" #include "stl-hashmap.h" +#include "cpu_time.h" + #define NO_WAIT_TIME_BOUND (-1) class MaxWaitTimes @@ -323,9 +325,9 @@ void add_dpcp_constraints( #ifdef CONFIG_MERGED_LINPROGS -BlockingBounds* lp_dpcp_bounds(const ResourceSharingInfo& info, - const ResourceLocality& locality, - bool use_rta) +static BlockingBounds* _lp_dpcp_bounds(const ResourceSharingInfo& info, + const ResourceLocality& locality, + bool use_rta) { BlockingBounds *results = new BlockingBounds(info); const unsigned int num_tasks = info.get_tasks().size(); @@ -337,6 +339,18 @@ BlockingBounds* lp_dpcp_bounds(const ResourceSharingInfo& info, LinearProgram lp; unsigned int var_idx = 0; +#if DEBUG_LP_OVERHEADS >= 2 + static DEFINE_CPU_CLOCK(model_gen_cost); + static DEFINE_CPU_CLOCK(solver_cost); + static DEFINE_CPU_CLOCK(extract_cost); + static DEFINE_CPU_CLOCK(total_cost); + + std::cout << "---- " << __FUNCTION__ << " ----" << std::endl; + + model_gen_cost.start(); + total_cost.start(); +#endif + // Generate a "merged" LP. for (unsigned int i = 0; i < num_tasks; i++) { @@ -351,11 +365,21 @@ BlockingBounds* lp_dpcp_bounds(const ResourceSharingInfo& info, var_idx = vars.get_next_var(); } +#if DEBUG_LP_OVERHEADS >= 2 + model_gen_cost.stop(); + solver_cost.start(); +#endif + // Solve the big, combined LP. Solution *sol = cplex_solve(lp, var_idx); assert(sol != NULL); +#if DEBUG_LP_OVERHEADS >= 2 + solver_cost.stop(); + extract_cost.start(); +#endif + // Extract each task's solution. for (unsigned int i = 0; i < num_tasks; i++) { @@ -370,6 +394,15 @@ BlockingBounds* lp_dpcp_bounds(const ResourceSharingInfo& info, results->set_local_blocking(i, local); } +#if DEBUG_LP_OVERHEADS >= 2 + extract_cost.stop(); + total_cost.stop(); + std::cout << model_gen_cost << std::endl; + std::cout << solver_cost << std::endl; + std::cout << extract_cost << std::endl; + std::cout << total_cost << std::endl; +#endif + delete sol; delete[] local_obj; delete[] remote_obj; @@ -392,13 +425,32 @@ static void apply_dpcp_bounds_for_task( 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(vars, info, locality, ti, lp, local_obj); add_dpcp_constraints(vars, info, locality, ti, prio_ceilings, lp, use_rta); +#if DEBUG_LP_OVERHEADS >= 2 + model_gen_cost.stop(); + std::cout << model_gen_cost << std::endl; + solver_cost.start(); +#endif + Solution *sol = cplex_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; @@ -416,9 +468,9 @@ static void apply_dpcp_bounds_for_task( } -BlockingBounds* lp_dpcp_bounds(const ResourceSharingInfo& info, - const ResourceLocality& locality, - bool use_rta) +static BlockingBounds* _lp_dpcp_bounds(const ResourceSharingInfo& info, + const ResourceLocality& locality, + bool use_rta) { BlockingBounds* results = new BlockingBounds(info); @@ -432,3 +484,23 @@ BlockingBounds* lp_dpcp_bounds(const ResourceSharingInfo& info, } #endif + +BlockingBounds* lp_dpcp_bounds(const ResourceSharingInfo& info, + const ResourceLocality& locality, + bool use_rta) +{ +#if DEBUG_LP_OVERHEADS >= 1 + static DEFINE_CPU_CLOCK(cpu_costs); + + cpu_costs.start(); +#endif + + BlockingBounds *results = _lp_dpcp_bounds(info, locality, use_rta); + +#if DEBUG_LP_OVERHEADS >= 1 + cpu_costs.stop(); + std::cout << cpu_costs << std::endl; +#endif + + return results; +} -- cgit v1.2.2