SimGrid  3.18
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

class  simgrid::kernel::lmm::Element
 LMM element Elements can be seen as glue between constraint objects and variable objects. More...
 
struct  simgrid::kernel::lmm::ConstraintLight
 
class  simgrid::kernel::lmm::Constraint
 LMM constraint Each constraint contains several partially overlapping logical sets of elements: More...
 
class  simgrid::kernel::lmm::Variable
 LMM variable. More...
 
class  simgrid::kernel::lmm::System
 LMM system. More...
 

Functions

void simgrid::kernel::lmm::lmm_solve (lmm_system_t sys)
 Solve the lmm system. More...
 
void simgrid::kernel::lmm::lagrange_solve (lmm_system_t sys)
 
void simgrid::kernel::lmm::bottleneck_solve (lmm_system_t sys)
 
void simgrid::kernel::lmm::set_default_protocol_function (double(*func_f)(const Variable &var, double x), double(*func_fp)(const Variable &var, double x), double(*func_fpi)(const Variable &var, double x))
 Attribute the value bound to var->bound. More...
 
double simgrid::kernel::lmm::func_reno_f (const Variable &var, double x)
 
double simgrid::kernel::lmm::func_reno_fp (const Variable &var, double x)
 
double simgrid::kernel::lmm::func_reno_fpi (const Variable &var, double x)
 
double simgrid::kernel::lmm::func_reno2_f (const Variable &var, double x)
 
double simgrid::kernel::lmm::func_reno2_fp (const Variable &var, double x)
 
double simgrid::kernel::lmm::func_reno2_fpi (const Variable &var, double x)
 
double simgrid::kernel::lmm::func_vegas_f (const Variable &var, double x)
 
double simgrid::kernel::lmm::func_vegas_fp (const Variable &var, double x)
 
double simgrid::kernel::lmm::func_vegas_fpi (const Variable &var, double x)
 
void simgrid::kernel::lmm::Element::make_active ()
 
void simgrid::kernel::lmm::Element::make_inactive ()
 

Variables

double(* simgrid::kernel::lmm::func_f_def )(const Variable &, double)
 
double(* simgrid::kernel::lmm::func_fp_def )(const Variable &, double)
 
double(* simgrid::kernel::lmm::func_fpi_def )(const Variable &, double)
 

Function Documentation

◆ lmm_solve()

void simgrid::kernel::lmm::lmm_solve ( lmm_system_t  sys)

Solve the lmm system.

Parameters
sysThe lmm system to solve

◆ lagrange_solve()

void simgrid::kernel::lmm::lagrange_solve ( lmm_system_t  sys)

◆ bottleneck_solve()

void simgrid::kernel::lmm::bottleneck_solve ( lmm_system_t  sys)

◆ set_default_protocol_function()

void simgrid::kernel::lmm::set_default_protocol_function ( double(*)(const Variable &var, double x)  func_f,
double(*)(const Variable &var, double x)  func_fp,
double(*)(const Variable &var, double x)  func_fpi 
)

Attribute the value bound to var->bound.

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.

When using the lagrangian approach.

◆ func_reno_f()

double simgrid::kernel::lmm::func_reno_f ( const Variable var,
double  x 
)

◆ func_reno_fp()

double simgrid::kernel::lmm::func_reno_fp ( const Variable var,
double  x 
)

◆ func_reno_fpi()

double simgrid::kernel::lmm::func_reno_fpi ( const Variable var,
double  x 
)

◆ func_reno2_f()

double simgrid::kernel::lmm::func_reno2_f ( const Variable var,
double  x 
)

◆ func_reno2_fp()

double simgrid::kernel::lmm::func_reno2_fp ( const Variable var,
double  x 
)

◆ func_reno2_fpi()

double simgrid::kernel::lmm::func_reno2_fpi ( const Variable var,
double  x 
)

◆ func_vegas_f()

double simgrid::kernel::lmm::func_vegas_f ( const Variable var,
double  x 
)

◆ func_vegas_fp()

double simgrid::kernel::lmm::func_vegas_fp ( const Variable var,
double  x 
)

◆ func_vegas_fpi()

double simgrid::kernel::lmm::func_vegas_fpi ( const Variable var,
double  x 
)

◆ make_active()

void simgrid::kernel::lmm::Element::make_active ( )
inline

◆ make_inactive()

void simgrid::kernel::lmm::Element::make_inactive ( )
inline

Variable Documentation

◆ func_f_def

double(* simgrid::kernel::lmm::func_f_def)(const Variable &, double)

◆ func_fp_def

double(* simgrid::kernel::lmm::func_fp_def)(const Variable &, double)

◆ func_fpi_def

double(* simgrid::kernel::lmm::func_fpi_def)(const Variable &, double)