X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/48f4267902051738a0b28d32db5a704d711fe37d..5843ccab4e336d47ca34f54e68760ac78d242f36:/src/kernel/lmm/System.cpp diff --git a/src/kernel/lmm/System.cpp b/src/kernel/lmm/System.cpp index 3902992b50..cebcb9632d 100644 --- a/src/kernel/lmm/System.cpp +++ b/src/kernel/lmm/System.cpp @@ -1,25 +1,26 @@ -/* Copyright (c) 2004-2022. The SimGrid Team. All rights reserved. */ +/* Copyright (c) 2004-2023. 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 "src/internal_config.h" #include "src/kernel/lmm/fair_bottleneck.hpp" #include "src/kernel/lmm/maxmin.hpp" +#include "src/simgrid/math_utils.h" #if SIMGRID_HAVE_EIGEN3 #include "src/kernel/lmm/bmf.hpp" #endif + #include #include XBT_LOG_NEW_DEFAULT_SUBCATEGORY(ker_lmm, kernel, "Kernel Linear Max-Min solver"); -double sg_maxmin_precision = 1E-5; /* Change this with --cfg=maxmin/precision:VALUE */ -double sg_surf_precision = 1E-9; /* Change this with --cfg=surf/precision:VALUE */ +double sg_precision_workamount = 1E-5; /* Change this with --cfg=precision/work-amount:VALUE */ +double sg_precision_timing = 1E-9; /* Change this with --cfg=precision/timing:VALUE */ int sg_concurrency_limit = -1; /* Change this with --cfg=maxmin/concurrency-limit:VALUE */ -namespace simgrid { -namespace kernel { -namespace lmm { +namespace simgrid::kernel::lmm { int Variable::next_rank_ = 1; int Constraint::next_rank_ = 1; @@ -31,6 +32,11 @@ Element::Element(Constraint* constraint, Variable* variable, double cweight) int Element::get_concurrency() const { + // just to try having the computation of the concurrency + if (constraint->get_sharing_policy() == Constraint::SharingPolicy::WIFI) { + return 1; + } + // Ignore element with weight less than one (e.g. cross-traffic) return (consumption_weight >= 1) ? 1 : 0; // There are other alternatives, but they will change the behavior of the model.. @@ -47,19 +53,19 @@ void Element::decrease_concurrency() constraint->concurrency_current_ -= get_concurrency(); } -void Element::increase_concurrency() +void Element::increase_concurrency(bool check_limit) { constraint->concurrency_current_ += get_concurrency(); if (constraint->concurrency_current_ > constraint->concurrency_maximum_) constraint->concurrency_maximum_ = constraint->concurrency_current_; - xbt_assert(constraint->get_concurrency_limit() < 0 || + xbt_assert(not check_limit || constraint->get_concurrency_limit() < 0 || constraint->concurrency_current_ <= constraint->get_concurrency_limit(), "Concurrency limit overflow!"); } -System* System::build(const std::string& solver_name, bool selective_update) +System* System::build(std::string_view solver_name, bool selective_update) { System* system = nullptr; if (solver_name == "bmf") { @@ -89,7 +95,7 @@ void System::validate_solver(const std::string& solver_name) void System::check_concurrency() const { - // These checks are very expensive, so do them only if we want to debug SURF LMM + // These checks are very expensive, so do them only if we want to debug the LMM if (not XBT_LOG_ISENABLED(ker_lmm, xbt_log_priority_debug)) return; @@ -102,8 +108,8 @@ void System::check_concurrency() const for (Element const& elem : cnst.disabled_element_set_) { // We should have staged variables only if concurrency is reached in some constraint - xbt_assert(cnst.get_concurrency_limit() < 0 || elem.variable->staged_penalty_ == 0 || - elem.variable->get_min_concurrency_slack() < elem.variable->concurrency_share_, + xbt_assert(cnst.get_concurrency_limit() < 0 || elem.variable->staged_sharing_penalty_ == 0 || + elem.variable->get_min_concurrency_slack() == 0, "should not have staged variable!"); } @@ -176,9 +182,10 @@ System::System(bool selective_update) : selective_update_active(selective_update System::~System() { while (Variable* var = extract_variable()) { - std::string demangled = boost::core::demangle(var->id_ ? typeid(*var->id_).name() : "(unidentified)"); - XBT_WARN("Probable bug: a %s variable (#%d) not removed before the LMM system destruction.", demangled.c_str(), - var->rank_); + const char* name = var->id_ ? typeid(*var->id_).name() : "(unidentified)"; + boost::core::scoped_demangled_name demangled(name); + XBT_WARN("Probable bug: a %s variable (#%d) not removed before the LMM system destruction.", + demangled.get() ? demangled.get() : name, var->rank_); var_free(var); } while (Constraint* cnst = extract_constraint()) @@ -243,31 +250,8 @@ void System::variable_free_all() variable_free(var); } -void System::expand(Constraint* cnst, Variable* var, double consumption_weight) +Element& System::expand_create_elem(Constraint* cnst, Variable* var, double consumption_weight) { - modified_ = true; - - // Check if this variable already has an active element in this constraint - // If it does, subtract it from the required slack - int current_share = 0; - if (var->concurrency_share_ > 1) { - for (const Element& elem : var->cnsts_) { - if (elem.constraint == cnst && elem.enabled_element_set_hook.is_linked()) - current_share += elem.get_concurrency(); - } - } - - // Check if we need to disable the variable - if (var->sharing_penalty_ > 0 && var->concurrency_share_ - current_share > cnst->get_concurrency_slack()) { - double penalty = var->sharing_penalty_; - disable_var(var); - for (Element const& elem : var->cnsts_) - on_disabled_var(elem.constraint); - consumption_weight = 0; - var->staged_penalty_ = penalty; - xbt_assert(not var->sharing_penalty_); - } - xbt_assert(var->cnsts_.size() < var->cnsts_.capacity(), "Too much constraints"); var->cnsts_.emplace_back(cnst, var, consumption_weight); @@ -275,58 +259,60 @@ void System::expand(Constraint* cnst, Variable* var, double consumption_weight) if (var->sharing_penalty_ != 0.0) { elem.constraint->enabled_element_set_.push_front(elem); - elem.increase_concurrency(); } else elem.constraint->disabled_element_set_.push_back(elem); - if (not selective_update_active) { + if (elem.consumption_weight > 0 || var->sharing_penalty_ > 0) { make_constraint_active(cnst); - } else if (elem.consumption_weight > 0 || var->sharing_penalty_ > 0) { - make_constraint_active(cnst); - update_modified_cnst_set(cnst); - // TODOLATER: Why do we need this second call? - if (var->cnsts_.size() > 1) - update_modified_cnst_set(var->cnsts_[0].constraint); } + return elem; +} - check_concurrency(); +Element& System::expand_add_to_elem(Element& elem, const Constraint* cnst, double consumption_weight) const +{ + elem.max_consumption_weight = std::max(elem.max_consumption_weight, consumption_weight); + if (cnst->sharing_policy_ != Constraint::SharingPolicy::FATPIPE) + elem.consumption_weight += consumption_weight; + else + elem.consumption_weight = std::max(elem.consumption_weight, consumption_weight); + return elem; } -void System::expand_add(Constraint* cnst, Variable* var, double value) +void System::expand(Constraint* cnst, Variable* var, double consumption_weight, bool force_creation) { modified_ = true; - check_concurrency(); - - // BEWARE: In case you have multiple elements in one constraint, this will always add value to the first element. auto elem_it = std::find_if(begin(var->cnsts_), end(var->cnsts_), [&cnst](Element const& x) { return x.constraint == cnst; }); - if (elem_it != end(var->cnsts_)) { - Element& elem = *elem_it; - if (var->sharing_penalty_ != 0.0) - elem.decrease_concurrency(); - elem.max_consumption_weight = std::max(elem.max_consumption_weight, value); - if (cnst->sharing_policy_ != Constraint::SharingPolicy::FATPIPE) - elem.consumption_weight += value; - else - elem.consumption_weight = std::max(elem.consumption_weight, value); - - // We need to check that increasing value of the element does not cross the concurrency limit - if (var->sharing_penalty_ != 0.0) { - if (cnst->get_concurrency_slack() < elem.get_concurrency()) { - double penalty = var->sharing_penalty_; - disable_var(var); - for (Element const& elem2 : var->cnsts_) - on_disabled_var(elem2.constraint); - var->staged_penalty_ = penalty; - xbt_assert(not var->sharing_penalty_); - } - elem.increase_concurrency(); + bool reuse_elem = elem_it != end(var->cnsts_) && not force_creation; + if (reuse_elem && var->sharing_penalty_ != 0.0) { + /* before changing it, decreases concurrency on constraint, it'll be added back later */ + elem_it->decrease_concurrency(); + } + Element& elem = reuse_elem ? expand_add_to_elem(*elem_it, cnst, consumption_weight) + : expand_create_elem(cnst, var, consumption_weight); + + // Check if we need to disable the variable + if (var->sharing_penalty_ != 0) { + /* increase concurrency in constraint that this element uses. + * as we don't check if constraint has reached its limit before increasing, + * we can't check the correct state at increase_concurrency, anyway + * it'll check if the slack is smaller than 0 just below */ + elem.increase_concurrency(false); + if (cnst->get_concurrency_slack() < 0) { + double penalty = var->sharing_penalty_; + disable_var(var); + for (Element const& elem2 : var->cnsts_) + on_disabled_var(elem2.constraint); + var->staged_sharing_penalty_ = penalty; + xbt_assert(not var->sharing_penalty_); } + } + + /* update modified constraint set accordingly */ + if (elem.consumption_weight > 0 || var->sharing_penalty_ > 0) update_modified_cnst_set(cnst); - } else - expand(cnst, var, value); check_concurrency(); } @@ -340,8 +326,6 @@ Variable* Constraint::get_variable(const Element** elem) const *elem = &enabled_element_set_.front(); else if (not disabled_element_set_.empty()) *elem = &disabled_element_set_.front(); - else - *elem = nullptr; } else { // elem is not null, so we carry on if ((*elem)->enabled_element_set_hook.is_linked()) { @@ -374,8 +358,6 @@ Variable* Constraint::get_variable_safe(const Element** elem, const Element** ne *elem = &enabled_element_set_.front(); else if (not disabled_element_set_.empty()) *elem = &disabled_element_set_.front(); - else - *elem = nullptr; } else { *elem = *nextelem; if (*numelem > 0) { @@ -447,7 +429,7 @@ void System::print() const } XBT_DEBUG("%s", buf.c_str()); buf.clear(); - xbt_assert(not double_positive(sum - cnst.bound_, cnst.bound_ * sg_maxmin_precision), + xbt_assert(not double_positive(sum - cnst.bound_, cnst.bound_ * sg_precision_workamount), "Incorrect value (%f is not smaller than %f): %g", sum, cnst.bound_, sum - cnst.bound_); } @@ -456,7 +438,7 @@ void System::print() const for (Variable const& var : variable_set) { if (var.bound_ > 0) { XBT_DEBUG("'%d'(%f) : %f (<=%f)", var.rank_, var.sharing_penalty_, var.value_, var.bound_); - xbt_assert(not double_positive(var.value_ - var.bound_, var.bound_ * sg_maxmin_precision), + xbt_assert(not double_positive(var.value_ - var.bound_, var.bound_ * sg_precision_workamount), "Incorrect value (%f is not smaller than %f", var.value_, var.bound_); } else { XBT_DEBUG("'%d'(%f) : %f", var.rank_, var.sharing_penalty_, var.value_); @@ -464,6 +446,11 @@ void System::print() const } } +resource::Action::ModifiedSet* System::get_modified_action_set() const +{ + return modified_set_.get(); +} + void System::solve() { if (not modified_) @@ -472,8 +459,20 @@ void System::solve() do_solve(); modified_ = false; - if (selective_update_active) + if (selective_update_active) { + /* update list of modified variables */ + for (const Constraint& cnst : modified_constraint_set) { + for (const Element& elem : cnst.enabled_element_set_) { + if (elem.consumption_weight > 0) { + resource::Action* action = elem.variable->id_; + if (not action->is_within_modified_set()) + modified_set_->push_back(*action); + } + } + } + /* clear list of modified constraint */ remove_all_modified_cnst_set(); + } if (XBT_LOG_ISENABLED(ker_lmm, xbt_log_priority_debug)) { print(); @@ -509,9 +508,8 @@ void Variable::initialize(resource::Action* id_value, double sharing_penalty, do rank_ = next_rank_++; cnsts_.reserve(number_of_constraints); sharing_penalty_ = sharing_penalty; - staged_penalty_ = 0.0; + staged_sharing_penalty_ = 0.0; bound_ = bound_value; - concurrency_share_ = 1; value_ = 0.0; visited_ = visited_value; mu_ = 0.0; @@ -543,8 +541,8 @@ void System::enable_var(Variable* var) { xbt_assert(not XBT_LOG_ISENABLED(ker_lmm, xbt_log_priority_debug) || var->can_enable()); - var->sharing_penalty_ = var->staged_penalty_; - var->staged_penalty_ = 0; + var->sharing_penalty_ = var->staged_sharing_penalty_; + var->staged_sharing_penalty_ = 0; // Enabling the variable, move var to list head. Subtlety is: here, we need to call update_modified_cnst_set AFTER // moving at least one element of var. @@ -565,7 +563,7 @@ void System::enable_var(Variable* var) void System::disable_var(Variable* var) { - xbt_assert(not var->staged_penalty_, "Staged penalty should have been cleared"); + xbt_assert(not var->staged_sharing_penalty_, "Staged penalty should have been cleared"); // Disabling the variable, move to var to list tail. Subtlety is: here, we need to call update_modified_cnst_set // BEFORE moving the last element of var. simgrid::xbt::intrusive_erase(variable_set, *var); @@ -580,7 +578,7 @@ void System::disable_var(Variable* var) } var->sharing_penalty_ = 0.0; - var->staged_penalty_ = 0.0; + var->staged_sharing_penalty_ = 0.0; var->value_ = 0.0; check_concurrency(); } @@ -613,7 +611,7 @@ void System::on_disabled_var(Constraint* cnstr) nextelem = nullptr; } - if (elem->variable->staged_penalty_ > 0 && elem->variable->can_enable()) { + if (elem->variable->staged_sharing_penalty_ > 0 && elem->variable->can_enable()) { // Found a staged variable // TODOLATER: Add random timing function to model reservation protocol fuzziness? Then how to make sure that // staged variables will eventually be called? @@ -648,12 +646,10 @@ void System::update_variable_penalty(Variable* var, double penalty) // Are we enabling this variable? if (enabling_var) { - var->staged_penalty_ = penalty; + var->staged_sharing_penalty_ = penalty; int minslack = var->get_min_concurrency_slack(); - if (minslack < var->concurrency_share_) { - XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with penalty %f and concurrency" - " share %i", - minslack, penalty, var->concurrency_share_); + if (minslack == 0) { + XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack is 0"); return; } XBT_DEBUG("Enabling var with min concurrency slack %i", minslack); @@ -751,7 +747,7 @@ void System::remove_all_modified_cnst_set() * If the resource is not shared (ie in FATPIPE mode), then the load is the max (not the sum) * of all resource usages located on this resource. */ -double Constraint::get_usage() const +double Constraint::get_load() const { double result = 0.0; if (sharing_policy_ != SharingPolicy::FATPIPE) { @@ -766,20 +762,12 @@ double Constraint::get_usage() const return result; } -int Constraint::get_variable_amount() const -{ - return static_cast(std::count_if(std::begin(enabled_element_set_), std::end(enabled_element_set_), - [](const Element& elem) { return elem.consumption_weight > 0; })); -} - void Constraint::set_sharing_policy(SharingPolicy policy, const s4u::NonLinearResourceCb& cb) { - xbt_assert(policy == SharingPolicy::NONLINEAR || not cb, + xbt_assert(policy == SharingPolicy::NONLINEAR || policy == SharingPolicy::WIFI || not cb, "Invalid sharing policy for constraint. Callback should be used with NONLINEAR sharing policy"); sharing_policy_ = policy; dyn_constraint_cb_ = cb; } -} // namespace lmm -} // namespace kernel -} // namespace simgrid \ No newline at end of file +} // namespace simgrid::kernel::lmm