X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/464d34f9d99aad1e50166cea9ed461f46c6099dd..8e70d54a095cd7779a53c7a164f775f7a37b29e5:/src/kernel/lmm/System.hpp diff --git a/src/kernel/lmm/System.hpp b/src/kernel/lmm/System.hpp index 8a414527a1..d83ae01bad 100644 --- a/src/kernel/lmm/System.hpp +++ b/src/kernel/lmm/System.hpp @@ -1,15 +1,14 @@ -/* 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. */ -#ifndef SURF_MAXMIN_HPP -#define SURF_MAXMIN_HPP +#ifndef SIMGRID_KERNEL_LMM_SYSTEM_HPP +#define SIMGRID_KERNEL_LMM_SYSTEM_HPP #include "simgrid/kernel/resource/Action.hpp" #include "simgrid/kernel/resource/Model.hpp" #include "simgrid/s4u/Link.hpp" -#include "src/surf/surf_interface.hpp" #include "xbt/asserts.h" #include "xbt/ex.h" #include "xbt/mallocator.h" @@ -18,11 +17,15 @@ #include #include #include +#include #include -namespace simgrid { -namespace kernel { -namespace lmm { +/* user-visible parameters */ +XBT_PUBLIC_DATA double sg_precision_workamount; +XBT_PUBLIC_DATA double sg_precision_timing; +XBT_PUBLIC_DATA int sg_concurrency_limit; + +namespace simgrid::kernel::lmm { /** @addtogroup SURF_lmm * @details @@ -126,11 +129,12 @@ namespace lmm { * - concurrency_current which is the current concurrency * - concurrency_maximum which is the observed maximum concurrency * - * Variables also have one field related to concurrency: concurrency_share. - * In effect, in some cases, one variable is involved multiple times (i.e. two elements) in a constraint. - * For example, cross-traffic is modeled using 2 elements per constraint. - * concurrency_share formally corresponds to the maximum number of elements that associate the variable and any given - * constraint. + * Variables consumes the concurrency_limit of each constraint they are using. + * Each pair variable/constrainst is linked by a *single* Element object. Through this + * object and the respective methods (get_concurrency(), increase_concurrency() and decrease_concurrency()), + * the variable changes the constraint's concurrency. + * The amount of concurrency slack taken by each variable is determined by the Element::get_concurrency() method. + * At the current state, each variable counts as 1 if its consumption weight is greater than 1. */ /** @{ @ingroup SURF_lmm */ @@ -150,9 +154,25 @@ public: Element(const Element&) = default; ~Element() = default; + /** + * @brief Gets the "weight" of this element for concurrency checks. + * + * This is the amount taken by this variable of the constraint's concurrency slack + * + * @return 1 if consumption_weight greater than 1, 0 otherwise + */ int get_concurrency() const; + /** + * @brief Decreases the constraint's concurrency + * + * Decreases the equivalent of get_concurrency() from the constraint related to this element + */ void decrease_concurrency(); - void increase_concurrency(); + /** + * @brief Increase constraint concurrency + * @param check_limit Don't check constraint concurrency overflow right now + */ + void increase_concurrency(bool check_limit = true); void make_active(); void make_inactive(); @@ -190,7 +210,7 @@ public: */ class XBT_PUBLIC Constraint { public: - enum class SharingPolicy { NONLINEAR = 2, SHARED = 1, FATPIPE = 0 }; + enum class SharingPolicy { WIFI = 3, NONLINEAR = 2, SHARED = 1, FATPIPE = 0 }; Constraint(resource::Resource* id_value, double bound_value); @@ -204,7 +224,6 @@ public: /** @brief Get the usage of the constraint after the last lmm solve */ double get_usage() const; - int get_variable_amount() const; /** @brief Sets the concurrency limit for this constraint */ void set_concurrency_limit(int limit) @@ -232,6 +251,14 @@ public: return concurrency_maximum_; } + /** + * @brief Get constraint current concurrency slack + * + * This represents the "space" available for new variables in this contraint. + * A variable can be enabled and use this constraint if its get_concurrency() <= slack + * + * @return Constraint's slack + */ int get_concurrency_slack() const { return concurrency_limit_ < 0 ? std::numeric_limits::max() : concurrency_limit_ - concurrency_current_; @@ -315,12 +342,6 @@ public: /** @brief Get the maximum value of the variable (-1.0 if no specified maximum) */ double get_bound() const { return bound_; } - /** - * @brief Set the concurrent share of the variable - * @param value The new concurrency share - */ - void set_concurrency_share(short int value) { concurrency_share_ = value; } - /** * @brief Get the numth constraint associated to the variable * @param num The rank of constraint we want to get @@ -353,7 +374,7 @@ public: /** @brief Check if a variable can be enabled * Make sure to set staged_penalty before, if your intent is only to check concurrency */ - bool can_enable() const { return staged_penalty_ > 0 && get_min_concurrency_slack() >= concurrency_share_; } + bool can_enable() const { return staged_sharing_penalty_ > 0 && get_min_concurrency_slack() > 0; } /* hookup to system */ boost::intrusive::list_member_hook<> variable_set_hook_; @@ -367,14 +388,13 @@ public: // on network, the actions with higher latency have a lesser sharing_penalty double sharing_penalty_; - double staged_penalty_; /* If non-zero, variable is staged for addition as soon as maxconcurrency constraints will be - met */ + double staged_sharing_penalty_; /* If non-zero, variable is staged for addition as soon as maxconcurrency constraints + will be met */ double bound_; double value_; - short int concurrency_share_; /* The maximum number of elements that variable will add to a constraint */ resource::Action* id_; int rank_; // Only used in debug messages to identify the variable - unsigned visited_; /* used by System::update_modified_set() */ + unsigned visited_; /* used by System::update_modified_cnst_set() */ double mu_; private: @@ -403,7 +423,7 @@ public: * @param selective_update Enables lazy updates * @return pointer to System instance */ - static System* build(const std::string& solver_name, bool selective_update); + static System* build(std::string_view solver_name, bool selective_update); /** @brief Validates solver configuration */ static void validate_solver(const std::string& solver_name); @@ -432,6 +452,9 @@ public: Variable* variable_new(resource::Action* id, double sharing_penalty, double bound = -1.0, size_t number_of_constraints = 1); + /** @brief Get the list of modified actions since last solve() */ + resource::Action::ModifiedSet* get_modified_action_set() const; + /** * @brief Free a variable * @param var The variable to free @@ -446,16 +469,11 @@ public: * @param cnst A constraint * @param var A variable * @param value The coefficient associated to the variable in the constraint + * @param force_creation Force the creation of new element linking the variable to the constraint. Should be used only + * by the model ptask_L07 to cope with ptasks composed of flows running on the same resource (see + * https://framagit.org/simgrid/simgrid/-/issues/111) */ - void expand(Constraint * cnst, Variable * var, double value); - - /** - * @brief Add value to the coefficient between a constraint and a variable or create one - * @param cnst A constraint - * @param var A variable - * @param value The value to add to the coefficient associated to the variable in the constraint - */ - void expand_add(Constraint * cnst, Variable * var, double value); + void expand(Constraint* cnst, Variable* var, double value, bool force_creation = false); /** @brief Update the bound of a variable */ void update_variable_bound(Variable * var, double bound); @@ -471,15 +489,14 @@ public: /** @brief Print the lmm system */ void print() const; - /** @brief Solve the lmm system */ - void lmm_solve(); - /** @brief Solve the lmm system. May be specialized in subclasses. */ - virtual void solve() { lmm_solve(); } + void solve(); private: static void* variable_mallocator_new_f(); static void variable_mallocator_free_f(void* var); + /** @brief Implements the solver. Must be specialized in subclasses. */ + virtual void do_solve() = 0; void var_free(Variable * var); void cnst_free(Constraint * cnst); @@ -523,6 +540,26 @@ private: void enable_var(Variable * var); void disable_var(Variable * var); void on_disabled_var(Constraint * cnstr); + void check_concurrency() const; + + /** + * @brief Auxiliary method to create a new Element which links a variable to a constraint + * + * @param cnst Constraint (resource) + * @param var Variable (action) + * @param consumption_weight how much of the resource is used for each unit of the action + * @return A reference to the new element + */ + Element& expand_create_elem(Constraint* cnst, Variable* var, double consumption_weight); + /** + * @brief Increments the element usage + * + * @param elem Element linking variable/action to resource + * @param cnst Constraint (resource) + * @param consumption_weight how much of the resource is used for each unit of the action + * @return elem itself + */ + Element& expand_add_to_elem(Element& elem, const Constraint* cnst, double consumption_weight) const; /** * @brief Update the value of element linking the constraint and the variable @@ -532,14 +569,12 @@ private: */ void update(Constraint * cnst, Variable * var, double value); - void update_modified_set(Constraint* cnst); - void update_modified_set_rec(const Constraint* cnst); - + /** @brief Given a variable, update modified_constraint_set_ */ + void update_modified_cnst_set_from_variable(const Variable* var); + void update_modified_cnst_set(Constraint* cnst); + void update_modified_cnst_set_rec(const Constraint* cnst); /** @brief Remove all constraints of the modified_constraint_set. */ - void remove_all_modified_set(); - void check_concurrency() const; - - template void lmm_solve(CnstList& cnst_list); + void remove_all_modified_cnst_set(); public: bool modified_ = false; @@ -556,42 +591,26 @@ public: &Constraint::saturated_constraint_set_hook_>> saturated_constraint_set; - std::unique_ptr modified_set_ = nullptr; - protected: - bool selective_update_active; /* flag to update partially the system only selecting changed portions */ + const bool selective_update_active; /* flag to update partially the system only selecting changed portions */ boost::intrusive::list, &Constraint::modified_constraint_set_hook_>> modified_constraint_set; private: - using dyn_light_t = std::vector; - - //Data used in lmm::solve - std::vector cnst_light_vec; - dyn_light_t saturated_constraints; - - unsigned visited_counter_ = 1; /* used by System::update_modified_set() and System::remove_all_modified_set() to - * cleverly (un-)flag the constraints (more details in these functions) */ + unsigned visited_counter_ = + 1; /* used by System::update_modified_cnst_set() and System::remove_all_modified_cnst_set() to + * cleverly (un-)flag the constraints (more details in these functions) */ boost::intrusive::list, &Constraint::constraint_set_hook_>> constraint_set; xbt_mallocator_t variable_mallocator_ = xbt_mallocator_new(65536, System::variable_mallocator_new_f, System::variable_mallocator_free_f, nullptr); -}; - -class XBT_PUBLIC FairBottleneck : public System { -public: - using System::System; - void solve() final { bottleneck_solve(); } -private: - void bottleneck_solve(); + std::unique_ptr modified_set_ = nullptr; }; /** @} */ -} // namespace lmm -} // namespace kernel -} // namespace simgrid +} // namespace simgrid::kernel::lmm #endif