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!");
}
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));
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();
}
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;
}
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;
}
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;
{
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; i<var->cnsts_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++)
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));
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)<lmm_element_concurrency(&var->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);
}
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");
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)){
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--;
lmm_print(sys);
}
+ lmm_check_concurrency(sys);
+
xbt_free(saturated_constraint_set->data);
xbt_free(saturated_constraint_set);
xbt_free(cnst_light_tab);
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<int>::(max)(), or something better within Simgrid?
if(cnstr->concurrency_limit<0)
return 666;
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){
xbt_swag_remove(elem, &(elem->constraint->active_element_set));
- lmm_decrease_concurrency(elem->constraint);
+ lmm_decrease_concurrency(elem);
}
var->weight=0.0;
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);
}
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(minslack<var->concurrency_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);
void *_var;
xbt_swag_foreach(_var, &sys->variable_set)
((lmm_variable_t)_var)->visited = 0;
- }
+ }
xbt_swag_reset(&sys->modified_constraint_set);
}
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");
+ }
+
+ }
}
}
