SimGrid  3.13
Versatile Simulation of Distributed Systems
maxmin.cpp File Reference
#include "xbt/sysdep.h"
#include "xbt/log.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)NULL)
 

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 (void)
 
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 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 (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...
 
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 total resource load. More...
 

Variables

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

Macro Definition Documentation

#define lmm_variable_mallocator_reset_f   ((void_f_pvoid_t)NULL)

Typedef Documentation

typedef struct s_dyn_light s_dyn_light_t
typedef struct s_dyn_light * dyn_light_t

Function Documentation

XBT_LOG_NEW_DEFAULT_SUBCATEGORY ( surf_maxmin  ,
surf  ,
"Logging specific to SURF (maxmin)"   
)
static void * lmm_variable_mallocator_new_f ( void  )
static
static void lmm_variable_mallocator_free_f ( void var)
static
static void lmm_update_modified_set ( lmm_system_t  sys,
lmm_constraint_t  cnst 
)
static
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
static void lmm_var_free ( lmm_system_t  sys,
lmm_variable_t  var 
)
static
static void lmm_cnst_free ( lmm_system_t  sys,
lmm_constraint_t  cnst 
)
inlinestatic
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)
static

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

Parameters
Thevariable to check for
void lmm_check_concurrency ( lmm_system_t  sys)
static
int lmm_element_concurrency ( lmm_element_t  elem)
inline
void lmm_decrease_concurrency ( lmm_element_t  elem)
inline
void lmm_increase_concurrency ( lmm_element_t  elem)
inline
void lmm_system_free ( lmm_system_t  sys)

Free an existing Linear MaxMin system.

Parameters
sysThe lmm system to free
static void lmm_variable_remove ( lmm_system_t  sys,
lmm_variable_t  var 
)
inlinestatic
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
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
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
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
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
void lmm_constraint_shared ( lmm_constraint_t  cnst)

Share a constraint.

Parameters
cnstThe constraint to share
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)

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

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
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
static void saturated_constraint_set_update ( double  usage,
int  cnst_light_num,
dyn_light_t  saturated_constraint_set,
double *  min_usage 
)
inlinestatic
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
void lmm_print ( lmm_system_t  sys)

Print the lmm system.

Parameters
sysThe lmm system to print
void lmm_solve ( lmm_system_t  sys)

Solve the lmm system.

Parameters
sysThe lmm system to solve
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.

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

double lmm_constraint_get_usage ( lmm_constraint_t  cnst)

Returns total resource load.

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

Parameters
cnstthe lmm_constraint_t associated to the resource

This is dead code, but we may use it later for debug/trace.

Variable Documentation

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