From 7c0dfd20f04a956fac7c83746f032632b5b00b68 Mon Sep 17 00:00:00 2001 From: velho Date: Thu, 12 Apr 2007 09:44:37 +0000 Subject: [PATCH] Sigma step working. git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@3400 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- src/surf/lagrange.c | 283 +++++++++++++++++++++----------------------- 1 file changed, 135 insertions(+), 148 deletions(-) diff --git a/src/surf/lagrange.c b/src/surf/lagrange.c index 48cd3277f8..8adc5c66b0 100644 --- a/src/surf/lagrange.c +++ b/src/surf/lagrange.c @@ -20,6 +20,8 @@ #include #endif +#define LAMBDA_STEP 0.01 + XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_lagrange, surf, "Logging specific to SURF (lagrange)"); @@ -31,56 +33,59 @@ void lagrange_solve(lmm_system_t sys); void lagrange_solve(lmm_system_t sys) { - /* * Lagrange Variables. */ - double epsilon_min_error = 1e-6; + int max_iterations= 1000000; + double epsilon_min_error = 0.00001; double overall_error = 1; - double sigma_step = 1e-3; - double capacity_error=0, bound_error=0; - + double sigma_step = LAMBDA_STEP; + //double capacity_error=0, bound_error=0; + int watch_out = 0; /* * Variables to manipulate the data structure proposed to model the maxmin * fairness. See docummentation for more details. */ xbt_swag_t elem_list = NULL; + //lmm_element_t elem = NULL; lmm_element_t elem1 = NULL; - lmm_element_t elem = NULL; + xbt_swag_t cnst_list = NULL; + //lmm_constraint_t cnst = NULL; lmm_constraint_t cnst1 = NULL; - lmm_constraint_t cnst2 = NULL; - lmm_constraint_t cnst = NULL; - double sum; + //lmm_constraint_t cnst2 = NULL; + + xbt_swag_t var_list = NULL; + //lmm_variable_t var = NULL; lmm_variable_t var1 = NULL; - lmm_variable_t var = NULL; lmm_variable_t var2 = NULL; - /* * Auxiliar variables. */ int iteration=0; - int max_iterations= 1000; double mu_partial=0; double lambda_partial=0; double tmp=0; int i,j; FILE *gnuplot_file=NULL; - char print_buf[1024]; - char *trace_buf=xbt_malloc0(sizeof(char)); - - + //char print_buf[1024]; + //char *trace_buf=xbt_malloc0(sizeof(char)); + //double sum; + DEBUG0("Iterative method configuration snapshot =====>"); + DEBUG1("#### Maximum number of iterations : %d", max_iterations); + DEBUG1("#### Minimum error tolerated : %e", epsilon_min_error); + DEBUG1("#### Step : %e", sigma_step); if ( !(sys->modified)) return; - + /* * Initialize the var list variable with only the active variables. * Associate an index in the swag variables. Initialize mu. @@ -89,12 +94,14 @@ void lagrange_solve(lmm_system_t sys) i=0; xbt_swag_foreach(var1, var_list) { if((var1->bound > 0.0) || (var1->weight <= 0.0)){ - DEBUG1("## NOTE var1(%d) is a boundless variable", i); + DEBUG1("#### NOTE var1(%d) is a boundless variable", i); var1->mu = -1.0; - } else + } else{ var1->mu = 1.0; - DEBUG2("## var1(%d)->mu: %e", i, var1->mu); - DEBUG2("## var1(%d)->weight: %e", i, var1->weight); + var1->new_mu = 2.0; + } + DEBUG2("#### var1(%d)->mu: %e", i, var1->mu); + DEBUG2("#### var1(%d)->weight: %e", i, var1->weight); i++; } @@ -104,12 +111,13 @@ void lagrange_solve(lmm_system_t sys) cnst_list=&(sys->active_constraint_set); xbt_swag_foreach(cnst1, cnst_list) { cnst1->lambda = 1.0; - DEBUG2("## cnst1(%p)->lambda: %e", cnst1, cnst1->lambda); + cnst1->new_lambda = 2.0; + DEBUG2("#### cnst1(%p)->lambda: %e", cnst1, cnst1->lambda); } if(XBT_LOG_ISENABLED(surf_writelambda, xbt_log_priority_debug)) { gnuplot_file = fopen("lambda.in", "w"); - fprintf(gnuplot_file, "# iteration lambda1 lambda2 lambda3 ... lambdaP"); + fprintf(gnuplot_file, "# iteration lambda1 lambda2 lambda3 ... lambdaP\n"); } @@ -133,31 +141,31 @@ void lagrange_solve(lmm_system_t sys) mu_partial = -1.0 / mu_partial + var1->bound; var1->new_mu = var1->mu - sigma_step * mu_partial; - /* Assert that var1->new_mu is positive */ - } - } - if(XBT_LOG_ISENABLED(surf_writelambda, xbt_log_priority_debug)) { - fprintf(gnuplot_file, "\n%d ", iteration); + if(var1->new_mu < 0){ + var1->new_mu = 0; + } + } } + /* d Dual * Compute the value of ------------- (\lambda^k, \mu^k) this portion * d \lambda_i^k * of code depends on function f(x). */ - - DEBUG1("######Lambda partial at iteration %d", iteration); - cnst_list=&(sys->active_constraint_set); j=0; + if(XBT_LOG_ISENABLED(surf_writelambda, xbt_log_priority_debug)) { + fprintf(gnuplot_file, "\n%d",iteration); + } xbt_swag_foreach(cnst1, cnst_list) { j++; lambda_partial = 0; elem_list = &(cnst1->element_set); + watch_out=0; xbt_swag_foreach(elem1, elem_list) { - lambda_partial = 0; var2 = elem1->variable; @@ -165,144 +173,120 @@ void lagrange_solve(lmm_system_t sys) tmp = 0; - //for each link with capacity cnsts[i] that uses flow of variable var1 do + for(i=0; icnsts_number; i++){ + tmp += (var2->cnsts[i].constraint)->lambda; + } if(var2->bound > 0) tmp += var2->mu; - for(i=0; icnsts_number; i++) - tmp += (var2->cnsts[i].constraint)->lambda; - lambda_partial += -1 / tmp; - } + if(tmp==0) break; - lambda_partial += cnst1->bound; + if (tmp==cnst1->lambda) + watch_out=1; + lambda_partial += (-1.0 / tmp); + } - DEBUG2("###########Lambda partial %p : %e", cnst1, lambda_partial); + if(tmp == 0) + cnst1->new_lambda = LAMBDA_STEP; + else { + lambda_partial += cnst1->bound; + if(watch_out && (lambda_partial>0)) { + /* INFO6("Watch Out (%d) %p! lambda_partial: %e; lambda : %e ; (%e %e) \n",iteration, cnst1, */ + /* lambda_partial, cnst1->lambda, cnst1->lambda / 2, */ + /* cnst1->lambda - sigma_step * lambda_partial); */ + + if(cnst1->lambda < 0) WARN2("Value of cnst1->lambda(%p) = %e < 0", cnst1, cnst1->lambda); + if((cnst1->lambda - sigma_step * lambda_partial) < 0) WARN1("Value of lambda_new = %e < 0", (cnst1->lambda - sigma_step * lambda_partial)); + + if(cnst1->lambda - sigma_step * lambda_partial < cnst1->lambda / 2) + cnst1->new_lambda = cnst1->lambda / 2; + else + cnst1->new_lambda = cnst1->lambda - sigma_step * lambda_partial; + } else + cnst1->new_lambda = cnst1->lambda - sigma_step * lambda_partial; + if(cnst1->new_lambda < 0){ + cnst1->new_lambda = 0; + } + } - cnst1->new_lambda = cnst1->lambda - sigma_step * lambda_partial; - if(XBT_LOG_ISENABLED(surf_writelambda, xbt_log_priority_debug)) { - fprintf(gnuplot_file, " %f", cnst1->lambda); + fprintf(gnuplot_file, " %e", cnst1->lambda); } + } - /* Updating lambda's and mu's */ - var_list = &(sys->variable_set); - xbt_swag_foreach(var1, var_list) - if(!((var1->bound > 0.0) || (var1->weight <= 0.0))) - var1->mu = var1->new_mu; - - cnst_list=&(sys->active_constraint_set); - xbt_swag_foreach(cnst1, cnst_list) - cnst1->lambda = cnst1->new_lambda; - /* * Now computes the values of each variable (\rho) based on * the values of \lambda and \mu. */ - var_list = &(sys->variable_set); + overall_error=0; xbt_swag_foreach(var1, var_list) { if(var1->weight <=0) var1->value = 0.0; else { tmp = 0; - if(var1->bound >0) - tmp+=var1->mu; - for(i=0; icnsts_number; i++) + for(i=0; icnsts_number; i++){ tmp += (var1->cnsts[i].constraint)->lambda; + if(var1->bound > 0) + tmp+=var1->mu; + } + + //computes de overall_error + if(overall_error < fabs(var1->value - 1.0/tmp)){ + overall_error = fabs(var1->value - 1.0/tmp); + } - var1->value = 1 / tmp; + var1->value = 1.0 / tmp; } - - DEBUG2("var1->value (id=%s) : %e", (char *)var1->id, var1->value); } - /* 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); - 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); - strcat(trace_buf, print_buf); - } - 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'; - - /* Printing Constraints */ - cnst_list = &(sys->active_constraint_set); - xbt_swag_foreach(cnst, cnst_list) { - 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); - 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); - 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); - 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'; - if(!(sum<=cnst->bound)) - DEBUG3("Incorrect value (%f is not smaller than %f): %g", - sum,cnst->bound,sum-cnst->bound); + + /* Updating lambda's and mu's */ + xbt_swag_foreach(var1, var_list) + if(!((var1->bound > 0.0) || (var1->weight <= 0.0))) + var1->mu = var1->new_mu; + + + xbt_swag_foreach(cnst1, cnst_list) + cnst1->lambda = cnst1->new_lambda; } - /* Printing Result */ - xbt_swag_foreach(var, var_list) { - if(var->bound>0) { - DEBUG4("'%p'(%f) : %f (<=%f)",var,var->weight,var->value, var->bound); - if(var->value<=var->bound) - DEBUG0("Incorrect value"); + + + + //verify the KKT property + xbt_swag_foreach(cnst1, cnst_list){ + tmp = 0; + elem_list = &(cnst1->element_set); + xbt_swag_foreach(elem1, elem_list) { + var1 = elem1->variable; + if(var1->weight<=0) continue; + tmp += var1->value; } - else - DEBUG3("'%p'(%f) : %f",var,var->weight,var->value); - } + tmp = tmp - cnst1->bound; + - /* - * Verify for each capacity constraint (lambda) the error associated. - */ - capacity_error = 0; - cnst_list=&(sys->active_constraint_set); - xbt_swag_foreach(cnst1, cnst_list) { - cnst2 = xbt_swag_getNext(cnst1,(var_list)->offset); - if(cnst2 != NULL){ - capacity_error += fabs( cnst1->lambda - cnst2->lambda ); - } + if(tmp != 0 || cnst1->lambda != 0){ + WARN4("The link %s(%p) doesn't match the KKT property, value expected (=0) got (lambda=%e) (sum_rho=%e)", (char *)cnst1->id, cnst1, cnst1->lambda, tmp); } + + } - /* - * Verify for each variable the error of round trip time constraint (mu). - */ - bound_error = 0; - var_list = &(sys->variable_set); - xbt_swag_foreach(var1, var_list) { - var2 = xbt_swag_getNext(var1,(var_list)->offset); - if(var2 != NULL){ - bound_error += fabs( var2->mu - var1->mu); - } + + xbt_swag_foreach(var1, var_list){ + if(var1->bound <= 0 || var1->weight <= 0) continue; + tmp = 0; + tmp = (var1->value - var1->bound); + + + if(tmp != 0 || var1->mu != 0){ + WARN4("The flow %s(%p) doesn't match the KKT property, value expected (=0) got (lambda=%e) (sum_rho=%e)", (char *)var1->id, var1, var1->mu, tmp); } - overall_error = capacity_error + bound_error; } @@ -320,21 +304,24 @@ void lagrange_solve(lmm_system_t sys) } - /* - * Now computes the values of each variable (\rho) based on - * the values of \lambda and \mu. - */ - var_list = &(sys->variable_set); - xbt_swag_foreach(var1, var_list) { - tmp = 0; - for(i=0; icnsts_number; i++){ - elem1 = &(var1->cnsts[i]); - tmp += (elem1->constraint)->lambda + var1->mu; - } - var1->weight = 1 / tmp; - DEBUG2("var1->weight (id=%s) : %e", (char *)var1->id, var1->weight); - } + + +/* /\* */ +/* * Now computes the values of each variable (\rho) based on */ +/* * the values of \lambda and \mu. */ +/* *\/ */ +/* var_list = &(sys->variable_set); */ +/* xbt_swag_foreach(var1, var_list) { */ +/* tmp = 0; */ +/* for(i=0; icnsts_number; i++){ */ +/* elem1 = &(var1->cnsts[i]); */ +/* tmp += (elem1->constraint)->lambda + var1->mu; */ +/* } */ +/* var1->weight = 1 / tmp; */ + +/* DEBUG2("var1->weight (id=%s) : %e", (char *)var1->id, var1->weight); */ +/* } */ -- 2.20.1