SimGrid
3.18
Versatile Simulation of Distributed Systems
|
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.
A possible system could be:
var1
, var2
, var3
cons1
, cons2
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:
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... | |
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) |
void simgrid::kernel::lmm::lmm_solve | ( | lmm_system_t | sys | ) |
Solve the lmm system.
sys | The lmm system to solve |
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(*)(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.
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.
When using the lagrangian approach.
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 | ||
) |
|
inline |
|
inline |
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) |