SimGrid  3.14.159
Versatile Simulation of Distributed Systems
maxmin.cpp File Reference
#include "xbt/sysdep.h"
#include "xbt/log.h"
#include "xbt/strbuff.h"
#include "xbt/mallocator.h"
#include "maxmin_private.hpp"
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

Classes

struct  s_dyn_light
 

Macros

#define lmm_variable_mallocator_reset_f   ((void_f_pvoid_t)nullptr)
 

Typedefs

typedef struct s_dyn_light s_dyn_light_t
 
typedef struct s_dyn_lightdyn_light_t
 

Functions

 XBT_LOG_NEW_DEFAULT_SUBCATEGORY (surf_maxmin, surf, "Logging specific to SURF (maxmin)")
 
static voidlmm_variable_mallocator_new_f ()
 
static void lmm_variable_mallocator_free_f (void *var)
 
static void lmm_update_modified_set (lmm_system_t sys, lmm_constraint_t cnst)
 
static void lmm_remove_all_modified_set (lmm_system_t sys)
 Remove all constraints of the modified_constraint_set. More...
 
static void lmm_var_free (lmm_system_t sys, lmm_variable_t var)
 
static void lmm_cnst_free (lmm_system_t sys, lmm_constraint_t cnst)
 
static void lmm_on_disabled_var (lmm_system_t sys, lmm_constraint_t cnstr)
 
static void lmm_enable_var (lmm_system_t sys, lmm_variable_t var)
 
static int lmm_can_enable_var (lmm_variable_t var)
 
static void lmm_disable_var (lmm_system_t sys, lmm_variable_t var)
 
static int lmm_concurrency_slack (lmm_constraint_t cnstr)
 
static int lmm_cnstrs_min_concurrency_slack (lmm_variable_t var)
 Measure the minimum concurrency slack across all constraints where the given var is involved. More...
 
static void lmm_check_concurrency (lmm_system_t sys)
 
int lmm_element_concurrency (lmm_element_t elem)
 
void lmm_decrease_concurrency (lmm_element_t elem)
 
void lmm_increase_concurrency (lmm_element_t elem)
 
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...
 
static void lmm_variable_remove (lmm_system_t sys, lmm_variable_t var)
 
lmm_constraint_t lmm_constraint_new (lmm_system_t sys, void *id, double bound_value)
 Create a new Linear MaxMin constraint. More...
 
int lmm_constraint_concurrency_limit_get (lmm_constraint_t cnst)
 Gets the concurrency limit for this constraint. More...
 
void lmm_constraint_concurrency_limit_set (lmm_constraint_t cnst, int concurrency_limit)
 Sets 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...
 
void lmm_constraint_shared (lmm_constraint_t cnst)
 Share a constraint. More...
 
int lmm_constraint_sharing_policy (lmm_constraint_t cnst)
 Return true if the constraint is shared, and false if it's FATPIPE. More...
 
void lmm_constraint_free (lmm_system_t sys, lmm_constraint_t cnst)
 Free a constraint. More...
 
lmm_variable_t lmm_variable_new (lmm_system_t sys, void *id, double weight, 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...
 
void lmm_variable_concurrency_share_set (lmm_variable_t var, short int concurrency_share)
 Set the concurrent share of the variable. 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, 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, 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, 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, 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, lmm_constraint_t cnst, lmm_element_t *elem, lmm_element_t *nextelem, int *numelem)
 Get a var associated to a constraint. 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...
 
static void saturated_constraint_set_update (double usage, int cnst_light_num, dyn_light_t saturated_constraint_set, double *min_usage)
 
static void saturated_variable_set_update (s_lmm_constraint_light_t *cnst_light_tab, dyn_light_t saturated_constraint_set, lmm_system_t sys)
 
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 lmm_update_variable_bound (lmm_system_t sys, lmm_variable_t var, double bound)
 Attribute the value bound to var->bound. 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...
 
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...
 
static void lmm_update_modified_set_rec (lmm_system_t sys, lmm_constraint_t cnst)
 Update the constraint set propagating recursively to other constraints so the system should not be entirely computed. More...
 
double lmm_constraint_get_usage (lmm_constraint_t cnst)
 Returns resource load (in flop per second, or byte per second, or similar) More...
 

Variables

double sg_maxmin_precision = 0.00001
 
double sg_surf_precision = 0.00001
 
int sg_concurrency_limit = 100
 
static int Global_debug_id = 1
 
static int Global_const_debug_id = 1
 

Macro Definition Documentation

§ lmm_variable_mallocator_reset_f

#define lmm_variable_mallocator_reset_f   ((void_f_pvoid_t)nullptr)

Typedef Documentation

§ s_dyn_light_t

typedef struct s_dyn_light s_dyn_light_t

§ dyn_light_t

typedef struct s_dyn_light * dyn_light_t

Function Documentation

§ XBT_LOG_NEW_DEFAULT_SUBCATEGORY()

XBT_LOG_NEW_DEFAULT_SUBCATEGORY ( surf_maxmin  ,
surf  ,
"Logging specific to SURF (maxmin)"   
)

§ lmm_variable_mallocator_new_f()

static void * lmm_variable_mallocator_new_f ( )
static

§ lmm_variable_mallocator_free_f()

static void lmm_variable_mallocator_free_f ( void var)
static

§ lmm_update_modified_set()

static void lmm_update_modified_set ( lmm_system_t  sys,
lmm_constraint_t  cnst 
)
static

§ lmm_remove_all_modified_set()

static void lmm_remove_all_modified_set ( lmm_system_t  sys)
static

Remove all constraints of the modified_constraint_set.

Parameters
systhe lmm_system_t

§ lmm_var_free()

static void lmm_var_free ( lmm_system_t  sys,
lmm_variable_t  var 
)
static

§ lmm_cnst_free()

static void lmm_cnst_free ( lmm_system_t  sys,
lmm_constraint_t  cnst 
)
inlinestatic

§ lmm_on_disabled_var()

void lmm_on_disabled_var ( lmm_system_t  sys,
lmm_constraint_t  cnstr 
)
static

§ lmm_enable_var()

void lmm_enable_var ( lmm_system_t  sys,
lmm_variable_t  var 
)
static

§ lmm_can_enable_var()

int lmm_can_enable_var ( lmm_variable_t  var)
static

§ lmm_disable_var()

void lmm_disable_var ( lmm_system_t  sys,
lmm_variable_t  var 
)
static

§ lmm_concurrency_slack()

int lmm_concurrency_slack ( lmm_constraint_t  cnstr)
static

§ lmm_cnstrs_min_concurrency_slack()

int lmm_cnstrs_min_concurrency_slack ( lmm_variable_t  var)
static

Measure the minimum concurrency slack across all constraints where the given var is involved.

§ lmm_check_concurrency()

void lmm_check_concurrency ( lmm_system_t  sys)
static

§ lmm_element_concurrency()

int lmm_element_concurrency ( lmm_element_t  elem)
inline

§ lmm_decrease_concurrency()

void lmm_decrease_concurrency ( lmm_element_t  elem)
inline

§ lmm_increase_concurrency()

void lmm_increase_concurrency ( lmm_element_t  elem)
inline

§ lmm_system_free()

void lmm_system_free ( lmm_system_t  sys)

Free an existing Linear MaxMin system.

Parameters
sysThe lmm system to free

§ lmm_variable_remove()

static void lmm_variable_remove ( lmm_system_t  sys,
lmm_variable_t  var 
)
inlinestatic

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

Return true if the constraint is shared, and false if it's FATPIPE.

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

§ saturated_constraint_set_update()

static void saturated_constraint_set_update ( double  usage,
int  cnst_light_num,
dyn_light_t  saturated_constraint_set,
double *  min_usage 
)
inlinestatic

§ saturated_variable_set_update()

static void saturated_variable_set_update ( s_lmm_constraint_light_t cnst_light_tab,
dyn_light_t  saturated_constraint_set,
lmm_system_t  sys 
)
inlinestatic

§ 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

§ lmm_update_variable_bound()

void lmm_update_variable_bound ( lmm_system_t  sys,
lmm_variable_t  var,
double  bound 
)

Attribute the value bound to var->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_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_update_modified_set_rec()

static void lmm_update_modified_set_rec ( lmm_system_t  sys,
lmm_constraint_t  cnst 
)
static

Update the constraint set propagating recursively to other constraints so the system should not be entirely computed.

Parameters
systhe lmm_system_t
cnstthe lmm_constraint_t affected by the change

A recursive algorithm to optimize the system recalculation selecting only constraints that have changed. Each constraint change is propagated to the list of constraints for each variable.

§ lmm_constraint_get_usage()

double lmm_constraint_get_usage ( lmm_constraint_t  cnst)

Returns resource load (in flop per second, or byte per second, or similar)

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

Variable Documentation

§ sg_maxmin_precision

double sg_maxmin_precision = 0.00001

§ sg_surf_precision

double sg_surf_precision = 0.00001

§ sg_concurrency_limit

int sg_concurrency_limit = 100

§ Global_debug_id

int Global_debug_id = 1
static

§ Global_const_debug_id

int Global_const_debug_id = 1
static