X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/a21681e5aca1a37efb2e9001e5055dec94c5de41..89edccc4eb98274e36279f5940ce8b4a0e887f4b:/src/surf/maxmin.cpp

diff --git a/src/surf/maxmin.cpp b/src/surf/maxmin.cpp
index 876fa33d9c..7a42307469 100644
--- a/src/surf/maxmin.cpp
+++ b/src/surf/maxmin.cpp
@@ -1,10 +1,9 @@
-/* Copyright (c) 2004-2013. The SimGrid Team.
+/* Copyright (c) 2004-2014. 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"
@@ -22,6 +21,7 @@ typedef struct s_dyn_light {
 } s_dyn_light_t, *dyn_light_t;
 
 XBT_EXPORT_NO_IMPORT(double) sg_maxmin_precision = 0.00001;
+XBT_EXPORT_NO_IMPORT(double) sg_surf_precision   = 0.00001;
 
 static void *lmm_variable_mallocator_new_f(void);
 static void lmm_variable_mallocator_free_f(void *var);
@@ -253,7 +253,7 @@ double lmm_variable_getvalue(lmm_variable_t var)
   return (var->value);
 }
 
-XBT_INLINE double lmm_variable_getbound(lmm_variable_t var)
+double lmm_variable_getbound(lmm_variable_t var)
 {
   return (var->bound);
 }
@@ -307,7 +307,7 @@ void lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
 
   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);
 
 
@@ -391,23 +391,6 @@ void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
     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)
@@ -485,6 +468,7 @@ static XBT_INLINE void saturated_variable_set_update(
     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;
@@ -579,7 +563,7 @@ void lmm_print(lmm_system_t sys)
     }
     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);
   }
@@ -591,7 +575,7 @@ void lmm_print(lmm_system_t sys)
     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 {
@@ -620,7 +604,7 @@ void lmm_solve(lmm_system_t sys)
   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->
@@ -628,7 +612,7 @@ void lmm_solve(lmm_system_t 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);
@@ -649,9 +633,9 @@ void lmm_solve(lmm_system_t sys)
 
   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);
@@ -667,12 +651,12 @@ void lmm_solve(lmm_system_t sys)
           cnst->usage = elem->value / elem->variable->weight;
 
         make_elem_active(elem);
-        ActionLmmPtr action = static_cast<ActionLmmPtr>(elem->variable->id);
+        ActionPtr action = static_cast<ActionPtr>(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) {
@@ -681,6 +665,7 @@ void lmm_solve(lmm_system_t sys)
       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++;
     }
   }
@@ -699,17 +684,17 @@ void lmm_solve(lmm_system_t sys)
       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);
       }
     }
@@ -719,11 +704,18 @@ void lmm_solve(lmm_system_t sys)
       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;
         }
@@ -732,19 +724,20 @@ void lmm_solve(lmm_system_t sys)
              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) {
+	  //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--;
@@ -755,21 +748,23 @@ void lmm_solve(lmm_system_t sys)
           }
           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--;
@@ -777,6 +772,7 @@ void lmm_solve(lmm_system_t sys)
             }
           } 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." );
           }
         }
       }
@@ -788,12 +784,14 @@ void lmm_solve(lmm_system_t sys)
     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,
@@ -924,7 +922,7 @@ XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t
 #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