SimGrid  3.11
Versatile Simulation of Distributed Systems
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
SURF Linear MaxMin

Describes how the linear MaxMin system work. More...

Data Structures

struct  lmm_element
 LMM element. More...
 
struct  lmm_constraint
 LMM constraint. More...
 
struct  lmm_variable
 LMM variable. More...
 
struct  lmm_system
 LMM system. More...
 

Typedefs

typedef struct lmm_element s_lmm_element_t
 LMM element.
 
typedef struct lmm_constraint s_lmm_constraint_t
 LMM constraint.
 
typedef struct lmm_variable s_lmm_variable_t
 LMM variable.
 
typedef struct lmm_system s_lmm_system_t
 LMM system.
 

Functions

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))
 

Detailed Description

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 $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:

A possible system could be:

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.

Function Documentation

lmm_system_t lmm_system_new ( int  selective_update)

Create a new Linear MaxMim system.

Parameters
selective_update[description]
void lmm_print ( lmm_system_t  sys)

Print informations about a lmm system.

Parameters
sysA lmm system
void lmm_system_free ( lmm_system_t  sys)

Free an existing Linear MaxMin system.

Parameters
sysThe lmm system to free
lmm_constraint_t lmm_constraint_new ( lmm_system_t  sys,
void *  id,
double  bound_value 
)

Create a new Linear MaxMin constraint.

Parameters
sysThe system in which we add a constraint
idData associated to the constraint (e.g.: a network link)
bound_valueThe bound value of the constraint
void lmm_constraint_shared ( lmm_constraint_t  cnst)

Share a constraint.

[long description]

Parameters
cnstThe constraint to share
int lmm_constraint_is_shared ( lmm_constraint_t  cnst)

Check if a constraint is shared (shared by default)

Parameters
cnstThe constraint to share
Returns
1 if shared, 0 otherwise
void lmm_constraint_free ( lmm_system_t  sys,
lmm_constraint_t  cnst 
)

Free a constraint.

Parameters
sysThe system associated to the constraint
cnstThe constraint to free
double lmm_constraint_get_usage ( lmm_constraint_t  cnst)

Get the usage of the constraint after the last lmm solve.

Parameters
cnstA constraint
Returns
The usage of the constraint

Returns total resource load

Parameters
cnstthe lmm_constraint_t associated to the resource
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.

Parameters
sysThe system in which we add a constaint
idData associated to the variable (e.g.: a network communication)
weight_valueThe weight of the variable (0.0 if not used)
boundThe maximum value of the variable (-1.0 if no maximum value)
number_of_constraintsThe maximum number of constraint to associate to the variable
void lmm_variable_free ( lmm_system_t  sys,
lmm_variable_t  var 
)

Free a variable.

Parameters
sysThe system associated to the variable
varThe variable to free
double lmm_variable_getvalue ( lmm_variable_t  var)

Get the value of the variable after the last lmm solve.

Parameters
varA variable
Returns
The value of the variable
double lmm_variable_getbound ( lmm_variable_t  var)

Get the maximum value of the variable (-1.0 if no maximum value)

Parameters
varA variable
Returns
The bound of the variable
void lmm_shrink ( lmm_system_t  sys,
lmm_constraint_t  cnst,
lmm_variable_t  var 
)

Remove a variable from a constraint.

Parameters
sysA system
cnstA constraint
varThe variable to remove
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.

Parameters
sysA system
cnstA constraint
varA variable
valueThe coefficient associated to the variable in the constraint
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.

Parameters
sysA system
cnstA constraint
varA variable
valueThe value to add to the coefficient associated to the variable in the constraint
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.

Parameters
sysThe system associated to the variable (not used)
varA variable
numThe rank of constraint we want to get
Returns
The numth constraint
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.

Parameters
sysThe system associated to the variable (not used)
varA variable
numThe rank of constraint we want to get
Returns
The numth constraint
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.

Parameters
sysThe system associated to the variable (not used)
varA variable
Returns
The number of constraint associated to the variable
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.

Get the first variable of the next variable of elem if elem is not NULL

Parameters
sysThe system associated to the variable (not used)
cnstA constraint
elemA element of constraint of the constraint or NULL
Returns
A variable associated to a constraint
lmm_constraint_t lmm_get_first_active_constraint ( lmm_system_t  sys)

Get the first active constraint of a system.

Parameters
sysA system
Returns
The first active constraint
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.

Parameters
sysA system
cnstAn active constraint of the system
Returns
The next active constraint
void* lmm_constraint_id ( lmm_constraint_t  cnst)

Get the data associated to a constraint.

Parameters
cnstA constraint
Returns
The data associated to the constraint
void* lmm_variable_id ( lmm_variable_t  var)

Get the data associated to a variable.

Parameters
varA variable
Returns
The data associated to the variable
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.

Parameters
sysA system
cnstA constraint
varA variable
valueThe new value
void lmm_update_variable_bound ( lmm_system_t  sys,
lmm_variable_t  var,
double  bound 
)

Update the bound of a variable.

Parameters
sysA system
varA constraint
boundThe new bound

Update the bound of a variable.

Parameters
systhe lmm_system_t
varthe lmm_variable_t
boundthe 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.

void lmm_update_variable_weight ( lmm_system_t  sys,
lmm_variable_t  var,
double  weight 
)

Update the weight of a variable.

Parameters
sysA system
varA variable
weightThe new weight of the variable
double lmm_get_variable_weight ( lmm_variable_t  var)

Get the weight of a variable.

Parameters
varA variable
Returns
The weight of the variable
void lmm_update_constraint_bound ( lmm_system_t  sys,
lmm_constraint_t  cnst,
double  bound 
)

Update a constraint bound.

Parameters
sysA system
cnstA constraint
boundThe new bound of the consrtaint
int lmm_constraint_used ( lmm_system_t  sys,
lmm_constraint_t  cnst 
)

[brief description]

Parameters
sysA system
cnstA constraint
Returns
[description]
void lmm_solve ( lmm_system_t  sys)

Solve the lmm system.

Parameters
sysThe lmm system to solve
void lmm_set_default_protocol_function ( double(*)(lmm_variable_t var, double x)  func_f,
double(*)(lmm_variable_t var, double x)  func_fp,
double(*)(lmm_variable_t var, double x)  func_fpi 
)

Default functions associated to the chosen protocol. When using the lagrangian approach.