src/kernel/lmm/System.cpp

   1 /* Copyright (c) 2004-2022. 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/fair_bottleneck.hpp"
   7 #include "src/kernel/lmm/maxmin.hpp"
   8 #if SIMGRID_HAVE_EIGEN3
   9 #include "src/kernel/lmm/bmf.hpp"
  10 #endif
  11 #include <boost/core/demangle.hpp>
  12 #include <typeinfo>
  13
  14 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(ker_lmm, kernel, "Kernel Linear Max-Min solver");
  15
  16 double sg_maxmin_precision = 1E-5; /* Change this with --cfg=maxmin/precision:VALUE */
  17 double sg_surf_precision   = 1E-9; /* Change this with --cfg=surf/precision:VALUE */
  18 int sg_concurrency_limit   = -1;      /* Change this with --cfg=maxmin/concurrency-limit:VALUE */
  19
  20 namespace simgrid {
  21 namespace kernel {
  22 namespace lmm {
  23
  24 int Variable::next_rank_   = 1;
  25 int Constraint::next_rank_ = 1;
  26
  27 Element::Element(Constraint* constraint, Variable* variable, double cweight)
  28     : constraint(constraint), variable(variable), consumption_weight(cweight), max_consumption_weight(cweight)
  29 {
  30 }
  31
  32 int Element::get_concurrency() const
  33 {
  34   // Ignore element with weight less than one (e.g. cross-traffic)
  35   return (consumption_weight >= 1) ? 1 : 0;
  36   // There are other alternatives, but they will change the behavior of the model..
  37   // So do not use it unless you want to make a new model.
  38   // If you do, remember to change the variables concurrency share to reflect it.
  39   // Potential examples are:
  40   // return (elem->weight>0)?1:0;//Include element as soon  as weight is non-zero
  41   // return (int)ceil(elem->weight);//Include element as the rounded-up integer value of the element weight
  42 }
  43
  44 void Element::decrease_concurrency()
  45 {
  46   xbt_assert(constraint->concurrency_current_ >= get_concurrency());
  47   constraint->concurrency_current_ -= get_concurrency();
  48 }
  49
  50 void Element::increase_concurrency()
  51 {
  52   constraint->concurrency_current_ += get_concurrency();
  53
  54   if (constraint->concurrency_current_ > constraint->concurrency_maximum_)
  55     constraint->concurrency_maximum_ = constraint->concurrency_current_;
  56
  57   xbt_assert(constraint->get_concurrency_limit() < 0 ||
  58                  constraint->concurrency_current_ <= constraint->get_concurrency_limit(),
  59              "Concurrency limit overflow!");
  60 }
  61
  62 System* System::build(const std::string& solver_name, bool selective_update)
  63 {
  64   System* system = nullptr;
  65   if (solver_name == "bmf") {
  66 #if SIMGRID_HAVE_EIGEN3
  67     system = new BmfSystem(selective_update);
  68 #endif
  69   } else if (solver_name == "fairbottleneck") {
  70     system = new FairBottleneck(selective_update);
  71   } else {
  72     system = new MaxMin(selective_update);
  73   }
  74   return system;
  75 }
  76
  77 void System::validate_solver(const std::string& solver_name)
  78 {
  79   static const std::vector<std::string> opts{"bmf", "maxmin", "fairbottleneck"};
  80   if (solver_name == "bmf") {
  81 #if !SIMGRID_HAVE_EIGEN3
  82     xbt_die("Cannot use the BMF solver without installing Eigen3.");
  83 #endif
  84   }
  85   if (std::find(opts.begin(), opts.end(), solver_name) == std::end(opts)) {
  86     xbt_die("Invalid system solver, it should be one of: \"maxmin\", \"fairbottleneck\" or \"bmf\"");
  87   }
  88 }
  89
  90 void System::check_concurrency() const
  91 {
  92   // These checks are very expensive, so do them only if we want to debug SURF LMM
  93   if (not XBT_LOG_ISENABLED(ker_lmm, xbt_log_priority_debug))
  94     return;
  95
  96   for (Constraint const& cnst : constraint_set) {
  97     int concurrency       = 0;
  98     for (Element const& elem : cnst.enabled_element_set_) {
  99       xbt_assert(elem.variable->sharing_penalty_ > 0);
 100       concurrency += elem.get_concurrency();
 101     }
 102
 103     for (Element const& elem : cnst.disabled_element_set_) {
 104       // We should have staged variables only if concurrency is reached in some constraint
 105       xbt_assert(cnst.get_concurrency_limit() < 0 || elem.variable->staged_penalty_ == 0 ||
 106                      elem.variable->get_min_concurrency_slack() < elem.variable->concurrency_share_,
 107                  "should not have staged variable!");
 108     }
 109
 110     xbt_assert(cnst.get_concurrency_limit() < 0 || cnst.get_concurrency_limit() >= concurrency,
 111                "concurrency check failed!");
 112     xbt_assert(cnst.concurrency_current_ == concurrency, "concurrency_current is out-of-date!");
 113   }
 114
 115   // Check that for each variable, all corresponding elements are in the same state (i.e. same element sets)
 116   for (Variable const& var : variable_set) {
 117     if (var.cnsts_.empty())
 118       continue;
 119
 120     const Element& elem    = var.cnsts_[0];
 121     bool belong_to_enabled  = elem.enabled_element_set_hook.is_linked();
 122     bool belong_to_disabled = elem.disabled_element_set_hook.is_linked();
 123     bool belong_to_active   = elem.active_element_set_hook.is_linked();
 124
 125     for (Element const& elem2 : var.cnsts_) {
 126       xbt_assert(belong_to_enabled == elem2.enabled_element_set_hook.is_linked(),
 127                  "Variable inconsistency (1): enabled_element_set");
 128       xbt_assert(belong_to_disabled == elem2.disabled_element_set_hook.is_linked(),
 129                  "Variable inconsistency (2): disabled_element_set");
 130       xbt_assert(belong_to_active == elem2.active_element_set_hook.is_linked(),
 131                  "Variable inconsistency (3): active_element_set");
 132     }
 133   }
 134 }
 135
 136 void System::var_free(Variable* var)
 137 {
 138   XBT_IN("(sys=%p, var=%p)", this, var);
 139   modified_ = true;
 140
 141   // TODOLATER Can do better than that by leaving only the variable in only one enabled_element_set, call
 142   // update_modified_set, and then remove it..
 143   if (not var->cnsts_.empty())
 144     update_modified_set(var->cnsts_[0].constraint);
 145
 146   for (Element& elem : var->cnsts_) {
 147     if (var->sharing_penalty_ > 0)
 148       elem.decrease_concurrency();
 149     if (elem.enabled_element_set_hook.is_linked())
 150       simgrid::xbt::intrusive_erase(elem.constraint->enabled_element_set_, elem);
 151     if (elem.disabled_element_set_hook.is_linked())
 152       simgrid::xbt::intrusive_erase(elem.constraint->disabled_element_set_, elem);
 153     if (elem.active_element_set_hook.is_linked())
 154       simgrid::xbt::intrusive_erase(elem.constraint->active_element_set_, elem);
 155     if (elem.constraint->enabled_element_set_.empty() && elem.constraint->disabled_element_set_.empty())
 156       make_constraint_inactive(elem.constraint);
 157     else
 158       on_disabled_var(elem.constraint);
 159   }
 160
 161   var->cnsts_.clear();
 162
 163   check_concurrency();
 164
 165   xbt_mallocator_release(variable_mallocator_, var);
 166   XBT_OUT();
 167 }
 168
 169 System::System(bool selective_update) : selective_update_active(selective_update)
 170 {
 171   XBT_DEBUG("Setting selective_update_active flag to %d", selective_update_active);
 172
 173   if (selective_update)
 174     modified_set_ = std::make_unique<kernel::resource::Action::ModifiedSet>();
 175 }
 176
 177 System::~System()
 178 {
 179   while (Variable* var = extract_variable()) {
 180     std::string demangled = boost::core::demangle(var->id_ ? typeid(*var->id_).name() : "(unidentified)");
 181     XBT_WARN("Probable bug: a %s variable (#%d) not removed before the LMM system destruction.", demangled.c_str(),
 182              var->rank_);
 183     var_free(var);
 184   }
 185   while (Constraint* cnst = extract_constraint())
 186     cnst_free(cnst);
 187
 188   xbt_mallocator_free(variable_mallocator_);
 189 }
 190
 191 void System::cnst_free(Constraint* cnst)
 192 {
 193   make_constraint_inactive(cnst);
 194   delete cnst;
 195 }
 196
 197 Constraint::Constraint(resource::Resource* id_value, double bound_value) : bound_(bound_value), id_(id_value)
 198 {
 199   rank_ = next_rank_++;
 200 }
 201
 202 Constraint* System::constraint_new(resource::Resource* id, double bound_value)
 203 {
 204   auto* cnst = new Constraint(id, bound_value);
 205   insert_constraint(cnst);
 206   return cnst;
 207 }
 208
 209 void* System::variable_mallocator_new_f()
 210 {
 211   return new Variable;
 212 }
 213
 214 void System::variable_mallocator_free_f(void* var)
 215 {
 216   delete static_cast<Variable*>(var);
 217 }
 218
 219 Variable* System::variable_new(resource::Action* id, double sharing_penalty, double bound, size_t number_of_constraints)
 220 {
 221   XBT_IN("(sys=%p, id=%p, penalty=%f, bound=%f, num_cons =%zu)", this, id, sharing_penalty, bound,
 222          number_of_constraints);
 223
 224   auto* var = static_cast<Variable*>(xbt_mallocator_get(variable_mallocator_));
 225   var->initialize(id, sharing_penalty, bound, number_of_constraints, visited_counter_ - 1);
 226   if (sharing_penalty > 0)
 227     variable_set.push_front(*var);
 228   else
 229     variable_set.push_back(*var);
 230
 231   XBT_OUT(" returns %p", var);
 232   return var;
 233 }
 234
 235 void System::variable_free(Variable* var)
 236 {
 237   remove_variable(var);
 238   var_free(var);
 239 }
 240
 241 void System::variable_free_all()
 242 {
 243   while (Variable* var = extract_variable())
 244     variable_free(var);
 245 }
 246
 247 void System::expand(Constraint* cnst, Variable* var, double consumption_weight)
 248 {
 249   modified_ = true;
 250
 251   // Check if this variable already has an active element in this constraint
 252   // If it does, subtract it from the required slack
 253   int current_share = 0;
 254   if (var->concurrency_share_ > 1) {
 255     for (const Element& elem : var->cnsts_) {
 256       if (elem.constraint == cnst && elem.enabled_element_set_hook.is_linked())
 257         current_share += elem.get_concurrency();
 258     }
 259   }
 260
 261   // Check if we need to disable the variable
 262   if (var->sharing_penalty_ > 0 && var->concurrency_share_ - current_share > cnst->get_concurrency_slack()) {
 263     double penalty = var->sharing_penalty_;
 264     disable_var(var);
 265     for (Element const& elem : var->cnsts_)
 266       on_disabled_var(elem.constraint);
 267     consumption_weight = 0;
 268     var->staged_penalty_ = penalty;
 269     xbt_assert(not var->sharing_penalty_);
 270   }
 271
 272   xbt_assert(var->cnsts_.size() < var->cnsts_.capacity(), "Too much constraints");
 273
 274   var->cnsts_.emplace_back(cnst, var, consumption_weight);
 275   Element& elem = var->cnsts_.back();
 276
 277   if (var->sharing_penalty_ != 0.0) {
 278     elem.constraint->enabled_element_set_.push_front(elem);
 279     elem.increase_concurrency();
 280   } else
 281     elem.constraint->disabled_element_set_.push_back(elem);
 282
 283   if (not selective_update_active) {
 284     make_constraint_active(cnst);
 285   } else if (elem.consumption_weight > 0 || var->sharing_penalty_ > 0) {
 286     make_constraint_active(cnst);
 287     update_modified_set(cnst);
 288     // TODOLATER: Why do we need this second call?
 289     if (var->cnsts_.size() > 1)
 290       update_modified_set(var->cnsts_[0].constraint);
 291   }
 292
 293   check_concurrency();
 294 }
 295
 296 void System::expand_add(Constraint* cnst, Variable* var, double value)
 297 {
 298   modified_ = true;
 299
 300   check_concurrency();
 301
 302   // BEWARE: In case you have multiple elements in one constraint, this will always add value to the first element.
 303   auto elem_it =
 304       std::find_if(begin(var->cnsts_), end(var->cnsts_), [&cnst](Element const& x) { return x.constraint == cnst; });
 305   if (elem_it != end(var->cnsts_)) {
 306     Element& elem = *elem_it;
 307     if (var->sharing_penalty_ != 0.0)
 308       elem.decrease_concurrency();
 309
 310     elem.max_consumption_weight = std::max(elem.max_consumption_weight, value);
 311     if (cnst->sharing_policy_ != Constraint::SharingPolicy::FATPIPE)
 312       elem.consumption_weight += value;
 313     else
 314       elem.consumption_weight = std::max(elem.consumption_weight, value);
 315
 316     // We need to check that increasing value of the element does not cross the concurrency limit
 317     if (var->sharing_penalty_ != 0.0) {
 318       if (cnst->get_concurrency_slack() < elem.get_concurrency()) {
 319         double penalty = var->sharing_penalty_;
 320         disable_var(var);
 321         for (Element const& elem2 : var->cnsts_)
 322           on_disabled_var(elem2.constraint);
 323         var->staged_penalty_ = penalty;
 324         xbt_assert(not var->sharing_penalty_);
 325       }
 326       elem.increase_concurrency();
 327     }
 328     update_modified_set(cnst);
 329   } else
 330     expand(cnst, var, value);
 331
 332   check_concurrency();
 333 }
 334
 335 Variable* Constraint::get_variable(const Element** elem) const
 336 {
 337   if (*elem == nullptr) {
 338     // That is the first call, pick the first element among enabled_element_set (or disabled_element_set if
 339     // enabled_element_set is empty)
 340     if (not enabled_element_set_.empty())
 341       *elem = &enabled_element_set_.front();
 342     else if (not disabled_element_set_.empty())
 343       *elem = &disabled_element_set_.front();
 344     else
 345       *elem = nullptr;
 346   } else {
 347     // elem is not null, so we carry on
 348     if ((*elem)->enabled_element_set_hook.is_linked()) {
 349       // Look at enabled_element_set, and jump to disabled_element_set when finished
 350       auto iter = std::next(enabled_element_set_.iterator_to(**elem));
 351       if (iter != std::end(enabled_element_set_))
 352         *elem = &*iter;
 353       else if (not disabled_element_set_.empty())
 354         *elem = &disabled_element_set_.front();
 355       else
 356         *elem = nullptr;
 357     } else {
 358       auto iter = std::next(disabled_element_set_.iterator_to(**elem));
 359       *elem     = iter != std::end(disabled_element_set_) ? &*iter : nullptr;
 360     }
 361   }
 362   if (*elem)
 363     return (*elem)->variable;
 364   else
 365     return nullptr;
 366 }
 367
 368 // if we modify the list between calls, normal version may loop forever
 369 // this safe version ensures that we browse the list elements only once
 370 Variable* Constraint::get_variable_safe(const Element** elem, const Element** nextelem, size_t* numelem) const
 371 {
 372   if (*elem == nullptr) {
 373     *numelem = enabled_element_set_.size() + disabled_element_set_.size() - 1;
 374     if (not enabled_element_set_.empty())
 375       *elem = &enabled_element_set_.front();
 376     else if (not disabled_element_set_.empty())
 377       *elem = &disabled_element_set_.front();
 378     else
 379       *elem = nullptr;
 380   } else {
 381     *elem = *nextelem;
 382     if (*numelem > 0) {
 383       (*numelem)--;
 384     } else
 385       return nullptr;
 386   }
 387   if (*elem) {
 388     // elem is not null, so we carry on
 389     if ((*elem)->enabled_element_set_hook.is_linked()) {
 390       // Look at enabled_element_set, and jump to disabled_element_set when finished
 391       auto iter = std::next(enabled_element_set_.iterator_to(**elem));
 392       if (iter != std::end(enabled_element_set_))
 393         *nextelem = &*iter;
 394       else if (not disabled_element_set_.empty())
 395         *nextelem = &disabled_element_set_.front();
 396       else
 397         *nextelem = nullptr;
 398     } else {
 399       auto iter = std::next(disabled_element_set_.iterator_to(**elem));
 400       *nextelem = iter != std::end(disabled_element_set_) ? &*iter : nullptr;
 401     }
 402     return (*elem)->variable;
 403   } else
 404     return nullptr;
 405 }
 406
 407 template <class ElemList>
 408 static void format_element_list(const ElemList& elem_list, Constraint::SharingPolicy sharing_policy, double& sum,
 409                                 std::string& buf)
 410 {
 411   for (Element const& elem : elem_list) {
 412     buf += std::to_string(elem.consumption_weight) + ".'" + std::to_string(elem.variable->rank_) + "'(" +
 413            std::to_string(elem.variable->value_) + ")" +
 414            (sharing_policy != Constraint::SharingPolicy::FATPIPE ? " + " : " , ");
 415     if (sharing_policy != Constraint::SharingPolicy::FATPIPE)
 416       sum += elem.consumption_weight * elem.variable->value_;
 417     else
 418       sum = std::max(sum, elem.consumption_weight * elem.variable->value_);
 419   }
 420 }
 421
 422 void System::print() const
 423 {
 424   std::string buf = "MAX-MIN ( ";
 425
 426   /* Printing Objective */
 427   for (Variable const& var : variable_set)
 428     buf += "'" + std::to_string(var.rank_) + "'(" + std::to_string(var.sharing_penalty_) + ") ";
 429   buf += ")";
 430   XBT_DEBUG("%20s", buf.c_str());
 431   buf.clear();
 432
 433   XBT_DEBUG("Constraints");
 434   /* Printing Constraints */
 435   for (Constraint const& cnst : active_constraint_set) {
 436     double sum            = 0.0;
 437     // Show  the enabled variables
 438     buf += "\t";
 439     buf += cnst.sharing_policy_ != Constraint::SharingPolicy::FATPIPE ? "(" : "max(";
 440     format_element_list(cnst.enabled_element_set_, cnst.sharing_policy_, sum, buf);
 441     // TODO: Adding disabled elements only for test compatibility, but do we really want them to be printed?
 442     format_element_list(cnst.disabled_element_set_, cnst.sharing_policy_, sum, buf);
 443
 444     buf += "0) <= " + std::to_string(cnst.bound_) + " ('" + std::to_string(cnst.rank_) + "')";
 445
 446     if (cnst.sharing_policy_ == Constraint::SharingPolicy::FATPIPE) {
 447       buf += " [MAX-Constraint]";
 448     }
 449     XBT_DEBUG("%s", buf.c_str());
 450     buf.clear();
 451     xbt_assert(not double_positive(sum - cnst.bound_, cnst.bound_ * sg_maxmin_precision),
 452                "Incorrect value (%f is not smaller than %f): %g", sum, cnst.bound_, sum - cnst.bound_);
 453   }
 454
 455   XBT_DEBUG("Variables");
 456   /* Printing Result */
 457   for (Variable const& var : variable_set) {
 458     if (var.bound_ > 0) {
 459       XBT_DEBUG("'%d'(%f) : %f (<=%f)", var.rank_, var.sharing_penalty_, var.value_, var.bound_);
 460       xbt_assert(not double_positive(var.value_ - var.bound_, var.bound_ * sg_maxmin_precision),
 461                  "Incorrect value (%f is not smaller than %f", var.value_, var.bound_);
 462     } else {
 463       XBT_DEBUG("'%d'(%f) : %f", var.rank_, var.sharing_penalty_, var.value_);
 464     }
 465   }
 466 }
 467
 468 void System::solve()
 469 {
 470   if (not modified_)
 471     return;
 472
 473   do_solve();
 474
 475   modified_ = false;
 476   if (selective_update_active)
 477     remove_all_modified_set();
 478
 479   if (XBT_LOG_ISENABLED(ker_lmm, xbt_log_priority_debug)) {
 480     print();
 481   }
 482
 483   check_concurrency();
 484 }
 485
 486 /** @brief Attribute the value bound to var->bound.
 487  *
 488  *  @param var the Variable*
 489  *  @param bound the new bound to associate with var
 490  *
 491  *  Makes var->bound equal to bound. Whenever this function is called a change is  signed in the system. To
 492  *  avoid false system changing detection it is a good idea to test (bound != 0) before calling it.
 493  */
 494 void System::update_variable_bound(Variable* var, double bound)
 495 {
 496   modified_  = true;
 497   var->bound_ = bound;
 498
 499   if (not var->cnsts_.empty()) {
 500     for (Element const& elem : var->cnsts_) {
 501       update_modified_set(elem.constraint);
 502     }
 503   }
 504 }
 505
 506 void Variable::initialize(resource::Action* id_value, double sharing_penalty, double bound_value,
 507                           size_t number_of_constraints, unsigned visited_value)
 508 {
 509   id_     = id_value;
 510   rank_   = next_rank_++;
 511   cnsts_.reserve(number_of_constraints);
 512   sharing_penalty_   = sharing_penalty;
 513   staged_penalty_    = 0.0;
 514   bound_             = bound_value;
 515   concurrency_share_ = 1;
 516   value_             = 0.0;
 517   visited_           = visited_value;
 518   mu_                = 0.0;
 519
 520   xbt_assert(not variable_set_hook_.is_linked());
 521   xbt_assert(not saturated_variable_set_hook_.is_linked());
 522 }
 523
 524 int Variable::get_min_concurrency_slack() const
 525 {
 526   int minslack = std::numeric_limits<int>::max();
 527   for (Element const& elem : cnsts_) {
 528     int slack = elem.constraint->get_concurrency_slack();
 529     if (slack < minslack) {
 530       // This is only an optimization, to avoid looking at more constraints when slack is already zero
 531       if (slack == 0)
 532         return 0;
 533       minslack = slack;
 534     }
 535   }
 536   return minslack;
 537 }
 538
 539 // Small remark: In this implementation of System::enable_var() and System::disable_var(), we will meet multiple times
 540 // with var when running System::update_modified_set().
 541 // A priori not a big performance issue, but we might do better by calling System::update_modified_set() within the for
 542 // loops (after doing the first for enabling==1, and before doing the last for disabling==1)
 543 void System::enable_var(Variable* var)
 544 {
 545   xbt_assert(not XBT_LOG_ISENABLED(ker_lmm, xbt_log_priority_debug) || var->can_enable());
 546
 547   var->sharing_penalty_ = var->staged_penalty_;
 548   var->staged_penalty_  = 0;
 549
 550   // Enabling the variable, move var to list head. Subtlety is: here, we need to call update_modified_set AFTER
 551   // moving at least one element of var.
 552
 553   simgrid::xbt::intrusive_erase(variable_set, *var);
 554   variable_set.push_front(*var);
 555   for (Element& elem : var->cnsts_) {
 556     simgrid::xbt::intrusive_erase(elem.constraint->disabled_element_set_, elem);
 557     elem.constraint->enabled_element_set_.push_front(elem);
 558     elem.increase_concurrency();
 559   }
 560   if (not var->cnsts_.empty())
 561     update_modified_set(var->cnsts_[0].constraint);
 562
 563   // When used within on_disabled_var, we would get an assertion fail, because transiently there can be variables
 564   // that are staged and could be activated.
 565   // Anyway, caller functions all call check_concurrency() in the end.
 566 }
 567
 568 void System::disable_var(Variable* var)
 569 {
 570   xbt_assert(not var->staged_penalty_, "Staged penalty should have been cleared");
 571   // Disabling the variable, move to var to list tail. Subtlety is: here, we need to call update_modified_set
 572   // BEFORE moving the last element of var.
 573   simgrid::xbt::intrusive_erase(variable_set, *var);
 574   variable_set.push_back(*var);
 575   if (not var->cnsts_.empty())
 576     update_modified_set(var->cnsts_[0].constraint);
 577   for (Element& elem : var->cnsts_) {
 578     simgrid::xbt::intrusive_erase(elem.constraint->enabled_element_set_, elem);
 579     elem.constraint->disabled_element_set_.push_back(elem);
 580     if (elem.active_element_set_hook.is_linked())
 581       simgrid::xbt::intrusive_erase(elem.constraint->active_element_set_, elem);
 582     elem.decrease_concurrency();
 583   }
 584
 585   var->sharing_penalty_ = 0.0;
 586   var->staged_penalty_  = 0.0;
 587   var->value_          = 0.0;
 588   check_concurrency();
 589 }
 590
 591 /* /brief Find variables that can be enabled and enable them.
 592  *
 593  * Assuming that the variable has already been removed from non-zero penalties
 594  * Can we find a staged variable to add?
 595  * If yes, check that none of the constraints that this variable is involved in is at the limit of its concurrency
 596  * And then add it to enabled variables
 597  */
 598 void System::on_disabled_var(Constraint* cnstr)
 599 {
 600   if (cnstr->get_concurrency_limit() < 0)
 601     return;
 602
 603   size_t numelem = cnstr->disabled_element_set_.size();
 604   if (numelem == 0)
 605     return;
 606
 607   Element* elem = &cnstr->disabled_element_set_.front();
 608
 609   // Cannot use foreach loop, because System::enable_var() will modify disabled_element_set.. within the loop
 610   while (numelem-- && elem) {
 611     Element* nextelem;
 612     if (elem->disabled_element_set_hook.is_linked()) {
 613       auto iter = std::next(cnstr->disabled_element_set_.iterator_to(*elem));
 614       nextelem  = iter != std::end(cnstr->disabled_element_set_) ? &*iter : nullptr;
 615     } else {
 616       nextelem = nullptr;
 617     }
 618
 619     if (elem->variable->staged_penalty_ > 0 && elem->variable->can_enable()) {
 620       // Found a staged variable
 621       // TODOLATER: Add random timing function to model reservation protocol fuzziness? Then how to make sure that
 622       // staged variables will eventually be called?
 623       enable_var(elem->variable);
 624     }
 625
 626     xbt_assert(cnstr->concurrency_current_ <= cnstr->get_concurrency_limit(), "Concurrency overflow!");
 627     if (cnstr->concurrency_current_ == cnstr->get_concurrency_limit())
 628       break;
 629
 630     elem = nextelem;
 631   }
 632
 633   // We could get an assertion fail, because transiently there can be variables that are staged and could be activated.
 634   // And we need to go through all constraints of the disabled var before getting back a coherent state.
 635   // Anyway, caller functions all call check_concurrency() in the end.
 636 }
 637
 638 /** @brief update the penalty of a variable (disable it by passing 0 as a penalty) */
 639 void System::update_variable_penalty(Variable* var, double penalty)
 640 {
 641   xbt_assert(penalty >= 0, "Variable penalty should not be negative!");
 642   if (penalty == var->sharing_penalty_)
 643     return;
 644
 645   bool enabling_var  = (penalty > 0 && var->sharing_penalty_ <= 0);
 646   bool disabling_var = (penalty <= 0 && var->sharing_penalty_ > 0);
 647
 648   XBT_IN("(sys=%p, var=%p, var->sharing_penalty = %f, penalty=%f)", this, var, var->sharing_penalty_, penalty);
 649
 650   modified_ = true;
 651
 652   // Are we enabling this variable?
 653   if (enabling_var) {
 654     var->staged_penalty_ = penalty;
 655     int minslack       = var->get_min_concurrency_slack();
 656     if (minslack < var->concurrency_share_) {
 657       XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with penalty %f and concurrency"
 658                 " share %i",
 659                 minslack, penalty, var->concurrency_share_);
 660       return;
 661     }
 662     XBT_DEBUG("Enabling var with min concurrency slack %i", minslack);
 663     enable_var(var);
 664   } else if (disabling_var) {
 665     disable_var(var);
 666   } else {
 667     var->sharing_penalty_ = penalty;
 668     if (not var->cnsts_.empty())
 669       update_modified_set(var->cnsts_[0].constraint);
 670   }
 671
 672   check_concurrency();
 673
 674   XBT_OUT();
 675 }
 676
 677 void System::update_constraint_bound(Constraint* cnst, double bound)
 678 {
 679   modified_ = true;
 680   update_modified_set(cnst);
 681   cnst->bound_ = bound;
 682 }
 683
 684 /** @brief Update the constraint set propagating recursively to other constraints so the system should not be entirely
 685  *  computed.
 686  *
 687  *  @param cnst the Constraint* affected by the change
 688  *
 689  *  A recursive algorithm to optimize the system recalculation selecting only constraints that have changed. Each
 690  *  constraint change is propagated to the list of constraints for each variable.
 691  */
 692 void System::update_modified_set_rec(const Constraint* cnst)
 693 {
 694   for (Element const& elem : cnst->enabled_element_set_) {
 695     Variable* var = elem.variable;
 696     for (Element const& elem2 : var->cnsts_) {
 697       if (var->visited_ == visited_counter_)
 698         break;
 699       if (elem2.constraint != cnst && not elem2.constraint->modified_constraint_set_hook_.is_linked()) {
 700         modified_constraint_set.push_back(*elem2.constraint);
 701         update_modified_set_rec(elem2.constraint);
 702       }
 703     }
 704     // var will be ignored in later visits as long as sys->visited_counter does not move
 705     var->visited_ = visited_counter_;
 706   }
 707 }
 708
 709 void System::update_modified_set(Constraint* cnst)
 710 {
 711   /* nothing to do if selective update isn't active */
 712   if (selective_update_active && not cnst->modified_constraint_set_hook_.is_linked()) {
 713     modified_constraint_set.push_back(*cnst);
 714     update_modified_set_rec(cnst);
 715   }
 716 }
 717
 718 void System::remove_all_modified_set()
 719 {
 720   // We cleverly un-flag all variables just by incrementing visited_counter
 721   // In effect, the var->visited value will no more be equal to visited counter
 722   // To be clean, when visited counter has wrapped around, we force these var->visited values so that variables that
 723   // were in the modified a long long time ago are not wrongly skipped here, which would lead to very nasty bugs
 724   // (i.e. not readily reproducible, and requiring a lot of run time before happening).
 725   if (++visited_counter_ == 1) {
 726     /* the counter wrapped around, reset each variable->visited */
 727     for (Variable& var : variable_set)
 728       var.visited_ = 0;
 729   }
 730   modified_constraint_set.clear();
 731 }
 732
 733 /**
 734  * Returns resource load (in flop per second, or byte per second, or similar)
 735  *
 736  * If the resource is shared (the default case), the load is sum of resource usage made by
 737  * every variables located on this resource.
 738  *
 739  * If the resource is not shared (ie in FATPIPE mode), then the load is the max (not the sum)
 740  * of all resource usages located on this resource.
 741  */
 742 double Constraint::get_usage() const
 743 {
 744   double result              = 0.0;
 745   if (sharing_policy_ != SharingPolicy::FATPIPE) {
 746     for (Element const& elem : enabled_element_set_)
 747       if (elem.consumption_weight > 0)
 748         result += elem.consumption_weight * elem.variable->value_;
 749   } else {
 750     for (Element const& elem : enabled_element_set_)
 751       if (elem.consumption_weight > 0)
 752         result = std::max(result, elem.consumption_weight * elem.variable->value_);
 753   }
 754   return result;
 755 }
 756
 757 int Constraint::get_variable_amount() const
 758 {
 759   return static_cast<int>(std::count_if(std::begin(enabled_element_set_), std::end(enabled_element_set_),
 760                                         [](const Element& elem) { return elem.consumption_weight > 0; }));
 761 }
 762
 763 void Constraint::set_sharing_policy(SharingPolicy policy, const s4u::NonLinearResourceCb& cb)
 764 {
 765   xbt_assert(policy == SharingPolicy::NONLINEAR || not cb,
 766              "Invalid sharing policy for constraint. Callback should be used with NONLINEAR sharing policy");
 767   sharing_policy_    = policy;
 768   dyn_constraint_cb_ = cb;
 769 }
 770
 771 } // namespace lmm
 772 } // namespace kernel
 773 } // namespace simgrid