X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/64caf78080c48d893d253680b7b7dd3e3822ea3a..HEAD:/src/kernel/lmm/bmf.hpp diff --git a/src/kernel/lmm/bmf.hpp b/src/kernel/lmm/bmf.hpp index 601151b087..3bebff17d9 100644 --- a/src/kernel/lmm/bmf.hpp +++ b/src/kernel/lmm/bmf.hpp @@ -1,33 +1,87 @@ -/* Copyright (c) 2004-2022. The SimGrid Team. All rights reserved. */ +/* Copyright (c) 2004-2023. The SimGrid Team. All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ -#ifndef SURF_BMF_HPP -#define SURF_BMF_HPP +#ifndef SIMGRID_KERNEL_LMM_BMF_HPP +#define SIMGRID_KERNEL_LMM_BMF_HPP + +#include "src/kernel/lmm/System.hpp" +#include "xbt/config.hpp" + +#include + +#ifdef __clang__ +// Ignore deprecation warnings with Eigen < 4.0 (see https://gitlab.com/libeigen/eigen/-/issues/1850) +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wdeprecated-declarations" +#endif +#include +#ifdef __clang__ +#pragma clang diagnostic pop +#endif -#include "src/kernel/lmm/maxmin.hpp" -#include -#include #include -namespace simgrid { -namespace kernel { -namespace lmm { +namespace simgrid::kernel::lmm { +/** @brief Generate all combinations of valid allocation */ class XBT_PUBLIC AllocationGenerator { public: explicit AllocationGenerator(Eigen::MatrixXd A); + /** + * @brief Get next valid allocation + * + * @param next_alloc Allocation (OUTPUT) + * @return true if there's an allocation not tested yet, false otherwise + */ bool next(std::vector& next_alloc); private: - Eigen::MatrixXd A_; //!< A_ji: resource usage matrix, each row j represents a resource and col i a flow/player + Eigen::MatrixXd A_; std::vector alloc_; bool first_ = true; }; +/** + * @beginrst + * + * Despite the simplicity of BMF fairness definition, it's quite hard to + * find a BMF allocation in the general case. + * + * This solver implements one possible algorithm to find a BMF, as proposed + * at: https://hal.archives-ouvertes.fr/hal-01552739. + * + * The idea of this algorithm is that each player/flow "selects" a resource to + * saturate. Then, we calculate the rate each flow would have with this allocation. + * If the allocation is a valid BMF and no one needs to move, it's over. Otherwise, + * each player selects a new resource to saturate based on the minimim rate possible + * between all resources. + * + * The steps: + * 1) Given an initial allocation B_i + * 2) Build a matrix A'_ji and C'_ji which assures that the player receives the most + * share at selected resources + * 3) Solve: A'_ji * rho_i = C'_j + * 4) Calculate the minimum fair rate for each resource j: f_j. The f_j represents + * the maximum each flow can receive at the resource j. + * 5) Builds a new vector B'_i = arg min(f_j/A_ji). + * 6) Stop if B == B' (nobody needs to move), go to step 2 otherwise + * + * Despite the overall good performance of this algorithm, which converges in a few + * iterations, we don't have any assurance about its convergence. In the worst case, + * it may be needed to test all possible combination of allocations (which is exponential). + * + * @endrst + */ class XBT_PUBLIC BmfSolver { + inline static simgrid::config::Flag cfg_bmf_max_iteration{ + "bmf/max-iterations", "Maximum number of steps to be performed while searching for a BMF allocation", 1000}; + + inline static simgrid::config::Flag cfg_bmf_precision{ + "bmf/precision", {"precision/bmf"}, "Numerical precision used when computing resource sharing", 1E-12}; + public: /** * @brief Instantiate the BMF solver @@ -55,6 +109,21 @@ private: * @return Actual resource capacity */ double get_resource_capacity(int resource, const std::vector& bounded_players) const; + /** + * @brief Get maxmin share of the resource + * + * @param resource Internal index of resource in C_ vector + * @param bounded_players List of players that are externally bounded + * @return maxmin share + */ + double get_maxmin_share(int resource, const std::vector& bounded_players) const; + /** + * @brief Auxiliary method to get list of bounded player from allocation + * + * @param alloc Current allocation + * @return list of bounded players + */ + std::vector get_bounded_players(const allocation_map_t& alloc) const; /** * @brief Given an allocation calculates the speed/rho for each player @@ -132,23 +201,57 @@ private: std::vector C_shared_; //!< shared_j Resource j is shared or not Eigen::VectorXd phi_; //!< phi_i bound for each player - std::unordered_set, boost::hash>> allocations_; + std::set> allocations_; //!< set of already tested allocations, since last identified loop AllocationGenerator gen_; - std::vector allocations_age_; static constexpr int NO_RESOURCE = -1; //!< flag to indicate player has selected no resource - int max_iteration_ = sg_bmf_max_iterations; //!< number maximum of iterations of BMF algorithm + int max_iteration_ = cfg_bmf_max_iteration; //!< number maximum of iterations of BMF algorithm }; +/** + * @beginrst + * + * A BMF (bottleneck max fairness) solver to resolve inequation systems. + * + * Usually, SimGrid relies on a *max-min fairness* solver to share the resources. + * Max-min is great when sharing homogenous resources, however it cannot be used with heterogeneous resources. + * + * BMF is a natural alternative to max-min, providing a fair-sharing of heterogeneous resources (CPU, network, disk). + * It is specially relevant for the implementation of parallel tasks whose sharing involves different + * kinds of resources. + * + * BMF assures that every flow receives the maximum share possible in at least 1 bottleneck (fully used) resource. + * + * The BMF is characterized by: + * - A_ji: a matrix of requirement for flows/player. For each resource j, and flow i, A_ji represents the utilization + * of resource j for 1 unit of the flow i. + * - rho_i: the rate allocated for flow i (same among all resources) + * - C_j: the capacity of each resource (can be bytes/s, flops/s, etc) + * + * Therefore, these conditions need to satisfied to an allocation be considered a BMF: + * 1) All constraints are respected (flows cannot use more than the resource has available) + * - for all resource j and player i: A_ji * rho_i <= C_j + * 2) At least 1 resource is fully used (bottleneck). + * - for some resource j: A_ji * rho_i = C_j + * 3) Each flow (player) receives the maximum share in at least 1 bottleneck. + * - for all player i: exist a resource j: A_ji * rho_i >= A_jk * rho_k for all other player k + * + * Despite the prove of existence of a BMF allocation in the general case, it may not + * be unique, which leads to possible different rate for the applications. + * + * More details about BMF can be found at: https://hal.inria.fr/hal-01243985/document + * + * @endrst + */ /** * @brief Bottleneck max-fair system */ class XBT_PUBLIC BmfSystem : public System { public: using System::System; - /** @brief Implements the solve method to calculate a BMF allocation */ - void solve() final; private: + /** @brief Implements the solve method to calculate a BMF allocation */ + void do_solve() final; using allocation_map_t = std::unordered_map>; /** * @brief Solve equation system to find a fair-sharing of resources @@ -168,7 +271,7 @@ private: * @param maxA Max subflow consumption matrix (OUTPUT) * @param phi Bounds for variables */ - void get_flows_data(int number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi); + void get_flows_data(Eigen::Index number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi); /** * @brief Builds the vector C_ with resource's capacity * @@ -183,8 +286,6 @@ private: std::unordered_map cnst2idx_; //!< Conversely map constraint to index }; -} // namespace lmm -} // namespace kernel -} // namespace simgrid +} // namespace simgrid::kernel::lmm -#endif \ No newline at end of file +#endif