-/* Copyright (c) 2004-2013. The SimGrid Team.
+/* Copyright (c) 2004-2015. The SimGrid Team.
* All rights reserved. */
/* This program is free software; you can redistribute it and/or modify it
* under the terms of the license (GNU LGPL) which comes with this package. */
-
#include "xbt/sysdep.h"
#include "xbt/log.h"
#include "xbt/mallocator.h"
int size;
} s_dyn_light_t, *dyn_light_t;
-XBT_EXPORT_NO_IMPORT(double) sg_maxmin_precision = 0.00001;
+double sg_maxmin_precision = 0.00001;
+double sg_surf_precision = 0.00001;
static void *lmm_variable_mallocator_new_f(void);
static void lmm_variable_mallocator_free_f(void *var);
l->selective_update_active = selective_update;
l->visited_counter = 1;
- XBT_DEBUG("Setting selective_update_active flag to %d\n",
+ XBT_DEBUG("Setting selective_update_active flag to %d",
l->selective_update_active);
xbt_swag_init(&(l->variable_set),
cnst->bound = bound_value;
cnst->usage = 0;
- cnst->shared = 1;
+ cnst->sharing_policy = 1; /* FIXME: don't hardcode the value */
insert_constraint(sys, cnst);
return cnst;
void lmm_constraint_shared(lmm_constraint_t cnst)
{
- cnst->shared = 0;
+ cnst->sharing_policy = 0;
}
-int lmm_constraint_is_shared(lmm_constraint_t cnst)
+/** Return true if the constraint is shared, and false if it's FATPIPE */
+int lmm_constraint_sharing_policy(lmm_constraint_t cnst)
{
- return (cnst->shared);
+ return (cnst->sharing_policy);
}
XBT_INLINE void lmm_constraint_free(lmm_system_t sys,
return (var->value);
}
-XBT_INLINE double lmm_variable_getbound(lmm_variable_t var)
+double lmm_variable_getbound(lmm_variable_t var)
{
return (var->bound);
}
sys->modified = 1;
- XBT_DEBUG("remove elem(value %lf, cnst %p, var %p) in var %p",
+ XBT_DEBUG("remove elem(value %f, cnst %p, var %p) in var %p",
elem->value, elem->constraint, elem->variable, var);
break;
if (i < var->cnsts_number) {
- if (cnst->shared)
+ if (cnst->sharing_policy)
var->cnsts[i].value += value;
else
var->cnsts[i].value = MAX(var->cnsts[i].value, value);
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;
-
- 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;
- sys->modified = 1;
- lmm_update_modified_set(sys, cnst);
- } else
- DIE_IMPOSSIBLE;
-}
-
lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t /*sys*/,
lmm_variable_t var,
int num)
return NULL;
}
+//if we modify the swag between calls, normal version may loop forever
+//this safe version ensures that we browse the swag elements only once
+lmm_variable_t lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/,
+ lmm_constraint_t cnst,
+ lmm_element_t * elem,
+ lmm_element_t * nextelem,
+ int * numelem)
+{
+ if (!(*elem)){
+ *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->element_set));
+ *numelem = xbt_swag_size(&(cnst->element_set))-1;
+ }else{
+ *elem = *nextelem;
+ if(*numelem>0){
+ (*numelem) --;
+ }else
+ return NULL;
+ }
+ if (*elem){
+ *nextelem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->element_set.offset);
+ return (*elem)->variable;
+ }else
+ return NULL;
+}
+
void *lmm_constraint_id(lmm_constraint_t cnst)
{
return cnst->id;
dyn_light_t saturated_constraint_set,
lmm_system_t sys)
{
+ /* Add active variables (i.e. variables that need to be set) from the set of constraints to saturate (cnst_light_tab)*/
lmm_constraint_light_t cnst = NULL;
void *_elem;
lmm_element_t elem = NULL;
trace_buf = (char*)
xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
strcat(trace_buf, print_buf);
- sprintf(print_buf, "%s(",(cnst->shared)?"":"max");
+ sprintf(print_buf, "%s(",(cnst->sharing_policy)?"":"max");
trace_buf = (char*)
xbt_realloc(trace_buf,
strlen(trace_buf) + strlen(print_buf) + 1);
xbt_swag_foreach(_elem, elem_list) {
elem = (lmm_element_t)_elem;
sprintf(print_buf, "%f.'%d'(%f) %s ", elem->value,
- elem->variable->id_int, elem->variable->value,(cnst->shared)?"+":",");
+ elem->variable->id_int, elem->variable->value,(cnst->sharing_policy)?"+":",");
trace_buf = (char*)
xbt_realloc(trace_buf,
strlen(trace_buf) + strlen(print_buf) + 1);
strcat(trace_buf, print_buf);
- if(cnst->shared)
- sum += elem->value * elem->variable->value;
+ if(cnst->sharing_policy)
+ sum += elem->value * elem->variable->value;
else
- sum = MAX(sum,elem->value * elem->variable->value);
+ sum = MAX(sum,elem->value * elem->variable->value);
}
sprintf(print_buf, "0) <= %f ('%d')", cnst->bound, cnst->id_int);
trace_buf = (char*)
xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
strcat(trace_buf, print_buf);
- if (!cnst->shared) {
+ if (!cnst->sharing_policy) {
sprintf(print_buf, " [MAX-Constraint]");
trace_buf = (char*)
xbt_realloc(trace_buf,
}
XBT_DEBUG("%s", trace_buf);
trace_buf[0] = '\000';
- xbt_assert(!double_positive(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 (var->bound > 0) {
XBT_DEBUG("'%d'(%f) : %f (<=%f)", var->id_int, var->weight, var->value,
var->bound);
- xbt_assert(!double_positive(var->value - var->bound),
+ xbt_assert(!double_positive(var->value - var->bound, var->bound*sg_maxmin_precision),
"Incorrect value (%f is not smaller than %f",
var->value, var->bound);
} else {
XBT_IN("(sys=%p)", sys);
/*
- * Compute Usage and store the variables that reach the maximum.
+ * Compute Usage and store the variables that reach the maximum. If selective_update_active is true, only constraints that changed are considered. Otherwise all constraints with active actions are considered.
*/
cnst_list =
sys->
&(sys->active_constraint_set);
XBT_DEBUG("Active constraints : %d", xbt_swag_size(cnst_list));
- /* Init: Only modified code portions */
+ /* Init: Only modified code portions: reset the value of active variables */
xbt_swag_foreach(_cnst, cnst_list) {
cnst = (lmm_constraint_t)_cnst;
elem_list = &(cnst->element_set);
xbt_swag_foreach_safe(_cnst, _cnst_next, cnst_list) {
cnst = (lmm_constraint_t)_cnst;
- /* INIT */
+ /* INIT: Collect constraints that actually need to be saturated (i.e remaining and usage are strictly positive) into cnst_light_tab. */
cnst->remaining = cnst->bound;
- if (cnst->remaining == 0)
+ if (!double_positive(cnst->remaining, cnst->bound*sg_maxmin_precision))
continue;
cnst->usage = 0;
elem_list = &(cnst->element_set);
if (elem->variable->weight <= 0)
break;
if ((elem->value > 0)) {
- if (cnst->shared)
+ if (cnst->sharing_policy)
cnst->usage += elem->value / elem->variable->weight;
else if (cnst->usage < elem->value / elem->variable->weight)
cnst->usage = elem->value / elem->variable->weight;
make_elem_active(elem);
- ActionLmmPtr action = static_cast<ActionLmmPtr>(elem->variable->id);
+ simgrid::surf::Action *action = static_cast<simgrid::surf::Action*>(elem->variable->id);
if (sys->keep_track && !action->is_linked())
sys->keep_track->push_back(*action);
}
}
- XBT_DEBUG("Constraint Usage '%d' : %f", cnst->id_int, cnst->usage);
+ XBT_DEBUG("Constraint '%d' usage: %f remaining: %f ", cnst->id_int, cnst->usage, cnst->remaining);
/* Saturated constraints update */
if(cnst->usage > 0) {
cnst_light_tab[cnst_light_num].remaining_over_usage = cnst->remaining / cnst->usage;
saturated_constraint_set_update(cnst_light_tab[cnst_light_num].remaining_over_usage,
cnst_light_num, saturated_constraint_set, &min_usage);
+ xbt_assert(cnst->active_element_set.count>0, "There is no sense adding a constraint that has no active element!" );
cnst_light_num++;
}
}
var = (lmm_variable_t)_var;
if (var->weight <= 0.0)
DIE_IMPOSSIBLE;
- /* First check if some of these variables have reach their upper
- bound and update min_usage accordingly. */
+ /* First check if some of these variables could reach their upper
+ bound and update min_bound accordingly. */
XBT_DEBUG
("var=%d, var->bound=%f, var->weight=%f, min_usage=%f, var->bound*var->weight=%f",
var->id_int, var->bound, var->weight, min_usage,
var->bound * var->weight);
if ((var->bound > 0) && (var->bound * var->weight < min_usage)) {
if (min_bound < 0)
- min_bound = var->bound;
+ min_bound = var->bound*var->weight;
else
- min_bound = MIN(min_bound, var->bound);
+ min_bound = MIN(min_bound, (var->bound*var->weight));
XBT_DEBUG("Updated min_bound=%f", min_bound);
}
}
int i;
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);
} else {
- if (min_bound == var->bound)
+ //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)){
var->value = var->bound;
+ XBT_DEBUG("Setting %p (%d) value to %f\n", var, var->id_int, var->value);
+ }
else {
+ // Variables which bound is different are not considered for this cycle, but they will be afterwards.
+ XBT_DEBUG("Do not consider %p (%d) \n", var, var->id_int);
xbt_swag_remove(var, var_list);
continue;
}
min_usage, var->id_int, var->weight, var->id_int, var->value);
- /* Update usage */
-
+ /* Update the usage of contraints where this variable is involved */
for (i = 0; i < var->cnsts_number; i++) {
elem = &var->cnsts[i];
cnst = elem->constraint;
- if (cnst->shared) {
- double_update(&(cnst->remaining), elem->value * var->value);
- double_update(&(cnst->usage), elem->value / var->weight);
- if(cnst->usage<=0 || cnst->remaining<=0) {
+ if (cnst->sharing_policy) {
+ //Remember: shared constraints require that sum(elem->value * var->value) < cnst->bound
+ double_update(&(cnst->remaining), elem->value * var->value, cnst->bound*sg_maxmin_precision);
+ double_update(&(cnst->usage), elem->value / var->weight, sg_maxmin_precision);
+ //If the constraint is saturated, remove it from the set of active constraints (light_tab)
+ 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 ",
- index,cnst_light_num, cnst, 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);
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--;
}
make_elem_inactive(elem);
} else {
+ //Remember: non-shared constraints only require that max(elem->value * var->value) < cnst->bound
cnst->usage = 0.0;
make_elem_inactive(elem);
elem_list = &(cnst->element_set);
xbt_swag_foreach(_elem, elem_list) {
elem = (lmm_element_t)_elem;
- if (elem->variable->weight <= 0 || elem->variable->value > 0)
- break;
+ if (elem->variable->weight <= 0) break; //Found an inactive variable -> no more active variables
+ if (elem->variable->value > 0) continue;
if (elem->value > 0)
cnst->usage = MAX(cnst->usage, elem->value / elem->variable->weight);
}
- if (cnst->usage<=0 || cnst->remaining<=0) {
+ //If the constraint is saturated, remove it from the set of active constraints (light_tab)
+ 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 ",
- index,cnst_light_num, cnst, 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);
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--;
}
} else {
cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
+ xbt_assert(cnst->active_element_set.count>0, "Should not keep a maximum constraint that has no active element! You want to check the maxmin precision and possible rounding effects." );
}
}
}
min_bound = -1;
saturated_constraint_set->pos = 0;
int pos;
- for(pos=0; pos<cnst_light_num; pos++)
+ for(pos=0; pos<cnst_light_num; pos++){
+ xbt_assert(cnst_light_tab[pos].cnst->active_element_set.count>0, "Cannot saturate more a constraint that has no active element! You may want to change the maxmin precision (--cfg=maxmin/precision:<new_value>) because of possible rounding effects.\n\tFor the record, the usage of this constraint is %g while the maxmin precision to which it is compared is %g.\n\tThe usage of the previous constraint is %g.", cnst_light_tab[pos].cnst->usage, sg_maxmin_precision, cnst_light_tab[pos-1].cnst->usage);
saturated_constraint_set_update(
cnst_light_tab[pos].remaining_over_usage,
pos,
saturated_constraint_set,
&min_usage);
+ }
saturated_variable_set_update( cnst_light_tab,
saturated_constraint_set,
#ifdef HAVE_LATENCY_BOUND_TRACKING
XBT_INLINE int lmm_is_variable_limited_by_latency(lmm_variable_t var)
{
- return (double_equals(var->bound, var->value));
+ return (double_equals(var->bound, var->value, var->bound*sg_maxmin_precision));
}
#endif
if (elem->variable->weight <= 0)
break;
if ((elem->value > 0)) {
- if (cnst->shared)
+ if (cnst->sharing_policy)
usage += elem->value * elem->variable->value;
else if (usage < elem->value * elem->variable->value)
usage = elem->value * elem->variable->value;