X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/cff982bd049d26d7acbd0e23324e0de051b06d0d..f9b13d923d31bb0336aeeaab6d5b7ba33812f3f7:/src/kernel/lmm/maxmin.cpp diff --git a/src/kernel/lmm/maxmin.cpp b/src/kernel/lmm/maxmin.cpp index ebbd7a2438..485159d1d6 100644 --- a/src/kernel/lmm/maxmin.cpp +++ b/src/kernel/lmm/maxmin.cpp @@ -1,12 +1,13 @@ -/* Copyright (c) 2004-2020. The SimGrid Team. All rights reserved. */ +/* Copyright (c) 2004-2022. 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 "xbt/backtrace.hpp" +#include +#include -XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf, "Logging specific to SURF (maxmin)"); +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 */ @@ -54,7 +55,7 @@ void Element::increase_concurrency() void System::check_concurrency() const { // These checks are very expensive, so do them only if we want to debug SURF LMM - if (not XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) + if (not XBT_LOG_ISENABLED(ker_lmm, xbt_log_priority_debug)) return; for (Constraint const& cnst : constraint_set) { @@ -116,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); @@ -141,16 +141,13 @@ System::System(bool selective_update) : selective_update_active(selective_update 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_); @@ -208,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); } @@ -240,7 +236,7 @@ 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; @@ -280,7 +276,7 @@ void System::expand_add(Constraint* cnst, Variable* var, double value) 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); @@ -339,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; @@ -406,14 +402,14 @@ static inline void saturated_variable_set_update(const ConstraintLight* cnst_lig } 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_); @@ -437,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()); @@ -494,15 +490,19 @@ 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_; @@ -564,28 +564,29 @@ template void System::lmm_solve(CnstList& cnst_list) XBT_DEBUG("Setting %p (%d) value to %f\n", &var, var.rank_, var.value_); } else { // Variables which bound is different are not considered for this cycle, but they will be afterwards. - XBT_DEBUG("Do not consider %p (%d) \n", &var, var.rank_); + XBT_DEBUG("Do not consider %p (%d)\n", &var, var.rank_); var_list.pop_front(); continue; } } - XBT_DEBUG("Min usage: %f, Var(%d).penalty: %f, Var(%d).value: %f ", min_usage, var.rank_, var.sharing_penalty_, + XBT_DEBUG("Min usage: %f, Var(%d).penalty: %f, Var(%d).value: %f", min_usage, var.rank_, var.sharing_penalty_, var.rank_, var.value_); /* 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--; @@ -610,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 " - "\t cnst_light_tab: %p usage: %f remaining: %f bound: %f ", + 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--; @@ -656,7 +657,7 @@ template void System::lmm_solve(CnstList& cnst_list) if (selective_update_active) remove_all_modified_set(); - if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { + if (XBT_LOG_ISENABLED(ker_lmm, xbt_log_priority_debug)) { print(); } @@ -681,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_++; @@ -719,7 +720,7 @@ int Variable::get_min_concurrency_slack() const // loops (after doing the first for enabling==1, and before doing the last for disabling==1) void System::enable_var(Variable* var) { - xbt_assert(not XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug) || var->can_enable()); + 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; @@ -777,8 +778,8 @@ 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(); @@ -816,14 +817,13 @@ void System::on_disabled_var(Constraint* cnstr) void System::update_variable_penalty(Variable* var, double penalty) { xbt_assert(penalty >= 0, "Variable penalty should not be negative!"); - if (penalty == var->sharing_penalty_) return; 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); + XBT_IN("(sys=%p, var=%p, var->sharing_penalty = %f, penalty=%f)", this, var, var->sharing_penalty_, penalty); modified_ = true; @@ -843,6 +843,8 @@ void System::update_variable_penalty(Variable* var, double penalty) disable_var(var); } else { var->sharing_penalty_ = penalty; + if (not var->cnsts_.empty()) + update_modified_set(var->cnsts_[0].constraint); } check_concurrency(); @@ -918,7 +920,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_; @@ -936,6 +938,14 @@ int Constraint::get_variable_amount() const [](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