SimGrid  3.14.159
Versatile Simulation of Distributed Systems
SURF Linear MaxMin

Detailed Description

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:

Variable:

Element:

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

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:

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.

Classes

struct  lmm_element
 LMM element Elements can be seen as glue between constraint objects and variable objects. More...
 
struct  lmm_constraint
 LMM constraint Each constraint contains several partially overlapping logical sets of elements: More...
 
struct  lmm_variable
 LMM variable. More...
 
struct  lmm_system
 LMM system. More...
 

Typedefs

typedef struct lmm_element s_lmm_element_t
 LMM element Elements can be seen as glue between constraint objects and variable objects. More...
 
typedef struct lmm_constraint s_lmm_constraint_t
 LMM constraint Each constraint contains several partially overlapping logical sets of elements: More...
 
typedef struct lmm_variable s_lmm_variable_t
 LMM variable. More...
 
typedef struct lmm_system s_lmm_system_t
 LMM system. More...
 

Variables

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...
 
voidlmm_constraint_id (lmm_constraint_t cnst)
 Get the data associated to a constraint. More...
 
voidlmm_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)
 

Typedef Documentation

§ s_lmm_element_t

typedef struct lmm_element 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

typedef struct lmm_system s_lmm_system_t

LMM system.

Function Documentation

§ lmm_system_new()

lmm_system_t lmm_system_new ( bool  selective_update)

Create a new Linear MaxMim system.

Parameters
selective_updatewhether we should do lazy updates

§ lmm_system_free()

void lmm_system_free ( lmm_system_t  sys)

Free an existing Linear MaxMin system.

Parameters
sysThe lmm system to free

§ lmm_constraint_new()

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

§ lmm_constraint_shared()

void lmm_constraint_shared ( lmm_constraint_t  cnst)

Share a constraint.

Parameters
cnstThe constraint to share

§ lmm_constraint_sharing_policy()

int lmm_constraint_sharing_policy ( lmm_constraint_t  cnst)

Check if a constraint is shared (shared by default)

Parameters
cnstThe constraint to share
Returns
1 if shared, 0 otherwise

Check if a constraint is shared (shared by default)

§ lmm_constraint_free()

void lmm_constraint_free ( lmm_system_t  sys,
lmm_constraint_t  cnst 
)
inline

Free a constraint.

Parameters
sysThe system associated to the constraint
cnstThe constraint to free

§ lmm_constraint_get_usage()

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

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

§ lmm_constraint_concurrency_limit_set()

void lmm_constraint_concurrency_limit_set ( lmm_constraint_t  cnst,
int  concurrency_limit 
)

Sets the concurrency limit for this constraint.

Parameters
cnstA constraint
concurrency_limitThe concurrency limit to use for this constraint

§ lmm_constraint_concurrency_limit_get()

int lmm_constraint_concurrency_limit_get ( lmm_constraint_t  cnst)

Gets the concurrency limit for this constraint.

Parameters
cnstA constraint
Returns
The concurrency limit used by this constraint

§ lmm_constraint_concurrency_maximum_reset()

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

Parameters
cnstA constraint

§ lmm_constraint_concurrency_maximum_get()

int lmm_constraint_concurrency_maximum_get ( lmm_constraint_t  cnst)

Get the concurrency maximum for a given variable (which reflects constraint evolution).

Parameters
cnstA constraint
Returns
the maximum concurrency of the constraint

§ lmm_variable_new()

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

§ lmm_variable_free()

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

§ lmm_variable_getvalue()

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

§ lmm_variable_getbound()

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

§ 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
varA variable
concurrency_shareThe new concurrency share

§ lmm_shrink()

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

§ lmm_expand()

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

§ lmm_expand_add()

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

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

§ lmm_get_cnst_weight_from_var()

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

§ lmm_get_number_of_cnst_from_var()

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

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

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.

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

Parameters
cnstA constraint
elemA element of constraint of the constraint or NULL
nextelemA element of constraint of the constraint or NULL, the one after elem
numelemparameter representing the number of elements to go
Returns
A variable associated to a constraint

§ lmm_get_first_active_constraint()

lmm_constraint_t lmm_get_first_active_constraint ( lmm_system_t  sys)
inline

Get the first active constraint of a system.

Parameters
sysA system
Returns
The first active constraint

§ lmm_get_next_active_constraint()

lmm_constraint_t lmm_get_next_active_constraint ( lmm_system_t  sys,
lmm_constraint_t  cnst 
)
inline

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

§ lmm_constraint_id()

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

§ lmm_variable_id()

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

§ lmm_update()

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

§ lmm_update_variable_bound()

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.

§ lmm_update_variable_weight()

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

§ lmm_get_variable_weight()

double lmm_get_variable_weight ( lmm_variable_t  var)

Get the weight of a variable.

Parameters
varA variable
Returns
The weight of the variable

§ lmm_update_constraint_bound()

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

§ lmm_constraint_used()

int lmm_constraint_used ( lmm_system_t  sys,
lmm_constraint_t  cnst 
)

[brief description]

Parameters
sysA system
cnstA constraint
Returns
[description]

§ lmm_print()

void lmm_print ( lmm_system_t  sys)

Print the lmm system.

Parameters
sysThe lmm system to print

§ lmm_solve()

void lmm_solve ( lmm_system_t  sys)

Solve the lmm system.

Parameters
sysThe lmm system to solve

§ lagrange_solve()

void lagrange_solve ( lmm_system_t  sys)

§ bottleneck_solve()

void bottleneck_solve ( lmm_system_t  sys)

§ lmm_set_default_protocol_function()

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.

Default functions associated to the chosen protocol.

Parameters
func_fpiinverse 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()

double func_reno_f ( lmm_variable_t  var,
double  x 
)

§ func_reno_fp()

double func_reno_fp ( lmm_variable_t  var,
double  x 
)

§ func_reno_fpi()

double func_reno_fpi ( lmm_variable_t  var,
double  x 
)

§ func_reno2_f()

double func_reno2_f ( lmm_variable_t  var,
double  x 
)

§ func_reno2_fp()

double func_reno2_fp ( lmm_variable_t  var,
double  x 
)

§ func_reno2_fpi()

double func_reno2_fpi ( lmm_variable_t  var,
double  x 
)

§ func_vegas_f()

double func_vegas_f ( lmm_variable_t  var,
double  x 
)

§ func_vegas_fp()

double func_vegas_fp ( lmm_variable_t  var,
double  x 
)

§ func_vegas_fpi()

double func_vegas_fpi ( lmm_variable_t  var,
double  x 
)

Variable Documentation

§ func_f_def

double(* func_f_def) (lmm_variable_t, double)

Print information about a lmm system.

Parameters
sysA lmm system