X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/c04c4303aa1b5682ea7e968811c039024425a535..caf6aba21918125649ff5a84fafb22e225b2d580:/src/include/surf/maxmin.h diff --git a/src/include/surf/maxmin.h b/src/include/surf/maxmin.h index cea914e718..27885bfeb7 100644 --- a/src/include/surf/maxmin.h +++ b/src/include/surf/maxmin.h @@ -7,25 +7,24 @@ #ifndef _SURF_MAXMIN_H #define _SURF_MAXMIN_H -#include "portable.h" +#include "src/portable.h" #include "xbt/misc.h" #include "xbt/asserts.h" #include "surf/datatypes.h" #include -//#include /** @addtogroup SURF_lmm * @details - * A linear maxmin solver to resolves inequations systems. + * A linear maxmin solver to resolve inequations systems. * * Most SimGrid model rely on a "fluid/steady-state" modeling that - * samount to share resources between actions at relatively + * simulate the sharing of resources between actions at relatively * coarse-grain. Such sharing is generally done by solving a set of * linear inequations. Let's take an example and assume we have the * variables \f$x_1\f$, \f$x_2\f$, \f$x_3\f$, and \f$x_4\f$ . Let's * say that \f$x_1\f$ and \f$x_2\f$ correspond to activities running - * and the same CPU \f$A\f$ whose capacity is \f$C_A\f$ . In such a + * and the same CPU \f$A\f$ whose capacity is \f$C_A\f$. In such a * case, we need to enforce: * * \f[ x_1 + x_2 \leq C_A \f] @@ -50,14 +49,17 @@ * \f$\sum_if(x_i)\f$, where \f$f\f$ is a strictly increasing concave * function. * + * * Constraint: * - bound (set) * - shared (set) * - usage (computed) + * * Variable: * - weight (set) * - bound (set) * - value (computed) + * * Element: * - value (set) * @@ -78,17 +80,54 @@ * var1.weight * var1.value * elem1.value + var2.weight * var2.value * elem2.value <= cons1.bound * var2.weight * var2.value * elem3.value + var3.weight * var3.value * elem4.value <= cons2.bound * - * where `var1.value`, `var2.value` and `var3.value` are the unknown values + * where `var1.value`, `var2.value` and `var3.value` are the unknown values. * - * if a constraint is not shared the sum is replace by a max + * If a constraint is not shared, the sum is replaced by a max. + * For example, a third non-shared constraint `cons3` and the associated elements `elem5` and `elem6` could write as: + * + * max( var1.weight * var1.value * elem5.value , var3.weight * var3.value * elem6.value ) <= cons3.bound + * + * This is usefull for the sharing of resources for various models. + * For instance, for the network model, each link is associated + * to a constraint and each communication to a variable. + * + * + * Implementation details + * + * For implementation reasons, we are interested in distinguishing variables that actually participate to the computation of constraints, and those who are part of the equations but are stuck to zero. + * We call enabled variables, those which var.weight is strictly positive. Zero-weight variables are called disabled variables. + * Unfortunately this concept of enabled/disabled variables intersects with active/inactive variable. + * Semantically, the intent is similar, but the conditions under which a variable is active is slightly more strict than the conditions for it to be enabled. + * A variable is active only if its var.value is non-zero (and, by construction, its var.weight is non-zero). + * In general, variables remain disabled after their creation, which often models an initialization phase (e.g. first packet propagating in the network). Then, it is enabled by the corresponding model. Afterwards, the max-min solver (lmm_solve()) activates it when appropriate. It is possible that the variable is again disabled, e.g. to model the pausing of an action. + * + * + * Concurrency limit and maximum * - * Its usefull for the sharing of resources for various models. - * For instance for the network model the link are associated - * to consrtaint and the communications to variables. + * We call concurrency, the number of variables that can be enabled at any time for each constraint. + * From a model perspective, this "concurrency" often represents the number of actions that actually compete for one constraint. + * The LMM solver is able to limit the concurrency for each constraint, and to monitor its maximum value. + * + * One may want to limit the concurrency of constraints for essentially three reasons: + * - Keep LMM system in a size that can be solved (it does not react very well with tens of thousands of variables per constraint) + * - Stay within parameters where the fluid model is accurate enough. + * - Model serialization effects + * + * The concurrency limit can also be set to a negative value to disable concurrency limit. This can improve performance slightly. + * + * Overall, each constraint contains three fields related to concurrency: + * - concurrency_limit which is the limit enforced by the solver + * - 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. */ -XBT_EXPORT_NO_IMPORT(double) sg_maxmin_precision; -XBT_EXPORT_NO_IMPORT(double) sg_surf_precision; +XBT_PUBLIC_DATA(double) sg_maxmin_precision; +XBT_PUBLIC_DATA(double) sg_surf_precision; static XBT_INLINE void double_update(double *variable, double value, double precision) { @@ -152,7 +191,7 @@ XBT_PUBLIC(void) lmm_constraint_shared(lmm_constraint_t cnst); * @param cnst The constraint to share * @return 1 if shared, 0 otherwise */ -XBT_PUBLIC(int) lmm_constraint_is_shared(lmm_constraint_t cnst); +XBT_PUBLIC(int) lmm_constraint_sharing_policy(lmm_constraint_t cnst); /** * @brief Free a constraint @@ -170,6 +209,41 @@ XBT_PUBLIC(void) lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst); */ XBT_PUBLIC(double) lmm_constraint_get_usage(lmm_constraint_t cnst); +/** + * @brief Sets the concurrency limit for this constraint + * + * @param cnst A constraint + * @param concurrency_limit The concurrency limit to use for this constraint + */ +XBT_PUBLIC(void) lmm_constraint_concurrency_limit_set(lmm_constraint_t cnst, int concurrency_limit); + +/** + * @brief Gets the concurrency limit for this constraint + * + * @param cnst A constraint + * @return The concurrency limit used by this constraint + */ +XBT_PUBLIC(int) lmm_constraint_concurrency_limit_get(lmm_constraint_t cnst); + + +/** + * @brief Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint evolution). + * + * @param cnst A constraint + * +*/ +XBT_PUBLIC(void) lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst); + + +/** + * @brief Get the concurrency maximum for a given variable (which reflects constraint evolution). + * + * @param cnst A constraint + * @return the maximum concurrency of the constraint + */ +XBT_PUBLIC(int) lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst); + + /** * @brief Create a new Linear MaxMin variable * @@ -207,6 +281,14 @@ XBT_PUBLIC(double) lmm_variable_getvalue(lmm_variable_t var); */ XBT_PUBLIC(double) lmm_variable_getbound(lmm_variable_t var); +/** + * @brief Set the concurrent share of the variable + * + * @param var A variable + * @param concurrency_share The new concurrency share + */ +XBT_PUBLIC(void) lmm_variable_concurrency_share_set(lmm_variable_t var, short int concurrency_share); + /** * @brief Remove a variable from a constraint * @@ -400,6 +482,13 @@ XBT_PUBLIC(void) lmm_update_constraint_bound(lmm_system_t sys, */ XBT_PUBLIC(int) lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst); +/** + * @brief Print the lmm system + * + * @param sys The lmm system to print + */ +XBT_PUBLIC(void) lmm_print(lmm_system_t sys); + /** * @brief Solve the lmm system *