From 6d64c296b8f063bec38fb27e00ad60469080228a Mon Sep 17 00:00:00 2001 From: Bruno Donassolo Date: Mon, 28 Feb 2022 14:39:44 +0100 Subject: [PATCH] Implements selective-update for bmf model (off by default). Add a cfg parameter: "bmf/selective-update" to enable it --- src/kernel/lmm/bmf.cpp | 45 ++++++++++++++++++++++++++++----------- src/kernel/lmm/bmf.hpp | 16 +++++++++----- src/kernel/lmm/maxmin.hpp | 10 +++++---- src/simgrid/sg_config.cpp | 5 +++++ src/surf/ptask_L07.cpp | 3 ++- 5 files changed, 56 insertions(+), 23 deletions(-) diff --git a/src/kernel/lmm/bmf.cpp b/src/kernel/lmm/bmf.cpp index 682522d712..7dfa0e06d6 100644 --- a/src/kernel/lmm/bmf.cpp +++ b/src/kernel/lmm/bmf.cpp @@ -352,11 +352,11 @@ Eigen::VectorXd BmfSolver::solve() /*****************************************************************************/ -void BmfSystem::get_flows_data(Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi) +void BmfSystem::get_flows_data(int number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi) { - A.resize(active_constraint_set.size(), variable_set.size()); + A.resize(number_cnsts, variable_set.size()); A.setZero(); - maxA.resize(active_constraint_set.size(), variable_set.size()); + maxA.resize(number_cnsts, variable_set.size()); maxA.setZero(); phi.resize(variable_set.size()); @@ -365,8 +365,15 @@ void BmfSystem::get_flows_data(Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen: if (var.sharing_penalty_ <= 0) continue; bool active = false; - var.value_ = 1; // assign something by default for tasks with 0 consumption + bool linked = false; // variable is linked to some constraint (specially for selective_update) for (const Element& elem : var.cnsts_) { + boost::intrusive::list_member_hook<>& cnst_hook = selective_update_active + ? elem.constraint->modified_constraint_set_hook_ + : elem.constraint->active_constraint_set_hook_; + if (not cnst_hook.is_linked()) + continue; + /* active and linked variable, lets check its consumption */ + linked = true; double consumption = elem.consumption_weight; if (consumption > 0) { int cnst_idx = cnst2idx_[elem.constraint]; @@ -375,10 +382,15 @@ void BmfSystem::get_flows_data(Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen: active = true; } } + /* skip variables not linked to any modified or active constraint */ + if (not linked) + continue; if (active) { - phi[var_idx] = var.get_bound(); + phi[var_idx] = var.get_bound(); idx2Var_[var_idx] = &var; var_idx++; + } else { + var.value_ = 1; // assign something by default for tasks with 0 consumption } } // resize matrix to active variables only @@ -387,30 +399,37 @@ void BmfSystem::get_flows_data(Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen: phi.conservativeResize(var_idx); } -void BmfSystem::get_constraint_data(Eigen::VectorXd& C) +template void BmfSystem::get_constraint_data(const CnstList& cnst_list, Eigen::VectorXd& C) { - C.resize(active_constraint_set.size()); + C.resize(cnst_list.size()); cnst2idx_.clear(); int cnst_idx = 0; - for (const Constraint& cnst : active_constraint_set) { + for (const Constraint& cnst : cnst_list) { C(cnst_idx) = cnst.bound_; cnst2idx_[&cnst] = cnst_idx; cnst_idx++; } } -void BmfSystem::bmf_solve() +void BmfSystem::solve() { - if (not modified_) - return; + if (modified_) { + if (selective_update_active) + bmf_solve(modified_constraint_set); + else + bmf_solve(active_constraint_set); + } +} +template void BmfSystem::bmf_solve(const CnstList& cnst_list) +{ /* initialize players' weight and constraint matrices */ idx2Var_.clear(); cnst2idx_.clear(); Eigen::MatrixXd A, maxA; Eigen::VectorXd C, bounds; - get_constraint_data(C); - get_flows_data(A, maxA, bounds); + get_constraint_data(cnst_list, C); + get_flows_data(C.size(), A, maxA, bounds); auto solver = BmfSolver(A, maxA, C, bounds); auto rho = solver.solve(); diff --git a/src/kernel/lmm/bmf.hpp b/src/kernel/lmm/bmf.hpp index 8ede833279..3b5b0afa34 100644 --- a/src/kernel/lmm/bmf.hpp +++ b/src/kernel/lmm/bmf.hpp @@ -136,12 +136,16 @@ class XBT_PUBLIC BmfSystem : public System { public: using System::System; /** @brief Implements the solve method to calculate a BMF allocation */ - void solve() final { bmf_solve(); } + void solve() final; private: using allocation_map_t = std::unordered_map>; - /** @brief Solve equation system to find a fair-sharing of resources */ - void bmf_solve(); + /** + * @brief Solve equation system to find a fair-sharing of resources + * + * @param cnst_list Constraint list (modified for selective update or active) + */ + template void bmf_solve(const CnstList& cnst_list); /** * @brief Iterates over system and build the consumption matrix A_ji and maxA_ji * @@ -149,17 +153,19 @@ private: * * Considers only active variables to build the matrix. * + * @param number_cnsts Number of constraints in the system * @param A Consumption matrix (OUTPUT) * @param maxA Max subflow consumption matrix (OUTPUT) * @param phi Bounds for variables */ - void get_flows_data(Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi); + void get_flows_data(int number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi); /** * @brief Builds the vector C_ with resource's capacity * + * @param cnst_list Constraint list (modified for selective update or active) * @param C Resource capacity vector */ - void get_constraint_data(Eigen::VectorXd& C); + template void get_constraint_data(const CnstList& cnst_list, Eigen::VectorXd& C); std::unordered_map idx2Var_; //!< Map player index (and position in matrices) to system's variable std::unordered_map cnst2idx_; //!< Conversely map constraint to index diff --git a/src/kernel/lmm/maxmin.hpp b/src/kernel/lmm/maxmin.hpp index 2aeab539ac..cae7c20661 100644 --- a/src/kernel/lmm/maxmin.hpp +++ b/src/kernel/lmm/maxmin.hpp @@ -548,6 +548,12 @@ public: std::unique_ptr modified_set_ = nullptr; +protected: + bool selective_update_active; /* flag to update partially the system only selecting changed portions */ + boost::intrusive::list, + &Constraint::modified_constraint_set_hook_>> + modified_constraint_set; + private: using dyn_light_t = std::vector; @@ -555,15 +561,11 @@ private: std::vector cnst_light_vec; dyn_light_t saturated_constraints; - bool selective_update_active; /* flag to update partially the system only selecting changed portions */ unsigned visited_counter_ = 1; /* used by System::update_modified_set() and System::remove_all_modified_set() to * cleverly (un-)flag the constraints (more details in these functions) */ boost::intrusive::list, &Constraint::constraint_set_hook_>> constraint_set; - boost::intrusive::list, - &Constraint::modified_constraint_set_hook_>> - modified_constraint_set; xbt_mallocator_t variable_mallocator_ = xbt_mallocator_new(65536, System::variable_mallocator_new_f, System::variable_mallocator_free_f, nullptr); }; diff --git a/src/simgrid/sg_config.cpp b/src/simgrid/sg_config.cpp index 0e705c6361..2ce0de033a 100644 --- a/src/simgrid/sg_config.cpp +++ b/src/simgrid/sg_config.cpp @@ -269,6 +269,11 @@ void sg_config_init(int *argc, char **argv) simgrid::config::bind_flag(sg_bmf_max_iterations, "bmf/max-iterations", "Maximum number of steps to be performed while searching for a BMF allocation"); + simgrid::config::declare_flag("bmf/selective-update", + "Update the constraint set propagating recursively to others constraints " + "(off by default)", + false); + /* The parameters of network models */ sg_latency_factor = 13.01; // comes from the default LV08 network model diff --git a/src/surf/ptask_L07.cpp b/src/surf/ptask_L07.cpp index 2aabd5ab57..9039cff205 100644 --- a/src/surf/ptask_L07.cpp +++ b/src/surf/ptask_L07.cpp @@ -35,7 +35,8 @@ void surf_host_model_init_ptask_BMF() { XBT_CINFO(xbt_cfg, "Switching to the BMF model to handle parallel tasks."); - auto* system = new simgrid::kernel::lmm::BmfSystem(false); + bool select = simgrid::config::get_value("bmf/selective-update"); + auto* system = new simgrid::kernel::lmm::BmfSystem(select); auto host_model = std::make_shared("Host_Ptask", system); auto* engine = simgrid::kernel::EngineImpl::get_instance(); engine->add_model(host_model); -- 2.20.1