src/surf/maxmin_private.hpp

   1 /* Copyright (c) 2004-2017. The SimGrid Team. All rights reserved.          */
   2
   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. */
   5
   6 #ifndef SURF_MAXMIN_PRIVATE_H
   7 #define SURF_MAXMIN_PRIVATE_H
   8
   9 #include "surf/maxmin.hpp"
  10 #include "surf_interface.hpp"
  11 #include "xbt/mallocator.h"
  12 #include "xbt/swag.h"
  13
  14 #include <vector>
  15
  16 /** @ingroup SURF_lmm
  17  * @brief LMM element
  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.
  21  */
  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;
  27
  28   lmm_constraint_t constraint;
  29   lmm_variable_t variable;
  30
  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;
  35 };
  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))
  38
  39 struct s_lmm_constraint_light_t {
  40   double remaining_over_usage;
  41   lmm_constraint_t cnst;
  42 };
  43
  44 /** @ingroup SURF_lmm
  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.
  50  *
  51  */
  52 struct s_lmm_constraint_t {
  53   /* hookup to system */
  54   s_xbt_swag_hookup_t constraint_set_hookup;
  55   s_xbt_swag_hookup_t active_constraint_set_hookup;
  56   s_xbt_swag_hookup_t modified_constraint_set_hookup;
  57   s_xbt_swag_hookup_t saturated_constraint_set_hookup;
  58
  59   s_xbt_swag_t enabled_element_set;     /* a list of lmm_element_t */
  60   s_xbt_swag_t disabled_element_set;     /* a list of lmm_element_t */
  61   s_xbt_swag_t active_element_set;      /* a list of lmm_element_t */
  62   double remaining;
  63   double usage;
  64   double bound;
  65   int concurrency_limit; /* The maximum number of variables that may be enabled at any time (stage variables if necessary) */
  66   //TODO MARTIN Check maximum value across resources at the end of simulation and give a warning is more than e.g. 500
  67   int concurrency_current; /* The current concurrency */
  68   int concurrency_maximum; /* The maximum number of (enabled and disabled) variables associated to the constraint at any given time (essentially for tracing)*/
  69
  70   int sharing_policy; /* see @e_surf_link_sharing_policy_t (0: FATPIPE, 1: SHARED, 2: FULLDUPLEX) */
  71   void *id;
  72   int id_int;
  73   double lambda;
  74   double new_lambda;
  75   lmm_constraint_light_t cnst_light;
  76 };
  77
  78 /** @ingroup SURF_lmm
  79  * @brief LMM variable
  80  *
  81  * 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
  82  */
  83 struct s_lmm_variable_t {
  84   /* hookup to system */
  85   s_xbt_swag_hookup_t variable_set_hookup;
  86   s_xbt_swag_hookup_t saturated_variable_set_hookup;
  87
  88   std::vector<s_lmm_element_t> cnsts;
  89
  90   // sharing_weight: variable's impact on the resource during the sharing
  91   //   if == 0, the variable is not considered by LMM
  92   //   on CPU, actions with N threads have a sharing of N
  93   //   on network, the actions with higher latency have a lesser sharing_weight
  94   double sharing_weight;
  95
  96   double staged_weight; /* If non-zero, variable is staged for addition as soon as maxconcurrency constraints will be met */
  97   double bound;
  98   double value;
  99   short int concurrency_share; /* The maximum number of elements that variable will add to a constraint */
 100   simgrid::surf::Action* id;
 101   int id_int;
 102   unsigned visited;             /* used by lmm_update_modified_set */
 103   /* \begin{For Lagrange only} */
 104   double mu;
 105   double new_mu;
 106   double (*func_f)(s_lmm_variable_t* var, double x);   /* (f)    */
 107   double (*func_fp)(s_lmm_variable_t* var, double x);  /* (f')    */
 108   double (*func_fpi)(s_lmm_variable_t* var, double x); /* (f')^{-1}    */
 109   /* \end{For Lagrange only} */
 110 };
 111
 112 /** @ingroup SURF_lmm
 113  * @brief LMM system
 114  */
 115 struct s_lmm_system_t {
 116   int modified;
 117   bool selective_update_active;  /* flag to update partially the system only selecting changed portions */
 118   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)*/
 119   s_xbt_swag_t variable_set;    /* a list of lmm_variable_t */
 120   s_xbt_swag_t constraint_set;  /* a list of lmm_constraint_t */
 121
 122   s_xbt_swag_t active_constraint_set;   /* a list of lmm_constraint_t */
 123   s_xbt_swag_t modified_constraint_set; /* a list of modified lmm_constraint_t */
 124
 125   s_xbt_swag_t saturated_variable_set;  /* a list of lmm_variable_t */
 126   s_xbt_swag_t saturated_constraint_set;        /* a list of lmm_constraint_t_t */
 127
 128   simgrid::surf::ActionLmmListPtr keep_track;
 129
 130   xbt_mallocator_t variable_mallocator;
 131
 132   void (*solve_fun)(lmm_system_t self);
 133 };
 134
 135 #define extract_variable(sys) xbt_swag_extract(&((sys)->variable_set))
 136 #define extract_constraint(sys) xbt_swag_extract(&((sys)->constraint_set))
 137 #define insert_constraint(sys, cnst) xbt_swag_insert((cnst), &((sys)->constraint_set))
 138 #define remove_variable(sys, var)                                                                                      \
 139   do {                                                                                                                 \
 140     xbt_swag_remove(var, &((sys)->variable_set));                                                                      \
 141     xbt_swag_remove(var, &((sys)->saturated_variable_set));                                                            \
 142   } while (0)
 143 #define remove_constraint(sys, cnst)                                                                                   \
 144   do {                                                                                                                 \
 145     xbt_swag_remove((cnst), &((sys)->constraint_set));                                                                 \
 146     xbt_swag_remove((cnst), &((sys)->saturated_constraint_set));                                                       \
 147   } while (0)
 148 #define make_constraint_active(sys, cnst) xbt_swag_insert((cnst), &((sys)->active_constraint_set))
 149 #define make_constraint_inactive(sys, cnst)                                                                            \
 150   do {                                                                                                                 \
 151     xbt_swag_remove((cnst), &(sys)->active_constraint_set);                                                            \
 152     xbt_swag_remove((cnst), &(sys)->modified_constraint_set);                                                          \
 153   } while (0)
 154
 155 /** @ingroup SURF_lmm
 156  * @brief Print information about a lmm system
 157  *
 158  * @param sys A lmm system
 159  */
 160 //XBT_PRIVATE void lmm_print(lmm_system_t sys);
 161
 162 extern XBT_PRIVATE double (*func_f_def) (lmm_variable_t, double);
 163 extern XBT_PRIVATE double (*func_fp_def) (lmm_variable_t, double);
 164 extern XBT_PRIVATE double (*func_fpi_def) (lmm_variable_t, double);
 165
 166 #endif /* SURF_MAXMIN_PRIVATE_H */