From 2b564f86aa3a75bc55e6610087f79145019708b2 Mon Sep 17 00:00:00 2001 From: Bruno Donassolo Date: Fri, 4 Mar 2022 17:51:02 +0100 Subject: [PATCH] Fix bug found at ptask experiments The consumption of bounded variables exceed constraint capacity leading to wrong behavior of the algorithm. Added some UTs for special case with bounds. --- src/kernel/lmm/bmf.cpp | 29 +++++++++++++++------ src/kernel/lmm/bmf.hpp | 7 ++++++ src/kernel/lmm/bmf_test.cpp | 50 +++++++++++++++++++++++++++++++++++++ 3 files changed, 79 insertions(+), 7 deletions(-) diff --git a/src/kernel/lmm/bmf.cpp b/src/kernel/lmm/bmf.cpp index 53b2e73dfe..328f1819c4 100644 --- a/src/kernel/lmm/bmf.cpp +++ b/src/kernel/lmm/bmf.cpp @@ -108,7 +108,7 @@ double BmfSolver::get_resource_capacity(int resource, const std::vector& bo for (int p : bounded_players) { capacity -= A_(resource, p) * phi_[p]; } - return capacity; + return std::max(0.0, capacity); } std::vector BmfSolver::alloc_map_to_vector(const allocation_map_t& alloc) const @@ -122,6 +122,17 @@ std::vector BmfSolver::alloc_map_to_vector(const allocation_map_t& alloc) c return alloc_by_player; } +std::vector BmfSolver::get_bounded_players(const allocation_map_t& alloc) const +{ + std::vector bounded_players; + for (const auto& e : alloc) { + if (e.first == NO_RESOURCE) { + bounded_players.insert(bounded_players.end(), e.second.begin(), e.second.end()); + } + } + return bounded_players; +} + Eigen::VectorXd BmfSolver::equilibrium(const allocation_map_t& alloc) const { int n_players = A_.cols(); @@ -129,14 +140,13 @@ Eigen::VectorXd BmfSolver::equilibrium(const allocation_map_t& alloc) const Eigen::VectorXd C_p = Eigen::VectorXd::Zero(n_players); int row = 0; - std::vector bounded_players; + auto bounded_players = get_bounded_players(alloc); for (const auto& e : alloc) { // add one row for the resource with A[r,] int cur_resource = e.first; - if (cur_resource == NO_RESOURCE) { - bounded_players.insert(bounded_players.end(), e.second.begin(), e.second.end()); + if (cur_resource == NO_RESOURCE) continue; - } + if (C_shared_[cur_resource]) { /* shared resource: fairly share it between players */ A_p.row(row) = A_.row(cur_resource); @@ -210,7 +220,8 @@ bool BmfSolver::get_alloc(const Eigen::VectorXd& fair_sharing, const allocation_ continue; double share = fair_sharing[cnst_idx] / A_(cnst_idx, player_idx); - if (min_share == -1 || double_positive(min_share - share, sg_maxmin_precision)) { + if (min_share == -1 || share < min_share) { + selected_resource = cnst_idx; min_share = share; } @@ -234,6 +245,8 @@ bool BmfSolver::get_alloc(const Eigen::VectorXd& fair_sharing, const allocation_ void BmfSolver::set_fair_sharing(const allocation_map_t& alloc, const Eigen::VectorXd& rho, Eigen::VectorXd& fair_sharing) const { + std::vector bounded_players = get_bounded_players(alloc); + for (int r = 0; r < fair_sharing.size(); r++) { auto it = alloc.find(r); if (it != alloc.end()) { // resource selected by some player, fair share depends on rho @@ -248,7 +261,7 @@ void BmfSolver::set_fair_sharing(const allocation_map_t& alloc, const Eigen::Vec int n_players = (A_.row(r).array() > 0).count(); fair_sharing[r] = C_[r] / n_players; } else { - fair_sharing[r] = C_[r]; + fair_sharing[r] = get_resource_capacity(r, bounded_players); } } } @@ -347,6 +360,8 @@ Eigen::VectorXd BmfSolver::solve() fprintf(stderr, "A:\n%s\n", debug_eigen(A_).c_str()); fprintf(stderr, "maxA:\n%s\n", debug_eigen(maxA_).c_str()); fprintf(stderr, "C:\n%s\n", debug_eigen(C_).c_str()); + fprintf(stderr, "C_shared:\n%s\n", debug_vector(C_shared_).c_str()); + fprintf(stderr, "phi:\n%s\n", debug_eigen(phi_).c_str()); fprintf(stderr, "rho:\n%s\n", debug_eigen(rho).c_str()); xbt_abort(); } diff --git a/src/kernel/lmm/bmf.hpp b/src/kernel/lmm/bmf.hpp index ec8300faab..afe62cb247 100644 --- a/src/kernel/lmm/bmf.hpp +++ b/src/kernel/lmm/bmf.hpp @@ -93,6 +93,13 @@ private: * @return Actual resource capacity */ double get_resource_capacity(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 diff --git a/src/kernel/lmm/bmf_test.cpp b/src/kernel/lmm/bmf_test.cpp index ea176752e3..2fe15f4c2c 100644 --- a/src/kernel/lmm/bmf_test.cpp +++ b/src/kernel/lmm/bmf_test.cpp @@ -568,6 +568,56 @@ TEST_CASE("kernel::bmf Loop", "[kernel-bmf-loop]") Sys.variable_free_all(); } +TEST_CASE("kernel::bmf Bugs", "[kernel-bmf-bug]") +{ + lmm::BmfSystem Sys(false); + xbt_log_control_set("ker_bmf.thres:debug"); + + SECTION("DadOu's bug: sum of bounds/phi greater than C") + { + /* + * Ptasks in a g5k platform. + * Extracted from original test. + * The sum of bounds for 1 resource exceed its capacity, giving a negative value in C' + */ + + lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 2.5e9); + lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 2.5e9); + lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, 2.27328e-10, 2); + lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, 2.27328e-10, 2); + lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1); + + Sys.expand_add(sys_cnst, rho_1, 1.84467e+19); + Sys.expand_add(sys_cnst2, rho_1, 1.84467e+19); + Sys.expand_add(sys_cnst, rho_2, 1.84467e+19); + Sys.expand_add(sys_cnst, rho_3, 1.91268e+11); + Sys.solve(); + } + + SECTION("is_bmf bug: all limited by bound") + { + /* + * Particular case, 1 flow is saturated and the other increases + * its speed until the contraint is reached + */ + + lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 10); + lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 8); + lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, 1.5, 2); + lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, 3, 2); + + Sys.expand_add(sys_cnst, rho_1, 5.0); + Sys.expand_add(sys_cnst2, rho_1, 1.0); + Sys.expand_add(sys_cnst, rho_2, 1.0); + Sys.expand_add(sys_cnst2, rho_2, 1.0); + Sys.solve(); + REQUIRE(double_equals(rho_1->get_value(), 1.4, sg_maxmin_precision)); + REQUIRE(double_equals(rho_2->get_value(), 3, sg_maxmin_precision)); + } + + Sys.variable_free_all(); +} + TEST_CASE("kernel::bmf Stress-tests", "[.kernel-bmf-stress]") { lmm::BmfSystem Sys(false); -- 2.20.1