X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/c027c476705c1c88c5c76570ccdd75809fbc3af2..cf56a22da60094d8e7f14b1457526dc194d40226:/src/surf/maxmin.c diff --git a/src/surf/maxmin.c b/src/surf/maxmin.c index e36c5c88fe..3177a75fe1 100644 --- a/src/surf/maxmin.c +++ b/src/surf/maxmin.c @@ -15,7 +15,7 @@ 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_new_f(void); static void lmm_variable_mallocator_free_f(void *var); static void lmm_variable_mallocator_reset_f(void *var); @@ -69,7 +69,7 @@ void lmm_variable_disable(lmm_system_t sys, lmm_variable_t var) int i; lmm_element_t elem = NULL; - XBT_IN2("(sys=%p, var=%p)",sys,var); + XBT_IN2("(sys=%p, var=%p)", sys, var); sys->modified = 1; for (i = 0; i < var->cnsts_number; i++) { @@ -131,15 +131,18 @@ 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) { +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) { +static void lmm_variable_mallocator_free_f(void *var) +{ xbt_free(var); } -static void lmm_variable_mallocator_reset_f(void *var) { +static void lmm_variable_mallocator_reset_f(void *var) +{ /* memset to zero like calloc */ memset(var, 0, sizeof(s_lmm_variable_t)); } @@ -152,12 +155,12 @@ lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id, int i; XBT_IN5("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)", - sys,id,weight,bound,number_of_constraints); + sys, id, weight, bound, number_of_constraints); var = xbt_mallocator_get(sys->variable_mallocator); var->id = id; var->cnsts = xbt_new0(s_lmm_element_t, number_of_constraints); - for(i=0; icnsts[i].element_set_hookup.next = NULL; @@ -169,20 +172,21 @@ lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id, var->cnsts[i].value = 0.0; } var->cnsts_size = number_of_constraints; - var->cnsts_number = 0; /* Should be useless because of the - calloc but it seems to help valgrind... */ + var->cnsts_number = 0; /* Should be useless because of the + calloc but it seems to help valgrind... */ var->weight = weight; var->bound = bound; var->value = 0.0; - var->df = 1.0; + var->df = 0.0; - var->func_f = func_f_def; - var->func_fp = func_fp_def; - var->func_fpi = func_fpi_def; - var->func_fpip = func_fpip_def; + var->func_f = func_f_def; + var->func_fp = func_fp_def; + var->func_fpi = func_fpi_def; - if(weight) xbt_swag_insert_at_head(var,&(sys->variable_set)); - else xbt_swag_insert_at_tail(var,&(sys->variable_set)); + if (weight) + xbt_swag_insert_at_head(var, &(sys->variable_set)); + else + xbt_swag_insert_at_tail(var, &(sys->variable_set)); XBT_OUT; return var; } @@ -205,8 +209,7 @@ void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, sys->modified = 1; - xbt_assert0(var->cnsts_number < var->cnsts_size, - "Too much constraints"); + xbt_assert0(var->cnsts_number < var->cnsts_size, "Too much constraints"); elem = &(var->cnsts[var->cnsts_number++]); @@ -214,8 +217,10 @@ void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, elem->constraint = cnst; elem->variable = var; - if(var->weight) xbt_swag_insert_at_head(elem,&(elem->constraint->element_set)); - else xbt_swag_insert_at_tail(elem,&(elem->constraint->element_set)); + if (var->weight) + xbt_swag_insert_at_head(elem, &(elem->constraint->element_set)); + else + xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set)); make_constraint_active(sys, cnst); } @@ -223,28 +228,33 @@ void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, double value) { - int i ; + int i; sys->modified = 1; - for(i=0; i< var->cnsts_number ; i++) - if(var->cnsts[i].constraint == cnst) break; - - if(icnsts_number) var->cnsts[i].value +=value; - else lmm_expand(sys,cnst,var,value); + for (i = 0; i < var->cnsts_number; i++) + if (var->cnsts[i].constraint == cnst) + break; + + if (i < var->cnsts_number) + var->cnsts[i].value += value; + else + lmm_expand(sys, cnst, var, value); } void lmm_elem_set_value(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, double value) { - int i ; + int i; - for(i=0; i< var->cnsts_number ; i++) - if(var->cnsts[i].constraint == cnst) break; + for (i = 0; i < var->cnsts_number; i++) + if (var->cnsts[i].constraint == cnst) + break; - if(icnsts_number) { - var->cnsts[i].value =value; + if (i < var->cnsts_number) { + var->cnsts[i].value = value; sys->modified = 1; - } else DIE_IMPOSSIBLE; + } else + DIE_IMPOSSIBLE; } lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys, @@ -288,7 +298,7 @@ static void saturated_constraint_set_update(lmm_system_t sys, { lmm_constraint_t useless_cnst = NULL; - XBT_IN3("sys=%p, cnst=%p, min_usage=%f",sys,cnst,*min_usage); + XBT_IN3("sys=%p, cnst=%p, min_usage=%f", sys, cnst, *min_usage); if (cnst->usage <= 0) { XBT_OUT; return; @@ -299,8 +309,8 @@ static void saturated_constraint_set_update(lmm_system_t sys, } if ((*min_usage < 0) || (*min_usage > cnst->remaining / cnst->usage)) { *min_usage = cnst->remaining / cnst->usage; - LOG3(xbt_log_priority_trace, - "min_usage=%f (cnst->remaining=%f, cnst->usage=%f)",*min_usage, + LOG3(xbt_log_priority_trace, + "min_usage=%f (cnst->remaining=%f, cnst->usage=%f)", *min_usage, cnst->remaining, cnst->usage); while ((useless_cnst = xbt_swag_getFirst(&(sys->saturated_constraint_set)))) @@ -324,7 +334,8 @@ static void saturated_variable_set_update(lmm_system_t sys) while ((cnst = xbt_swag_getFirst(cnst_list))) { elem_list = &(cnst->active_element_set); xbt_swag_foreach(elem, elem_list) { - if(elem->variable->weight<=0) break; + if (elem->variable->weight <= 0) + break; if ((elem->value > 0)) xbt_swag_insert(elem->variable, &(sys->saturated_variable_set)); } @@ -341,63 +352,77 @@ void lmm_print(lmm_system_t sys) xbt_swag_t var_list = NULL; xbt_swag_t elem_list = NULL; char print_buf[1024]; - char *trace_buf=xbt_malloc0(sizeof(char)); - double sum=0.0; + char *trace_buf = xbt_malloc0(sizeof(char)); + double sum = 0.0; /* Printing Objective */ var_list = &(sys->variable_set); - sprintf(print_buf,"MAX-MIN ( "); - trace_buf = xbt_realloc(trace_buf,strlen(trace_buf)+strlen(print_buf)+1); + sprintf(print_buf, "MAX-MIN ( "); + trace_buf = + xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); strcat(trace_buf, print_buf); xbt_swag_foreach(var, var_list) { - sprintf(print_buf,"'%p'(%f) ",var,var->weight); - trace_buf = xbt_realloc(trace_buf,strlen(trace_buf)+strlen(print_buf)+1); + sprintf(print_buf, "'%p'(%f) ", var, var->weight); + trace_buf = + xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); strcat(trace_buf, print_buf); } - sprintf(print_buf,")"); - trace_buf = xbt_realloc(trace_buf,strlen(trace_buf)+strlen(print_buf)+1); + sprintf(print_buf, ")"); + 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'; + DEBUG1("%s", trace_buf); + trace_buf[0] = '\000'; + DEBUG0("Constraints"); /* Printing Constraints */ cnst_list = &(sys->active_constraint_set); xbt_swag_foreach(cnst, cnst_list) { - sum=0.0; + sum = 0.0; elem_list = &(cnst->element_set); - sprintf(print_buf,"\t"); - trace_buf = xbt_realloc(trace_buf,strlen(trace_buf)+strlen(print_buf)+1); + sprintf(print_buf, "\t"); + trace_buf = + xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1); strcat(trace_buf, print_buf); xbt_swag_foreach(elem, elem_list) { - sprintf(print_buf,"%f.'%p'(%f) + ",elem->value, - elem->variable,elem->variable->value); - trace_buf = xbt_realloc(trace_buf,strlen(trace_buf)+strlen(print_buf)+1); + sprintf(print_buf, "%f.'%p'(%f) + ", elem->value, + 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; } - sprintf(print_buf,"0 <= %f ('%p')",cnst->bound,cnst); - trace_buf = xbt_realloc(trace_buf,strlen(trace_buf)+strlen(print_buf)+1); + 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); + 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_assert3((sum<=cnst->bound), "Incorrect value (%f is not smaller than %f): %g", - sum,cnst->bound,sum-cnst->bound); + DEBUG1("%s", trace_buf); + trace_buf[0] = '\000'; + if (double_positive(sum - cnst->bound)) + WARN3("Incorrect value (%f is not smaller than %f): %g", + sum, cnst->bound, sum - cnst->bound); } + DEBUG0("Variables"); /* Printing Result */ xbt_swag_foreach(var, var_list) { - if(var->bound>0) { - DEBUG4("'%p'(%f) : %f (<=%f)",var,var->weight,var->value, var->bound); - xbt_assert0((var->value<=var->bound), "Incorrect value"); - } - else - DEBUG3("'%p'(%f) : %f",var,var->weight,var->value); + if (var->bound > 0) { + DEBUG4("'%p'(%f) : %f (<=%f)", var, var->weight, var->value, + var->bound); + if (double_positive(var->value - var->bound)) + WARN2("Incorrect value (%f is not smaller than %f", + var->value, var->bound); + } else + DEBUG3("'%p'(%f) : %f", var, var->weight, var->value); } free(trace_buf); @@ -420,7 +445,14 @@ void lmm_solve(lmm_system_t sys) var_list = &(sys->variable_set); DEBUG1("Variable set : %d", xbt_swag_size(var_list)); xbt_swag_foreach(var, var_list) { + int nb=0; + int i; var->value = 0.0; + for (i = 0; i < var->cnsts_number; i++) { + if(var->cnsts[i].value==0.0) nb++; + } + if((nb==var->cnsts_number) && (var->weight>0.0)) + var->value = 1.0; } /* @@ -435,14 +467,14 @@ void lmm_solve(lmm_system_t sys) elem_list = &(cnst->element_set); cnst->usage = 0.0; xbt_swag_foreach(elem, elem_list) { - if(elem->variable->weight <=0) break; + if (elem->variable->weight <= 0) + break; if ((elem->value > 0)) { - if(cnst->shared) + if (cnst->shared) cnst->usage += elem->value / elem->variable->weight; - else - if(cnst->usagevalue / elem->variable->weight) - cnst->usage = elem->value / elem->variable->weight; - DEBUG2("Constraint Usage %p : %f",cnst,cnst->usage); + else if (cnst->usage < elem->value / elem->variable->weight) + cnst->usage = elem->value / elem->variable->weight; + DEBUG2("Constraint Usage %p : %f", cnst, cnst->usage); make_elem_active(elem); } } @@ -460,11 +492,13 @@ void lmm_solve(lmm_system_t sys) xbt_swag_foreach(var, var_list) { /* First check if some of these variables have reach their upper bound and update min_usage accordingly. */ - DEBUG5("var=%p, var->bound=%f, var->weight=%f, min_usage=%f, var->bound*var->weight=%f", - var, var->bound, var->weight, min_usage,var->bound * var->weight); + DEBUG5 + ("var=%p, var->bound=%f, var->weight=%f, min_usage=%f, var->bound*var->weight=%f", + var, var->bound, var->weight, min_usage, + var->bound * var->weight); if ((var->bound > 0) && (var->bound * var->weight < min_usage)) { min_usage = var->bound * var->weight; - DEBUG1("Updated min_usage=%f",min_usage); + DEBUG1("Updated min_usage=%f", min_usage); } } @@ -473,7 +507,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); + DEBUG5("Min usage: %f, Var(%p)->weight: %f, Var(%p)->value: %f ", + min_usage, var, var->weight, var, var->value); /* Update usage */ @@ -481,23 +516,25 @@ void lmm_solve(lmm_system_t sys) for (i = 0; i < var->cnsts_number; i++) { elem = &var->cnsts[i]; cnst = elem->constraint; - if(cnst->shared) { + if (cnst->shared) { 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.... :( */ + } 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->variable->weight <= 0) + break; + if (elem->variable->value > 0) + break; if ((elem->value > 0)) { - if(cnst->usagevalue / elem->variable->weight) + if (cnst->usage < elem->value / elem->variable->weight) cnst->usage = elem->value / elem->variable->weight; - DEBUG2("Constraint Usage %p : %f",cnst,cnst->usage); + DEBUG2("Constraint Usage %p : %f", cnst, cnst->usage); make_elem_active(elem); } - } + } } } xbt_swag_remove(var, var_list); @@ -514,7 +551,7 @@ void lmm_solve(lmm_system_t sys) } while (xbt_swag_size(&(sys->saturated_variable_set))); sys->modified = 0; - if(XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { + if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { lmm_print(sys); } } @@ -566,7 +603,7 @@ void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, * */ void lmm_update_variable_latency(lmm_system_t sys, lmm_variable_t var, - double delta) + double delta) { sys->modified = 1; var->df += delta; @@ -575,27 +612,30 @@ void lmm_update_variable_latency(lmm_system_t sys, lmm_variable_t var, void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var, double weight) { - int i ; + int i; lmm_element_t elem; - XBT_IN3("(sys=%p, var=%p, weight=%f)",sys,var,weight); + XBT_IN3("(sys=%p, var=%p, weight=%f)", sys, var, weight); sys->modified = 1; var->weight = weight; - xbt_swag_remove(var,&(sys->variable_set)); - if(weight) xbt_swag_insert_at_head(var,&(sys->variable_set)); - else xbt_swag_insert_at_tail(var,&(sys->variable_set)); + xbt_swag_remove(var, &(sys->variable_set)); + if (weight) + xbt_swag_insert_at_head(var, &(sys->variable_set)); + else + xbt_swag_insert_at_tail(var, &(sys->variable_set)); for (i = 0; i < var->cnsts_number; i++) { elem = &var->cnsts[i]; xbt_swag_remove(elem, &(elem->constraint->element_set)); - if(weight) xbt_swag_insert_at_head(elem, &(elem->constraint->element_set)); - else xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set)); + if (weight) + xbt_swag_insert_at_head(elem, &(elem->constraint->element_set)); + else + xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set)); } XBT_OUT; } double lmm_get_variable_weight(lmm_variable_t var) - { return var->weight; } @@ -617,129 +657,8 @@ lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t sys) return xbt_swag_getFirst(&(sys->active_constraint_set)); } -lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys, lmm_constraint_t cnst) +lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys, + lmm_constraint_t cnst) { - 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. This is a polimorfism in C pure, enjoy the roots of programming. - * - */ -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 Vegas f: $\alpha_f d_f \log\left(x_f\right)$ - */ -double func_vegas_f(lmm_variable_t var, double x){ - return var->df * log(x); -} - -/* - * For Vegas fp: $\frac{\alpha D_f}{x}$ - */ -double func_vegas_fp(lmm_variable_t var, double x){ - //avoid a disaster value - c'est du bricolage mais ca marche - if(x == 0) x = 10e-8; - return var->df/x; -} - -/* - * For Vegas fpi: $\frac{\alpha D_f}{x}$ - */ -double func_vegas_fpi(lmm_variable_t var, double x){ - //avoid a disaster value - c'est du bricolage mais ca marche - if(x == 0) x = 10e-8; - return var->df/x; -} - -/* - * For Vegas fpip: $-\frac{\alpha D_f}{x^2}$ - */ -double func_vegas_fpip(lmm_variable_t var, double x){ - //avoid a disaster value - c'est du bricolage mais ca marche - if(x == 0) x = 10e-8; - return -( var->df/(x*x) ) ; -} - - -/* - * For Reno f: $\frac{\sqrt{\frac{3}{2}}}{D_f} \arctan\left(\sqrt{\frac{3}{2}}x_f D_f\right)$ - */ -double func_reno_f(lmm_variable_t var, double x){ - xbt_assert0( var->df, "Please report this bug."); - // \sqrt{3/2} = 0.8164965808 - return (0.8164965808 / var->df) * atan( (0.8164965808 / var->df)*x ); -} - -/* - * For Reno fp: $\frac{3}{3 {D_f}^2 x^2 + 2}$ - */ -double func_reno_fp(lmm_variable_t var, double x){ - return 3 / (3*var->df*var->df*x*x + 2); -} - -/* - * For Reno fpi: $\sqrt{\frac{1}{{D_f}^2 x} - \frac{2}{3{D_f}^2}}$ - */ -double func_reno_fpi(lmm_variable_t var, double x){ - double res_fpi; - xbt_assert0( var->df, "Please report this bug."); - - //avoid a disaster value - c'est du bricolage mais ca marche - if(x == 0) x = 10e-8; - - res_fpi = 1/(var->df*var->df*x) - 2/(3*var->df*var->df); - - //avoid a disaster value of res_fpi - if(res_fpi < 0.0) return 0.0; - else return sqrt(res_fpi); -} - -/* - * For Reno fpip: $-\frac{1}{2 {D_f}^2 x^2\sqrt{\frac{1}{{D_f}^2 x} - \frac{2}{3{D_f}^2}}}$ - */ -double func_reno_fpip(lmm_variable_t var, double x){ - double res_fpip; - double critical_test; - - xbt_assert0(var->df,"Please report this bug."); - - //avoid division by zero - c'est du bricolage mais ca marche - if(x == 0) x = 10e-8; - - res_fpip = 1/(var->df*var->df*x) - 2/(3*var->df*var->df); - - //avoid square root of negative number - if(res_fpip < 0.0) return 0.0; - - //avoid division by zero - critical_test = (2*var->df*var->df*x*x*sqrt(res_fpip)); - - if(critical_test == 0.0) return 0.0; - else return -(1/critical_test); + return xbt_swag_getNext(cnst, (sys->active_constraint_set).offset); }