src/kernel/lmm/fair_bottleneck.cpp

   1 /* Copyright (c) 2007-2018. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include "src/kernel/lmm/maxmin.hpp"
   7 #include "xbt/log.h"
   8 #include "xbt/sysdep.h"
   9 #include <algorithm>
  10 #include <cfloat>
  11 #include <cmath>
  12 #include <cstdlib>
  13 #include <xbt/utility.hpp>
  14
  15 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_maxmin);
  16 #define SHOW_EXPR_G(expr) XBT_DEBUG(#expr " = %g", expr);
  17 #define SHOW_EXPR_D(expr) XBT_DEBUG(#expr " = %d", expr);
  18 #define SHOW_EXPR_P(expr) XBT_DEBUG(#expr " = %p", expr);
  19
  20 void simgrid::kernel::lmm::bottleneck_solve(lmm::System* sys)
  21 {
  22   if (not sys->modified)
  23     return;
  24
  25   XBT_DEBUG("Variable set : %zu", sys->variable_set.size());
  26   for (Variable& var : sys->variable_set) {
  27     var.value = 0.0;
  28     XBT_DEBUG("Handling variable %p", &var);
  29     if (var.sharing_weight > 0.0 && std::find_if(begin(var.cnsts), end(var.cnsts), [](Element const& x) {
  30                                       return x.consumption_weight != 0.0;
  31                                     }) != end(var.cnsts)) {
  32       sys->saturated_variable_set.push_back(var);
  33     } else {
  34       XBT_DEBUG("Err, finally, there is no need to take care of variable %p", &var);
  35       if (var.sharing_weight > 0.0)
  36         var.value = 1.0;
  37     }
  38   }
  39
  40   XBT_DEBUG("Active constraints : %zu", sys->active_constraint_set.size());
  41   for (Constraint& cnst : sys->active_constraint_set) {
  42     sys->saturated_constraint_set.push_back(cnst);
  43   }
  44   for (Constraint& cnst : sys->saturated_constraint_set) {
  45     cnst.remaining = cnst.bound;
  46     cnst.usage     = 0.0;
  47   }
  48
  49   XBT_DEBUG("Fair bottleneck Initialized");
  50
  51   /*
  52    * Compute Usage and store the variables that reach the maximum.
  53    */
  54   auto& var_list  = sys->saturated_variable_set;
  55   auto& cnst_list = sys->saturated_constraint_set;
  56   do {
  57     if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
  58       XBT_DEBUG("Fair bottleneck done");
  59       sys->print();
  60     }
  61     XBT_DEBUG("******* Constraints to process: %zu *******", cnst_list.size());
  62     for (auto iter = std::begin(cnst_list); iter != std::end(cnst_list);) {
  63       Constraint& cnst = *iter;
  64       int nb = 0;
  65       XBT_DEBUG("Processing cnst %p ", &cnst);
  66       cnst.usage = 0.0;
  67       for (Element& elem : cnst.enabled_element_set) {
  68         xbt_assert(elem.variable->sharing_weight > 0);
  69         if (elem.consumption_weight > 0 && elem.variable->saturated_variable_set_hook.is_linked())
  70           nb++;
  71       }
  72       XBT_DEBUG("\tThere are %d variables", nb);
  73       if (nb > 0 && not cnst.sharing_policy)
  74         nb = 1;
  75       if (nb == 0) {
  76         cnst.remaining = 0.0;
  77         cnst.usage     = 0.0;
  78         iter           = cnst_list.erase(iter);
  79       } else {
  80         cnst.usage = cnst.remaining / nb;
  81         XBT_DEBUG("\tConstraint Usage %p : %f with %d variables", &cnst, cnst.usage, nb);
  82         iter++;
  83       }
  84     }
  85
  86     for (auto iter = std::begin(var_list); iter != std::end(var_list);) {
  87       Variable& var  = *iter;
  88       double min_inc = DBL_MAX;
  89       for (Element const& elm : var.cnsts) {
  90         if (elm.consumption_weight > 0)
  91           min_inc = std::min(min_inc, elm.constraint->usage / elm.consumption_weight);
  92       }
  93       if (var.bound > 0)
  94         min_inc = std::min(min_inc, var.bound - var.value);
  95       var.mu    = min_inc;
  96       XBT_DEBUG("Updating variable %p maximum increment: %g", &var, var.mu);
  97       var.value += var.mu;
  98       if (var.value == var.bound)
  99         iter = var_list.erase(iter);
 100       else
 101         iter++;
 102     }
 103
 104     for (auto iter = std::begin(cnst_list); iter != std::end(cnst_list);) {
 105       Constraint& cnst = *iter;
 106       XBT_DEBUG("Updating cnst %p ", &cnst);
 107       if (cnst.sharing_policy) {
 108         for (Element& elem : cnst.enabled_element_set) {
 109           xbt_assert(elem.variable->sharing_weight > 0);
 110           XBT_DEBUG("\tUpdate constraint %p (%g) with variable %p by %g", &cnst, cnst.remaining, elem.variable,
 111                     elem.variable->mu);
 112           double_update(&cnst.remaining, elem.consumption_weight * elem.variable->mu, sg_maxmin_precision);
 113         }
 114       } else {
 115         for (Element& elem : cnst.enabled_element_set) {
 116           xbt_assert(elem.variable->sharing_weight > 0);
 117           XBT_DEBUG("\tNon-Shared variable. Update constraint usage of %p (%g) with variable %p by %g", &cnst,
 118                     cnst.usage, elem.variable, elem.variable->mu);
 119           cnst.usage = std::min(cnst.usage, elem.consumption_weight * elem.variable->mu);
 120         }
 121         XBT_DEBUG("\tUpdate constraint %p (%g) by %g", &cnst, cnst.remaining, cnst.usage);
 122         double_update(&cnst.remaining, cnst.usage, sg_maxmin_precision);
 123       }
 124
 125       XBT_DEBUG("\tRemaining for %p : %g", &cnst, cnst.remaining);
 126       if (cnst.remaining <= 0.0) {
 127         XBT_DEBUG("\tGet rid of constraint %p", &cnst);
 128
 129         iter = cnst_list.erase(iter);
 130         for (Element& elem : cnst.enabled_element_set) {
 131           if (elem.variable->sharing_weight <= 0)
 132             break;
 133           if (elem.consumption_weight > 0 && elem.variable->saturated_variable_set_hook.is_linked()) {
 134             XBT_DEBUG("\t\tGet rid of variable %p", elem.variable);
 135             simgrid::xbt::intrusive_erase(var_list, *elem.variable);
 136           }
 137         }
 138       } else {
 139         iter++;
 140       }
 141     }
 142   } while (not var_list.empty());
 143
 144   cnst_list.clear();
 145   sys->modified = true;
 146   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
 147     XBT_DEBUG("Fair bottleneck done");
 148     sys->print();
 149   }
 150 }