1 /* Copyright (c) 2004-2017. The SimGrid Team. All rights reserved. */
3 /* This program is free software; you can redistribute it and/or modify it
4 * under the terms of the license (GNU LGPL) which comes with this package. */
6 #ifndef SURF_MAXMIN_PRIVATE_H
7 #define SURF_MAXMIN_PRIVATE_H
9 #include "surf/maxmin.hpp"
10 #include "surf_interface.hpp"
11 #include "xbt/mallocator.h"
18 * Elements can be seen as glue between constraint objects and variable objects.
19 * Basically, each variable will have a set of elements, one for each constraint where it is involved.
20 * Then, it is used to list all variables involved in constraint through constraint's xxx_element_set lists, or vice-versa list all constraints for a given variable.
22 struct s_lmm_element_t {
23 /* hookup to constraint */
24 s_xbt_swag_hookup_t enabled_element_set_hookup;
25 s_xbt_swag_hookup_t disabled_element_set_hookup;
26 s_xbt_swag_hookup_t active_element_set_hookup;
28 lmm_constraint_t constraint;
29 lmm_variable_t variable;
31 // consumption_weight: impact of 1 byte or flop of your application onto the resource (in byte or flop)
32 // - if CPU, then probably 1.
33 // - If network, then 1 in forward direction and 0.05 backward for the ACKs
34 double consumption_weight;
36 #define make_elem_active(elem) xbt_swag_insert_at_head((elem), &((elem)->constraint->active_element_set))
37 #define make_elem_inactive(elem) xbt_swag_remove((elem), &((elem)->constraint->active_element_set))
39 struct s_lmm_constraint_light_t {
40 double remaining_over_usage;
41 lmm_constraint_t cnst;
45 * @brief LMM constraint
46 * Each constraint contains several partially overlapping logical sets of elements:
47 * \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).
48 * \li Enabled elements which variable's weight is non-zero. They are utilized in some LMM functions.
49 * \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.
52 class s_lmm_constraint_t {
54 s_lmm_constraint_t() = default;
55 s_lmm_constraint_t(void* id_value, double bound_value);
57 /** @brief Share a constraint. FIXME: name is misleading */
58 void shared() { sharing_policy = 0; }
61 * @brief Check if a constraint is shared (shared by default)
62 * @return 1 if shared, 0 otherwise
64 int get_sharing_policy() const { return sharing_policy; }
67 * @brief Get the usage of the constraint after the last lmm solve
68 * @return The usage of the constraint
70 double get_usage() const;
71 int get_variable_amount() const;
74 * @brief Sets the concurrency limit for this constraint
75 * @param concurrency_limit The concurrency limit to use for this constraint
77 void set_concurrency_limit(int limit)
79 xbt_assert(limit < 0 || concurrency_maximum <= limit,
80 "New concurrency limit should be larger than observed concurrency maximum. Maybe you want to call"
81 " concurrency_maximum_reset() to reset the maximum?");
82 concurrency_limit = limit;
86 * @brief Gets the concurrency limit for this constraint
87 * @return The concurrency limit used by this constraint
89 int get_concurrency_limit() const { return concurrency_limit; }
92 * @brief Reset the concurrency maximum for a given variable (we will update the maximum to reflect constraint
95 void reset_concurrency_maximum() { concurrency_maximum = 0; }
98 * @brief Get the concurrency maximum for a given variable (which reflects constraint evolution).
99 * @return the maximum concurrency of the constraint
101 int get_concurrency_maximum() const
103 xbt_assert(concurrency_limit < 0 || concurrency_maximum <= concurrency_limit,
104 "Very bad: maximum observed concurrency is higher than limit. This is a bug of SURF, please report it.");
105 return concurrency_maximum;
108 int get_concurrency_slack() const
110 return concurrency_limit < 0 ? std::numeric_limits<int>::max() : concurrency_limit - concurrency_current;
114 * @brief Get a var associated to a constraint
115 * @details Get the first variable of the next variable of elem if elem is not NULL
116 * @param elem A element of constraint of the constraint or NULL
117 * @return A variable associated to a constraint
119 lmm_variable_t get_variable(lmm_element_t* elem) const;
122 * @brief Get a var associated to a constraint
123 * @details Get the first variable of the next variable of elem if elem is not NULL
124 * @param elem A element of constraint of the constraint or NULL
125 * @param nextelem A element of constraint of the constraint or NULL, the one after elem
126 * @param numelem parameter representing the number of elements to go
127 * @return A variable associated to a constraint
129 lmm_variable_t get_variable_safe(lmm_element_t* elem, lmm_element_t* nextelem, int* numelem) const;
132 * @brief Get the data associated to a constraint
133 * @return The data associated to the constraint
135 void* get_id() const { return id; }
137 /* hookup to system */
138 s_xbt_swag_hookup_t constraint_set_hookup = {nullptr, nullptr};
139 s_xbt_swag_hookup_t active_constraint_set_hookup = {nullptr, nullptr};
140 s_xbt_swag_hookup_t modified_constraint_set_hookup = {nullptr, nullptr};
141 s_xbt_swag_hookup_t saturated_constraint_set_hookup = {nullptr, nullptr};
142 s_xbt_swag_t enabled_element_set; /* a list of lmm_element_t */
143 s_xbt_swag_t disabled_element_set; /* a list of lmm_element_t */
144 s_xbt_swag_t active_element_set; /* a list of lmm_element_t */
148 //TODO MARTIN Check maximum value across resources at the end of simulation and give a warning is more than e.g. 500
149 int concurrency_current; /* The current concurrency */
150 int concurrency_maximum; /* The maximum number of (enabled and disabled) variables associated to the constraint at any given time (essentially for tracing)*/
152 int sharing_policy; /* see @e_surf_link_sharing_policy_t (0: FATPIPE, 1: SHARED, 2: FULLDUPLEX) */
156 lmm_constraint_light_t cnst_light;
159 static int Global_debug_id;
160 int concurrency_limit; /* The maximum number of variables that may be enabled at any time (stage variables if
165 /** @ingroup SURF_lmm
166 * @brief LMM variable
168 * 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
170 struct s_lmm_variable_t {
171 /* hookup to system */
172 s_xbt_swag_hookup_t variable_set_hookup;
173 s_xbt_swag_hookup_t saturated_variable_set_hookup;
175 std::vector<s_lmm_element_t> cnsts;
177 // sharing_weight: variable's impact on the resource during the sharing
178 // if == 0, the variable is not considered by LMM
179 // on CPU, actions with N threads have a sharing of N
180 // on network, the actions with higher latency have a lesser sharing_weight
181 double sharing_weight;
183 double staged_weight; /* If non-zero, variable is staged for addition as soon as maxconcurrency constraints will be met */
186 short int concurrency_share; /* The maximum number of elements that variable will add to a constraint */
187 simgrid::surf::Action* id;
189 unsigned visited; /* used by lmm_update_modified_set */
190 /* \begin{For Lagrange only} */
193 double (*func_f)(s_lmm_variable_t* var, double x); /* (f) */
194 double (*func_fp)(s_lmm_variable_t* var, double x); /* (f') */
195 double (*func_fpi)(s_lmm_variable_t* var, double x); /* (f')^{-1} */
196 /* \end{For Lagrange only} */
199 /** @ingroup SURF_lmm
202 class s_lmm_system_t {
205 * @brief Create a new Linear MaxMim system
206 * @param selective_update whether we should do lazy updates
208 s_lmm_system_t(bool selective_update);
209 /** @brief Free an existing Linear MaxMin system */
213 * @brief Create a new Linear MaxMin constraint
214 * @param id Data associated to the constraint (e.g.: a network link)
215 * @param bound_value The bound value of the constraint
217 lmm_constraint_t constraint_new(void* id, double bound_value);
220 * @brief Create a new Linear MaxMin variable
221 * @param id Data associated to the variable (e.g.: a network communication)
222 * @param weight_value The weight of the variable (0.0 if not used)
223 * @param bound The maximum value of the variable (-1.0 if no maximum value)
224 * @param number_of_constraints The maximum number of constraint to associate to the variable
226 lmm_variable_t variable_new(simgrid::surf::Action* id, double weight_value, double bound, int number_of_constraints);
229 * @brief Free a variable
230 * @param var The variable to free
232 void variable_free(lmm_variable_t var);
235 * @brief Associate a variable to a constraint with a coefficient
236 * @param cnst A constraint
237 * @param var A variable
238 * @param value The coefficient associated to the variable in the constraint
240 void expand(lmm_constraint_t cnst, lmm_variable_t var, double value);
243 * @brief Add value to the coefficient between a constraint and a variable or create one
244 * @param cnst A constraint
245 * @param var A variable
246 * @param value The value to add to the coefficient associated to the variable in the constraint
248 void expand_add(lmm_constraint_t cnst, lmm_variable_t var, double value);
251 * @brief Update the bound of a variable
252 * @param var A constraint
253 * @param bound The new bound
255 void update_variable_bound(lmm_variable_t var, double bound);
258 * @brief Update the weight of a variable
259 * @param var A variable
260 * @param weight The new weight of the variable
262 void update_variable_weight(lmm_variable_t var, double weight);
265 * @brief Update a constraint bound
266 * @param cnst A constraint
267 * @param bound The new bound of the consrtaint
269 void update_constraint_bound(lmm_constraint_t cnst, double bound);
272 * @brief [brief description]
273 * @param cnst A constraint
274 * @return [description]
276 int constraint_used(lmm_constraint_t cnst) { return xbt_swag_belongs(cnst, &active_constraint_set); }
278 /** @brief Print the lmm system */
281 /** @brief Solve the lmm system */
285 static void* variable_mallocator_new_f();
286 static void variable_mallocator_free_f(void* var);
288 void var_free(lmm_variable_t var);
289 void cnst_free(lmm_constraint_t cnst);
290 lmm_variable_t extract_variable() { return static_cast<lmm_variable_t>(xbt_swag_extract(&variable_set)); }
291 lmm_constraint_t extract_constraint() { return static_cast<lmm_constraint_t>(xbt_swag_extract(&constraint_set)); }
292 void insert_constraint(lmm_constraint_t cnst) { xbt_swag_insert(cnst, &constraint_set); }
293 void remove_variable(lmm_variable_t var)
295 xbt_swag_remove(var, &variable_set);
296 xbt_swag_remove(var, &saturated_variable_set);
298 void remove_constraint(lmm_constraint_t cnst) // FIXME: unused
300 xbt_swag_remove(cnst, &constraint_set);
301 xbt_swag_remove(cnst, &saturated_constraint_set);
303 void make_constraint_active(lmm_constraint_t cnst) { xbt_swag_insert(cnst, &active_constraint_set); }
304 void make_constraint_inactive(lmm_constraint_t cnst)
306 xbt_swag_remove(cnst, &active_constraint_set);
307 xbt_swag_remove(cnst, &modified_constraint_set);
310 void enable_var(lmm_variable_t var);
311 void disable_var(lmm_variable_t var);
312 void on_disabled_var(lmm_constraint_t cnstr);
315 * @brief Update the value of element linking the constraint and the variable
316 * @param cnst A constraint
317 * @param var A variable
318 * @param value The new value
320 void update(lmm_constraint_t cnst, lmm_variable_t var, double value);
322 void update_modified_set(lmm_constraint_t cnst);
323 void update_modified_set_rec(lmm_constraint_t cnst);
325 /** @brief Remove all constraints of the modified_constraint_set. */
326 void remove_all_modified_set();
327 void check_concurrency();
331 s_xbt_swag_t variable_set; /* a list of lmm_variable_t */
332 s_xbt_swag_t active_constraint_set; /* a list of lmm_constraint_t */
333 s_xbt_swag_t saturated_variable_set; /* a list of lmm_variable_t */
334 s_xbt_swag_t saturated_constraint_set; /* a list of lmm_constraint_t_t */
336 simgrid::surf::ActionLmmListPtr keep_track;
338 void (*solve_fun)(lmm_system_t self);
341 bool selective_update_active; /* flag to update partially the system only selecting changed portions */
342 unsigned visited_counter; /* used by lmm_update_modified_set and lmm_remove_modified_set to cleverly (un-)flag the
343 * constraints (more details in these functions) */
344 s_xbt_swag_t constraint_set; /* a list of lmm_constraint_t */
345 s_xbt_swag_t modified_constraint_set; /* a list of modified lmm_constraint_t */
346 xbt_mallocator_t variable_mallocator;
349 extern XBT_PRIVATE double (*func_f_def) (lmm_variable_t, double);
350 extern XBT_PRIVATE double (*func_fp_def) (lmm_variable_t, double);
351 extern XBT_PRIVATE double (*func_fpi_def) (lmm_variable_t, double);
353 #endif /* SURF_MAXMIN_PRIVATE_H */