X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/16bbb8a8212497d9c44c81333ed2c0e689e0c5af..219810d5f28a3f177c7d9341b0fd227cbf651082:/src/surf/maxmin.cpp diff --git a/src/surf/maxmin.cpp b/src/surf/maxmin.cpp index 5e7441057e..e40a1ab08a 100644 --- a/src/surf/maxmin.cpp +++ b/src/surf/maxmin.cpp @@ -35,7 +35,7 @@ static int Global_debug_id = 1; static int Global_const_debug_id = 1; static void lmm_var_free(lmm_system_t sys, lmm_variable_t var); -static XBT_INLINE void lmm_cnst_free(lmm_system_t sys, +static inline void lmm_cnst_free(lmm_system_t sys, lmm_constraint_t cnst); static void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr); @@ -46,15 +46,32 @@ static int lmm_concurrency_slack(lmm_constraint_t cnstr); static int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var); static void lmm_check_concurrency(lmm_system_t sys); - -inline void lmm_decrease_concurrency(lmm_constraint_t cnstr){ - xbt_assert(cnstr->concurrency_current>0); - cnstr->concurrency_current--; + +inline int lmm_element_concurrency(lmm_element_t elem) { + //Ignore element with weight less than one (e.g. cross-traffic) + return (elem->value>=1)?1:0; + //There are other alternatives, but they will change the behaviour of the model.. + //So do not use it unless you want to make a new model. + //If you do, remember to change the variables concurrency share to reflect it. + //Potential examples are: + //return (elem->weight>0)?1:0;//Include element as soon as weight is non-zero + //return (int)ceil(elem->weight);//Include element as the rounded-up integer value of the element weight } -inline void lmm_increase_concurrency(lmm_constraint_t cnstr){ - if(++cnstr->concurrency_current > cnstr->concurrency_maximum) - cnstr->concurrency_maximum=cnstr->concurrency_current; +inline void lmm_decrease_concurrency(lmm_element_t elem) { + xbt_assert(elem->constraint->concurrency_current>=lmm_element_concurrency(elem)); + elem->constraint->concurrency_current-=lmm_element_concurrency(elem); +} + +inline void lmm_increase_concurrency(lmm_element_t elem) { + + elem->constraint->concurrency_current+= lmm_element_concurrency(elem); + + lmm_constraint_t cnstr=elem->constraint; + + if(cnstr->concurrency_current > cnstr->concurrency_maximum) + cnstr->concurrency_maximum= cnstr->concurrency_current; + xbt_assert(cnstr->concurrency_limit<0 || cnstr->concurrency_current<=cnstr->concurrency_limit,"Concurrency limit overflow!"); } @@ -98,17 +115,16 @@ lmm_system_t lmm_system_new(int selective_update) void lmm_system_free(lmm_system_t sys) { - lmm_variable_t var = NULL; - lmm_constraint_t cnst = NULL; + lmm_variable_t var = nullptr; + lmm_constraint_t cnst = nullptr; + + if (!sys) + return; - while ((var = (lmm_variable_t) extract_variable(sys))) { - XBT_WARN - ("Variable %p (%d) still in system when freing it: this may be a bug", - var, var->id_int); + XBT_WARN("Variable %d still in system when freing it: this may be a bug", var->id_int); lmm_var_free(sys, var); } - while ((cnst = (lmm_constraint_t) extract_constraint(sys))) lmm_cnst_free(sys, cnst); @@ -116,7 +132,7 @@ void lmm_system_free(lmm_system_t sys) free(sys); } -static XBT_INLINE void lmm_variable_remove(lmm_system_t sys, lmm_variable_t var) +static inline void lmm_variable_remove(lmm_system_t sys, lmm_variable_t var) { int i; int nelements; @@ -133,7 +149,7 @@ static XBT_INLINE void lmm_variable_remove(lmm_system_t sys, lmm_variable_t var) for (i = 0; i < var->cnsts_number; i++) { elem = &var->cnsts[i]; if(var->weight>0) - lmm_decrease_concurrency(elem->constraint); + lmm_decrease_concurrency(elem); xbt_swag_remove(elem, &(elem->constraint->enabled_element_set)); xbt_swag_remove(elem, &(elem->constraint->disabled_element_set)); xbt_swag_remove(elem, &(elem->constraint->active_element_set)); @@ -141,12 +157,23 @@ static XBT_INLINE void lmm_variable_remove(lmm_system_t sys, lmm_variable_t var) xbt_swag_size(&(elem->constraint->disabled_element_set)); if (!nelements) make_constraint_inactive(sys, elem->constraint); - //Check if we can enable new variables going through the constraints where var was. else lmm_on_disabled_var(sys,elem->constraint); } - + + //Check if we can enable new variables going through the constraints where var was. + //Do it after removing all elements, so he first disabled variables get priority over those with smaller + //requirement + for (i = 0; i < var->cnsts_number; i++) { + elem = &var->cnsts[i]; + if(xbt_swag_size(&(elem->constraint->disabled_element_set))) + lmm_on_disabled_var(sys,elem->constraint); + } + var->cnsts_number = 0; + + lmm_check_concurrency(sys); + XBT_OUT(); } @@ -157,7 +184,7 @@ static void lmm_var_free(lmm_system_t sys, lmm_variable_t var) xbt_mallocator_release(sys->variable_mallocator, var); } -static XBT_INLINE void lmm_cnst_free(lmm_system_t sys, +static inline void lmm_cnst_free(lmm_system_t sys, lmm_constraint_t cnst) { make_constraint_inactive(sys, cnst); @@ -192,8 +219,14 @@ lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id, return cnst; } +int lmm_constraint_concurrency_limit_get(lmm_constraint_t cnst) +{ + return cnst->concurrency_limit; +} + void lmm_constraint_concurrency_limit_set(lmm_constraint_t cnst, int concurrency_limit) { + xbt_assert(concurrency_limit<0 || cnst->concurrency_maximum<=concurrency_limit,"New concurrency limit should be larger than observed concurrency maximum. Maybe you want to call lmm_constraint_concurrency_maximum_reset() to reset the maximum?"); cnst->concurrency_limit = concurrency_limit; } @@ -204,6 +237,7 @@ void lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst) int lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst) { + xbt_assert(cnst->concurrency_limit<0 || cnst->concurrency_maximum<=cnst->concurrency_limit,"Very bad: maximum observed concurrency is higher than limit. This is a bug of SURF, please report it."); return cnst->concurrency_maximum; } @@ -223,7 +257,7 @@ int lmm_constraint_sharing_policy(lmm_constraint_t cnst) * Apparently, this call was designed assuming that constraint would no more have elements in it. * If this is not the case, assertion will fail, and you need to add calls e.g. to lmm_shrink before effectively removing it. */ -XBT_INLINE void lmm_constraint_free(lmm_system_t sys, +inline void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst) { xbt_assert(!xbt_swag_size(&(cnst->active_element_set)),"Removing constraint but it still has active elements"); @@ -354,7 +388,7 @@ void lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst, lmm_update_modified_set(sys, var->cnsts[0].constraint); // will look up enabled_element_set of this constraint, and then each var in the enabled_element_set, and each var->cnsts[i]. if(xbt_swag_remove(elem, &(elem->constraint->enabled_element_set))) - lmm_decrease_concurrency(elem->constraint); + lmm_decrease_concurrency(elem); xbt_swag_remove(elem, &(elem->constraint->active_element_set)); elem->constraint = NULL; @@ -379,11 +413,24 @@ void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, { lmm_element_t elem = NULL; double weight; - int i; + int i,current_share; + sys->modified = 1; - if(var->weight>0 && lmm_concurrency_slack(cnst)==0){ + //Check if this variable already has an active element in this constraint + //If it does, substract it from the required slack + current_share=0; + if(var->concurrency_share>1){ + for( i=0; icnsts_number;i++){ + if(var->cnsts[i].constraint==cnst && xbt_swag_belongs(&var->cnsts[i],&(var->cnsts[i].constraint->enabled_element_set))) + current_share+=lmm_element_concurrency(&(var->cnsts[i])); + } + } + + //Check if we need to disable the variable + if(var->weight>0 && var->concurrency_share-current_share>lmm_concurrency_slack(cnst)) + { weight=var->weight; lmm_disable_var(sys,var); for (i = 0; i < var->cnsts_number; i++) @@ -404,7 +451,7 @@ void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, if (var->weight){ xbt_swag_insert_at_head(elem, &(elem->constraint->enabled_element_set)); - lmm_increase_concurrency(elem->constraint); + lmm_increase_concurrency(elem); } else xbt_swag_insert_at_tail(elem, &(elem->constraint->disabled_element_set)); @@ -425,20 +472,40 @@ 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,j; + double weight; sys->modified = 1; - + lmm_check_concurrency(sys); + //BEWARE: In case you have multiple elements in one constraint, this will always + //add value to the first element. for (i = 0; i < var->cnsts_number; i++) if (var->cnsts[i].constraint == cnst) break; if (i < var->cnsts_number) { + if (var->weight) + lmm_decrease_concurrency(&var->cnsts[i]); + if (cnst->sharing_policy) var->cnsts[i].value += value; else var->cnsts[i].value = MAX(var->cnsts[i].value, value); + + //We need to check that increasing value of the element does not cross the concurrency limit + if (var->weight){ + if(lmm_concurrency_slack(cnst)cnsts[i])){ + weight=var->weight; + lmm_disable_var(sys,var); + for (j = 0; j < var->cnsts_number; j++) + lmm_on_disabled_var(sys,var->cnsts[j].constraint); + var->staged_weight=weight; + xbt_assert(!var->weight); + } + lmm_increase_concurrency(&var->cnsts[i]); + } + lmm_update_modified_set(sys, cnst); } else lmm_expand(sys, cnst, var, value); @@ -544,7 +611,7 @@ void *lmm_variable_id(lmm_variable_t var) return var->id; } -static XBT_INLINE void saturated_constraint_set_update(double usage, +static inline void saturated_constraint_set_update(double usage, int cnst_light_num, dyn_light_t saturated_constraint_set, double *min_usage) @@ -566,7 +633,7 @@ static XBT_INLINE void saturated_constraint_set_update(double usage, } } -static XBT_INLINE void saturated_variable_set_update( +static inline void saturated_variable_set_update( s_lmm_constraint_light_t *cnst_light_tab, dyn_light_t saturated_constraint_set, lmm_system_t sys) @@ -683,9 +750,12 @@ void lmm_print(lmm_system_t sys) } XBT_DEBUG("%s", trace_buf); trace_buf[0] = '\000'; - xbt_assert(!double_positive(sum - cnst->bound, cnst->bound*sg_maxmin_precision), - "Incorrect value (%f is not smaller than %f): %g", - sum, cnst->bound, sum - cnst->bound); + xbt_assert(!double_positive(sum - cnst->bound, cnst->bound*sg_maxmin_precision), + "Incorrect value (%f is not smaller than %f): %g", + sum, cnst->bound, sum - cnst->bound); + //if(double_positive(sum - cnst->bound, cnst->bound*sg_maxmin_precision)) + //XBT_ERROR("Incorrect value (%f is not smaller than %f): %g",sum, cnst->bound, sum - cnst->bound); + } XBT_DEBUG("Variables"); @@ -773,7 +843,7 @@ void lmm_solve(lmm_system_t sys) sys->keep_track->push_back(*action); } } - XBT_DEBUG("Constraint '%d' usage: %f remaining: %f ", cnst->id_int, cnst->usage, cnst->remaining); + XBT_DEBUG("Constraint '%d' usage: %f remaining: %f concurrency: %i<=%i<=%i", cnst->id_int, cnst->usage, cnst->remaining,cnst->concurrency_current,cnst->concurrency_maximum,cnst->concurrency_limit); /* Saturated constraints update */ if(cnst->usage > 0) { @@ -823,7 +893,8 @@ void lmm_solve(lmm_system_t sys) if (min_bound < 0) { //If no variable could reach its bound, deal iteratively the constraints usage ( at worst one constraint is saturated at each cycle) var->value = min_usage / var->weight; - XBT_DEBUG("Setting %p (%d) value to %f\n", var, var->id_int, var->value); + // XBT_DEBUG("Setting %p (%d) value to %f\n", var, var->id_int, var->value); + XBT_DEBUG("Setting var (%d) value to %f\n", var->id_int, var->value); } else { //If there exist a variable that can reach its bound, only update it (and other with the same bound) for now. if (double_equals(min_bound, var->bound*var->weight, sg_maxmin_precision)){ @@ -853,8 +924,10 @@ void lmm_solve(lmm_system_t sys) if(!double_positive(cnst->usage,sg_maxmin_precision) || !double_positive(cnst->remaining,cnst->bound*sg_maxmin_precision)) { if (cnst->cnst_light) { int index = (cnst->cnst_light-cnst_light_tab); - XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p \t cnst_light_tab: %p usage: %f remaining: %f bound: %f ", - index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab, cnst->usage, cnst->remaining, cnst->bound); + XBT_DEBUG("index: %d \t cnst_light_num: %d \t || usage: %f remaining: %f bound: %f ", + index,cnst_light_num, cnst->usage, cnst->remaining, cnst->bound); + // XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p \t cnst_light_tab: %p usage: %f remaining: %f bound: %f ", + //index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab, cnst->usage, cnst->remaining, cnst->bound); cnst_light_tab[index]=cnst_light_tab[cnst_light_num-1]; cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index]; cnst_light_num--; @@ -924,6 +997,8 @@ void lmm_solve(lmm_system_t sys) lmm_print(sys); } + lmm_check_concurrency(sys); + xbt_free(saturated_constraint_set->data); xbt_free(saturated_constraint_set); xbt_free(cnst_light_tab); @@ -957,8 +1032,6 @@ void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, int lmm_concurrency_slack(lmm_constraint_t cnstr){ - xbt_assert(xbt_swag_size(&(cnstr->enabled_element_set))==cnstr->concurrency_current,"concurrency_current is not up to date!"); - //FIXME MARTIN: Replace by infinite value std::numeric_limits::(max)(), or something better within Simgrid? if(cnstr->concurrency_limit<0) return 666; @@ -1020,12 +1093,14 @@ void lmm_enable_var(lmm_system_t sys, lmm_variable_t var){ elem = &var->cnsts[i]; xbt_swag_remove(elem, &(elem->constraint->disabled_element_set)); xbt_swag_insert_at_head(elem, &(elem->constraint->enabled_element_set)); - lmm_increase_concurrency(elem->constraint); + lmm_increase_concurrency(elem); } if (var->cnsts_number) lmm_update_modified_set(sys, var->cnsts[0].constraint); - lmm_check_concurrency(sys); + //When used within lmm_on_disabled_var, we would get an assertion fail, because transiently there can be variables that are staged and could be activated. + //Anyway, caller functions all call lmm_check_concurrency() in the end. + // lmm_check_concurrency(sys); } void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){ @@ -1045,7 +1120,7 @@ void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){ xbt_swag_remove(elem, &(elem->constraint->active_element_set)); - lmm_decrease_concurrency(elem->constraint); + lmm_decrease_concurrency(elem); } var->weight=0.0; @@ -1064,28 +1139,43 @@ void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){ void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr){ lmm_element_t elem; + lmm_element_t nextelem; + int numelem; + if(cnstr->concurrency_limit<0) return; - - int concurrency=cnstr->concurrency_current; - xbt_swag_foreach(elem, &(cnstr->disabled_element_set)) { + + numelem=xbt_swag_size(&(cnstr->disabled_element_set)); + if(!numelem) + return; + + elem= (lmm_element_t) xbt_swag_getFirst(&(cnstr->disabled_element_set)); + + //Cannot use xbt_swag_foreach, because lmm_enable_var will modify disabled_element_set.. within the loop + while(numelem-- && elem ){ + + nextelem = (lmm_element_t) xbt_swag_getNext(elem, cnstr->disabled_element_set.offset); if (elem->variable->staged_weight>0 ) { - //Found a staged variable - //TODOLATER: Add random timing function to model reservation protocol fuzziness? Then how to make sure that staged variables will eventually be called? - if(lmm_can_enable_var(elem->variable)){ - lmm_enable_var(sys,elem->variable); - concurrency++; - } + //Found a staged variable + //TODOLATER: Add random timing function to model reservation protocol fuzziness? Then how to make sure that staged variables will eventually be called? + if(lmm_can_enable_var(elem->variable)){ + lmm_enable_var(sys,elem->variable); + } } - xbt_assert(concurrency<=cnstr->concurrency_limit,"Concurrency overflow!"); - if(concurrency==cnstr->concurrency_limit) + xbt_assert(cnstr->concurrency_current<=cnstr->concurrency_limit,"Concurrency overflow!"); + if(cnstr->concurrency_current==cnstr->concurrency_limit) break; + + elem = nextelem; } - lmm_check_concurrency(sys); + //We could get an assertion fail, because transiently there can be variables that are staged and could be activated. + //And we need to go through all constraints of the disabled var before getting back a coherent state. + //Anyway, caller functions all call lmm_check_concurrency() in the end. + // lmm_check_concurrency(sys); } @@ -1113,8 +1203,8 @@ void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var, if (enabling_var){ var->staged_weight = weight; minslack=lmm_cnstrs_min_concurrency_slack(var); - if(minslack==0){ - XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with weight %f", minslack, weight); + if(minslackconcurrency_share){ + XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with weight %f and concurrency share %i", minslack, weight, var->concurrency_share); return; } XBT_DEBUG("Enabling var with min concurrency slack %i", minslack); @@ -1151,13 +1241,13 @@ int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst) return xbt_swag_belongs(cnst, &(sys->active_constraint_set)); } -XBT_INLINE lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t +inline lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t sys) { return (lmm_constraint_t)xbt_swag_getFirst(&(sys->active_constraint_set)); } -XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t +inline lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys, lmm_constraint_t cnst) @@ -1165,14 +1255,6 @@ XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t return (lmm_constraint_t)xbt_swag_getNext(cnst, (sys->active_constraint_set).offset); } -#ifdef HAVE_LATENCY_BOUND_TRACKING -XBT_PUBLIC(int) lmm_is_variable_limited_by_latency(lmm_variable_t var) -{ - return (double_equals(var->bound, var->value, var->bound*sg_maxmin_precision)); -} -#endif - - /** \brief Update the constraint set propagating recursively to * other constraints so the system should not be entirely computed. * @@ -1235,7 +1317,7 @@ static void lmm_remove_all_modified_set(lmm_system_t sys) void *_var; xbt_swag_foreach(_var, &sys->variable_set) ((lmm_variable_t)_var)->visited = 0; - } + } xbt_swag_reset(&sys->modified_constraint_set); } @@ -1268,34 +1350,58 @@ double lmm_constraint_get_usage(lmm_constraint_t cnst) { void lmm_check_concurrency(lmm_system_t sys){ void* _cnst; void* _elem; + void* _var; lmm_element_t elem; lmm_constraint_t cnst; + lmm_variable_t var; int concurrency; - + int i,belong_to_enabled,belong_to_disabled,belong_to_active; + //These checks are very expensive, so do them only if we want to debug SURF LMM if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { xbt_swag_foreach(_cnst, &(sys->constraint_set)) { cnst = (lmm_constraint_t) _cnst; concurrency=0; - xbt_swag_foreach(_elem, &(cnst->enabled_element_set)) { - elem = (lmm_element_t)_elem; - xbt_assert(elem->variable->weight > 0); - concurrency++; + elem = (lmm_element_t)_elem; + xbt_assert(elem->variable->weight > 0); + concurrency+=lmm_element_concurrency(elem); } - + xbt_swag_foreach(_elem, &(cnst->disabled_element_set)) { elem = (lmm_element_t)_elem; - //We should have staged variables only if conccurency is reached in some constraint + //We should have staged variables only if concurrency is reached in some constraint xbt_assert(cnst->concurrency_limit<0 || elem->variable->staged_weight==0 || lmm_cnstrs_min_concurrency_slack(elem->variable) < elem->variable->concurrency_share,"should not have staged variable!"); } xbt_assert(cnst->concurrency_limit<0 || cnst->concurrency_limit >= concurrency,"concurrency check failed!"); xbt_assert(cnst->concurrency_current == concurrency, "concurrency_current is out-of-date!"); - xbt_assert(cnst->concurrency_current == xbt_swag_size(&(cnst->enabled_element_set)), "concurrency_current is out-of-date (2) !"); - } + + //Check that for each variable, all corresponding elements are in the same state (i.e. same element sets) + xbt_swag_foreach(_var, &(sys->variable_set)) { + var= (lmm_variable_t) _var; + + if(!var->cnsts_number) + continue; + + elem = &var->cnsts[0]; + belong_to_enabled=xbt_swag_belongs(elem,&(elem->constraint->enabled_element_set)); + belong_to_disabled=xbt_swag_belongs(elem,&(elem->constraint->disabled_element_set)); + belong_to_active=xbt_swag_belongs(elem,&(elem->constraint->active_element_set)); + + for (i = 1; i < var->cnsts_number; i++) { + elem = &var->cnsts[i]; + xbt_assert(belong_to_enabled==xbt_swag_belongs(elem,&(elem->constraint->enabled_element_set)), + "Variable inconsistency (1): enabled_element_set"); + xbt_assert(belong_to_disabled==xbt_swag_belongs(elem,&(elem->constraint->disabled_element_set)), + "Variable inconsistency (2): disabled_element_set"); + xbt_assert(belong_to_active==xbt_swag_belongs(elem,&(elem->constraint->active_element_set)), + "Variable inconsistency (3): active_element_set"); + } + + } } }