src/kernel/lmm/System.cpp

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