X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/c88f85a40ebbc997a9471e1e6542ebb7ec1decd7..92a1a3afd9e836da4c7cec7022097b7956c6d749:/src/surf/maxmin.c diff --git a/src/surf/maxmin.c b/src/surf/maxmin.c index f74b96a5b8..d616c715e0 100644 --- a/src/surf/maxmin.c +++ b/src/surf/maxmin.c @@ -8,11 +8,17 @@ #include "xbt/sysdep.h" #include "xbt/log.h" +#include "xbt/mallocator.h" #include "maxmin_private.h" #include +#include XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf, "Logging specific to SURF (maxmin)"); +static void* lmm_variable_mallocator_new_f(void); +static void lmm_variable_mallocator_free_f(void *var); +static void lmm_variable_mallocator_reset_f(void *var); + lmm_system_t lmm_system_new(void) { lmm_system_t l = NULL; @@ -35,6 +41,11 @@ lmm_system_t lmm_system_new(void) xbt_swag_init(&(l->saturated_constraint_set), xbt_swag_offset(cnst, saturated_constraint_set_hookup)); + l->variable_mallocator = xbt_mallocator_new(64, + lmm_variable_mallocator_new_f, + lmm_variable_mallocator_free_f, + lmm_variable_mallocator_reset_f); + return l; } @@ -49,6 +60,7 @@ void lmm_system_free(lmm_system_t sys) while ((cnst = extract_constraint(sys))) lmm_cnst_free(sys, cnst); + xbt_mallocator_free(sys->variable_mallocator); free(sys); } @@ -75,9 +87,8 @@ static void lmm_var_free(lmm_system_t sys, lmm_variable_t var) { lmm_variable_disable(sys, var); - memset(var->cnsts,0,var->cnsts_size*sizeof(s_lmm_element_t)); free(var->cnsts); - free(var); + xbt_mallocator_release(sys->variable_mallocator, var); } static void lmm_cnst_free(lmm_system_t sys, lmm_constraint_t cnst) @@ -120,6 +131,19 @@ void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst) lmm_cnst_free(sys, cnst); } +static void* lmm_variable_mallocator_new_f(void) { + return xbt_new(s_lmm_variable_t, 1); +} + +static void lmm_variable_mallocator_free_f(void *var) { + xbt_free(var); +} + +static void lmm_variable_mallocator_reset_f(void *var) { + /* memset to zero like calloc */ + memset(var, 0, sizeof(s_lmm_variable_t)); +} + lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id, double weight, double bound, int number_of_constraints) @@ -130,7 +154,7 @@ lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id, XBT_IN5("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)", sys,id,weight,bound,number_of_constraints); - var = xbt_new0(s_lmm_variable_t, 1); + var = xbt_mallocator_get(sys->variable_mallocator); var->id = id; var->cnsts = xbt_new0(s_lmm_element_t, number_of_constraints); for(i=0; iweight = weight; var->bound = bound; var->value = 0.0; + var->df = 0.0; if(weight) xbt_swag_insert_at_head(var,&(sys->variable_set)); else xbt_swag_insert_at_tail(var,&(sys->variable_set)); XBT_OUT; @@ -301,7 +326,7 @@ static void saturated_variable_set_update(lmm_system_t sys) } } -static void lmm_print(lmm_system_t sys) +void lmm_print(lmm_system_t sys) { lmm_constraint_t cnst = NULL; lmm_element_t elem = NULL; @@ -339,7 +364,7 @@ static void lmm_print(lmm_system_t sys) strcat(trace_buf, print_buf); xbt_swag_foreach(elem, elem_list) { sprintf(print_buf,"%f.'%p'(%f) + ",elem->value, - elem->variable,elem->variable->weight); + elem->variable,elem->variable->value); trace_buf = xbt_realloc(trace_buf,strlen(trace_buf)+strlen(print_buf)+1); strcat(trace_buf, print_buf); sum += elem->value * elem->variable->value; @@ -347,10 +372,16 @@ static void lmm_print(lmm_system_t sys) sprintf(print_buf,"0 <= %f ('%p')",cnst->bound,cnst); trace_buf = xbt_realloc(trace_buf,strlen(trace_buf)+strlen(print_buf)+1); strcat(trace_buf, print_buf); + + if(!cnst->shared) { + sprintf(print_buf," [MAX-Constraint]"); + trace_buf = xbt_realloc(trace_buf,strlen(trace_buf)+strlen(print_buf)+1); + strcat(trace_buf, print_buf); + } DEBUG1("%s",trace_buf); trace_buf[0]='\000'; - xbt_assert2((sum<=cnst->bound), "Incorrect value (%f is not smaller than %f)", - sum,cnst->bound); + xbt_assert3((sum<=cnst->bound), "Incorrect value (%f is not smaller than %f): %g", + sum,cnst->bound,sum-cnst->bound); } /* Printing Result */ @@ -386,9 +417,9 @@ void lmm_solve(lmm_system_t sys) var->value = 0.0; } - - /* Compute Usage and store the variables that reach the maximum */ - + /* + * Compute Usage and store the variables that reach the maximum. + */ cnst_list = &(sys->active_constraint_set); DEBUG1("Active constraints : %d", xbt_swag_size(cnst_list)); xbt_swag_foreach(cnst, cnst_list) { @@ -396,21 +427,22 @@ void lmm_solve(lmm_system_t sys) cnst->remaining = cnst->bound; cnst->usage = 0; elem_list = &(cnst->element_set); + cnst->usage = 0.0; xbt_swag_foreach(elem, elem_list) { if(elem->variable->weight <=0) break; if ((elem->value > 0)) { if(cnst->shared) cnst->usage += elem->value / elem->variable->weight; else - cnst->usage = 1; + if(cnst->usagevalue / elem->variable->weight) + cnst->usage = elem->value / elem->variable->weight; + DEBUG2("Constraint Usage %p : %f",cnst,cnst->usage); make_elem_active(elem); } } - /* Saturated constraints update */ saturated_constraint_set_update(sys, cnst, &min_usage); } - saturated_variable_set_update(sys); /* Saturated variables update */ @@ -435,6 +467,8 @@ void lmm_solve(lmm_system_t sys) int i; var->value = min_usage / var->weight; + DEBUG5("Min usage: %f, Var(%p)->weight: %f, Var(%p)->value: %f ",min_usage,var,var->weight,var,var->value); + /* Update usage */ @@ -442,10 +476,23 @@ void lmm_solve(lmm_system_t sys) elem = &var->cnsts[i]; cnst = elem->constraint; if(cnst->shared) { - cnst->remaining -= elem->value * var->value; - cnst->usage -= elem->value / var->weight; + double_update(&(cnst->remaining), elem->value * var->value); + double_update(&(cnst->usage), elem->value / var->weight); + make_elem_inactive(elem); + } else { /* FIXME one day: We recompute usage.... :( */ + cnst->usage = 0.0; + make_elem_inactive(elem); + xbt_swag_foreach(elem, elem_list) { + if(elem->variable->weight <=0) break; + if(elem->variable->value > 0) break; + if ((elem->value > 0)) { + if(cnst->usagevalue / elem->variable->weight) + cnst->usage = elem->value / elem->variable->weight; + DEBUG2("Constraint Usage %p : %f",cnst,cnst->usage); + make_elem_active(elem); + } + } } - make_elem_inactive(elem); } xbt_swag_remove(var, var_list); } @@ -481,6 +528,18 @@ void lmm_update(lmm_system_t sys, lmm_constraint_t cnst, } } +/** \brief Attribute the value bound to var->bound. + * + * \param sys the lmm_system_t + * \param var the lmm_variable_t + * \param bound the new bound to associate with var + * + * Makes var->bound equal to bound. Whenever this function is called + * a change is signed in the system. To + * avoid false system changing detection it is a good idea to test + * (bound != 0) before calling it. + * + */ void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, double bound) { @@ -488,6 +547,25 @@ void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, var->bound = bound; } +/** \brief Add the value delta to var->df (the sum of latencies). + * + * \param sys the lmm_system_t associated + * \param var the lmm_variable_t which need to updated + * \param delta the variation of the latency + * + * Add the value delta to var->df (the sum of latencys associated to the + * flow). Whenever this function is called a change is signed in the system. To + * avoid false system changing detection it is a good idea to test + * (delta != 0) before calling it. + * + */ +void lmm_update_variable_latency(lmm_system_t sys, lmm_variable_t var, + double delta) +{ + sys->modified = 1; + var->df += delta; +} + void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var, double weight) { @@ -538,3 +616,102 @@ lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys, lmm_constraint return xbt_swag_getNext(cnst,(sys->active_constraint_set).offset); } +/** \brief Attribute the value bound to var->bound. + * + * \param func_f default function f associated with the chosen protocol flavor + * \param func_fp partial differential of f (f prime, f') + * \param func_fpi inverse of the partial differential of f (f prime inverse, (f')^{-1}) + * \param func_fpip partial differential of the inverse of the partial differential of f (f prime inverse prime, ((f')^{-1})') + * + * Set default functions to the ones passed as parameters. + * + */ +void lmm_set_default_protocol_functions(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), + double (* func_fpip) (lmm_variable_t var, double x)) + +{ + func_f_def = func_f; + func_fp_def = func_fp; + func_fpi_def = func_fpi; + func_fpip_def = func_fpip; +} + + +/* + * NOTE for Reno: all functions consider the network + * coeficient (alpha) equal to 1. + */ + +/* + * For Reno f: $\alpha_f d_f \log\left(x_f\right)$ + */ +double func_reno_f(lmm_variable_t var, double x){ + xbt_assert0(x,"Please report this bug."); + return var->df * log(x); +} + +/* + * For Reno fp: $\frac{\alpha D_f}{x}$ + */ +double func_reno_fp(lmm_variable_t var, double x){ + xbt_assert0(x,"Please report this bug."); + return var->df/x; +} + +/* + * For Reno fpi: $\frac{\alpha D_f}{x}$ + */ +double func_reno_fpi(lmm_variable_t var, double x){ + xbt_assert0(x,"Please report this bug."); + return var->df/x; +} + +/* + * For Reno fpip: $-\frac{\alpha D_f}{x^2}$ + */ +double func_reno_fpip(lmm_variable_t var, double x){ + xbt_assert0(x,"Please report this bug."); + return -( var->df/(x*x) ) ; +} + + +/* + * For Vegas f: $\frac{\sqrt{\frac{3}{2}}}{D_f} \arctan\left(\sqrt{\frac{3}{2}}x_f D_f\right)$ + */ +double func_vegas_f(lmm_variable_t var, double x){ + xbt_assert0(x,"Please report this bug."); + // \sqrt{3/2} = 0.8164965808 + return (0.8164965808 / var->df) * atan( (0.8164965808 / var->df)*x ); +} + +/* + * For Vegas fp: $\frac{3{D_f}^2}{3{D_f}^2x^2 + 2}$ + */ +double func_vegas_fp(lmm_variable_t var, double x){ + xbt_assert0(x,"Please report this bug."); + return (3*var->df*var->df) / (3*var->df*var->df*x*x + 2); +} + +/* + * For Vegas fpi: $\sqrt{\frac{1}{x} - \frac{2}{3{D_f}^2}}$ + */ +double func_vegas_fpi(lmm_variable_t var, double x){ + double res_fpi; + xbt_assert0( (x<0.0) ,"Please report this bug."); + xbt_assert0( (var->df<0.0), "Please report this bug."); + res_fpi = (1/x) - 2/(3*var->df*var->df); + return sqrt(res_fpi); +} + +/* + * For Vegas fpip: $-\frac{1}{2x^2\sqrt{\frac{1}{x} - \frac{2}{3{D_f}^2}}}$ + */ +double func_vegas_fpip(lmm_variable_t var, double x){ + double res_fpip; + xbt_assert0(x,"Please report this bug."); + xbt_assert0( (x<0.0), "Please report this bug."); + res_fpip = sqrt(1/x - 2/(3*var->df*var->df)); + return -(1/(2*x*x*res_fpip)); +}