X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/281f8c29e177852dcb1591fc31e363e1176857c8..6270ece7967b322385bbff766ee5f882ba1ef2a2:/src/surf/lagrange.cpp diff --git a/src/surf/lagrange.cpp b/src/surf/lagrange.cpp index 1b4cc9550b..ad8eabcc46 100644 --- a/src/surf/lagrange.cpp +++ b/src/surf/lagrange.cpp @@ -1,4 +1,4 @@ -/* Copyright (c) 2007, 2008, 2009, 2010. The SimGrid Team. +/* Copyright (c) 2007-2014. The SimGrid Team. * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it @@ -11,9 +11,8 @@ */ #include "xbt/log.h" #include "xbt/sysdep.h" -//#include "maxmin_private.h" -#include "solver.h" -#include "solver.hpp" +#include "maxmin_private.hpp" + #include #ifndef MATH #include @@ -41,58 +40,58 @@ static double dichotomy(double init, double diff(double, void *), //computes the value of the differential of constraint param_cnst applied to lambda static double partial_diff_lambda(double lambda, void *param_cnst); -static int __check_feasible(std::vector *cnstList, std::vector *varList, +static int __check_feasible(xbt_swag_t cnst_list, xbt_swag_t var_list, int warn) { - std::vector *elemList = NULL; + void *_cnst, *_elem, *_var; + xbt_swag_t elem_list = NULL; lmm_element_t elem = NULL; lmm_constraint_t cnst = NULL; lmm_variable_t var = NULL; - std::vector::iterator varIt; - std::vector::iterator elemIt; - std::vector::iterator cnstIt; double tmp; - for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) { - cnst = (*cnstIt); + xbt_swag_foreach(_cnst, cnst_list) { + cnst = (lmm_constraint_t)_cnst; tmp = 0; - elemList = &(cnst->m_elementSet); - for (elemIt=elemList->begin(); elemIt!=elemList->end(); ++elemIt) { - var = (*elemIt)->p_variable; - if (var->m_weight <= 0) + elem_list = &(cnst->element_set); + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; + var = elem->variable; + if (var->weight <= 0) continue; - tmp += var->m_value; + tmp += var->value; } - if (double_positive(tmp - cnst->m_bound)) { + if (double_positive(tmp - cnst->bound, sg_maxmin_precision)) { if (warn) XBT_WARN ("The link (%p) is over-used. Expected less than %f and got %f", - cnst, cnst->m_bound, tmp); + cnst, cnst->bound, tmp); return 0; } XBT_DEBUG ("Checking feasability for constraint (%p): sat = %f, lambda = %f ", - cnst, tmp - cnst->m_bound, cnst->m_lambda); + cnst, tmp - cnst->bound, cnst->lambda); } - for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { - if (!var->m_weight) + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; + if (!var->weight) break; - if (var->m_bound < 0) + if (var->bound < 0) continue; XBT_DEBUG("Checking feasability for variable (%p): sat = %f mu = %f", var, - var->m_value - var->m_bound, var->m_mu); + var->value - var->bound, var->mu); - if (double_positive(var->m_value - var->m_bound)) { + if (double_positive(var->value - var->bound, sg_maxmin_precision)) { if (warn) XBT_WARN ("The variable (%p) is too large. Expected less than %f and got %f", - var, var->m_bound, var->m_value); + var, var->bound, var->value); return 0; } - } + } return 1; } @@ -100,17 +99,16 @@ static double new_value(lmm_variable_t var) { double tmp = 0; int i; - std::vector::iterator elemIt; - for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) { - tmp += ((*elemIt)->p_constraint)->m_lambda; + for (i = 0; i < var->cnsts_number; i++) { + tmp += (var->cnsts[i].constraint)->lambda; } - if (var->m_bound > 0) - tmp += var->m_mu; + if (var->bound > 0) + tmp += var->mu; XBT_DEBUG("\t Working on var (%p). cost = %e; Weight = %e", var, tmp, - var->m_weight); + var->weight); //uses the partial differential inverse function - return var->p_funcFPI(var, tmp); + return var->func_fpi(var, tmp); } static double new_mu(lmm_variable_t var) @@ -118,53 +116,52 @@ static double new_mu(lmm_variable_t var) double mu_i = 0.0; double sigma_i = 0.0; int j; - std::vector::iterator elemIt; - for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) { - sigma_i += ((*elemIt)->p_constraint)->m_lambda; + for (j = 0; j < var->cnsts_number; j++) { + sigma_i += (var->cnsts[j].constraint)->lambda; } - mu_i = var->p_funcFP(var, var->m_bound) - sigma_i; + mu_i = var->func_fp(var, var->bound) - sigma_i; if (mu_i < 0.0) return 0.0; return mu_i; } -static double dual_objective(std::vector *varList, std::vector *cnstList) +static double dual_objective(xbt_swag_t var_list, xbt_swag_t cnst_list) { + void *_cnst, *_var; lmm_constraint_t cnst = NULL; lmm_variable_t var = NULL; double obj = 0.0; - std::vector::iterator varIt; - std::vector::iterator elemIt; - std::vector::iterator cnstIt; - for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { - var = (*varIt); + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; double sigma_i = 0.0; int j; - if (!var->m_weight) + if (!var->weight) break; - for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) - sigma_i += ((*elemIt)->p_constraint)->m_lambda; - - if (var->m_bound > 0) - sigma_i += var->m_mu; + for (j = 0; j < var->cnsts_number; j++) + sigma_i += (var->cnsts[j].constraint)->lambda; + + if (var->bound > 0) + sigma_i += var->mu; XBT_DEBUG("var %p : sigma_i = %1.20f", var, sigma_i); - obj += var->p_funcF(var, var->p_funcFPI(var, sigma_i)) - - sigma_i * var->p_funcFPI(var, sigma_i); + obj += var->func_f(var, var->func_fpi(var, sigma_i)) - + sigma_i * var->func_fpi(var, sigma_i); + + if (var->bound > 0) + obj += var->mu * var->bound; + } - if (var->m_bound > 0) - obj += var->m_mu * var->m_bound; + xbt_swag_foreach(_cnst, cnst_list) { + cnst = (lmm_constraint_t)_cnst; + obj += cnst->lambda * cnst->bound; } - for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) - obj += (*cnstIt)->m_lambda * (*cnstIt)->m_bound; - return obj; } @@ -174,7 +171,7 @@ void lagrange_solve(lmm_system_t sys) * Lagrange Variables. */ int max_iterations = 100; - double epsilon_min_error = MAXMIN_PRECISION; + double epsilon_min_error = 0.00001; /* this is the precision on the objective function so it's none of the configurable values and this value is the legacy one */ double dichotomy_min_error = 1e-14; double overall_modification = 1; @@ -182,18 +179,16 @@ void lagrange_solve(lmm_system_t sys) * Variables to manipulate the data structure proposed to model the maxmin * fairness. See docummentation for more details. */ - std::vector *cnstList = NULL; - std::vector::iterator cnstIt; + xbt_swag_t cnst_list = NULL; + void *_cnst; lmm_constraint_t cnst = NULL; - std::vector *varList = NULL; - std::vector::iterator varIt; + xbt_swag_t var_list = NULL; + void *_var; lmm_variable_t var = NULL; - std::vector::iterator elemIt; - /* - * Auxiliar variables. + * Auxiliary variables. */ int iteration = 0; double tmp = 0; @@ -211,58 +206,59 @@ void lagrange_solve(lmm_system_t sys) lmm_print(sys); } - if (!(sys->m_modified)) + if (!(sys->modified)) return; + /* * Initialize lambda. */ - cnstList = &(sys->m_activeConstraintSet); - for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) { - cnst = *cnstIt; - cnst->m_lambda = 1.0; - cnst->m_newLambda = 2.0; - XBT_DEBUG("#### cnst(%p)->lambda : %e", cnst, cnst->m_lambda); + cnst_list = &(sys->active_constraint_set); + xbt_swag_foreach(_cnst, cnst_list) { + cnst = (lmm_constraint_t)_cnst; + cnst->lambda = 1.0; + cnst->new_lambda = 2.0; + XBT_DEBUG("#### cnst(%p)->lambda : %e", cnst, cnst->lambda); } /* * Initialize the var list variable with only the active variables. * Associate an index in the swag variables. Initialize mu. */ - varList = &(sys->m_variableSet); + var_list = &(sys->variable_set); i = 0; - for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { - var = *varIt; - if (!var->m_weight) - var->m_value = 0.0; + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; + if (!var->weight) + var->value = 0.0; else { int nb = 0; - if (var->m_bound < 0.0) { + if (var->bound < 0.0) { XBT_DEBUG("#### NOTE var(%d) is a boundless variable", i); - var->m_mu = -1.0; - var->m_value = new_value(var); + var->mu = -1.0; + var->value = new_value(var); } else { - var->m_mu = 1.0; - var->m_newMu = 2.0; - var->m_value = new_value(var); + var->mu = 1.0; + var->new_mu = 2.0; + var->value = new_value(var); } - XBT_DEBUG("#### var(%p) ->weight : %e", var, var->m_weight); - XBT_DEBUG("#### var(%p) ->mu : %e", var, var->m_mu); - XBT_DEBUG("#### var(%p) ->weight: %e", var, var->m_weight); - XBT_DEBUG("#### var(%p) ->bound: %e", var, var->m_bound); - for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) { - if ((*elemIt)->m_value == 0.0) + XBT_DEBUG("#### var(%p) ->weight : %e", var, var->weight); + XBT_DEBUG("#### var(%p) ->mu : %e", var, var->mu); + XBT_DEBUG("#### var(%p) ->weight: %e", var, var->weight); + XBT_DEBUG("#### var(%p) ->bound: %e", var, var->bound); + for (i = 0; i < var->cnsts_number; i++) { + if (var->cnsts[i].value == 0.0) nb++; } - if (nb == var->m_cnsts.size()) - var->m_value = 1.0; + if (nb == var->cnsts_number) + var->value = 1.0; } } /* * Compute dual objective. */ - obj = dual_objective(varList, cnstList); + obj = dual_objective(var_list, cnst_list); /* * While doesn't reach a minimun error or a number maximum of iterations. @@ -278,20 +274,20 @@ void lagrange_solve(lmm_system_t sys) /* * Improve the value of mu_i */ - for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { - var = *varIt; - if (!var->m_weight) + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; + if (!var->weight) break; - if (var->m_bound >= 0) { + if (var->bound >= 0) { XBT_DEBUG("Working on var (%p)", var); - var->m_newMu = new_mu(var); + var->new_mu = new_mu(var); /* dual_updated += (fabs(var->new_mu-var->mu)>dichotomy_min_error); */ /* XBT_DEBUG("dual_updated (%d) : %1.20f",dual_updated,fabs(var->new_mu-var->mu)); */ XBT_DEBUG("Updating mu : var->mu (%p) : %1.20f -> %1.20f", var, - var->m_mu, var->m_newMu); - var->m_mu = var->m_newMu; + var->mu, var->new_mu); + var->mu = var->new_mu; - new_obj = dual_objective(varList, cnstList); + new_obj = dual_objective(var_list, cnst_list); XBT_DEBUG("Improvement for Objective (%g -> %g) : %g", obj, new_obj, obj - new_obj); xbt_assert(obj - new_obj >= -epsilon_min_error, @@ -303,19 +299,19 @@ void lagrange_solve(lmm_system_t sys) /* * Improve the value of lambda_i */ - for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) { - cnst = *cnstIt; + xbt_swag_foreach(_cnst, cnst_list) { + cnst = (lmm_constraint_t)_cnst; XBT_DEBUG("Working on cnst (%p)", cnst); - cnst->m_newLambda = - dichotomy(cnst->m_lambda, partial_diff_lambda, cnst, + cnst->new_lambda = + dichotomy(cnst->lambda, partial_diff_lambda, cnst, dichotomy_min_error); /* dual_updated += (fabs(cnst->new_lambda-cnst->lambda)>dichotomy_min_error); */ /* XBT_DEBUG("dual_updated (%d) : %1.20f",dual_updated,fabs(cnst->new_lambda-cnst->lambda)); */ XBT_DEBUG("Updating lambda : cnst->lambda (%p) : %1.20f -> %1.20f", - cnst, cnst->m_lambda, cnst->m_newLambda); - cnst->m_lambda = cnst->m_newLambda; + cnst, cnst->lambda, cnst->new_lambda); + cnst->lambda = cnst->new_lambda; - new_obj = dual_objective(varList, cnstList); + new_obj = dual_objective(var_list, cnst_list); XBT_DEBUG("Improvement for Objective (%g -> %g) : %g", obj, new_obj, obj - new_obj); xbt_assert(obj - new_obj >= -epsilon_min_error, @@ -329,24 +325,24 @@ void lagrange_solve(lmm_system_t sys) */ XBT_DEBUG("-------------- Check convergence ----------"); overall_modification = 0; - for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) { - var = *varIt; - if (var->m_weight <= 0) - var->m_value = 0.0; + xbt_swag_foreach(_var, var_list) { + var = (lmm_variable_t)_var; + if (var->weight <= 0) + var->value = 0.0; else { tmp = new_value(var); overall_modification = - MAX(overall_modification, fabs(var->m_value - tmp)); + MAX(overall_modification, fabs(var->value - tmp)); - var->m_value = tmp; + var->value = tmp; XBT_DEBUG("New value of var (%p) = %e, overall_modification = %e", - var, var->m_value, overall_modification); + var, var->value, overall_modification); } } XBT_DEBUG("-------------- Check feasability ----------"); - if (!__check_feasible(cnstList, varList, 0)) + if (!__check_feasible(cnst_list, var_list, 0)) overall_modification = 1.0; XBT_DEBUG("Iteration %d: overall_modification : %f", iteration, overall_modification); @@ -355,7 +351,8 @@ void lagrange_solve(lmm_system_t sys) /* break; */ /* } */ } - __check_feasible(cnstList, varList, 1); + + __check_feasible(cnst_list, var_list, 1); if (overall_modification <= epsilon_min_error) { XBT_DEBUG("The method converges in %d iterations.", iteration); @@ -387,7 +384,6 @@ void lagrange_solve(lmm_system_t sys) static double dichotomy(double init, double diff(double, void *), void *var_cnst, double min_error) { - #ifdef TOREPAIR double min, max; double overall_error; double middle; @@ -401,7 +397,6 @@ static double dichotomy(double init, double diff(double, void *), min = max = 0.5; } - min_diff = max_diff = middle_diff = 0.0; overall_error = 1; if ((diff_0 = diff(1e-16, var_cnst)) >= 0) { @@ -491,13 +486,13 @@ static double dichotomy(double init, double diff(double, void *), XBT_CDEBUG(surf_lagrange_dichotomy, "returning %e", (min + max) / 2.0); XBT_OUT(); return ((min + max) / 2.0); - #endif } static double partial_diff_lambda(double lambda, void *param_cnst) { - #ifdef TOREPAIR + int j; + void *_elem; xbt_swag_t elem_list = NULL; lmm_element_t elem = NULL; lmm_variable_t var = NULL; @@ -510,7 +505,8 @@ static double partial_diff_lambda(double lambda, void *param_cnst) XBT_CDEBUG(surf_lagrange_dichotomy, "Computing diff of cnst (%p)", cnst); - xbt_swag_foreach(elem, elem_list) { + xbt_swag_foreach(_elem, elem_list) { + elem = (lmm_element_t)_elem; var = elem->variable; if (var->weight <= 0) continue; @@ -543,7 +539,6 @@ static double partial_diff_lambda(double lambda, void *param_cnst) diff); XBT_OUT(); return diff; - #endif } /** \brief Attribute the value bound to var->bound. @@ -553,9 +548,18 @@ static double partial_diff_lambda(double lambda, void *param_cnst) * Set default functions to the ones passed as parameters. This is a polimorfism in C pure, enjoy the roots of programming. * */ -void lmm_set_default_protocol_function(double (*func_f) (lmm_variable_t var, double x), - double (*func_fp) (lmm_variable_t var, double x), - double (*func_fpi) (lmm_variable_t var, double x)) +void lmm_set_default_protocol_function(double (*func_f) + + + + + + + (lmm_variable_t var, double x), + double (*func_fp) (lmm_variable_t + var, double x), + double (*func_fpi) (lmm_variable_t + var, double x)) { func_f_def = func_f; func_fp_def = func_fp; @@ -578,26 +582,20 @@ void lmm_set_default_protocol_function(double (*func_f) (lmm_variable_t var, dou double func_vegas_f(lmm_variable_t var, double x) { - #ifdef TOREPAIR xbt_assert(x > 0.0, "Don't call me with stupid values! (%1.20f)", x); return VEGAS_SCALING * var->weight * log(x); - #endif } double func_vegas_fp(lmm_variable_t var, double x) { - #ifdef TOREPAIR xbt_assert(x > 0.0, "Don't call me with stupid values! (%1.20f)", x); return VEGAS_SCALING * var->weight / x; - #endif } double func_vegas_fpi(lmm_variable_t var, double x) { - #ifdef TOREPAIR xbt_assert(x > 0.0, "Don't call me with stupid values! (%1.20f)", x); return var->weight / (x / VEGAS_SCALING); - #endif } /* @@ -608,15 +606,15 @@ double func_vegas_fpi(lmm_variable_t var, double x) #define RENO_SCALING 1.0 double func_reno_f(lmm_variable_t var, double x) { - xbt_assert(var->m_weight > 0.0, "Don't call me with stupid values!"); + xbt_assert(var->weight > 0.0, "Don't call me with stupid values!"); - return RENO_SCALING * sqrt(3.0 / 2.0) / var->m_weight * - atan(sqrt(3.0 / 2.0) * var->m_weight * x); + return RENO_SCALING * sqrt(3.0 / 2.0) / var->weight * + atan(sqrt(3.0 / 2.0) * var->weight * x); } double func_reno_fp(lmm_variable_t var, double x) { - return RENO_SCALING * 3.0 / (3.0 * var->m_weight * var->m_weight * x * x + + return RENO_SCALING * 3.0 / (3.0 * var->weight * var->weight * x * x + 2.0); } @@ -624,15 +622,15 @@ double func_reno_fpi(lmm_variable_t var, double x) { double res_fpi; - xbt_assert(var->m_weight > 0.0, "Don't call me with stupid values!"); + xbt_assert(var->weight > 0.0, "Don't call me with stupid values!"); xbt_assert(x > 0.0, "Don't call me with stupid values!"); res_fpi = - 1.0 / (var->m_weight * var->m_weight * (x / RENO_SCALING)) - - 2.0 / (3.0 * var->m_weight * var->m_weight); + 1.0 / (var->weight * var->weight * (x / RENO_SCALING)) - + 2.0 / (3.0 * var->weight * var->weight); if (res_fpi <= 0.0) return 0.0; -// xbt_assert(res_fpi>0.0,"Don't call me with stupid values!"); +/* xbt_assert(res_fpi>0.0,"Don't call me with stupid values!"); */ return sqrt(res_fpi); } @@ -645,16 +643,16 @@ double func_reno_fpi(lmm_variable_t var, double x) #define RENO2_SCALING 1.0 double func_reno2_f(lmm_variable_t var, double x) { - xbt_assert(var->m_weight > 0.0, "Don't call me with stupid values!"); - return RENO2_SCALING * (1.0 / var->m_weight) * log((x * var->m_weight) / - (2.0 * x * var->m_weight + + xbt_assert(var->weight > 0.0, "Don't call me with stupid values!"); + return RENO2_SCALING * (1.0 / var->weight) * log((x * var->weight) / + (2.0 * x * var->weight + 3.0)); } double func_reno2_fp(lmm_variable_t var, double x) { - return RENO2_SCALING * 3.0 / (var->m_weight * x * - (2.0 * var->m_weight * x + 3.0)); + return RENO2_SCALING * 3.0 / (var->weight * x * + (2.0 * var->weight * x + 3.0)); } double func_reno2_fpi(lmm_variable_t var, double x) @@ -663,7 +661,7 @@ double func_reno2_fpi(lmm_variable_t var, double x) double tmp; xbt_assert(x > 0.0, "Don't call me with stupid values!"); - tmp = x * var->m_weight * var->m_weight; + tmp = x * var->weight * var->weight; res_fpi = tmp * (9.0 * x + 24.0); if (res_fpi <= 0.0)