Describes how the linear MaxMin system work.
More...
|
void | lmm_print (lmm_system_t sys) |
| Print informations about a lmm system. More...
|
|
lmm_system_t | lmm_system_new (int 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_is_shared (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...
|
|
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_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_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_solve (lmm_system_t sys) |
| Solve the lmm system. More...
|
|
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)) |
|
Describes how the linear MaxMin system work.
A linear maxmin solver to resolves inequations systems.
Most SimGrid model rely on a "fluid/steady-state" modeling that samount to share 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
,
,
, and
. Let's say that
and
correspond to activities running and the same CPU
whose capacity is
. In such a case, we need to enforce:
Likewise, if
(resp.
) corresponds to a network flow
(resp.
) that goes through a set of links
and
(resp.
and
), then we need to enforce:
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
. This ensures that all the
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
, where
is a strictly increasing concave function.
Constraint:
- bound (set)
- shared (set)
- usage (computed) Variable:
- weight (set)
- bound (set)
- value (computed) Element:
- value (set)
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 replace by a max
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.
Create a new Linear MaxMim system.
- Parameters
-
selective_update | [description] |
Print informations about a lmm system.
- Parameters
-
Free an existing Linear MaxMin system.
- Parameters
-
sys | The lmm system to free |
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 |
Share a constraint.
[long description]
- Parameters
-
cnst | The constraint to share |
Check if a constraint is shared (shared by default)
- Parameters
-
cnst | The constraint to share |
- Returns
- 1 if shared, 0 otherwise
Free a constraint.
- Parameters
-
sys | The system associated to the constraint |
cnst | The constraint to free |
Get the usage of the constraint after the last lmm solve.
- Parameters
-
- Returns
- The usage of the constraint
Returns total resource load
- Parameters
-
cnst | the lmm_constraint_t associated to the resource |
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 |
Free a variable.
- Parameters
-
sys | The system associated to the variable |
var | The variable to free |
Get the value of the variable after the last lmm solve.
- Parameters
-
- Returns
- The value of the variable
Get the maximum value of the variable (-1.0 if no maximum value)
- Parameters
-
- Returns
- The bound of the variable
Remove a variable from a constraint.
- Parameters
-
sys | A system |
cnst | A constraint |
var | The variable to remove |
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 |
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 |
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
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
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
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
Get the first active constraint of a system.
- Parameters
-
- Returns
- The first 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
Get the data associated to a constraint.
- Parameters
-
- Returns
- The data associated to the constraint
Get the data associated to a variable.
- Parameters
-
- Returns
- The data associated to the variable
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 |
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.
Update the weight of a variable.
- Parameters
-
sys | A system |
var | A variable |
weight | The new weight of the variable |
Get the weight of a variable.
- Parameters
-
- Returns
- The weight of the variable
Update a constraint bound.
- Parameters
-
sys | A system |
cnst | A constraint |
bound | The new bound of the consrtaint |
[brief description]
- Parameters
-
sys | A system |
cnst | A constraint |
- Returns
- [description]
Solve the lmm system.
- Parameters
-
sys | The lmm system to solve |
Default functions associated to the chosen protocol. When using the lagrangian approach.