X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/a7b730f954add6f47db2cae39946e333114fbe82..47950eebfede4e41862022469d15e5e4fe19c7ba:/src/kernel/lmm/maxmin.cpp?ds=sidebyside diff --git a/src/kernel/lmm/maxmin.cpp b/src/kernel/lmm/maxmin.cpp index 6e02aa2387..96cc184dac 100644 --- a/src/kernel/lmm/maxmin.cpp +++ b/src/kernel/lmm/maxmin.cpp @@ -31,7 +31,7 @@ int Element::get_concurrency() const { // 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 behaviour of the model.. + // There are other alternatives, but they will change the behavior of the model.. // So do not use it unless you want to make a new model. // If you do, remember to change the variables concurrency share to reflect it. // Potential examples are: @@ -66,13 +66,13 @@ void System::check_concurrency() const for (Constraint const& cnst : constraint_set) { int concurrency = 0; for (Element const& elem : cnst.enabled_element_set_) { - xbt_assert(elem.variable->sharing_weight_ > 0); + xbt_assert(elem.variable->sharing_penalty_ > 0); concurrency += elem.get_concurrency(); } 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_weight_ == 0 || + xbt_assert(cnst.get_concurrency_limit() < 0 || elem.variable->staged_penalty_ == 0 || elem.variable->get_min_concurrency_slack() < elem.variable->concurrency_share_, "should not have staged variable!"); } @@ -114,7 +114,7 @@ void System::var_free(Variable* var) update_modified_set(var->cnsts_[0].constraint); for (Element& elem : var->cnsts_) { - if (var->sharing_weight_ > 0) + if (var->sharing_penalty_ > 0) elem.decrease_concurrency(); if (elem.enabled_element_set_hook.is_linked()) simgrid::xbt::intrusive_erase(elem.constraint->enabled_element_set_, elem); @@ -151,7 +151,7 @@ System::~System() Constraint* cnst; while ((var = extract_variable())) { - auto demangled = simgrid::xbt::demangle(typeid(*var->id_).name()); + 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(), var->rank_); var_free(var); @@ -169,7 +169,7 @@ void System::cnst_free(Constraint* cnst) delete cnst; } -Constraint::Constraint(void* id_value, double bound_value) : bound_(bound_value), id_(id_value) +Constraint::Constraint(resource::Resource* id_value, double bound_value) : bound_(bound_value), id_(id_value) { rank_ = next_rank_++; @@ -185,7 +185,7 @@ Constraint::Constraint(void* id_value, double bound_value) : bound_(bound_value) cnst_light_ = nullptr; } -Constraint* System::constraint_new(void* id, double bound_value) +Constraint* System::constraint_new(resource::Resource* id, double bound_value) { Constraint* cnst = new Constraint(id, bound_value); insert_constraint(cnst); @@ -202,13 +202,14 @@ void System::variable_mallocator_free_f(void* var) delete static_cast(var); } -Variable* System::variable_new(resource::Action* id, double sharing_weight, double bound, size_t number_of_constraints) +Variable* System::variable_new(resource::Action* id, double sharing_penalty, double bound, size_t number_of_constraints) { - XBT_IN("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%zu)", this, id, sharing_weight, bound, number_of_constraints); + 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_)); - var->initialize(id, sharing_weight, bound, number_of_constraints, visited_counter_ - 1); - if (sharing_weight > 0) + var->initialize(id, sharing_penalty, bound, number_of_constraints, visited_counter_ - 1); + if (sharing_penalty > 0) variable_set.push_front(*var); else variable_set.push_back(*var); @@ -223,12 +224,19 @@ void System::variable_free(Variable* var) var_free(var); } +void System::variable_free_all() +{ + Variable* var; + while ((var = extract_variable())) + variable_free(var); +} + void System::expand(Constraint* cnst, Variable* var, double consumption_weight) { modified_ = true; // Check if this variable already has an active element in this constraint - // If it does, substract it from the required slack + // If it does, subtract it from the required slack int current_share = 0; if (var->concurrency_share_ > 1) { for (Element& elem : var->cnsts_) { @@ -238,14 +246,14 @@ void System::expand(Constraint* cnst, Variable* var, double consumption_weight) } // Check if we need to disable the variable - if (var->sharing_weight_ > 0 && var->concurrency_share_ - current_share > cnst->get_concurrency_slack()) { - double weight = var->sharing_weight_; + 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_weight_ = weight; - xbt_assert(not var->sharing_weight_); + var->staged_penalty_ = penalty; + xbt_assert(not var->sharing_penalty_); } xbt_assert(var->cnsts_.size() < var->cnsts_.capacity(), "Too much constraints"); @@ -257,7 +265,7 @@ void System::expand(Constraint* cnst, Variable* var, double consumption_weight) elem.constraint = cnst; elem.variable = var; - if (var->sharing_weight_) { + if (var->sharing_penalty_) { elem.constraint->enabled_element_set_.push_front(elem); elem.increase_concurrency(); } else @@ -265,7 +273,7 @@ void System::expand(Constraint* cnst, Variable* var, double consumption_weight) if (not selective_update_active) { make_constraint_active(cnst); - } else if (elem.consumption_weight > 0 || var->sharing_weight_ > 0) { + } else if (elem.consumption_weight > 0 || var->sharing_penalty_ > 0) { make_constraint_active(cnst); update_modified_set(cnst); // TODOLATER: Why do we need this second call? @@ -287,7 +295,7 @@ 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_weight_) + if (var->sharing_penalty_) elem.decrease_concurrency(); if (cnst->sharing_policy_ != s4u::Link::SharingPolicy::FATPIPE) @@ -296,14 +304,14 @@ void System::expand_add(Constraint* cnst, Variable* var, double value) 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_weight_) { + if (var->sharing_penalty_) { if (cnst->get_concurrency_slack() < elem.get_concurrency()) { - double weight = var->sharing_weight_; + double penalty = var->sharing_penalty_; disable_var(var); for (Element const& elem2 : var->cnsts_) on_disabled_var(elem2.constraint); - var->staged_weight_ = weight; - xbt_assert(not var->sharing_weight_); + var->staged_penalty_ = penalty; + xbt_assert(not var->sharing_penalty_); } elem.increase_concurrency(); } @@ -408,8 +416,7 @@ static inline void saturated_variable_set_update(ConstraintLight* cnst_light_tab for (int const& saturated_cnst : saturated_constraints) { ConstraintLight& cnst = cnst_light_tab[saturated_cnst]; for (Element const& elem : cnst.cnst->active_element_set_) { - // Visiting active_element_set, so, by construction, should never get a zero weight, correct? - xbt_assert(elem.variable->sharing_weight_ > 0); + 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()) sys->saturated_variable_set.push_back(*elem.variable); } @@ -437,7 +444,7 @@ void System::print() const /* Printing Objective */ for (Variable const& var : variable_set) - buf += "'" + std::to_string(var.rank_) + "'(" + std::to_string(var.sharing_weight_) + ") "; + buf += "'" + std::to_string(var.rank_) + "'(" + std::to_string(var.sharing_penalty_) + ") "; buf += ")"; XBT_DEBUG("%20s", buf.c_str()); buf.clear(); @@ -468,11 +475,11 @@ void System::print() const /* Printing Result */ for (Variable const& var : variable_set) { if (var.bound_ > 0) { - XBT_DEBUG("'%d'(%f) : %f (<=%f)", var.rank_, var.sharing_weight_, var.value_, var.bound_); + 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), "Incorrect value (%f is not smaller than %f", var.value_, var.bound_); } else { - XBT_DEBUG("'%d'(%f) : %f", var.rank_, var.sharing_weight_, var.value_); + XBT_DEBUG("'%d'(%f) : %f", var.rank_, var.sharing_penalty_, var.value_); } } } @@ -498,17 +505,9 @@ template void System::lmm_solve(CnstList& cnst_list) double min_bound = -1; XBT_DEBUG("Active constraints : %zu", cnst_list.size()); - /* Init: Only modified code portions: reset the value of active variables */ - for (Constraint const& cnst : cnst_list) { - for (Element const& elem : cnst.enabled_element_set_) { - xbt_assert(elem.variable->sharing_weight_ > 0.0); - elem.variable->value_ = 0.0; - } - } - - ConstraintLight* cnst_light_tab = new ConstraintLight[cnst_list.size()](); + cnst_light_vec.reserve(cnst_list.size()); + ConstraintLight* cnst_light_tab = cnst_light_vec.data(); int cnst_light_num = 0; - dyn_light_t saturated_constraints; for (Constraint& cnst : cnst_list) { /* INIT: Collect constraints that actually need to be saturated (i.e remaining and usage are strictly positive) @@ -518,12 +517,13 @@ template void System::lmm_solve(CnstList& cnst_list) continue; cnst.usage_ = 0; for (Element& elem : cnst.enabled_element_set_) { - xbt_assert(elem.variable->sharing_weight_ > 0); + 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) - cnst.usage_ += elem.consumption_weight / elem.variable->sharing_weight_; - else if (cnst.usage_ < elem.consumption_weight / elem.variable->sharing_weight_) - cnst.usage_ = elem.consumption_weight / elem.variable->sharing_weight_; + 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_); @@ -554,16 +554,16 @@ template void System::lmm_solve(CnstList& cnst_list) /* Fix the variables that have to be */ auto& var_list = saturated_variable_set; for (Variable const& var : var_list) { - if (var.sharing_weight_ <= 0.0) + if (var.sharing_penalty_ <= 0.0) DIE_IMPOSSIBLE; /* First check if some of these variables could reach their upper bound and update min_bound accordingly. */ - XBT_DEBUG("var=%d, var.bound=%f, var.weight=%f, min_usage=%f, var.bound*var.weight=%f", var.rank_, var.bound_, - var.sharing_weight_, min_usage, var.bound_ * var.sharing_weight_); - if ((var.bound_ > 0) && (var.bound_ * var.sharing_weight_ < min_usage)) { + XBT_DEBUG("var=%d, var.bound=%f, var.penalty=%f, min_usage=%f, var.bound*var.penalty=%f", var.rank_, var.bound_, + var.sharing_penalty_, min_usage, var.bound_ * var.sharing_penalty_); + if ((var.bound_ > 0) && (var.bound_ * var.sharing_penalty_ < min_usage)) { if (min_bound < 0) - min_bound = var.bound_ * var.sharing_weight_; + min_bound = var.bound_ * var.sharing_penalty_; else - min_bound = std::min(min_bound, (var.bound_ * var.sharing_weight_)); + min_bound = std::min(min_bound, (var.bound_ * var.sharing_penalty_)); XBT_DEBUG("Updated min_bound=%f", min_bound); } } @@ -573,11 +573,11 @@ template void System::lmm_solve(CnstList& cnst_list) if (min_bound < 0) { // If no variable could reach its bound, deal iteratively the constraints usage ( at worst one constraint is // saturated at each cycle) - var.value_ = min_usage / var.sharing_weight_; + var.value_ = min_usage / var.sharing_penalty_; XBT_DEBUG("Setting var (%d) value to %f\n", var.rank_, var.value_); } else { // If there exist a variable that can reach its bound, only update it (and other with the same bound) for now. - if (double_equals(min_bound, var.bound_ * var.sharing_weight_, sg_maxmin_precision)) { + if (double_equals(min_bound, var.bound_ * var.sharing_penalty_, sg_maxmin_precision)) { var.value_ = var.bound_; XBT_DEBUG("Setting %p (%d) value to %f\n", &var, var.rank_, var.value_); } else { @@ -587,16 +587,16 @@ template void System::lmm_solve(CnstList& cnst_list) continue; } } - XBT_DEBUG("Min usage: %f, Var(%d).weight: %f, Var(%d).value: %f ", min_usage, var.rank_, var.sharing_weight_, + 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 contraints where this variable is involved */ + /* 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) { // 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->usage_), elem.consumption_weight / var.sharing_weight_, 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)) { @@ -610,7 +610,9 @@ template void System::lmm_solve(CnstList& cnst_list) cnst->cnst_light_ = nullptr; } } else { - cnst->cnst_light_->remaining_over_usage = cnst->remaining_ / cnst->usage_; + if (cnst->cnst_light_) { + cnst->cnst_light_->remaining_over_usage = cnst->remaining_ / cnst->usage_; + } } elem.make_inactive(); } else { @@ -618,11 +620,11 @@ template void System::lmm_solve(CnstList& cnst_list) cnst->usage_ = 0.0; elem.make_inactive(); for (Element& elem2 : cnst->enabled_element_set_) { - xbt_assert(elem2.variable->sharing_weight_ > 0); + xbt_assert(elem2.variable->sharing_penalty_ > 0); if (elem2.variable->value_ > 0) continue; if (elem2.consumption_weight > 0) - cnst->usage_ = std::max(cnst->usage_, elem2.consumption_weight / elem2.variable->sharing_weight_); + cnst->usage_ = std::max(cnst->usage_, elem2.consumption_weight / elem2.variable->sharing_penalty_); } // If the constraint is saturated, remove it from the set of active constraints (light_tab) if (not double_positive(cnst->usage_, sg_maxmin_precision) || @@ -639,10 +641,12 @@ template void System::lmm_solve(CnstList& cnst_list) cnst->cnst_light_ = nullptr; } } else { - cnst->cnst_light_->remaining_over_usage = cnst->remaining_ / cnst->usage_; - xbt_assert(not cnst->active_element_set_.empty(), - "Should not keep a maximum constraint that has no active" - " element! You want to check the maxmin precision and possible rounding effects."); + if (cnst->cnst_light_) { + cnst->cnst_light_->remaining_over_usage = cnst->remaining_ / cnst->usage_; + xbt_assert(not cnst->active_element_set_.empty(), + "Should not keep a maximum constraint that has no active" + " element! You want to check the maxmin precision and possible rounding effects."); + } } } } @@ -665,7 +669,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; @@ -677,8 +680,6 @@ template void System::lmm_solve(CnstList& cnst_list) } check_concurrency(); - - delete[] cnst_light_tab; } /** @brief Attribute the value bound to var->bound. @@ -698,20 +699,19 @@ void System::update_variable_bound(Variable* var, double bound) update_modified_set(var->cnsts_[0].constraint); } -void Variable::initialize(resource::Action* id_value, double sharing_weight_value, double bound_value, +void Variable::initialize(resource::Action* id_value, double sharing_penalty, double bound_value, int number_of_constraints, unsigned visited_value) { id_ = id_value; rank_ = next_rank_++; cnsts_.reserve(number_of_constraints); - sharing_weight_ = sharing_weight_value; - staged_weight_ = 0.0; + sharing_penalty_ = sharing_penalty; + staged_penalty_ = 0.0; bound_ = bound_value; concurrency_share_ = 1; value_ = 0.0; visited_ = visited_value; mu_ = 0.0; - new_mu_ = 0.0; xbt_assert(not variable_set_hook_.is_linked()); xbt_assert(not saturated_variable_set_hook_.is_linked()); @@ -740,8 +740,8 @@ void System::enable_var(Variable* var) { xbt_assert(not XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug) || var->can_enable()); - var->sharing_weight_ = var->staged_weight_; - var->staged_weight_ = 0; + var->sharing_penalty_ = var->staged_penalty_; + var->staged_penalty_ = 0; // Enabling the variable, move var to list head. Subtlety is: here, we need to call update_modified_set AFTER // moving at least one element of var. @@ -763,7 +763,7 @@ void System::enable_var(Variable* var) void System::disable_var(Variable* var) { - xbt_assert(not var->staged_weight_, "Staged weight should have been cleared"); + xbt_assert(not var->staged_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_set // BEFORE moving the last element of var. simgrid::xbt::intrusive_erase(variable_set, *var); @@ -778,15 +778,15 @@ void System::disable_var(Variable* var) elem.decrease_concurrency(); } - var->sharing_weight_ = 0.0; - var->staged_weight_ = 0.0; + var->sharing_penalty_ = 0.0; + var->staged_penalty_ = 0.0; var->value_ = 0.0; check_concurrency(); } /* /brief Find variables that can be enabled and enable them. * - * Assuming that the variable has already been removed from non-zero weights + * Assuming that the variable has already been removed from non-zero penalties * Can we find a staged variable to add? * If yes, check that none of the constraints that this variable is involved in is at the limit of its concurrency * And then add it to enabled variables @@ -804,7 +804,6 @@ void System::on_disabled_var(Constraint* cnstr) // 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)); @@ -813,7 +812,7 @@ void System::on_disabled_var(Constraint* cnstr) nextelem = nullptr; } - if (elem->variable->staged_weight_ > 0 && elem->variable->can_enable()) { + if (elem->variable->staged_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? @@ -832,40 +831,37 @@ void System::on_disabled_var(Constraint* cnstr) // Anyway, caller functions all call check_concurrency() in the end. } -/* @brief update the weight of a variable, and enable/disable it. - * @return Returns whether a change was made - */ -void System::update_variable_weight(Variable* var, double weight) +/** @brief update the penalty of a variable (disable it by passing 0 as a penalty) */ +void System::update_variable_penalty(Variable* var, double penalty) { - xbt_assert(weight >= 0, "Variable weight should not be negative!"); + xbt_assert(penalty >= 0, "Variable penalty should not be negative!"); - if (weight == var->sharing_weight_) + if (penalty == var->sharing_penalty_) return; - int enabling_var = (weight > 0 && var->sharing_weight_ <= 0); - int disabling_var = (weight <= 0 && var->sharing_weight_ > 0); + int enabling_var = (penalty > 0 && var->sharing_penalty_ <= 0); + int disabling_var = (penalty <= 0 && var->sharing_penalty_ > 0); - XBT_IN("(sys=%p, var=%p, weight=%f)", this, var, weight); + XBT_IN("(sys=%p, var=%p, penalty=%f)", this, var, penalty); modified_ = true; // Are we enabling this variable? if (enabling_var) { - var->staged_weight_ = weight; + var->staged_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 weight %f and concurrency" + XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with penalty %f and concurrency" " share %i", - minslack, weight, var->concurrency_share_); + minslack, penalty, var->concurrency_share_); return; } XBT_DEBUG("Enabling var with min concurrency slack %i", minslack); enable_var(var); } else if (disabling_var) { - // Are we disabling this variable? disable_var(var); } else { - var->sharing_weight_ = weight; + var->sharing_penalty_ = penalty; } check_concurrency(); @@ -920,7 +916,7 @@ void System::remove_all_modified_set() // In effect, the var->visited value will no more be equal to visited counter // To be clean, when visited counter has wrapped around, we force these var->visited values so that variables that // were in the modified a long long time ago are not wrongly skipped here, which would lead to very nasty bugs - // (i.e. not readibily reproducible, and requiring a lot of run time before happening). + // (i.e. not readily reproducible, and requiring a lot of run time before happening). if (++visited_counter_ == 1) { /* the counter wrapped around, reset each variable->visited */ for (Variable& var : variable_set) @@ -958,6 +954,7 @@ 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; }); } -} -} -} + +} // namespace lmm +} // namespace kernel +} // namespace simgrid