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. */
9 #include "src/kernel/lmm/maxmin.hpp"
10 #include <boost/container_hash/hash.hpp>
11 #include <eigen3/Eigen/Dense>
12 #include <unordered_set>
18 class XBT_PUBLIC AllocationGenerator {
20 explicit AllocationGenerator(Eigen::MatrixXd A);
22 bool next(std::vector<int>& next_alloc);
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_;
30 class XBT_PUBLIC BmfSolver {
32 BmfSolver(Eigen::MatrixXd A, Eigen::MatrixXd maxA, Eigen::VectorXd C, Eigen::VectorXd phi);
33 /** @brief Solve equation system to find a fair-sharing of resources */
34 Eigen::VectorXd solve();
37 using allocation_map_t = std::unordered_map<int, std::unordered_set<int>>;
39 * @brief Get actual resource capacity considering bounded players
41 * Calculates the resource capacity considering that some players on it may be bounded by user,
42 * i.e. an explicit limit in speed was configured
44 * @param resource Internal index of resource in C_ vector
45 * @param bounded_players List of players that are externally bounded
46 * @return Actual resource capacity
48 double get_resource_capacity(int resource, const std::vector<int>& bounded_players) const;
51 * @brief Given an allocation calculates the speed/rho for each player
54 * Builds 2 auxiliares matrices A' and C' and solves the system: rho_i = inv(A'_ji) * C'_j
56 * All resources in A' and C' are saturated, i.e., sum(A'_j * rho_i) = C'_j.
58 * The matrix A' is built as follows:
59 * - For each resource j in alloc: copy row A_j to A'
60 * - If 2 players (i, k) share a same resource, assure fairness by adding a row in A' such as:
61 * - A_ji*rho_i - Ajk*rho_j = 0
63 * @param alloc for each resource, players that chose to saturate it
64 * @return Vector rho with "players' speed"
66 Eigen::VectorXd equilibrium(const allocation_map_t& alloc) const;
69 * @brief Given a fair_sharing vector, gets the allocation
71 * The allocation for player i is given by: min(bound, f_j/A_ji).
72 * The minimum between all fair-sharing and the external bound (if any)
74 * The algorithm dictates a random initial allocation. For simplicity, we opt to use the same
75 * logic with the fair_sharing vector.
77 * @param fair_sharing Fair sharing vector
78 * @param initial Is this the initial allocation?
79 * @return allocation vector
81 bool get_alloc(const Eigen::VectorXd& fair_sharing, const allocation_map_t& last_alloc, allocation_map_t& alloc,
84 bool disturb_allocation(allocation_map_t& alloc, std::vector<int>& alloc_by_player);
86 * @brief Calculates the fair sharing for each resource
88 * Basically 3 options:
89 * 1) resource in allocation: A_ji*rho_i since all players who selected this resource have the same share
90 * 2) resource not selected by saturated (fully used): divide it by the number of players C_/n_players
91 * 3) resource not selected and not-saturated: no limitation
93 * @param alloc Allocation map (resource-> players)
94 * @param rho Speed for each player i
95 * @param fair_sharing Output vector, fair sharing for each resource j
97 void set_fair_sharing(const allocation_map_t& alloc, const Eigen::VectorXd& rho, Eigen::VectorXd& fair_sharing) const;
100 * @brief Check if allocation is BMF
102 * To be a bmf allocation it must:
103 * - respect the capacity of all resources
104 * - saturate at least 1 resource
105 * - every player receives maximum share in at least 1 saturated resource
106 * @param rho Allocation
107 * @return true if BMF false otherwise
109 bool is_bmf(const Eigen::VectorXd& rho) const;
110 std::vector<int> alloc_map_to_vector(const allocation_map_t& alloc) const;
113 * @brief Set of debug functions to print the different objects
115 template <typename T> std::string debug_eigen(const T& obj) const;
116 template <typename C> std::string debug_vector(const C& container) const;
117 std::string debug_alloc(const allocation_map_t& alloc) const;
119 Eigen::MatrixXd A_; //!< A_ji: resource usage matrix, each row j represents a resource and col i a flow/player
120 Eigen::MatrixXd maxA_; //!< maxA_ji, similar as A_, but containing the maximum consumption of player i (if player a
121 //!< single flow it's equal to A_)
122 Eigen::VectorXd C_; //!< C_j Capacity of each resource
123 Eigen::VectorXd phi_; //!< phi_i bound for each player
125 std::unordered_set<std::vector<int>, boost::hash<std::vector<int>>> allocations_;
126 AllocationGenerator gen_;
127 std::vector<int> allocations_age_;
128 static constexpr int NO_RESOURCE = -1; //!< flag to indicate player has selected no resource
129 int max_iteration_ = sg_bmf_max_iterations; //!< number maximum of iterations of BMF algorithm
133 * @brief Bottleneck max-fair system
135 class XBT_PUBLIC BmfSystem : public System {
137 using System::System;
138 /** @brief Implements the solve method to calculate a BMF allocation */
142 using allocation_map_t = std::unordered_map<int, std::unordered_set<int>>;
144 * @brief Solve equation system to find a fair-sharing of resources
146 * @param cnst_list Constraint list (modified for selective update or active)
148 template <class CnstList> void bmf_solve(const CnstList& cnst_list);
150 * @brief Iterates over system and build the consumption matrix A_ji and maxA_ji
152 * Each row j represents a resource and each col i a player/flow
154 * Considers only active variables to build the matrix.
156 * @param number_cnsts Number of constraints in the system
157 * @param A Consumption matrix (OUTPUT)
158 * @param maxA Max subflow consumption matrix (OUTPUT)
159 * @param phi Bounds for variables
161 void get_flows_data(int number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi);
163 * @brief Builds the vector C_ with resource's capacity
165 * @param cnst_list Constraint list (modified for selective update or active)
166 * @param C Resource capacity vector
168 template <class CnstList> void get_constraint_data(const CnstList& cnst_list, Eigen::VectorXd& C);
170 std::unordered_map<int, Variable*> idx2Var_; //!< Map player index (and position in matrices) to system's variable
171 std::unordered_map<const Constraint*, int> cnst2idx_; //!< Conversely map constraint to index
175 } // namespace kernel
176 } // namespace simgrid