src/surf/fair_bottleneck.cpp

   1 /* Copyright (c) 2007, 2008, 2009, 2010. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 #include "xbt/sysdep.h"
   8 #include "xbt/log.h"
   9 #include "solver.hpp"
  10 #include <stdlib.h>
  11 #include <math.h>
  12
  13 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_maxmin);
  14 #define SHOW_EXPR_G(expr) XBT_DEBUG(#expr " = %g",expr);
  15 #define SHOW_EXPR_D(expr) XBT_DEBUG(#expr " = %d",expr);
  16 #define SHOW_EXPR_P(expr) XBT_DEBUG(#expr " = %p",expr);
  17
  18 void bottleneck_solve(lmm_system_t sys)
  19 {
  20   lmm_variable_t var_next = NULL;
  21   lmm_constraint_t cnst = NULL;
  22   //s_lmm_constraint_t s_cnst;
  23   lmm_constraint_t cnst_next = NULL;
  24   xbt_swag_t cnst_list = NULL;
  25
  26   xbt_swag_t elem_list = NULL;
  27   int i;
  28
  29   static s_xbt_swag_t cnst_to_update;
  30   vector<ConstraintPtr> cnstToUpdate;
  31
  32   if (!(lmm_system_modified(sys)))
  33     return;
  34
  35   /* Init */
  36
  37   lmm_variable_t var = NULL;
  38   lmm_element_t elem = NULL;
  39   std::vector<VariablePtr> *varList;
  40   std::vector<VariablePtr>::iterator varIt;
  41   std::vector<ElementPtr> *elemList;
  42   std::vector<ElementPtr>::iterator elemIt;
  43   std::vector<ConstraintPtr> *cnstList;
  44   std::vector<ConstraintPtr>::iterator cnstIt;
  45
  46   varList = &(sys->m_variableSet);
  47   XBT_DEBUG("Variable set : %d", varList->size());
  48   for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) {
  49     int nb = 0;
  50     var = *varIt;
  51     var->m_value = 0.0;
  52     XBT_DEBUG("Handling variable %p", var);
  53     sys->m_saturatedVariableSet.push_back(var);
  54     for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt)
  55       if ((*elemIt)->m_value == 0.0)
  56         nb++;
  57     if ((nb == var->getNumberOfCnst()) && (var->m_weight > 0.0)) {
  58       XBT_DEBUG("Err, finally, there is no need to take care of variable %p",
  59                var);
  60       sys->m_saturatedVariableSet.erase(std::find(sys->m_saturatedVariableSet.begin(), sys->m_saturatedVariableSet.end(), var));
  61       var->m_value = 1.0;
  62     }
  63     if (var->m_weight <= 0.0) {
  64       XBT_DEBUG("Err, finally, there is no need to take care of variable %p",
  65              var);
  66       sys->m_saturatedVariableSet.erase(std::find(sys->m_saturatedVariableSet.begin(), sys->m_saturatedVariableSet.end(), var));
  67     }
  68   }
  69   varList = &(sys->m_saturatedVariableSet);
  70   cnstList = &(sys->m_activeConstraintSet);
  71   XBT_DEBUG("Active constraints : %d", cnstList->size());
  72   sys->m_saturatedConstraintSet.insert(sys->m_saturatedConstraintSet.end(), cnstList->begin(), cnstList->end());
  73   cnstList = &(sys->m_saturatedConstraintSet);
  74   for(cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) {
  75     (*cnstIt)->m_remaining = (*cnstIt)->m_bound;
  76     (*cnstIt)->m_usage = 0.0;
  77   }
  78   XBT_DEBUG("Fair bottleneck Initialized");
  79
  80   /*
  81    * Compute Usage and store the variables that reach the maximum.
  82    */
  83
  84   do {
  85     if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
  86       XBT_DEBUG("Fair bottleneck done");
  87       lmm_print(sys);
  88     }
  89     XBT_DEBUG("******* Constraints to process: %d *******",
  90            cnstList->size());
  91     for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end();){
  92       cnst = *cnstIt;
  93       int nb = 0;
  94       XBT_DEBUG("Processing cnst %p ", cnst);
  95       elemList = &(cnst->m_elementSet);
  96       cnst->m_usage = 0.0;
  97       for(elemIt=elemList->begin(); elemIt!=elemList->end(); elemIt++) {
  98         if (elem->p_variable->m_weight <= 0)
  99           break;
 100         if ((elem->m_value > 0)
 101             && std::find(varList->begin(), varList->end(), elem->p_variable)!=varList->end());
 102           nb++;
 103       }
 104       XBT_DEBUG("\tThere are %d variables", nb);
 105       if (nb > 0 && !cnst->m_shared)
 106         nb = 1;
 107       if (!nb) {
 108         cnst->m_remaining = 0.0;
 109         cnst->m_usage = cnst->m_remaining;
 110         cnstList->erase(std::find(cnstList->begin(), cnstList->end(), *cnstIt));
 111         continue;
 112       }
 113       cnst->m_usage = cnst->m_remaining / nb;
 114       XBT_DEBUG("\tConstraint Usage %p : %f with %d variables", cnst,
 115              cnst->m_usage, nb);
 116       ++cnstIt;
 117     }
 118
 119     for (varIt=varList->begin(); varIt!=varList->end();){
 120       var = *varIt;
 121       double minInc =
 122           var->m_cnsts.front()->p_constraint->m_usage / var->m_cnsts.front()->m_value;
 123       for (elemIt=++var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) {
 124         elem = (*elemIt);
 125         minInc = MIN(minInc, elem->p_constraint->m_usage / elem->m_value);
 126       }
 127       if (var->m_bound > 0)
 128         minInc = MIN(minInc, var->m_bound - var->m_value);
 129       var->m_mu = minInc;
 130       XBT_DEBUG("Updating variable %p maximum increment: %g", var, var->m_mu);
 131       var->m_value += var->m_mu;
 132       if (var->m_value == var->m_bound) {
 133         varList->erase(std::find(varList->begin(), varList->end(), var));
 134       } else
 135         ++varIt;
 136     }
 137
 138     for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end();) {
 139       cnst = *cnstIt;
 140       XBT_DEBUG("Updating cnst %p ", cnst);
 141       elemList = &(cnst->m_elementSet);
 142       for (elemIt=elemList->begin(); elemIt!=elemList->end();++elemIt) {
 143         elem = *elemIt;
 144         if (elem->p_variable->m_weight <= 0)
 145           break;
 146         if (cnst->m_shared) {
 147           XBT_DEBUG("\tUpdate constraint %p (%g) with variable %p by %g",
 148                  cnst, cnst->m_remaining, elem->p_variable,
 149                  elem->p_variable->m_mu);
 150           double_update(&(cnst->m_remaining),
 151                         elem->m_value * elem->p_variable->m_mu);
 152         } else {
 153           XBT_DEBUG
 154               ("\tNon-Shared variable. Update constraint usage of %p (%g) with variable %p by %g",
 155                cnst, cnst->m_usage, elem->p_variable, elem->p_variable->m_mu);
 156           cnst->m_usage = MIN(cnst->m_usage, elem->m_value * elem->p_variable->m_mu);
 157         }
 158       }
 159
 160       if (!cnst->m_shared) {
 161         XBT_DEBUG("\tUpdate constraint %p (%g) by %g",
 162                cnst, cnst->m_remaining, cnst->m_usage);
 163
 164         double_update(&(cnst->m_remaining), cnst->m_usage);
 165       }
 166
 167       XBT_DEBUG("\tRemaining for %p : %g", cnst, cnst->m_remaining);
 168       if (cnst->m_remaining == 0.0) {
 169         XBT_DEBUG("\tGet rid of constraint %p", cnst);
 170
 171         cnstList->erase(std::find(cnstList->begin(), cnstList->end(), cnst));
 172
 173         for (elemIt=elemList->begin(); elemIt!=elemList->end();++elemIt) {
 174           if (elem->p_variable->m_weight <= 0)
 175             break;
 176           if (elem->m_value > 0) {
 177             XBT_DEBUG("\t\tGet rid of variable %p", elem->p_variable);
 178             varList->erase(std::find(varList->begin(), varList->end(), elem->p_variable));
 179           }
 180         }
 181       } else
 182         ++cnstIt;
 183     }
 184   } while (!varList->empty());
 185
 186   cnstList->clear();
 187   sys->m_modified = 0;
 188   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
 189     XBT_DEBUG("Fair bottleneck done");
 190     sys->print();
 191   }
 192 }