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 SURF_BMF_HPP
   7 #define SURF_BMF_HPP
   8
   9 #include "src/kernel/lmm/maxmin.hpp"
  10 #include <boost/container_hash/hash.hpp>
  11 #include <eigen3/Eigen/Dense>
  12 #include <unordered_set>
  13
  14 namespace simgrid {
  15 namespace kernel {
  16 namespace lmm {
  17
  18 class XBT_PUBLIC AllocationGenerator {
  19 public:
  20   explicit AllocationGenerator(Eigen::MatrixXd A);
  21
  22   bool next(std::vector<int>& next_alloc);
  23
  24 private:
  25   Eigen::MatrixXd A_; //!< A_ji: resource usage matrix, each row j represents a resource and col i a flow/player
  26   std::vector<int> alloc_;
  27   bool first_ = true;
  28 };
  29
  30 class XBT_PUBLIC BmfSolver {
  31 public:
  32   /**
  33    * @brief Instantiate the BMF solver
  34    *
  35    * @param A A_ji: consumption of player i on resource j
  36    * @param maxA maxA_ji: consumption of larger player i on resource j
  37    * @param C Resource capacity
  38    * @param shared Is resource shared between player or each player receives the full capacity (FATPIPE links)
  39    * @param phi Bound for each player
  40    */
  41   BmfSolver(Eigen::MatrixXd A, Eigen::MatrixXd maxA, Eigen::VectorXd C, std::vector<bool> shared, Eigen::VectorXd phi);
  42   /** @brief Solve equation system to find a fair-sharing of resources */
  43   Eigen::VectorXd solve();
  44
  45 private:
  46   using allocation_map_t = std::unordered_map<int, std::unordered_set<int>>;
  47   /**
  48    * @brief Get actual resource capacity considering bounded players
  49    *
  50    * Calculates the resource capacity considering that some players on it may be bounded by user,
  51    * i.e. an explicit limit in speed was configured
  52    *
  53    * @param resource Internal index of resource in C_ vector
  54    * @param bounded_players List of players that are externally bounded
  55    * @return Actual resource capacity
  56    */
  57   double get_resource_capacity(int resource, const std::vector<int>& bounded_players) const;
  58
  59   /**
  60    * @brief Given an allocation calculates the speed/rho for each player
  61    *
  62    * Do the magic!!
  63    * Builds 2 auxiliares matrices A' and C' and solves the system: rho_i = inv(A'_ji) * C'_j
  64    *
  65    * All resources in A' and C' are saturated, i.e., sum(A'_j * rho_i) = C'_j.
  66    *
  67    * The matrix A' is built as follows:
  68    * - For each resource j in alloc: copy row A_j to A'
  69    * - If 2 players (i, k) share a same resource, assure fairness by adding a row in A' such as:
  70    *   -  A_ji*rho_i - Ajk*rho_j = 0
  71    *
  72    * @param alloc for each resource, players that chose to saturate it
  73    * @return Vector rho with "players' speed"
  74    */
  75   Eigen::VectorXd equilibrium(const allocation_map_t& alloc) const;
  76
  77   /**
  78    * @brief Given a fair_sharing vector, gets the allocation
  79    *
  80    * The allocation for player i is given by: min(bound, f_j/A_ji).
  81    * The minimum between all fair-sharing and the external bound (if any)
  82    *
  83    * The algorithm dictates a random initial allocation. For simplicity, we opt to use the same
  84    * logic with the fair_sharing vector.
  85    *
  86    * @param fair_sharing Fair sharing vector
  87    * @param initial Is this the initial allocation?
  88    * @return allocation vector
  89    */
  90   bool get_alloc(const Eigen::VectorXd& fair_sharing, const allocation_map_t& last_alloc, allocation_map_t& alloc,
  91                  bool initial);
  92
  93   bool disturb_allocation(allocation_map_t& alloc, std::vector<int>& alloc_by_player);
  94   /**
  95    * @brief Calculates the fair sharing for each resource
  96    *
  97    * Basically 3 options:
  98    * 1) resource in allocation: A_ji*rho_i since all players who selected this resource have the same share
  99    * 2) resource not selected by saturated (fully used): divide it by the number of players C_/n_players
 100    * 3) resource not selected and not-saturated: no limitation
 101    *
 102    * @param alloc Allocation map (resource-> players)
 103    * @param rho Speed for each player i
 104    * @param fair_sharing Output vector, fair sharing for each resource j
 105    */
 106   void set_fair_sharing(const allocation_map_t& alloc, const Eigen::VectorXd& rho, Eigen::VectorXd& fair_sharing) const;
 107
 108   /**
 109    * @brief Check if allocation is BMF
 110    *
 111    * To be a bmf allocation it must:
 112    * - respect the capacity of all resources
 113    * - saturate at least 1 resource
 114    * - every player receives maximum share in at least 1 saturated resource
 115    * @param rho Allocation
 116    * @return true if BMF false otherwise
 117    */
 118   bool is_bmf(const Eigen::VectorXd& rho) const;
 119   std::vector<int> alloc_map_to_vector(const allocation_map_t& alloc) const;
 120
 121   /**
 122    * @brief Set of debug functions to print the different objects
 123    */
 124   template <typename T> std::string debug_eigen(const T& obj) const;
 125   template <typename C> std::string debug_vector(const C& container) const;
 126   std::string debug_alloc(const allocation_map_t& alloc) const;
 127
 128   Eigen::MatrixXd A_;    //!< A_ji: resource usage matrix, each row j represents a resource and col i a flow/player
 129   Eigen::MatrixXd maxA_; //!< maxA_ji,  similar as A_, but containing the maximum consumption of player i (if player a
 130                          //!< single flow it's equal to A_)
 131   Eigen::VectorXd C_;    //!< C_j Capacity of each resource
 132   std::vector<bool> C_shared_; //!< shared_j Resource j is shared or not
 133   Eigen::VectorXd phi_;        //!< phi_i bound for each player
 134
 135   std::unordered_set<std::vector<int>, boost::hash<std::vector<int>>> allocations_;
 136   AllocationGenerator gen_;
 137   std::vector<int> allocations_age_;
 138   static constexpr int NO_RESOURCE = -1;                    //!< flag to indicate player has selected no resource
 139   int max_iteration_               = sg_bmf_max_iterations; //!< number maximum of iterations of BMF algorithm
 140 };
 141
 142 /**
 143  * @brief Bottleneck max-fair system
 144  */
 145 class XBT_PUBLIC BmfSystem : public System {
 146 public:
 147   using System::System;
 148   /** @brief Implements the solve method to calculate a BMF allocation */
 149   void solve() final;
 150
 151 private:
 152   using allocation_map_t = std::unordered_map<int, std::unordered_set<int>>;
 153   /**
 154    * @brief Solve equation system to find a fair-sharing of resources
 155    *
 156    * @param cnst_list Constraint list (modified for selective update or active)
 157    */
 158   template <class CnstList> void bmf_solve(const CnstList& cnst_list);
 159   /**
 160    * @brief Iterates over system and build the consumption matrix A_ji and maxA_ji
 161    *
 162    * Each row j represents a resource and each col i a player/flow
 163    *
 164    * Considers only active variables to build the matrix.
 165    *
 166    * @param number_cnsts Number of constraints in the system
 167    * @param A Consumption matrix (OUTPUT)
 168    * @param maxA Max subflow consumption matrix (OUTPUT)
 169    * @param phi Bounds for variables
 170    */
 171   void get_flows_data(int number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi);
 172   /**
 173    * @brief Builds the vector C_ with resource's capacity
 174    *
 175    * @param cnst_list Constraint list (modified for selective update or active)
 176    * @param C Resource capacity vector
 177    * @param shared Resource is shared or not (fatpipe links)
 178    */
 179   template <class CnstList>
 180   void get_constraint_data(const CnstList& cnst_list, Eigen::VectorXd& C, std::vector<bool>& shared);
 181
 182   std::unordered_map<int, Variable*> idx2Var_; //!< Map player index (and position in matrices) to system's variable
 183   std::unordered_map<const Constraint*, int> cnst2idx_; //!< Conversely map constraint to index
 184 };
 185
 186 } // namespace lmm
 187 } // namespace kernel
 188 } // namespace simgrid
 189
 190 #endif