X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/f6a71a271e4625c51f4949eb5919ee9f94641531..f8babb62e07e0f0a89dda9e3d0d64db0fcb4e87e:/src/kernel/lmm/maxmin.cpp diff --git a/src/kernel/lmm/maxmin.cpp b/src/kernel/lmm/maxmin.cpp index 4168178fb5..1586f5e3b9 100644 --- a/src/kernel/lmm/maxmin.cpp +++ b/src/kernel/lmm/maxmin.cpp @@ -1,32 +1,27 @@ -/* Copyright (c) 2004-2019. The SimGrid Team. All rights reserved. */ +/* Copyright (c) 2004-2021. 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/kernel/lmm/maxmin.hpp" -#include "src/surf/surf_interface.hpp" -#include "xbt/backtrace.hpp" +#include +#include XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf, "Logging specific to SURF (maxmin)"); -double sg_maxmin_precision = 0.00001; /* Change this with --cfg=maxmin/precision:VALUE */ -double sg_surf_precision = 0.00001; /* Change this with --cfg=surf/precision:VALUE */ +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 */ int sg_concurrency_limit = -1; /* Change this with --cfg=maxmin/concurrency-limit:VALUE */ namespace simgrid { namespace kernel { namespace lmm { -typedef std::vector dyn_light_t; +using dyn_light_t = std::vector; int Variable::next_rank_ = 1; int Constraint::next_rank_ = 1; -System* make_new_maxmin_system(bool selective_update) -{ - return new System(selective_update); -} - int Element::get_concurrency() const { // Ignore element with weight less than one (e.g. cross-traffic) @@ -88,9 +83,9 @@ void System::check_concurrency() const continue; const Element& elem = var.cnsts_[0]; - int belong_to_enabled = elem.enabled_element_set_hook.is_linked(); - int belong_to_disabled = elem.disabled_element_set_hook.is_linked(); - int belong_to_active = elem.active_element_set_hook.is_linked(); + bool belong_to_enabled = elem.enabled_element_set_hook.is_linked(); + bool belong_to_disabled = elem.disabled_element_set_hook.is_linked(); + bool belong_to_active = elem.active_element_set_hook.is_linked(); for (Element const& elem2 : var.cnsts_) { xbt_assert(belong_to_enabled == elem2.enabled_element_set_hook.is_linked(), @@ -122,8 +117,7 @@ void System::var_free(Variable* var) simgrid::xbt::intrusive_erase(elem.constraint->disabled_element_set_, elem); if (elem.active_element_set_hook.is_linked()) simgrid::xbt::intrusive_erase(elem.constraint->active_element_set_, elem); - int nelements = elem.constraint->enabled_element_set_.size() + elem.constraint->disabled_element_set_.size(); - if (nelements == 0) + if (elem.constraint->enabled_element_set_.empty() && elem.constraint->disabled_element_set_.empty()) make_constraint_inactive(elem.constraint); else on_disabled_var(elem.constraint); @@ -142,25 +136,21 @@ System::System(bool selective_update) : selective_update_active(selective_update XBT_DEBUG("Setting selective_update_active flag to %d", selective_update_active); if (selective_update) - modified_set_ = new kernel::resource::Action::ModifiedSet(); + modified_set_ = std::make_unique(); } System::~System() { - Variable* var; - Constraint* cnst; - - while ((var = extract_variable())) { - auto demangled = simgrid::xbt::demangle(var->id_ ? typeid(*var->id_).name() : "(unidentified)"); - XBT_WARN("Probable bug: a %s variable (#%d) not removed before the LMM system destruction.", demangled.get(), + 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_); var_free(var); } - while ((cnst = extract_constraint())) + while (Constraint* cnst = extract_constraint()) cnst_free(cnst); xbt_mallocator_free(variable_mallocator_); - delete modified_set_; } void System::cnst_free(Constraint* cnst) @@ -172,22 +162,11 @@ void System::cnst_free(Constraint* cnst) Constraint::Constraint(resource::Resource* id_value, double bound_value) : bound_(bound_value), id_(id_value) { rank_ = next_rank_++; - - remaining_ = 0.0; - usage_ = 0.0; - concurrency_limit_ = sg_concurrency_limit; - concurrency_current_ = 0; - concurrency_maximum_ = 0; - sharing_policy_ = s4u::Link::SharingPolicy::SHARED; - - lambda_ = 0.0; - new_lambda_ = 0.0; - cnst_light_ = nullptr; } Constraint* System::constraint_new(resource::Resource* id, double bound_value) { - Constraint* cnst = new Constraint(id, bound_value); + auto* cnst = new Constraint(id, bound_value); insert_constraint(cnst); return cnst; } @@ -207,7 +186,7 @@ Variable* System::variable_new(resource::Action* id, double sharing_penalty, dou XBT_IN("(sys=%p, id=%p, penalty=%f, bound=%f, num_cons =%zu)", this, id, sharing_penalty, bound, number_of_constraints); - Variable* var = static_cast(xbt_mallocator_get(variable_mallocator_)); + auto* var = static_cast(xbt_mallocator_get(variable_mallocator_)); var->initialize(id, sharing_penalty, bound, number_of_constraints, visited_counter_ - 1); if (sharing_penalty > 0) variable_set.push_front(*var); @@ -226,8 +205,7 @@ void System::variable_free(Variable* var) void System::variable_free_all() { - Variable* var; - while ((var = extract_variable())) + while (Variable* var = extract_variable()) variable_free(var); } @@ -239,7 +217,7 @@ void System::expand(Constraint* cnst, Variable* var, double consumption_weight) // If it does, subtract it from the required slack int current_share = 0; if (var->concurrency_share_ > 1) { - for (Element& elem : var->cnsts_) { + for (const Element& elem : var->cnsts_) { if (elem.constraint == cnst && elem.enabled_element_set_hook.is_linked()) current_share += elem.get_concurrency(); } @@ -258,14 +236,14 @@ void System::expand(Constraint* cnst, Variable* var, double consumption_weight) xbt_assert(var->cnsts_.size() < var->cnsts_.capacity(), "Too much constraints"); - var->cnsts_.resize(var->cnsts_.size() + 1); + var->cnsts_.emplace_back(); Element& elem = var->cnsts_.back(); elem.consumption_weight = consumption_weight; elem.constraint = cnst; elem.variable = var; - if (var->sharing_penalty_) { + if (var->sharing_penalty_ != 0.0) { elem.constraint->enabled_element_set_.push_front(elem); elem.increase_concurrency(); } else @@ -295,16 +273,16 @@ void System::expand_add(Constraint* cnst, Variable* var, double value) 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_) + if (var->sharing_penalty_ != 0.0) elem.decrease_concurrency(); - if (cnst->sharing_policy_ != s4u::Link::SharingPolicy::FATPIPE) + 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_) { + if (var->sharing_penalty_ != 0.0) { if (cnst->get_concurrency_slack() < elem.get_concurrency()) { double penalty = var->sharing_penalty_; disable_var(var); @@ -357,7 +335,7 @@ Variable* Constraint::get_variable(const Element** elem) const // if we modify the list between calls, normal version may loop forever // this safe version ensures that we browse the list elements only once -Variable* Constraint::get_variable_safe(const Element** elem, const Element** nextelem, int* numelem) const +Variable* Constraint::get_variable_safe(const Element** elem, const Element** nextelem, size_t* numelem) const { if (*elem == nullptr) { *numelem = enabled_element_set_.size() + disabled_element_set_.size() - 1; @@ -408,13 +386,13 @@ static inline void saturated_constraints_update(double usage, int cnst_light_num } } -static inline void saturated_variable_set_update(ConstraintLight* cnst_light_tab, +static inline void saturated_variable_set_update(const ConstraintLight* cnst_light_tab, const dyn_light_t& saturated_constraints, System* sys) { /* Add active variables (i.e. variables that need to be set) from the set of constraints to saturate * (cnst_light_tab)*/ for (int const& saturated_cnst : saturated_constraints) { - ConstraintLight& cnst = cnst_light_tab[saturated_cnst]; + const ConstraintLight& cnst = cnst_light_tab[saturated_cnst]; for (Element const& elem : cnst.cnst->active_element_set_) { xbt_assert(elem.variable->sharing_penalty_ > 0); // All elements of active_element_set should be active if (elem.consumption_weight > 0 && not elem.variable->saturated_variable_set_hook_.is_linked()) @@ -424,14 +402,14 @@ static inline void saturated_variable_set_update(ConstraintLight* cnst_light_tab } template -static void format_element_list(const ElemList& elem_list, s4u::Link::SharingPolicy sharing_policy, double& sum, +static void format_element_list(const ElemList& elem_list, Constraint::SharingPolicy sharing_policy, double& sum, std::string& buf) { for (Element const& elem : elem_list) { buf += std::to_string(elem.consumption_weight) + ".'" + std::to_string(elem.variable->rank_) + "'(" + std::to_string(elem.variable->value_) + ")" + - (sharing_policy != s4u::Link::SharingPolicy::FATPIPE ? " + " : " , "); - if (sharing_policy != s4u::Link::SharingPolicy::FATPIPE) + (sharing_policy != Constraint::SharingPolicy::FATPIPE ? " + " : " , "); + if (sharing_policy != Constraint::SharingPolicy::FATPIPE) sum += elem.consumption_weight * elem.variable->value_; else sum = std::max(sum, elem.consumption_weight * elem.variable->value_); @@ -440,7 +418,7 @@ static void format_element_list(const ElemList& elem_list, s4u::Link::SharingPol void System::print() const { - std::string buf = std::string("MAX-MIN ( "); + std::string buf = "MAX-MIN ( "; /* Printing Objective */ for (Variable const& var : variable_set) @@ -455,14 +433,14 @@ void System::print() const double sum = 0.0; // Show the enabled variables buf += "\t"; - buf += cnst.sharing_policy_ != s4u::Link::SharingPolicy::FATPIPE ? "(" : "max("; + buf += cnst.sharing_policy_ != Constraint::SharingPolicy::FATPIPE ? "(" : "max("; format_element_list(cnst.enabled_element_set_, cnst.sharing_policy_, sum, buf); // TODO: Adding disabled elements only for test compatibility, but do we really want them to be printed? format_element_list(cnst.disabled_element_set_, cnst.sharing_policy_, sum, buf); buf += "0) <= " + std::to_string(cnst.bound_) + " ('" + std::to_string(cnst.rank_) + "')"; - if (cnst.sharing_policy_ == s4u::Link::SharingPolicy::FATPIPE) { + if (cnst.sharing_policy_ == Constraint::SharingPolicy::FATPIPE) { buf += " [MAX-Constraint]"; } XBT_DEBUG("%s", buf.c_str()); @@ -512,21 +490,25 @@ template void System::lmm_solve(CnstList& cnst_list) for (Constraint& cnst : cnst_list) { /* INIT: Collect constraints that actually need to be saturated (i.e remaining and usage are strictly positive) * into cnst_light_tab. */ - cnst.remaining_ = cnst.bound_; - if (not double_positive(cnst.remaining_, cnst.bound_ * sg_maxmin_precision)) + cnst.dynamic_bound_ = cnst.bound_; + if (cnst.get_sharing_policy() == Constraint::SharingPolicy::NONLINEAR && cnst.dyn_constraint_cb_) { + cnst.dynamic_bound_ = cnst.dyn_constraint_cb_(cnst.bound_, cnst.concurrency_current_); + } + cnst.remaining_ = cnst.dynamic_bound_; + if (not double_positive(cnst.remaining_, cnst.dynamic_bound_ * sg_maxmin_precision)) continue; cnst.usage_ = 0; for (Element& elem : cnst.enabled_element_set_) { xbt_assert(elem.variable->sharing_penalty_ > 0.0); elem.variable->value_ = 0.0; if (elem.consumption_weight > 0) { - if (cnst.sharing_policy_ != s4u::Link::SharingPolicy::FATPIPE) + if (cnst.sharing_policy_ != Constraint::SharingPolicy::FATPIPE) cnst.usage_ += elem.consumption_weight / elem.variable->sharing_penalty_; else if (cnst.usage_ < elem.consumption_weight / elem.variable->sharing_penalty_) cnst.usage_ = elem.consumption_weight / elem.variable->sharing_penalty_; elem.make_active(); - resource::Action* action = static_cast(elem.variable->id_); + resource::Action* action = elem.variable->id_; if (modified_set_ && not action->is_within_modified_set()) modified_set_->push_back(*action); } @@ -593,17 +575,18 @@ template void System::lmm_solve(CnstList& cnst_list) /* Update the usage of constraints where this variable is involved */ for (Element& elem : var.cnsts_) { Constraint* cnst = elem.constraint; - if (cnst->sharing_policy_ != s4u::Link::SharingPolicy::FATPIPE) { + if (cnst->sharing_policy_ != Constraint::SharingPolicy::FATPIPE) { // Remember: shared constraints require that sum(elem.value * var.value) < cnst->bound - double_update(&(cnst->remaining_), elem.consumption_weight * var.value_, cnst->bound_ * sg_maxmin_precision); + double_update(&(cnst->remaining_), elem.consumption_weight * var.value_, + cnst->dynamic_bound_ * sg_maxmin_precision); double_update(&(cnst->usage_), elem.consumption_weight / var.sharing_penalty_, sg_maxmin_precision); // If the constraint is saturated, remove it from the set of active constraints (light_tab) if (not double_positive(cnst->usage_, sg_maxmin_precision) || - not double_positive(cnst->remaining_, cnst->bound_ * sg_maxmin_precision)) { + not double_positive(cnst->remaining_, cnst->dynamic_bound_ * sg_maxmin_precision)) { if (cnst->cnst_light_) { - int index = (cnst->cnst_light_ - cnst_light_tab); - XBT_DEBUG("index: %d \t cnst_light_num: %d \t || usage: %f remaining: %f bound: %f ", index, - cnst_light_num, cnst->usage_, cnst->remaining_, cnst->bound_); + size_t index = (cnst->cnst_light_ - cnst_light_tab); + XBT_DEBUG("index: %zu \t cnst_light_num: %d \t || usage: %f remaining: %f bound: %f ", index, + cnst_light_num, cnst->usage_, cnst->remaining_, cnst->dynamic_bound_); cnst_light_tab[index] = cnst_light_tab[cnst_light_num - 1]; cnst_light_tab[index].cnst->cnst_light_ = &cnst_light_tab[index]; cnst_light_num--; @@ -619,7 +602,7 @@ template void System::lmm_solve(CnstList& cnst_list) // Remember: non-shared constraints only require that max(elem.value * var.value) < cnst->bound cnst->usage_ = 0.0; elem.make_inactive(); - for (Element& elem2 : cnst->enabled_element_set_) { + for (const Element& elem2 : cnst->enabled_element_set_) { xbt_assert(elem2.variable->sharing_penalty_ > 0); if (elem2.variable->value_ > 0) continue; @@ -628,13 +611,13 @@ template void System::lmm_solve(CnstList& cnst_list) } // If the constraint is saturated, remove it from the set of active constraints (light_tab) if (not double_positive(cnst->usage_, sg_maxmin_precision) || - not double_positive(cnst->remaining_, cnst->bound_ * sg_maxmin_precision)) { + not double_positive(cnst->remaining_, cnst->dynamic_bound_ * sg_maxmin_precision)) { if (cnst->cnst_light_) { - int index = (cnst->cnst_light_ - cnst_light_tab); - XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p " + size_t index = (cnst->cnst_light_ - cnst_light_tab); + XBT_DEBUG("index: %zu \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p " "\t cnst_light_tab: %p usage: %f remaining: %f bound: %f ", index, cnst_light_num, cnst, cnst->cnst_light_, cnst_light_tab, cnst->usage_, cnst->remaining_, - cnst->bound_); + cnst->dynamic_bound_); cnst_light_tab[index] = cnst_light_tab[cnst_light_num - 1]; cnst_light_tab[index].cnst->cnst_light_ = &cnst_light_tab[index]; cnst_light_num--; @@ -657,8 +640,7 @@ template void System::lmm_solve(CnstList& cnst_list) min_usage = -1; min_bound = -1; saturated_constraints.clear(); - int pos; - for (pos = 0; pos < cnst_light_num; pos++) { + for (int pos = 0; pos < cnst_light_num; pos++) { xbt_assert(not cnst_light_tab[pos].cnst->active_element_set_.empty(), "Cannot saturate more a constraint that has" " no active element! You may want to change the maxmin precision (--cfg=maxmin/precision:)" @@ -669,7 +651,6 @@ template void System::lmm_solve(CnstList& cnst_list) } saturated_variable_set_update(cnst_light_tab, saturated_constraints, this); - } while (cnst_light_num > 0); modified_ = false; @@ -681,7 +662,6 @@ template void System::lmm_solve(CnstList& cnst_list) } check_concurrency(); - } /** @brief Attribute the value bound to var->bound. @@ -702,7 +682,7 @@ void System::update_variable_bound(Variable* var, double bound) } void Variable::initialize(resource::Action* id_value, double sharing_penalty, double bound_value, - int number_of_constraints, unsigned visited_value) + size_t number_of_constraints, unsigned visited_value) { id_ = id_value; rank_ = next_rank_++; @@ -798,15 +778,14 @@ void System::on_disabled_var(Constraint* cnstr) if (cnstr->get_concurrency_limit() < 0) return; - int numelem = cnstr->disabled_element_set_.size(); - if (not numelem) + size_t numelem = cnstr->disabled_element_set_.size(); + if (numelem == 0) return; Element* elem = &cnstr->disabled_element_set_.front(); // Cannot use foreach loop, because System::enable_var() will modify disabled_element_set.. within the loop while (numelem-- && elem) { - Element* nextelem; if (elem->disabled_element_set_hook.is_linked()) { auto iter = std::next(cnstr->disabled_element_set_.iterator_to(*elem)); @@ -842,8 +821,8 @@ void System::update_variable_penalty(Variable* var, double penalty) if (penalty == var->sharing_penalty_) return; - int enabling_var = (penalty > 0 && var->sharing_penalty_ <= 0); - int disabling_var = (penalty <= 0 && var->sharing_penalty_ > 0); + bool enabling_var = (penalty > 0 && var->sharing_penalty_ <= 0); + bool disabling_var = (penalty <= 0 && var->sharing_penalty_ > 0); XBT_IN("(sys=%p, var=%p, penalty=%f)", this, var, penalty); @@ -887,7 +866,7 @@ void System::update_constraint_bound(Constraint* cnst, double bound) * A recursive algorithm to optimize the system recalculation selecting only constraints that have changed. Each * constraint change is propagated to the list of constraints for each variable. */ -void System::update_modified_set_rec(Constraint* cnst) +void System::update_modified_set_rec(const Constraint* cnst) { for (Element const& elem : cnst->enabled_element_set_) { Variable* var = elem.variable; @@ -940,7 +919,7 @@ void System::remove_all_modified_set() double Constraint::get_usage() const { double result = 0.0; - if (sharing_policy_ != s4u::Link::SharingPolicy::FATPIPE) { + if (sharing_policy_ != SharingPolicy::FATPIPE) { for (Element const& elem : enabled_element_set_) if (elem.consumption_weight > 0) result += elem.consumption_weight * elem.variable->value_; @@ -954,9 +933,18 @@ double Constraint::get_usage() const int Constraint::get_variable_amount() const { - return std::count_if(std::begin(enabled_element_set_), std::end(enabled_element_set_), - [](const Element& elem) { return elem.consumption_weight > 0; }); -} -} + 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, + "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