Describes how the linear MaxMin system work.
A linear maxmin solver to resolve inequations systems.
Most SimGrid model rely on a "fluid/steady-state" modeling that 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 \(x_1\), \(x_2\), \(x_3\), and \(x_4\) . Let's say that \(x_1\) and \(x_2\) correspond to activities running and the same CPU \(A\) whose capacity is \(C_A\). In such a case, we need to enforce:
\[ x_1 + x_2 \leq C_A \]
Likewise, if \(x_3\) (resp. \(x_4\)) corresponds to a network flow \(F_3\) (resp. \(F_4\)) that goes through a set of links \(L_1\) and \(L_2\) (resp. \(L_2\) and \(L_3\)), then we need to enforce:
\[ x_3 \leq C_{L_1} \]
\[ x_3 + x_4 \leq C_{L_2} \]
\[ x_4 \leq C_{L_3} \]
One could set every variable to 0 to make sure the constraints are satisfied but this would obviously not be very realistic. A possible objective is to try to maximize the minimum of the \(x_i\) . This ensures that all the \(x_i\) are positive and "as large as possible".
This is called max-min fairness and is the most commonly used objective in SimGrid. Another possibility is to maximize \(\sum_if(x_i)\), where \(f\) is a strictly increasing concave function.
Constraint:
- bound (set)
- shared (set)
- usage (computed)
Variable:
- weight (set)
- bound (set)
- value (computed)
Element:
A possible system could be:
- three variables:
var1
, var2
, var3
- two constraints:
cons1
, cons2
- four elements linking:
elem1
linking var1
and cons1
elem2
linking var2
and cons1
elem3
linking var2
and cons2
elem4
linking var3
and cons2
And the corresponding inequations will be:
var1.value <= var1.bound
var2.value <= var2.bound
var3.value <= var3.bound
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.
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
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.
|
double(* | func_f_def )(lmm_variable_t, double) |
| Print information about a lmm system. More...
|
|
lmm_system_t | lmm_system_new (bool selective_update) |
| Create a new Linear MaxMim system. More...
|
|
void | lmm_system_free (lmm_system_t sys) |
| Free an existing Linear MaxMin system. More...
|
|
lmm_constraint_t | lmm_constraint_new (lmm_system_t sys, void *id, double bound_value) |
| Create a new Linear MaxMin constraint. More...
|
|
void | lmm_constraint_shared (lmm_constraint_t cnst) |
| Share a constraint. More...
|
|
int | lmm_constraint_sharing_policy (lmm_constraint_t cnst) |
| Check if a constraint is shared (shared by default) More...
|
|
void | lmm_constraint_free (lmm_system_t sys, lmm_constraint_t cnst) |
| Free a constraint. More...
|
|
double | lmm_constraint_get_usage (lmm_constraint_t cnst) |
| Get the usage of the constraint after the last lmm solve. More...
|
|
void | lmm_constraint_concurrency_limit_set (lmm_constraint_t cnst, int concurrency_limit) |
| Sets the concurrency limit for this constraint. More...
|
|
int | lmm_constraint_concurrency_limit_get (lmm_constraint_t cnst) |
| Gets the concurrency limit for this constraint. More...
|
|
void | lmm_constraint_concurrency_maximum_reset (lmm_constraint_t cnst) |
| Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint evolution). More...
|
|
int | lmm_constraint_concurrency_maximum_get (lmm_constraint_t cnst) |
| Get the concurrency maximum for a given variable (which reflects constraint evolution). More...
|
|
lmm_variable_t | lmm_variable_new (lmm_system_t sys, void *id, double weight_value, double bound, int number_of_constraints) |
| Create a new Linear MaxMin variable. More...
|
|
void | lmm_variable_free (lmm_system_t sys, lmm_variable_t var) |
| Free a variable. More...
|
|
double | lmm_variable_getvalue (lmm_variable_t var) |
| Get the value of the variable after the last lmm solve. More...
|
|
double | lmm_variable_getbound (lmm_variable_t var) |
| Get the maximum value of the variable (-1.0 if no maximum value) More...
|
|
void | lmm_variable_concurrency_share_set (lmm_variable_t var, short int concurrency_share) |
| Set the concurrent share of the variable. More...
|
|
void | lmm_shrink (lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var) |
| Remove a variable from a constraint. More...
|
|
void | lmm_expand (lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, double value) |
| Associate a variable to a constraint with a coefficient. More...
|
|
void | lmm_expand_add (lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, double value) |
| Add value to the coefficient between a constraint and a variable or create one. More...
|
|
lmm_constraint_t | lmm_get_cnst_from_var (lmm_system_t sys, lmm_variable_t var, int num) |
| Get the numth constraint associated to the variable. More...
|
|
double | lmm_get_cnst_weight_from_var (lmm_system_t sys, lmm_variable_t var, int num) |
| Get the weigth of the numth constraint associated to the variable. More...
|
|
int | lmm_get_number_of_cnst_from_var (lmm_system_t sys, lmm_variable_t var) |
| Get the number of constraint associated to a variable. More...
|
|
lmm_variable_t | lmm_get_var_from_cnst (lmm_system_t sys, lmm_constraint_t cnst, lmm_element_t *elem) |
| Get a var associated to a constraint. More...
|
|
lmm_variable_t | lmm_get_var_from_cnst_safe (lmm_system_t sys, lmm_constraint_t cnst, lmm_element_t *elem, lmm_element_t *nextelem, int *numelem) |
| Get a var associated to a constraint. More...
|
|
lmm_constraint_t | lmm_get_first_active_constraint (lmm_system_t sys) |
| Get the first active constraint of a system. More...
|
|
lmm_constraint_t | lmm_get_next_active_constraint (lmm_system_t sys, lmm_constraint_t cnst) |
| Get the next active constraint of a constraint in a system. More...
|
|
void * | lmm_constraint_id (lmm_constraint_t cnst) |
| Get the data associated to a constraint. More...
|
|
void * | lmm_variable_id (lmm_variable_t var) |
| Get the data associated to a variable. More...
|
|
void | lmm_update (lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, double value) |
| Update the value of element linking the constraint and the variable. More...
|
|
void | lmm_update_variable_bound (lmm_system_t sys, lmm_variable_t var, double bound) |
| Update the bound of a variable. More...
|
|
void | lmm_update_variable_weight (lmm_system_t sys, lmm_variable_t var, double weight) |
| Update the weight of a variable. More...
|
|
double | lmm_get_variable_weight (lmm_variable_t var) |
| Get the weight of a variable. More...
|
|
void | lmm_update_constraint_bound (lmm_system_t sys, lmm_constraint_t cnst, double bound) |
| Update a constraint bound. More...
|
|
int | lmm_constraint_used (lmm_system_t sys, lmm_constraint_t cnst) |
| [brief description] More...
|
|
void | lmm_print (lmm_system_t sys) |
| Print the lmm system. More...
|
|
void | lmm_solve (lmm_system_t sys) |
| Solve the lmm system. More...
|
|
void | lagrange_solve (lmm_system_t sys) |
|
void | bottleneck_solve (lmm_system_t sys) |
|
void | lmm_set_default_protocol_function (double(*func_f)(lmm_variable_t var, double x), double(*func_fp)(lmm_variable_t var, double x), double(*func_fpi)(lmm_variable_t var, double x)) |
| Default functions associated to the chosen protocol. More...
|
|
double | func_reno_f (lmm_variable_t var, double x) |
|
double | func_reno_fp (lmm_variable_t var, double x) |
|
double | func_reno_fpi (lmm_variable_t var, double x) |
|
double | func_reno2_f (lmm_variable_t var, double x) |
|
double | func_reno2_fp (lmm_variable_t var, double x) |
|
double | func_reno2_fpi (lmm_variable_t var, double x) |
|
double | func_vegas_f (lmm_variable_t var, double x) |
|
double | func_vegas_fp (lmm_variable_t var, double x) |
|
double | func_vegas_fpi (lmm_variable_t var, double x) |
|
§ s_lmm_element_t
LMM element Elements can be seen as glue between constraint objects and variable objects.
Basically, each variable will have a set of elements, one for each constraint where it is involved. Then, it is used to list all variables involved in constraint through constraint's xxx_element_set lists, or vice-versa list all constraints for a given variable.
§ s_lmm_constraint_t
LMM constraint Each constraint contains several partially overlapping logical sets of elements:
- Disabled elements which variable's weight is zero. This variables are not at all processed by LMM, but eventually the corresponding action will enable it (at least this is the idea).
- Enabled elements which variable's weight is non-zero. They are utilized in some LMM functions.
- Active elements which variable's weight is non-zero (i.e. it is enabled) AND its element value is non-zero. LMM_solve iterates over active elements during resolution, dynamically making them active or unactive.
§ s_lmm_variable_t
LMM variable.
When something prevents us from enabling a variable, we "stage" the weight that we would have like to set, so that as soon as possible we enable the variable with desired weight
§ s_lmm_system_t
§ lmm_system_new()
Create a new Linear MaxMim system.
- Parameters
-
selective_update | whether we should do lazy updates |
§ lmm_system_free()
Free an existing Linear MaxMin system.
- Parameters
-
sys | The lmm system to free |
§ lmm_constraint_new()
Create a new Linear MaxMin constraint.
- Parameters
-
sys | The system in which we add a constraint |
id | Data associated to the constraint (e.g.: a network link) |
bound_value | The bound value of the constraint |
§ lmm_constraint_shared()
Share a constraint.
- Parameters
-
cnst | The constraint to share |
§ lmm_constraint_sharing_policy()
Check if a constraint is shared (shared by default)
- Parameters
-
cnst | The constraint to share |
- Returns
- 1 if shared, 0 otherwise
Check if a constraint is shared (shared by default)
§ lmm_constraint_free()
Free a constraint.
- Parameters
-
sys | The system associated to the constraint |
cnst | The constraint to free |
§ lmm_constraint_get_usage()
Get the usage of the constraint after the last lmm solve.
- Parameters
-
- Returns
- The usage of the constraint
Get the usage of the constraint after the last lmm solve.
If the resource is shared (the default case), the load is sum of resource usage made by every variables located on this resource.
If the resource is not shared (ie in FATPIPE mode), then the the load is the max (not the sum) of all resource usages located on this resource.
- Parameters
-
cnst | the lmm_constraint_t associated to the resource |
§ lmm_constraint_concurrency_limit_set()
Sets the concurrency limit for this constraint.
- Parameters
-
cnst | A constraint |
concurrency_limit | The concurrency limit to use for this constraint |
§ lmm_constraint_concurrency_limit_get()
Gets the concurrency limit for this constraint.
- Parameters
-
- Returns
- The concurrency limit used by this constraint
§ lmm_constraint_concurrency_maximum_reset()
Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint evolution).
- Parameters
-
§ lmm_constraint_concurrency_maximum_get()
Get the concurrency maximum for a given variable (which reflects constraint evolution).
- Parameters
-
- Returns
- the maximum concurrency of the constraint
§ lmm_variable_new()
Create a new Linear MaxMin variable.
- Parameters
-
sys | The system in which we add a constaint |
id | Data associated to the variable (e.g.: a network communication) |
weight_value | The weight of the variable (0.0 if not used) |
bound | The maximum value of the variable (-1.0 if no maximum value) |
number_of_constraints | The maximum number of constraint to associate to the variable |
§ lmm_variable_free()
Free a variable.
- Parameters
-
sys | The system associated to the variable |
var | The variable to free |
§ lmm_variable_getvalue()
Get the value of the variable after the last lmm solve.
- Parameters
-
- Returns
- The value of the variable
§ lmm_variable_getbound()
Get the maximum value of the variable (-1.0 if no maximum value)
- Parameters
-
- Returns
- The bound of the variable
§ lmm_variable_concurrency_share_set()
void lmm_variable_concurrency_share_set |
( |
lmm_variable_t |
var, |
|
|
short int |
concurrency_share |
|
) |
| |
Set the concurrent share of the variable.
- Parameters
-
var | A variable |
concurrency_share | The new concurrency share |
§ lmm_shrink()
Remove a variable from a constraint.
- Parameters
-
sys | A system |
cnst | A constraint |
var | The variable to remove |
§ lmm_expand()
Associate a variable to a constraint with a coefficient.
- Parameters
-
sys | A system |
cnst | A constraint |
var | A variable |
value | The coefficient associated to the variable in the constraint |
§ lmm_expand_add()
Add value to the coefficient between a constraint and a variable or create one.
- Parameters
-
sys | A system |
cnst | A constraint |
var | A variable |
value | The value to add to the coefficient associated to the variable in the constraint |
§ lmm_get_cnst_from_var()
Get the numth constraint associated to the variable.
- Parameters
-
sys | The system associated to the variable (not used) |
var | A variable |
num | The rank of constraint we want to get |
- Returns
- The numth constraint
§ lmm_get_cnst_weight_from_var()
Get the weigth of the numth constraint associated to the variable.
- Parameters
-
sys | The system associated to the variable (not used) |
var | A variable |
num | The rank of constraint we want to get |
- Returns
- The numth constraint
§ lmm_get_number_of_cnst_from_var()
Get the number of constraint associated to a variable.
- Parameters
-
sys | The system associated to the variable (not used) |
var | A variable |
- Returns
- The number of constraint associated to the variable
§ lmm_get_var_from_cnst()
Get a var associated to a constraint.
Get the first variable of the next variable of elem if elem is not NULL
- Parameters
-
sys | The system associated to the variable (not used) |
cnst | A constraint |
elem | A element of constraint of the constraint or NULL |
- Returns
- A variable associated to a constraint
§ lmm_get_var_from_cnst_safe()
Get a var associated to a constraint.
Get the first variable of the next variable of elem if elem is not NULL
- Parameters
-
cnst | A constraint |
elem | A element of constraint of the constraint or NULL |
nextelem | A element of constraint of the constraint or NULL, the one after elem |
numelem | parameter representing the number of elements to go |
- Returns
- A variable associated to a constraint
§ lmm_get_first_active_constraint()
Get the first active constraint of a system.
- Parameters
-
- Returns
- The first active constraint
§ lmm_get_next_active_constraint()
Get the next active constraint of a constraint in a system.
- Parameters
-
sys | A system |
cnst | An active constraint of the system |
- Returns
- The next active constraint
§ lmm_constraint_id()
Get the data associated to a constraint.
- Parameters
-
- Returns
- The data associated to the constraint
§ lmm_variable_id()
Get the data associated to a variable.
- Parameters
-
- Returns
- The data associated to the variable
§ lmm_update()
Update the value of element linking the constraint and the variable.
- Parameters
-
sys | A system |
cnst | A constraint |
var | A variable |
value | The new value |
§ lmm_update_variable_bound()
Update the bound of a variable.
- Parameters
-
sys | A system |
var | A constraint |
bound | The new bound |
Update the bound of a variable.
- Parameters
-
sys | the lmm_system_t |
var | the lmm_variable_t |
bound | the new bound to associate with var |
Makes var->bound equal to bound. Whenever this function is called a change is signed in the system. To avoid false system changing detection it is a good idea to test (bound != 0) before calling it.
§ lmm_update_variable_weight()
Update the weight of a variable.
- Parameters
-
sys | A system |
var | A variable |
weight | The new weight of the variable |
§ lmm_get_variable_weight()
Get the weight of a variable.
- Parameters
-
- Returns
- The weight of the variable
§ lmm_update_constraint_bound()
Update a constraint bound.
- Parameters
-
sys | A system |
cnst | A constraint |
bound | The new bound of the consrtaint |
§ lmm_constraint_used()
[brief description]
- Parameters
-
sys | A system |
cnst | A constraint |
- Returns
- [description]
§ lmm_print()
Print the lmm system.
- Parameters
-
sys | The lmm system to print |
§ lmm_solve()
Solve the lmm system.
- Parameters
-
sys | The lmm system to solve |
§ lagrange_solve()
§ bottleneck_solve()
§ lmm_set_default_protocol_function()
Default functions associated to the chosen protocol.
When using the lagrangian approach.
Default functions associated to the chosen protocol.
- Parameters
-
func_fpi | inverse of the partial differential of f (f prime inverse, (f')^{-1}) |
Set default functions to the ones passed as parameters. This is a polymorphism in C pure, enjoy the roots of programming.
§ func_reno_f()
§ func_reno_fp()
§ func_reno_fpi()
§ func_reno2_f()
§ func_reno2_fp()
§ func_reno2_fpi()
§ func_vegas_f()
§ func_vegas_fp()
§ func_vegas_fpi()
§ func_f_def
Print information about a lmm system.
- Parameters
-