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