src/kernel/lmm/bmf.hpp

   1 /* Copyright (c) 2004-2022. 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 SIMGRID_KERNEL_LMM_BMF_HPP
   7 #define SIMGRID_KERNEL_LMM_BMF_HPP
   8
   9 #include "src/kernel/lmm/System.hpp"
  10
  11 #ifdef __clang__
  12 // Ignore deprecation warnings with Eigen < 4.0 (see https://gitlab.com/libeigen/eigen/-/issues/1850)
  13 #pragma clang diagnostic push
  14 #pragma clang diagnostic ignored "-Wdeprecated-declarations"
  15 #endif
  16 #include <Eigen/Dense>
  17 #ifdef __clang__
  18 #pragma clang diagnostic pop
  19 #endif
  20
  21 #include <unordered_set>
  22
  23 namespace simgrid {
  24 namespace kernel {
  25 namespace lmm {
  26
  27 /** @brief Generate all combinations of valid allocation */
  28 class XBT_PUBLIC AllocationGenerator {
  29 public:
  30   explicit AllocationGenerator(Eigen::MatrixXd A);
  31
  32   /**
  33    * @brief Get next valid allocation
  34    *
  35    * @param next_alloc Allocation (OUTPUT)
  36    * @return true if there's an allocation not tested yet, false otherwise
  37    */
  38   bool next(std::vector<int>& next_alloc);
  39
  40 private:
  41   Eigen::MatrixXd A_;
  42   std::vector<int> alloc_;
  43   bool first_ = true;
  44 };
  45
  46 /**
  47  * @beginrst
  48  *
  49  * Despite the simplicity of BMF fairness definition, it's quite hard to
  50  * find a BMF allocation in the general case.
  51  *
  52  * This solver implements one possible algorithm to find a BMF, as proposed
  53  * at: https://hal.archives-ouvertes.fr/hal-01552739.
  54  *
  55  * The idea of this algorithm is that each player/flow "selects" a resource to
  56  * saturate. Then, we calculate the rate each flow would have with this allocation.
  57  * If the allocation is a valid BMF and no one needs to move, it's over. Otherwise,
  58  * each player selects a new resource to saturate based on the minimim rate possible
  59  * between all resources.
  60  *
  61  * The steps:
  62  * 1) Given an initial allocation B_i
  63  * 2) Build a matrix A'_ji and C'_ji which assures that the player receives the most
  64  * share at selected resources
  65  * 3) Solve: A'_ji * rho_i = C'_j
  66  * 4) Calculate the minimum fair rate for each resource j: f_j. The f_j represents
  67  * the maximum each flow can receive at the resource j.
  68  * 5) Builds a new vector B'_i = arg min(f_j/A_ji).
  69  * 6) Stop if B == B' (nobody needs to move), go to step 2 otherwise
  70  *
  71  * Despite the overall good performance of this algorithm, which converges in a few
  72  * iterations, we don't have any assurance about its convergence. In the worst case,
  73  * it may be needed to test all possible combination of allocations (which is exponential).
  74  *
  75  * @endrst
  76  */
  77 class XBT_PUBLIC BmfSolver {
  78 public:
  79   /**
  80    * @brief Instantiate the BMF solver
  81    *
  82    * @param A A_ji: consumption of player i on resource j
  83    * @param maxA maxA_ji: consumption of larger player i on resource j
  84    * @param C Resource capacity
  85    * @param shared Is resource shared between player or each player receives the full capacity (FATPIPE links)
  86    * @param phi Bound for each player
  87    */
  88   BmfSolver(Eigen::MatrixXd A, Eigen::MatrixXd maxA, Eigen::VectorXd C, std::vector<bool> shared, Eigen::VectorXd phi);
  89   /** @brief Solve equation system to find a fair-sharing of resources */
  90   Eigen::VectorXd solve();
  91
  92 private:
  93   using allocation_map_t = std::unordered_map<int, std::unordered_set<int>>;
  94   /**
  95    * @brief Get actual resource capacity considering bounded players
  96    *
  97    * Calculates the resource capacity considering that some players on it may be bounded by user,
  98    * i.e. an explicit limit in speed was configured
  99    *
 100    * @param resource Internal index of resource in C_ vector
 101    * @param bounded_players List of players that are externally bounded
 102    * @return Actual resource capacity
 103    */
 104   double get_resource_capacity(int resource, const std::vector<int>& bounded_players) const;
 105   /**
 106    * @brief Get maxmin share of the resource
 107    *
 108    * @param resource Internal index of resource in C_ vector
 109    * @param bounded_players List of players that are externally bounded
 110    * @return maxmin share
 111    */
 112   double get_maxmin_share(int resource, const std::vector<int>& bounded_players) const;
 113   /**
 114    * @brief Auxiliary method to get list of bounded player from allocation
 115    *
 116    * @param alloc Current allocation
 117    * @return list of bounded players
 118    */
 119   std::vector<int> get_bounded_players(const allocation_map_t& alloc) const;
 120
 121   /**
 122    * @brief Given an allocation calculates the speed/rho for each player
 123    *
 124    * Do the magic!!
 125    * Builds 2 auxiliares matrices A' and C' and solves the system: rho_i = inv(A'_ji) * C'_j
 126    *
 127    * All resources in A' and C' are saturated, i.e., sum(A'_j * rho_i) = C'_j.
 128    *
 129    * The matrix A' is built as follows:
 130    * - For each resource j in alloc: copy row A_j to A'
 131    * - If 2 players (i, k) share a same resource, assure fairness by adding a row in A' such as:
 132    *   -  A_ji*rho_i - Ajk*rho_j = 0
 133    *
 134    * @param alloc for each resource, players that chose to saturate it
 135    * @return Vector rho with "players' speed"
 136    */
 137   Eigen::VectorXd equilibrium(const allocation_map_t& alloc) const;
 138
 139   /**
 140    * @brief Given a fair_sharing vector, gets the allocation
 141    *
 142    * The allocation for player i is given by: min(bound, f_j/A_ji).
 143    * The minimum between all fair-sharing and the external bound (if any)
 144    *
 145    * The algorithm dictates a random initial allocation. For simplicity, we opt to use the same
 146    * logic with the fair_sharing vector.
 147    *
 148    * @param fair_sharing Fair sharing vector
 149    * @param initial Is this the initial allocation?
 150    * @return allocation vector
 151    */
 152   bool get_alloc(const Eigen::VectorXd& fair_sharing, const allocation_map_t& last_alloc, allocation_map_t& alloc,
 153                  bool initial);
 154
 155   bool disturb_allocation(allocation_map_t& alloc, std::vector<int>& alloc_by_player);
 156   /**
 157    * @brief Calculates the fair sharing for each resource
 158    *
 159    * Basically 3 options:
 160    * 1) resource in allocation: A_ji*rho_i since all players who selected this resource have the same share
 161    * 2) resource not selected by saturated (fully used): divide it by the number of players C_/n_players
 162    * 3) resource not selected and not-saturated: no limitation
 163    *
 164    * @param alloc Allocation map (resource-> players)
 165    * @param rho Speed for each player i
 166    * @param fair_sharing Output vector, fair sharing for each resource j
 167    */
 168   void set_fair_sharing(const allocation_map_t& alloc, const Eigen::VectorXd& rho, Eigen::VectorXd& fair_sharing) const;
 169
 170   /**
 171    * @brief Check if allocation is BMF
 172    *
 173    * To be a bmf allocation it must:
 174    * - respect the capacity of all resources
 175    * - saturate at least 1 resource
 176    * - every player receives maximum share in at least 1 saturated resource
 177    * @param rho Allocation
 178    * @return true if BMF false otherwise
 179    */
 180   bool is_bmf(const Eigen::VectorXd& rho) const;
 181   std::vector<int> alloc_map_to_vector(const allocation_map_t& alloc) const;
 182
 183   /**
 184    * @brief Set of debug functions to print the different objects
 185    */
 186   template <typename T> std::string debug_eigen(const T& obj) const;
 187   template <typename C> std::string debug_vector(const C& container) const;
 188   std::string debug_alloc(const allocation_map_t& alloc) const;
 189
 190   Eigen::MatrixXd A_;    //!< A_ji: resource usage matrix, each row j represents a resource and col i a flow/player
 191   Eigen::MatrixXd maxA_; //!< maxA_ji,  similar as A_, but containing the maximum consumption of player i (if player a
 192                          //!< single flow it's equal to A_)
 193   Eigen::VectorXd C_;    //!< C_j Capacity of each resource
 194   std::vector<bool> C_shared_; //!< shared_j Resource j is shared or not
 195   Eigen::VectorXd phi_;        //!< phi_i bound for each player
 196
 197   std::set<std::vector<int>> allocations_; //!< set of already tested allocations, since last identified loop
 198   AllocationGenerator gen_;
 199   static constexpr int NO_RESOURCE = -1;                    //!< flag to indicate player has selected no resource
 200   int max_iteration_;                                       //!< number maximum of iterations of BMF algorithm
 201 };
 202
 203 /**
 204  * @beginrst
 205  *
 206  * A BMF (bottleneck max fairness) solver to resolve inequation systems.
 207  *
 208  * Usually, SimGrid relies on a *max-min fairness* solver to share the resources.
 209  * Max-min is great when sharing homogenous resources, however it cannot be used with heterogeneous resources.
 210  *
 211  * BMF is a natural alternative to max-min, providing a fair-sharing of heterogeneous resources (CPU, network, disk).
 212  * It is specially relevant for the implementation of parallel tasks whose sharing involves different
 213  * kinds of resources.
 214  *
 215  * BMF assures that every flow receives the maximum share possible in at least 1 bottleneck (fully used) resource.
 216  *
 217  * The BMF is characterized by:
 218  * - A_ji: a matrix of requirement for flows/player. For each resource j, and flow i, A_ji represents the utilization
 219  * of resource j for 1 unit of the flow i.
 220  * - rho_i: the rate allocated for flow i (same among all resources)
 221  * - C_j: the capacity of each resource (can be bytes/s, flops/s, etc)
 222  *
 223  * Therefore, these conditions need to satisfied to an allocation be considered a BMF:
 224  * 1) All constraints are respected (flows cannot use more than the resource has available)
 225  *   - for all resource j and player i: A_ji * rho_i <= C_j
 226  * 2) At least 1 resource is fully used (bottleneck).
 227  *   - for some resource j: A_ji * rho_i = C_j
 228  * 3) Each flow (player) receives the maximum share in at least 1 bottleneck.
 229  *   - for all player i: exist a resource j: A_ji * rho_i >= A_jk * rho_k for all other player k
 230  *
 231  * Despite the prove of existence of a BMF allocation in the general case, it may not
 232  * be unique, which leads to possible different rate for the applications.
 233  *
 234  * More details about BMF can be found at: https://hal.inria.fr/hal-01243985/document
 235  *
 236  * @endrst
 237  */
 238 /**
 239  * @brief Bottleneck max-fair system
 240  */
 241 class XBT_PUBLIC BmfSystem : public System {
 242 public:
 243   using System::System;
 244
 245 private:
 246   /** @brief Implements the solve method to calculate a BMF allocation */
 247   void do_solve() final;
 248   using allocation_map_t = std::unordered_map<int, std::unordered_set<int>>;
 249   /**
 250    * @brief Solve equation system to find a fair-sharing of resources
 251    *
 252    * @param cnst_list Constraint list (modified for selective update or active)
 253    */
 254   template <class CnstList> void bmf_solve(const CnstList& cnst_list);
 255   /**
 256    * @brief Iterates over system and build the consumption matrix A_ji and maxA_ji
 257    *
 258    * Each row j represents a resource and each col i a player/flow
 259    *
 260    * Considers only active variables to build the matrix.
 261    *
 262    * @param number_cnsts Number of constraints in the system
 263    * @param A Consumption matrix (OUTPUT)
 264    * @param maxA Max subflow consumption matrix (OUTPUT)
 265    * @param phi Bounds for variables
 266    */
 267   void get_flows_data(Eigen::Index number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi);
 268   /**
 269    * @brief Builds the vector C_ with resource's capacity
 270    *
 271    * @param cnst_list Constraint list (modified for selective update or active)
 272    * @param C Resource capacity vector
 273    * @param shared Resource is shared or not (fatpipe links)
 274    */
 275   template <class CnstList>
 276   void get_constraint_data(const CnstList& cnst_list, Eigen::VectorXd& C, std::vector<bool>& shared);
 277
 278   std::unordered_map<int, Variable*> idx2Var_; //!< Map player index (and position in matrices) to system's variable
 279   std::unordered_map<const Constraint*, int> cnst2idx_; //!< Conversely map constraint to index
 280 };
 281
 282 } // namespace lmm
 283 } // namespace kernel
 284 } // namespace simgrid
 285
 286 #endif