Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Changes to the Surf LMM:
[simgrid.git] / src / surf / maxmin_private.hpp
1 /* Copyright (c) 2004-2014. The SimGrid Team.
2  * All rights reserved.                                                     */
3
4 /* This program is free software; you can redistribute it and/or modify it
5  * under the terms of the license (GNU LGPL) which comes with this package. */
6
7 #ifndef _SURF_MAXMIN_PRIVATE_H
8 #define _SURF_MAXMIN_PRIVATE_H
9
10 #include <xbt/base.h>
11
12 #include "surf/maxmin.h"
13 #include "xbt/swag.h"
14 #include "xbt/mallocator.h"
15 #include "surf_interface.hpp"
16
17 /** @ingroup SURF_lmm
18  * @brief LMM element
19  * Elements can be seen as glue between constraint objects and variable objects.
20  * Basically, each variable will have a set of elements, one for each constraint where it is involved.
21  * Then, it is used to list all variables involved in constraint through constraint's element_set lists, or vice-versa list all constraints for a given variable.  
22  */
23 typedef struct lmm_element {
24   /* hookup to constraint */
25   s_xbt_swag_hookup_t element_set_hookup;
26   s_xbt_swag_hookup_t active_element_set_hookup;
27
28   lmm_constraint_t constraint;
29   lmm_variable_t variable;
30   double value;
31 } s_lmm_element_t;
32 #define make_elem_active(elem) xbt_swag_insert_at_head(elem,&(elem->constraint->active_element_set))
33 #define make_elem_inactive(elem) xbt_swag_remove(elem,&(elem->constraint->active_element_set))
34
35 typedef struct lmm_constraint_light {
36   double remaining_over_usage;
37   lmm_constraint_t cnst;
38 } s_lmm_constraint_light_t;
39
40 /** @ingroup SURF_lmm
41  * @brief LMM constraint
42  * Each constraint contains several partially overlapping logical sets of elements: 
43  * \li 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).
44  * \li Enabled elements which variable's weight is non-zero. They are utilized in some LMM functions.
45  * \li 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. 
46  * 
47  * Also note that we maintain element_set such that all enabled elements (i.e. var->weight>0) come before disabled elements.
48  */
49 typedef struct lmm_constraint {
50   /* hookup to system */
51   s_xbt_swag_hookup_t constraint_set_hookup;
52   s_xbt_swag_hookup_t active_constraint_set_hookup;
53   s_xbt_swag_hookup_t modified_constraint_set_hookup;
54   s_xbt_swag_hookup_t saturated_constraint_set_hookup;
55
56   //TODO we could split element_set in, say, enabled_element_set and disabled_element_set depending on var->weight
57   //Could make code more readable and should not pose implementation issues (only lmm_print does not stop at the end of enabled elements
58   s_xbt_swag_t element_set;     /* a list of lmm_element_t */
59   s_xbt_swag_t active_element_set;      /* a list of lmm_element_t */
60   double remaining;
61   double usage;
62   double bound;
63   int concurrency_limit; /* The maximum number of variables that may be enabled at any time (stage variables if necessary) */
64   //TODO MARTIN Check maximum value across resources at the end of simulation and give a warning is more than e.g. 500 
65   int concurrency_current; /* The current concurrency */
66   int concurrency_maximum; /* The maximum number of (enabled and disabled) variables associated to the constraint at any given time (essentially for tracing)*/
67   
68   int sharing_policy; /* see @e_surf_link_sharing_policy_t (0: FATPIPE, 1: SHARED, 2: FULLDUPLEX) */
69   void *id;
70   int id_int;
71   double lambda;
72   double new_lambda;
73   lmm_constraint_light_t cnst_light;
74 } s_lmm_constraint_t;
75
76 /** @ingroup SURF_lmm
77  * @brief LMM variable
78  * 
79  * 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
80  */
81 typedef struct lmm_variable {
82   /* hookup to system */
83   s_xbt_swag_hookup_t variable_set_hookup;
84   s_xbt_swag_hookup_t saturated_variable_set_hookup;
85
86   s_lmm_element_t *cnsts;
87   int cnsts_size;
88   int cnsts_number;
89   double weight; /* weight > 0 means variable is considered by LMM, weight == 0 means variable is not considered by LMM*/
90   double staged_weight; /* If non-zero, variable is staged for addition as soon as maxconcurrency constraints will be met */
91   double bound;
92   double value;
93   short int concurrency_share; /* The maximum number of elements that variable will add to a constraint */
94   void *id;
95   int id_int;
96   unsigned visited;             /* used by lmm_update_modified_set */
97   /* \begin{For Lagrange only} */
98   double mu;
99   double new_mu;
100   double (*func_f) (struct lmm_variable * var, double x);       /* (f)    */
101   double (*func_fp) (struct lmm_variable * var, double x);      /* (f')    */
102   double (*func_fpi) (struct lmm_variable * var, double x);     /* (f')^{-1}    */
103   /* \end{For Lagrange only} */
104 } s_lmm_variable_t;
105
106 /** @ingroup SURF_lmm
107  * @brief LMM system
108  */
109 typedef struct lmm_system {
110   int modified;
111   int selective_update_active;  /* flag to update partially the system only selecting changed portions */
112   unsigned visited_counter;     /* used by lmm_update_modified_set  and lmm_remove_modified_set to cleverly (un-)flag the constraints (more details in these functions)*/
113   s_xbt_swag_t variable_set;    /* a list of lmm_variable_t */
114   s_xbt_swag_t constraint_set;  /* a list of lmm_constraint_t */
115
116   s_xbt_swag_t active_constraint_set;   /* a list of lmm_constraint_t */
117   s_xbt_swag_t modified_constraint_set; /* a list of modified lmm_constraint_t */
118
119   s_xbt_swag_t saturated_variable_set;  /* a list of lmm_variable_t */
120   s_xbt_swag_t saturated_constraint_set;        /* a list of lmm_constraint_t_t */
121
122   simgrid::surf::ActionLmmListPtr keep_track;
123
124   xbt_mallocator_t variable_mallocator;
125 } s_lmm_system_t;
126
127 #define extract_variable(sys) xbt_swag_extract(&(sys->variable_set))
128 #define extract_constraint(sys) xbt_swag_extract(&(sys->constraint_set))
129 #define insert_constraint(sys,cnst) xbt_swag_insert(cnst,&(sys->constraint_set))
130 #define remove_variable(sys,var) do {xbt_swag_remove(var,&(sys->variable_set));\
131                                  xbt_swag_remove(var,&(sys->saturated_variable_set));} while(0)
132 #define remove_constraint(sys,cnst) do {xbt_swag_remove(cnst,&(sys->constraint_set));\
133                                         xbt_swag_remove(cnst,&(sys->saturated_constraint_set));} while(0)
134 #define make_constraint_active(sys,cnst) xbt_swag_insert(cnst,&(sys->active_constraint_set))
135 #define make_constraint_inactive(sys,cnst) \
136   do { xbt_swag_remove(cnst, &sys->active_constraint_set);              \
137     xbt_swag_remove(cnst, &sys->modified_constraint_set); } while (0)
138
139 /** @ingroup SURF_lmm
140  * @brief Print informations about a lmm system
141  * 
142  * @param sys A lmm system
143  */
144 XBT_PRIVATE void lmm_print(lmm_system_t sys);
145
146 extern XBT_PRIVATE double (*func_f_def) (lmm_variable_t, double);
147 extern XBT_PRIVATE double (*func_fp_def) (lmm_variable_t, double);
148 extern XBT_PRIVATE double (*func_fpi_def) (lmm_variable_t, double);
149
150 #endif                          /* _SURF_MAXMIN_PRIVATE_H */
151
152