# We need pybind11. SimGrid will pick it automatically if the subdir is here
- cmd: git clone --branch stable --depth=1 https://github.com/pybind/pybind11.git
+before_build:
+ - cmd: if not exist C:\"Program Files"\Eigen\include\eigen3\Eigen\Core (
+ curl -LO https://gitlab.com/libeigen/eigen/-/archive/3.4.0/eigen-3.4.0.tar.gz &&
+ cmake -E tar zxf eigen-3.4.0.tar.gz &&
+ cd eigen-3.4.0 &&
+ mkdir build &&
+ cd build &&
+ cmake -G "Visual Studio 2019" .. &&
+ cmake --build . --target install &&
+ cd ..\..
+ ) else (echo Using cached Eigen3)
+
build_script:
-- cmake -G "MinGW Makefiles" -Denable_documentation=OFF -Denable_java=ON -Denable_msg=ON -Denable_smpi=OFF -Denable_mallocators=OFF -Denable_lto=OFF .
+- cmake -G "MinGW Makefiles" -Denable_documentation=OFF -Denable_java=ON -Denable_msg=ON -Denable_smpi=OFF -Denable_mallocators=OFF -Denable_lto=OFF -DEIGEN3_INCLUDE_DIR="C:\Program Files\Eigen\include\eigen3" .
- mingw32-make.exe VERBOSE=1 java-all python-bindings # Only the Java and Python parts
- ctest --output-on-failure -R java
- ctest --output-on-failure -R python
set(CMAKE_THREAD_PREFER_PTHREAD TRUE)
find_package(Threads)
+### Check for Eigen library
+find_package (Eigen3 3.3 REQUIRED NO_MODULE)
+
### Setup Options
include(${CMAKE_HOME_DIRECTORY}/tools/cmake/Option.cmake)
- It is mostly intended to test the simgrid core in extreme conditions,
but users may find it interesting too.
+Models:
+ - New model for parallel task: ptask_BMF.
+ - More realistic sharing of heterogeneous resources compared to ptask_L07.
+ - Implement the BMF (Bottleneck max fairness) fairness.
+ - Improved resource sharing for parallel tasks with sub-flows (parallel
+ communications between same source and destination inside the ptask).
+ - Parameters:
+ - "--cfg=host/model:ptask_BMF": enable the model.
+ - "--cfg=bmf/max-iterations: <N>" - maximum number of iterations performed
+ by BMF solver (default: 1000).
+ - "--cfg=bmf/selective-update:<true/false>" - enable/disable the
+ selective-update optimization. Only invalidates and recomputes modified
+ parts of inequations system. May speed up simulation if sparse resource
+ utilization (default: false).
+ - ATTENTION: this model requires Eigen3 library. If you install SimGrid
+ from source, please see the "Installing from source" section:
+ https://simgrid.org/doc/latest/Installing_SimGrid.html#installing-from-the-source.
+ No action is required if you use pre-compiled packages.
+
XBT:
- Drop xbt_dynar_shrink().
include teshsuite/models/cloud-sharing/cloud-sharing.tesh
include teshsuite/models/cm02-set-lat-bw/cm02-set-lat-bw.cpp
include teshsuite/models/cm02-set-lat-bw/cm02-set-lat-bw.tesh
+include teshsuite/models/ptask-subflows/ptask-subflows.cpp
+include teshsuite/models/ptask-subflows/ptask-subflows.tesh
include teshsuite/models/ptask_L07_usage/ptask_L07_usage.cpp
include teshsuite/models/ptask_L07_usage/ptask_L07_usage.tesh
include teshsuite/models/wifi_usage/wifi_usage.cpp
include src/kernel/context/ContextThread.hpp
include src/kernel/context/ContextUnix.cpp
include src/kernel/context/ContextUnix.hpp
+include src/kernel/lmm/bmf.cpp
+include src/kernel/lmm/bmf.hpp
+include src/kernel/lmm/bmf_test.cpp
include src/kernel/lmm/fair_bottleneck.cpp
include src/kernel/lmm/maxmin.cpp
include src/kernel/lmm/maxmin.hpp
- **ptask_L07:** Host model somehow similar to Cas01+CM02 but
allowing "parallel tasks", that are intended to model the moldable
tasks of the grid scheduling literature.
+ - **ptask_BMF:** More realistic model for heterogeneous resource sharing.
+ Implements BMF (Bottleneck max fairness) fairness. To be used with
+ parallel tasks instead of ptask_L07.
- ``storage/model``: specify the used storage model. Only one model is
provided so far.
configuration options (e.g., if your Python installation is not standard).
boost (at least v1.48, v1.59 recommended)
- On Debian / Ubuntu: ``apt install libboost-dev libboost-context-dev``
+ - On CentOS / Fedora: ``yum install boost-devel``
- On macOS with homebrew: ``brew install boost``
+Eigen3
+ - On Debian / Ubuntu: ``apt install libeigen3-dev``
+ - On CentOS / Fedora: ``yum install eigen3-devel``
+ - On macOS with homebrew: ``brew install eigen``
Java (optional):
- Debian / Ubuntu: ``apt install default-jdk libgcj18-dev`` (or
any version of libgcj)
gfortran \
libboost-dev \
libboost-all-dev \
+ libeigen3-dev \
cmake \
dpkg-dev \
# misc tools
gfortran \
libboost-dev \
libboost-all-dev \
+ libeigen3-dev \
cmake \
dpkg-dev \
# misc tools
static void (*copy_data_callback_)(CommImpl*, void*, size_t);
- double rate_ = 0.0;
+ double rate_ = -1.0;
double size_ = 0.0;
bool detached_ = false; /* If detached or not */
bool copied_ = false; /* whether the data were already copied */
--- /dev/null
+/* Copyright (c) 2007-2022. 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. */
+
+#include "src/kernel/lmm/bmf.hpp"
+#include <eigen3/Eigen/LU>
+#include <iostream>
+#include <numeric>
+#include <sstream>
+
+XBT_LOG_NEW_DEFAULT_SUBCATEGORY(ker_bmf, kernel, "Kernel BMF solver");
+
+int sg_bmf_max_iterations = 1000; /* Change this with --cfg=bmf/max-iterations:VALUE */
+
+namespace simgrid {
+namespace kernel {
+namespace lmm {
+
+AllocationGenerator::AllocationGenerator(Eigen::MatrixXd A) : A_(std::move(A)), alloc_(A_.cols(), 0)
+{
+ // got a first valid allocation
+ for (size_t p = 0; p < alloc_.size(); p++) {
+ for (int r = 0; r < A_.rows(); r++) {
+ if (A_(r, p) > 0) {
+ alloc_[p] = r;
+ break;
+ }
+ }
+ }
+}
+
+bool AllocationGenerator::next(std::vector<int>& next_alloc)
+{
+ if (first_) {
+ next_alloc = alloc_;
+ first_ = false;
+ return true;
+ }
+
+ int n_resources = A_.rows();
+ size_t idx = 0;
+ while (idx < alloc_.size()) {
+ alloc_[idx] = (++alloc_[idx]) % n_resources;
+ if (alloc_[idx] == 0) {
+ idx++;
+ continue;
+ } else {
+ idx = 0;
+ }
+ if (A_(alloc_[idx], idx) > 0) {
+ next_alloc = alloc_;
+ return true;
+ }
+ }
+ return false;
+}
+
+/*****************************************************************************/
+
+BmfSolver::BmfSolver(Eigen::MatrixXd A, Eigen::MatrixXd maxA, Eigen::VectorXd C, std::vector<bool> shared,
+ Eigen::VectorXd phi)
+ : A_(std::move(A))
+ , maxA_(std::move(maxA))
+ , C_(std::move(C))
+ , C_shared_(std::move(shared))
+ , phi_(std::move(phi))
+ , gen_(A_)
+{
+ xbt_assert(max_iteration_ > 0,
+ "Invalid number of iterations for BMF solver. Please check your \"bmf/max-iterations\" configuration.");
+ xbt_assert(A_.cols() == maxA_.cols(), "Invalid number of cols in matrix A (%ld) or maxA (%ld)", A_.cols(),
+ maxA_.cols());
+ xbt_assert(A_.cols() == static_cast<long>(phi_.size()), "Invalid size of phi vector (%ld)", phi_.size());
+ xbt_assert(static_cast<long>(C_shared_.size()) == C_.size(), "Invalid size param shared (%zu)", C_shared_.size());
+}
+
+template <typename T> std::string BmfSolver::debug_eigen(const T& obj) const
+{
+ std::stringstream debug;
+ debug << obj;
+ return debug.str();
+}
+
+template <typename C> std::string BmfSolver::debug_vector(const C& container) const
+{
+ std::stringstream debug;
+ std::copy(container.begin(), container.end(),
+ std::ostream_iterator<typename std::remove_reference<decltype(container)>::type::value_type>(debug, " "));
+ return debug.str();
+}
+
+std::string BmfSolver::debug_alloc(const allocation_map_t& alloc) const
+{
+ std::stringstream debug;
+ for (const auto& e : alloc) {
+ debug << "{" + std::to_string(e.first) + ": [" + debug_vector(e.second) + "]}, ";
+ }
+ return debug.str();
+}
+
+double BmfSolver::get_resource_capacity(int resource, const std::vector<int>& bounded_players) const
+{
+ double capacity = C_[resource];
+ if (not C_shared_[resource])
+ return capacity;
+
+ for (int p : bounded_players) {
+ capacity -= A_(resource, p) * phi_[p];
+ }
+ return std::max(0.0, capacity);
+}
+
+std::vector<int> BmfSolver::alloc_map_to_vector(const allocation_map_t& alloc) const
+{
+ std::vector<int> alloc_by_player(A_.cols(), -1);
+ for (auto it : alloc) {
+ for (auto p : it.second) {
+ alloc_by_player[p] = it.first;
+ }
+ }
+ return alloc_by_player;
+}
+
+std::vector<int> BmfSolver::get_bounded_players(const allocation_map_t& alloc) const
+{
+ std::vector<int> 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();
+ Eigen::MatrixXd A_p = Eigen::MatrixXd::Zero(n_players, n_players); // square matrix with number of players
+ Eigen::VectorXd C_p = Eigen::VectorXd::Zero(n_players);
+
+ int row = 0;
+ 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)
+ continue;
+
+ if (C_shared_[cur_resource]) {
+ /* shared resource: fairly share it between players */
+ A_p.row(row) = A_.row(cur_resource);
+ C_p[row] = get_resource_capacity(cur_resource, bounded_players);
+ row++;
+ if (e.second.size() > 1) {
+ // if 2 players have chosen the same resource
+ // they must have a fair sharing of this resource, adjust A_p and C_p accordingly
+ auto it = e.second.begin();
+ int i = *it; // first player
+ /* for each other player sharing this resource */
+ for (++it; it != e.second.end(); ++it) {
+ /* player i and k on this resource j: so maxA_ji*rho_i - maxA_jk*rho_k = 0 */
+ int k = *it;
+ C_p[row] = 0;
+ A_p(row, i) = maxA_(cur_resource, i);
+ A_p(row, k) = -maxA_(cur_resource, k);
+ row++;
+ }
+ }
+ } else {
+ /* not shared resource, each player can receive the full capacity of the resource */
+ for (int i : e.second) {
+ C_p[row] = get_resource_capacity(cur_resource, bounded_players);
+ A_p(row, i) = A_(cur_resource, i);
+ row++;
+ }
+ }
+ }
+ /* clear players which are externally bounded */
+ for (int p : bounded_players) {
+ A_p.col(p).setZero();
+ }
+
+ XBT_DEBUG("A':\n%s", debug_eigen(A_p).c_str());
+
+ XBT_DEBUG("C':\n%s", debug_eigen(C_p).c_str());
+ Eigen::VectorXd rho = Eigen::FullPivLU<Eigen::MatrixXd>(A_p).solve(C_p);
+ for (int p : bounded_players) {
+ rho[p] = phi_[p];
+ }
+ return rho;
+}
+
+bool BmfSolver::disturb_allocation(allocation_map_t& alloc, std::vector<int>& alloc_by_player)
+{
+ while (gen_.next(alloc_by_player)) {
+ if (allocations_.find(alloc_by_player) == allocations_.end()) {
+ allocations_.clear();
+ allocations_.insert(alloc_by_player);
+ alloc.clear();
+ for (size_t p = 0; p < alloc_by_player.size(); p++) {
+ alloc[alloc_by_player[p]].insert(p);
+ }
+ return false;
+ }
+ }
+ return true;
+}
+
+bool BmfSolver::get_alloc(const Eigen::VectorXd& fair_sharing, const allocation_map_t& last_alloc,
+ allocation_map_t& alloc, bool initial)
+{
+ alloc.clear();
+ for (int player_idx = 0; player_idx < A_.cols(); player_idx++) {
+ int selected_resource = NO_RESOURCE;
+ double bound = phi_[player_idx];
+ double min_share = (bound <= 0 || initial) ? -1 : bound;
+ for (int cnst_idx = 0; cnst_idx < A_.rows(); cnst_idx++) {
+ if (A_(cnst_idx, player_idx) <= 0.0)
+ continue;
+
+ double share = fair_sharing[cnst_idx] / A_(cnst_idx, player_idx);
+ if (min_share == -1 || share < min_share) {
+
+ selected_resource = cnst_idx;
+ min_share = share;
+ }
+ }
+ alloc[selected_resource].insert(player_idx);
+ }
+ bool is_stable = (alloc == last_alloc);
+ if (is_stable)
+ return true;
+
+ std::vector<int> alloc_by_player = alloc_map_to_vector(alloc);
+ auto ret = allocations_.insert(alloc_by_player);
+ /* oops, allocation already tried, let's pertube it a bit */
+ if (not ret.second) {
+ XBT_DEBUG("Allocation already tried: %s", debug_alloc(alloc).c_str());
+ return disturb_allocation(alloc, alloc_by_player);
+ }
+ return false;
+}
+
+void BmfSolver::set_fair_sharing(const allocation_map_t& alloc, const Eigen::VectorXd& rho,
+ Eigen::VectorXd& fair_sharing) const
+{
+ std::vector<int> 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
+ int player = *(it->second.begin()); // equilibrium assures that every player receives the same, use one of them to
+ // calculate the fair sharing for resource r
+ fair_sharing[r] = A_(r, player) * rho[player];
+ } else { // nobody selects this resource, fair_sharing depends on resource saturation
+ // resource r is saturated (A[r,*] * rho > C), divide it among players
+ double consumption_r = A_.row(r) * rho;
+ double_update(&consumption_r, C_[r], sg_maxmin_precision);
+ if (consumption_r > 0.0) {
+ int n_players = (A_.row(r).array() > 0).count();
+ fair_sharing[r] = C_[r] / n_players;
+ } else {
+ fair_sharing[r] = get_resource_capacity(r, bounded_players);
+ }
+ }
+ }
+}
+
+bool BmfSolver::is_bmf(const Eigen::VectorXd& rho) const
+{
+ bool bmf = true;
+
+ // 1) the capacity of all resources is respected
+ Eigen::VectorXd shared(C_shared_.size());
+ for (int j = 0; j < shared.size(); j++)
+ shared[j] = C_shared_[j] ? 1.0 : 0.0;
+
+ Eigen::VectorXd remaining = (A_ * rho) - C_;
+ remaining = remaining.array() * shared.array(); // ignore non shared resources
+ bmf = bmf && (not std::any_of(remaining.data(), remaining.data() + remaining.size(),
+ [](double v) { return double_positive(v, sg_maxmin_precision); }));
+
+ // 3) every player receives maximum share in at least 1 saturated resource
+ // due to subflows, compare with the maximum consumption and not the A matrix
+ Eigen::MatrixXd usage =
+ maxA_.array().rowwise() * rho.transpose().array(); // usage_ji: indicates the usage of player i on resource j
+
+ XBT_DEBUG("Usage_ji considering max consumption:\n%s", debug_eigen(usage).c_str());
+ auto max_share = usage.rowwise().maxCoeff(); // max share for each resource j
+
+ // matrix_ji: boolean indicating player p has the maximum share at resource j
+ Eigen::MatrixXi player_max_share =
+ ((usage.array().colwise() - max_share.array()).abs() <= sg_maxmin_precision).cast<int>();
+ // but only saturated resources must be considered
+ Eigen::VectorXi saturated = ((remaining.array().abs() <= sg_maxmin_precision)).cast<int>();
+ XBT_DEBUG("Saturated_j resources:\n%s", debug_eigen(saturated).c_str());
+ player_max_share.array().colwise() *= saturated.array();
+
+ // just check if it has received at least it's bound
+ for (int p = 0; p < rho.size(); p++) {
+ if (double_equals(rho[p], phi_[p], sg_maxmin_precision)) {
+ player_max_share(0, p) = 1; // it doesn't really matter, just to say that it's a bmf
+ saturated[0] = 1;
+ }
+ }
+
+ // 2) at least 1 resource is saturated
+ bmf = bmf && (saturated.array() == 1).any();
+
+ XBT_DEBUG("Player_ji usage of saturated resources:\n%s", debug_eigen(player_max_share).c_str());
+ // for all columns(players) it has to be the max at least in 1
+ bmf = bmf && (player_max_share.colwise().sum().all() >= 1);
+ return bmf;
+}
+
+Eigen::VectorXd BmfSolver::solve()
+{
+ XBT_DEBUG("Starting BMF solver");
+
+ XBT_DEBUG("A:\n%s", debug_eigen(A_).c_str());
+ XBT_DEBUG("maxA:\n%s", debug_eigen(maxA_).c_str());
+ XBT_DEBUG("C:\n%s", debug_eigen(C_).c_str());
+
+ /* no flows to share, just returns */
+ if (A_.cols() == 0)
+ return {};
+
+ int it = 0;
+ auto fair_sharing = C_;
+
+ /* BMF allocation for each player (current and last one) stop when are equal */
+ allocation_map_t last_alloc, cur_alloc;
+ Eigen::VectorXd rho;
+
+ while (it < max_iteration_ && not get_alloc(fair_sharing, last_alloc, cur_alloc, it == 0)) {
+ last_alloc = cur_alloc;
+ XBT_DEBUG("BMF: iteration %d", it);
+ XBT_DEBUG("B (current allocation): %s", debug_alloc(cur_alloc).c_str());
+
+ // solve inv(A)*rho = C
+ rho = equilibrium(cur_alloc);
+ XBT_DEBUG("rho:\n%s", debug_eigen(rho).c_str());
+
+ // get fair sharing for each resource
+ set_fair_sharing(cur_alloc, rho, fair_sharing);
+ XBT_DEBUG("Fair sharing vector (per resource):\n%s", debug_eigen(fair_sharing).c_str());
+
+ // get new allocation for players
+ it++;
+ }
+
+ /* Not mandatory but a safe check to assure we have a proper solution */
+ if (not is_bmf(rho)) {
+ fprintf(stderr, "Unable to find a BMF allocation for your system.\n"
+ "You may try to increase the maximum number of iterations performed by BMF solver "
+ "(\"--cfg=bmf/max-iterations\").\n"
+ "Additionally, you could decrease numerical precision (\"--cfg=surf/precision\").\n");
+ fprintf(stderr, "Internal states (after %d iterations):\n", it);
+ 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();
+ }
+
+ XBT_DEBUG("BMF done after %d iterations", it);
+ return rho;
+}
+
+/*****************************************************************************/
+
+void BmfSystem::get_flows_data(int number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi)
+{
+ A.resize(number_cnsts, variable_set.size());
+ A.setZero();
+ maxA.resize(number_cnsts, variable_set.size());
+ maxA.setZero();
+ phi.resize(variable_set.size());
+
+ int var_idx = 0;
+ for (Variable& var : variable_set) {
+ if (var.sharing_penalty_ <= 0)
+ continue;
+ bool active = false;
+ 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];
+ A(cnst_idx, var_idx) += consumption;
+ // a variable with double penalty must receive half share, so it max weight is greater
+ maxA(cnst_idx, var_idx) = std::max(maxA(cnst_idx, var_idx), elem.max_consumption_weight * var.sharing_penalty_);
+ active = true;
+ }
+ }
+ /* skip variables not linked to any modified or active constraint */
+ if (not linked)
+ continue;
+ if (active) {
+ 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
+ A.conservativeResize(Eigen::NoChange_t::NoChange, var_idx);
+ maxA.conservativeResize(Eigen::NoChange_t::NoChange, var_idx);
+ phi.conservativeResize(var_idx);
+}
+
+template <class CnstList>
+void BmfSystem::get_constraint_data(const CnstList& cnst_list, Eigen::VectorXd& C, std::vector<bool>& shared)
+{
+ C.resize(cnst_list.size());
+ shared.resize(cnst_list.size());
+ cnst2idx_.clear();
+ int cnst_idx = 0;
+ for (const Constraint& cnst : cnst_list) {
+ C(cnst_idx) = cnst.bound_;
+ if (cnst.get_sharing_policy() == Constraint::SharingPolicy::NONLINEAR && cnst.dyn_constraint_cb_) {
+ C(cnst_idx) = cnst.dyn_constraint_cb_(cnst.bound_, cnst.concurrency_current_);
+ if (not warned_nonlinear_) {
+ XBT_WARN("You are using dynamic constraint bound with parallel tasks and BMF model."
+ " The BMF solver assumes that all flows (and subflows) are always active and executing."
+ " This is quite pessimist, specially considering parallel tasks with small subflows."
+ " Analyze your results with caution.");
+ warned_nonlinear_ = true;
+ }
+ }
+ cnst2idx_[&cnst] = cnst_idx;
+ // FATPIPE links aren't really shared
+ shared[cnst_idx] = (cnst.sharing_policy_ != Constraint::SharingPolicy::FATPIPE);
+ cnst_idx++;
+ }
+}
+
+void BmfSystem::solve()
+{
+ if (modified_) {
+ if (selective_update_active)
+ bmf_solve(modified_constraint_set);
+ else
+ bmf_solve(active_constraint_set);
+ }
+}
+
+template <class CnstList> 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;
+ std::vector<bool> shared;
+ get_constraint_data(cnst_list, C, shared);
+ get_flows_data(C.size(), A, maxA, bounds);
+
+ auto solver = BmfSolver(std::move(A), std::move(maxA), std::move(C), std::move(shared), std::move(bounds));
+ auto rho = solver.solve();
+
+ if (rho.size() == 0)
+ return;
+
+ /* setting rhos */
+ for (int i = 0; i < rho.size(); i++) {
+ idx2Var_[i]->value_ = rho[i];
+ }
+
+ print();
+}
+
+} // namespace lmm
+} // namespace kernel
+} // namespace simgrid
\ No newline at end of file
--- /dev/null
+/* Copyright (c) 2004-2022. 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
+
+#include "src/kernel/lmm/maxmin.hpp"
+#include <boost/container_hash/hash.hpp>
+#include <eigen3/Eigen/Dense>
+#include <unordered_set>
+
+namespace simgrid {
+namespace kernel {
+namespace 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<int>& next_alloc);
+
+private:
+ Eigen::MatrixXd A_;
+ std::vector<int> 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 {
+public:
+ /**
+ * @brief Instantiate the BMF solver
+ *
+ * @param A A_ji: consumption of player i on resource j
+ * @param maxA maxA_ji: consumption of larger player i on resource j
+ * @param C Resource capacity
+ * @param shared Is resource shared between player or each player receives the full capacity (FATPIPE links)
+ * @param phi Bound for each player
+ */
+ BmfSolver(Eigen::MatrixXd A, Eigen::MatrixXd maxA, Eigen::VectorXd C, std::vector<bool> shared, Eigen::VectorXd phi);
+ /** @brief Solve equation system to find a fair-sharing of resources */
+ Eigen::VectorXd solve();
+
+private:
+ using allocation_map_t = std::unordered_map<int, std::unordered_set<int>>;
+ /**
+ * @brief Get actual resource capacity considering bounded players
+ *
+ * Calculates the resource capacity considering that some players on it may be bounded by user,
+ * i.e. an explicit limit in speed was configured
+ *
+ * @param resource Internal index of resource in C_ vector
+ * @param bounded_players List of players that are externally bounded
+ * @return Actual resource capacity
+ */
+ double get_resource_capacity(int resource, const std::vector<int>& 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<int> get_bounded_players(const allocation_map_t& alloc) const;
+
+ /**
+ * @brief Given an allocation calculates the speed/rho for each player
+ *
+ * Do the magic!!
+ * Builds 2 auxiliares matrices A' and C' and solves the system: rho_i = inv(A'_ji) * C'_j
+ *
+ * All resources in A' and C' are saturated, i.e., sum(A'_j * rho_i) = C'_j.
+ *
+ * The matrix A' is built as follows:
+ * - For each resource j in alloc: copy row A_j to A'
+ * - If 2 players (i, k) share a same resource, assure fairness by adding a row in A' such as:
+ * - A_ji*rho_i - Ajk*rho_j = 0
+ *
+ * @param alloc for each resource, players that chose to saturate it
+ * @return Vector rho with "players' speed"
+ */
+ Eigen::VectorXd equilibrium(const allocation_map_t& alloc) const;
+
+ /**
+ * @brief Given a fair_sharing vector, gets the allocation
+ *
+ * The allocation for player i is given by: min(bound, f_j/A_ji).
+ * The minimum between all fair-sharing and the external bound (if any)
+ *
+ * The algorithm dictates a random initial allocation. For simplicity, we opt to use the same
+ * logic with the fair_sharing vector.
+ *
+ * @param fair_sharing Fair sharing vector
+ * @param initial Is this the initial allocation?
+ * @return allocation vector
+ */
+ bool get_alloc(const Eigen::VectorXd& fair_sharing, const allocation_map_t& last_alloc, allocation_map_t& alloc,
+ bool initial);
+
+ bool disturb_allocation(allocation_map_t& alloc, std::vector<int>& alloc_by_player);
+ /**
+ * @brief Calculates the fair sharing for each resource
+ *
+ * Basically 3 options:
+ * 1) resource in allocation: A_ji*rho_i since all players who selected this resource have the same share
+ * 2) resource not selected by saturated (fully used): divide it by the number of players C_/n_players
+ * 3) resource not selected and not-saturated: no limitation
+ *
+ * @param alloc Allocation map (resource-> players)
+ * @param rho Speed for each player i
+ * @param fair_sharing Output vector, fair sharing for each resource j
+ */
+ void set_fair_sharing(const allocation_map_t& alloc, const Eigen::VectorXd& rho, Eigen::VectorXd& fair_sharing) const;
+
+ /**
+ * @brief Check if allocation is BMF
+ *
+ * To be a bmf allocation it must:
+ * - respect the capacity of all resources
+ * - saturate at least 1 resource
+ * - every player receives maximum share in at least 1 saturated resource
+ * @param rho Allocation
+ * @return true if BMF false otherwise
+ */
+ bool is_bmf(const Eigen::VectorXd& rho) const;
+ std::vector<int> alloc_map_to_vector(const allocation_map_t& alloc) const;
+
+ /**
+ * @brief Set of debug functions to print the different objects
+ */
+ template <typename T> std::string debug_eigen(const T& obj) const;
+ template <typename C> std::string debug_vector(const C& container) const;
+ std::string debug_alloc(const allocation_map_t& alloc) const;
+
+ Eigen::MatrixXd A_; //!< A_ji: resource usage matrix, each row j represents a resource and col i a flow/player
+ Eigen::MatrixXd maxA_; //!< maxA_ji, similar as A_, but containing the maximum consumption of player i (if player a
+ //!< single flow it's equal to A_)
+ Eigen::VectorXd C_; //!< C_j Capacity of each resource
+ std::vector<bool> C_shared_; //!< shared_j Resource j is shared or not
+ Eigen::VectorXd phi_; //!< phi_i bound for each player
+
+ std::unordered_set<std::vector<int>, boost::hash<std::vector<int>>> allocations_;
+ AllocationGenerator gen_;
+ std::vector<int> 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
+};
+
+/**
+ * @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:
+ using allocation_map_t = std::unordered_map<int, std::unordered_set<int>>;
+ /**
+ * @brief Solve equation system to find a fair-sharing of resources
+ *
+ * @param cnst_list Constraint list (modified for selective update or active)
+ */
+ template <class CnstList> void bmf_solve(const CnstList& cnst_list);
+ /**
+ * @brief Iterates over system and build the consumption matrix A_ji and maxA_ji
+ *
+ * Each row j represents a resource and each col i a player/flow
+ *
+ * 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(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
+ * @param shared Resource is shared or not (fatpipe links)
+ */
+ template <class CnstList>
+ void get_constraint_data(const CnstList& cnst_list, Eigen::VectorXd& C, std::vector<bool>& shared);
+
+ std::unordered_map<int, Variable*> idx2Var_; //!< Map player index (and position in matrices) to system's variable
+ std::unordered_map<const Constraint*, int> cnst2idx_; //!< Conversely map constraint to index
+ bool warned_nonlinear_ = false;
+};
+
+} // namespace lmm
+} // namespace kernel
+} // namespace simgrid
+
+#endif
\ No newline at end of file
--- /dev/null
+/* Copyright (c) 2019-2022. 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. */
+
+#include "src/include/catch.hpp"
+#include "src/kernel/lmm/bmf.hpp"
+#include "src/surf/surf_interface.hpp"
+#include "xbt/log.h"
+
+namespace lmm = simgrid::kernel::lmm;
+
+TEST_CASE("kernel::bmf Basic tests", "[kernel-bmf-basic]")
+{
+ lmm::BmfSystem Sys(false);
+ xbt_log_control_set("ker_bmf.thres:debug");
+
+ SECTION("Single flow")
+ {
+ /*
+ * A single variable using a single resource
+ *
+ * In details:
+ * o System: a1 * p1 * \rho1 < C
+ * o consumption_weight: a1=1
+ * o sharing_penalty: p1=1
+ *
+ * Expectations
+ * o rho1 = C
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
+
+ Sys.expand(sys_cnst, rho_1, 1);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), 3, sg_maxmin_precision));
+ }
+
+ SECTION("Two flows")
+ {
+ /*
+ * Two flows sharing a single resource
+ *
+ * In details:
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
+ * o consumption_weight: a1=1 ; a2=10
+ * o sharing_penalty: p1=1 ; p2=1
+ *
+ * Expectations
+ * o a1*rho1 = C/2
+ * o a2*rho2 = C/2
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
+
+ Sys.expand(sys_cnst, rho_1, 1);
+ Sys.expand(sys_cnst, rho_2, 10);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), 3.0 / 2.0, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), (3.0 / 2.0) / 10.0, sg_maxmin_precision));
+ }
+
+ SECTION("Variable penalty/priority")
+ {
+ /*
+ * A variable with twice the penalty gets half of the share
+ *
+ * In details:
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
+ * o consumption_weight: a1=1 ; a2=1
+ * o sharing_penalty: p1=1 ; p2=2
+ *
+ * Expectations
+ * o rho1 = 2* rho2 (because rho2 has twice the penalty)
+ * o rho1 + rho2 = C (because all weights are 1)
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2);
+
+ Sys.expand(sys_cnst, rho_1, 1);
+ Sys.expand(sys_cnst, rho_2, 1);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), 2, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), 1, sg_maxmin_precision));
+ }
+
+ SECTION("Disable variable doesn't count")
+ {
+ /*
+ * Two flows sharing a single resource, but only disabled
+ *
+ * In details:
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
+ * o consumption_weight: a1=1 ; a2=10
+ * o sharing_penalty: p1=1 ; p2=0
+ *
+ * Expectations
+ * o a1*rho1 = C
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 0);
+
+ Sys.expand(sys_cnst, rho_1, 1);
+ Sys.expand(sys_cnst, rho_2, 10);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), 3.0, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), 0.0, sg_maxmin_precision));
+ }
+
+ SECTION("No consumption variable")
+ {
+ /*
+ * An empty variable, no consumption, just assure it receives something
+ *
+ * o System: a1 * p1 * \rho1 < C
+ * o consumption_weight: a1=0
+ * o sharing_penalty: p1=1
+ *
+ * Expectations
+ * o rho1 > 0
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 0);
+
+ Sys.expand(sys_cnst, rho_1, 1);
+ Sys.expand(sys_cnst, rho_2, 10);
+ Sys.solve();
+
+ REQUIRE(double_positive(rho_1->get_value(), sg_maxmin_precision));
+ }
+
+ SECTION("Bounded variable")
+ {
+ /*
+ * Assures a player receives the min(bound, share) if it's bounded
+ *
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
+ * o bounds: b1=0.1, b2=-1
+ * o consumption_weight: a1=1, a2=1
+ * o sharing_penalty: p1=1, p2=1
+ *
+ * Expectations
+ * o rho1 = .1
+ * o rho2 = .8
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, .1);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
+
+ Sys.expand(sys_cnst, rho_1, 2);
+ Sys.expand(sys_cnst, rho_2, 1);
+ Sys.solve();
+ REQUIRE(double_equals(rho_1->get_value(), .1, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), .8, sg_maxmin_precision));
+ }
+
+ SECTION("Fatpipe")
+ {
+ /*
+ * Two flows using a fatpipe resource
+ *
+ * In details:
+ * o System: a1 * p1 * \rho1 < C and a2 * p2 * \rho2 < C
+ * o consumption_weight: a1=1 ; a2=1
+ * o sharing_penalty: p1=1 ; p2=1
+ *
+ * Expectations
+ * o a1*rho1 = C
+ * o a2*rho2 = C
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
+ sys_cnst->set_sharing_policy(lmm::Constraint::SharingPolicy::FATPIPE, {});
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
+
+ Sys.expand(sys_cnst, rho_1, 1);
+ Sys.expand(sys_cnst, rho_2, 1);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), 3.0, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), 3.0, sg_maxmin_precision));
+ }
+
+ SECTION("(un)Bounded variable")
+ {
+ /*
+ * Assures a player receives the share if bound is greater than share
+ *
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
+ * o bounds: b1=1, b2=-1
+ * o consumption_weight: a1=1, a2=1
+ * o sharing_penalty: p1=1, p2=1
+ *
+ * Expectations
+ * o rho1 = .5
+ * o rho2 = .5
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, 1);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
+
+ Sys.expand(sys_cnst, rho_1, 1);
+ Sys.expand(sys_cnst, rho_2, 1);
+ Sys.solve();
+ REQUIRE(double_equals(rho_1->get_value(), .5, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), .5, sg_maxmin_precision));
+ }
+
+ SECTION("Dynamic bounds")
+ {
+ /*
+ * Resource bound is modified by user callback and shares are adapted accordingly
+ *
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
+ * o consumption_weight: a1=1, a2=1
+ * o sharing_penalty: p1=1, p2=1
+ *
+ * Expectations
+ * o rho1 = .5 and .25
+ * o rho2 = - and .25
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
+ sys_cnst->set_sharing_policy(lmm::Constraint::SharingPolicy::NONLINEAR,
+ [](double bound, int n) { return bound / n; });
+ // alone, full capacity
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
+ Sys.expand(sys_cnst, rho_1, 1);
+ Sys.solve();
+ REQUIRE(double_equals(rho_1->get_value(), 1, sg_maxmin_precision));
+
+ // add another variable, half initial capacity
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
+ Sys.expand(sys_cnst, rho_2, 1);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), .25, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), .25, sg_maxmin_precision));
+ }
+
+ Sys.variable_free_all();
+}
+
+TEST_CASE("kernel::bmf Advanced tests", "[kernel-bmf-advanced]")
+{
+ lmm::BmfSystem Sys(false);
+ xbt_log_control_set("ker_bmf.thres:debug");
+
+ SECTION("2 flows, 2 resources")
+ {
+ /*
+ * Two flows sharing 2 resources with opposite requirements
+ *
+ * In details:
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C2
+ * o C1 == C2
+ * o consumption_weight: a11=1, a12=10, a21=10, a22=1
+ * o sharing_penalty: p1=1, p2=1
+ *
+ * Expectations
+ * o rho1 = rho2 = C/11
+
+ * Matrices:
+ * [1 10] * [rho1 rho2] = [1]
+ * [10 1] [1]
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
+ lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 2);
+
+ Sys.expand(sys_cnst, rho_1, 1);
+ Sys.expand(sys_cnst2, rho_1, 10);
+ Sys.expand(sys_cnst, rho_2, 10);
+ Sys.expand(sys_cnst2, rho_2, 1);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), 1.0 / 11.0, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), 1.0 / 11.0, sg_maxmin_precision));
+ }
+
+ SECTION("BMF paper example")
+ {
+ /*
+ * 3 flows sharing 3 resources
+ *
+ * In details:
+ * [1 1 1/2] * [rho1 rho2 rho3] = [1]
+ * [1 1/2 1 ] [1]
+ * [1 3/4 3/4] [1]
+ *
+ * Expectations (several possible BMF allocations, our algorithm return this)
+ * o rho1 = rho2 = rho3 = 2/5
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
+ lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
+ lmm::Constraint* sys_cnst3 = Sys.constraint_new(nullptr, 1);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 3);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 3);
+ lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 3);
+
+ Sys.expand(sys_cnst3, rho_1, 1.0); // put this expand first to force a singular A' matrix
+ Sys.expand(sys_cnst, rho_1, 1.0);
+ Sys.expand(sys_cnst2, rho_1, 1.0);
+ Sys.expand(sys_cnst, rho_2, 1.0);
+ Sys.expand(sys_cnst2, rho_2, 1.0 / 2.0);
+ Sys.expand(sys_cnst3, rho_2, 3.0 / 4.0);
+ Sys.expand(sys_cnst, rho_3, 1.0 / 2.0);
+ Sys.expand(sys_cnst2, rho_3, 1.0);
+ Sys.expand(sys_cnst3, rho_3, 3.0 / 4.0);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), 1.0 / 3.0, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), 4.0 / 9.0, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_3->get_value(), 4.0 / 9.0, sg_maxmin_precision));
+ }
+
+ SECTION("IO - example")
+ {
+ /*
+ * Two flows sharing 1 disk
+ * read, write and readwrite constraint
+ *
+ * In details:
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C1
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C2
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C3
+ * o C1 == C2 == C3
+ * o consumption_weight: a1=1, a2=1
+ * o sharing_penalty: p1=1, p2=1
+ *
+ * Expectations
+ * o rho1 = rho2 = C/2
+
+ * Matrices:
+ * [1 10] * [rho1 rho2] = [1]
+ * [10 1] [1]
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1e6);
+ lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1e6);
+ lmm::Constraint* sys_cnst3 = Sys.constraint_new(nullptr, 1e6);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 3);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 3);
+
+ /* A' and C' matrices are dependent on the order of initialization
+ * this order is needed to identify a bug in the solver */
+ Sys.expand(sys_cnst2, rho_2, 1);
+ Sys.expand(sys_cnst, rho_1, 1);
+ Sys.expand(sys_cnst3, rho_1, 1);
+ Sys.expand(sys_cnst3, rho_2, 1);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), 1e6 / 2.0, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), 1e6 / 2.0, sg_maxmin_precision));
+ }
+
+ SECTION("Proportional fairness")
+ {
+ /*
+ * 3 flows sharing 2 resources with crosstraffic
+ *
+ * Regular max-min would give B/2 for every flow.
+ * BMF is equivalent to proportional fairness in this case, and give a quite
+ * different sharing.
+ *
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
+ lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 2);
+ lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 2);
+
+ double epsilon = 0.05;
+ Sys.expand(sys_cnst, rho_1, 1.0);
+ Sys.expand(sys_cnst2, rho_1, epsilon);
+ Sys.expand(sys_cnst, rho_2, 1.0);
+ Sys.expand(sys_cnst2, rho_2, epsilon);
+ Sys.expand(sys_cnst2, rho_3, 1.0);
+ Sys.expand(sys_cnst, rho_3, epsilon);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), 1.0 / (2.0 + 2 * epsilon), sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), 1.0 / (2.0 + 2 * epsilon), sg_maxmin_precision));
+ REQUIRE(double_equals(rho_3->get_value(), 1.0 / (1.0 + epsilon), sg_maxmin_precision));
+ }
+
+ Sys.variable_free_all();
+}
+
+TEST_CASE("kernel::bmf Subflows", "[kernel-bmf-subflow]")
+{
+ lmm::BmfSystem Sys(false);
+ xbt_log_control_set("ker_bmf.thres:debug");
+
+ SECTION("2 subflows and 1 resource")
+ {
+ /*
+ * 2 identical flows composed of 2 subflows
+ *
+ * They must receive the same share and use same amount of resources
+ *
+ * In details:
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
+ * o consumption_weight: a11=5, a12=7, a2=7, a2=5
+ * o sharing_penalty: p1=1, p2=1
+ *
+ * Expectations
+ * o rho1 = rho2 = (C/2)/12
+
+ * Matrices:
+ * [12 12] * [rho1 rho2] = [1]
+ * [12 12] [0]
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 5);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
+
+ Sys.expand_add(sys_cnst, rho_1, 5);
+ Sys.expand_add(sys_cnst, rho_1, 7);
+ Sys.expand_add(sys_cnst, rho_2, 7);
+ Sys.expand_add(sys_cnst, rho_2, 5);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), 5.0 / 24.0, sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), 5.0 / 24.0, sg_maxmin_precision));
+ }
+
+ SECTION("1 subflows, 1 flow and 1 resource")
+ {
+ /*
+ * 2 flows, 1 resource
+ * 1 flow composed of 2 subflows
+ *
+ * Same share/rho, but subflow uses 50% more resources since it has a second connection/subflow
+ *
+ * In details:
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
+ * o consumption_weight: a11=10, a12=5 a2=10
+ * o sharing_penalty: p1=1, p2=1
+ *
+ * Expectations
+ * o rho1 = (C/25)
+ * o rho2 = (C/25)
+
+ * Matrices:
+ * [15 10] * [rho1 rho2] = [1]
+ * [10 10] [0]
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 5);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
+
+ Sys.expand_add(sys_cnst, rho_1, 10);
+ Sys.expand_add(sys_cnst, rho_1, 5);
+ Sys.expand(sys_cnst, rho_2, 10);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), (5.0 / 25.0), sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), (5.0 / 25.0), sg_maxmin_precision));
+ REQUIRE(double_equals(15 * rho_1->get_value(), 10 * rho_2->get_value() * 3 / 2, sg_maxmin_precision));
+ }
+
+ SECTION("1 subflows using 2 resources: different max for each resource")
+ {
+ /*
+ * Test condition that we may have different max for different resources
+ *
+ * In details:
+ * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C
+ * o consumption_weight: a11=1, a12=1, a2=1
+ * o consumption_weight: a21=1/2, a12=1/2 a2=3/2
+ * o sharing_penalty: p1=1, p2=1
+ *
+ * Expectations
+ * o rho1 = (C1/3)
+ * o rho2 = (C1/3)
+
+ * Matrices:
+ * [2 1 ] * [rho1 rho2] = [1]
+ * [1 -1] [0]
+ */
+
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
+ lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 2);
+
+ Sys.expand_add(sys_cnst, rho_1, 1.0);
+ Sys.expand_add(sys_cnst, rho_1, 1.0);
+ Sys.expand(sys_cnst, rho_2, 1);
+ Sys.expand_add(sys_cnst2, rho_1, 1.0 / 2.0);
+ Sys.expand_add(sys_cnst2, rho_1, 1.0 / 2.0);
+ Sys.expand(sys_cnst2, rho_2, 3.0 / 2.0);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), (1.0 / 3.0), sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), (1.0 / 3.0), sg_maxmin_precision));
+ }
+
+ Sys.variable_free_all();
+}
+
+TEST_CASE("kernel::bmf Loop", "[kernel-bmf-loop]")
+{
+ lmm::BmfSystem Sys(false);
+ xbt_log_control_set("ker_bmf.thres:debug");
+
+ SECTION("Initial allocation loops")
+ {
+ /*
+ * Complex matrix whose initial allocation loops and is unable
+ * to stabilize after 10 iterations.
+ *
+ * The algorithm needs to restart from another point
+ */
+
+ std::vector<double> C = {1.0, 1.0, 1.0, 1.0, 1.0};
+ std::vector<std::vector<double>> A = {
+ {0.0918589, 0.980201, 0.553352, 0.0471331, 0.397493, 0.0494386, 0.158874, 0.737557, 0.822504, 0.364411},
+ {0.852866, 0.383171, 0.924183, 0.318345, 0.937625, 0.980201, 0.0471331, 0.0494386, 0.737557, 0.364411},
+ {0.12043, 0.985661, 0.153195, 0.852866, 0.247113, 0.318345, 0.0918589, 0.0471331, 0.158874, 0.364411},
+ {0.387291, 0.159939, 0.641492, 0.985661, 0.0540999, 0.383171, 0.318345, 0.980201, 0.0494386, 0.364411},
+ {0.722983, 0.924512, 0.474874, 0.819576, 0.572598, 0.0540999, 0.247113, 0.937625, 0.397493, 0.364411}};
+
+ std::vector<lmm::Constraint*> sys_cnst;
+ for (auto c : C) {
+ sys_cnst.push_back(Sys.constraint_new(nullptr, c));
+ }
+ std::vector<lmm::Variable*> vars;
+ for (size_t i = 0; i < A[0].size(); i++) {
+ vars.push_back(Sys.variable_new(nullptr, 1, -1, A.size()));
+ }
+ for (size_t j = 0; j < A.size(); j++) {
+ for (size_t i = 0; i < A[j].size(); i++) {
+ Sys.expand_add(sys_cnst[j], vars[i], A[j][i]);
+ }
+ }
+ Sys.solve();
+
+ for (auto* rho : vars) {
+ REQUIRE(double_positive(rho->get_value(), sg_maxmin_precision));
+ }
+ }
+
+ 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);
+
+ SECTION("Random consumptions - independent flows")
+ {
+ int C = 5;
+ int N = 2;
+ auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
+ std::vector<lmm::Constraint*> sys_cnst;
+ for (int i = 0; i < C; i++) {
+ sys_cnst.push_back(Sys.constraint_new(nullptr, 1));
+ }
+ for (int j = 0; j < N; j++) {
+ for (int i = 0; i < C; i++) {
+ lmm::Variable* rho = Sys.variable_new(nullptr, 1);
+ Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
+ }
+ }
+ Sys.solve();
+ }
+
+ SECTION("Random consumptions - flows sharing resources")
+ {
+ int C = 5;
+ int N = 10;
+ auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
+
+ std::vector<lmm::Constraint*> sys_cnst;
+ for (int i = 0; i < C; i++) {
+ sys_cnst.push_back(Sys.constraint_new(nullptr, 1));
+ }
+ for (int j = 0; j < N; j++) {
+ lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
+ for (int i = 0; i < C; i++) {
+ Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
+ }
+ }
+
+ Sys.solve();
+ }
+
+ SECTION("Random integer consumptions - flows sharing resources")
+ {
+ int C = 5;
+ int N = 10;
+ auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
+
+ std::vector<lmm::Constraint*> sys_cnst;
+ for (int i = 0; i < C; i++) {
+ sys_cnst.push_back(Sys.constraint_new(nullptr, 10));
+ }
+ for (int j = 0; j < N; j++) {
+ lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
+ for (int i = 0; i < C; i++) {
+ Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
+ }
+ }
+ Sys.solve();
+ }
+
+ SECTION("Random consumptions - high number of constraints")
+ {
+ int C = 500;
+ int N = 10;
+ auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0))));
+
+ std::vector<lmm::Constraint*> sys_cnst;
+ for (int i = 0; i < C; i++) {
+ sys_cnst.push_back(Sys.constraint_new(nullptr, 1));
+ }
+ for (int j = 0; j < N; j++) {
+ lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
+ for (int i = 0; i < C; i++) {
+ Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
+ }
+ }
+ Sys.solve();
+ }
+
+ SECTION("Random integer consumptions - high number of constraints")
+ {
+ int C = 500;
+ int N = 10;
+ auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10))));
+
+ std::vector<lmm::Constraint*> sys_cnst;
+ for (int i = 0; i < C; i++) {
+ sys_cnst.push_back(Sys.constraint_new(nullptr, 10));
+ }
+ for (int j = 0; j < N; j++) {
+ lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C);
+ for (int i = 0; i < C; i++) {
+ Sys.expand_add(sys_cnst[i], rho, data[i * j + j]);
+ }
+ }
+ Sys.solve();
+ }
+
+ Sys.variable_free_all();
+}
+
+TEST_CASE("kernel::AllocationGenerator Basic tests", "[kernel-bmf-allocation-gen]")
+{
+ SECTION("Full combinations")
+ {
+ Eigen::MatrixXd A(3, 3);
+ A << 1, .5, 1, 1, 1, .5, 1, .75, .75;
+ lmm::AllocationGenerator gen(std::move(A));
+ int i = 0;
+ std::vector<int> alloc;
+ while (gen.next(alloc))
+ i++;
+ REQUIRE(i == 3 * 3 * 3);
+ }
+
+ SECTION("Few options per player")
+ {
+ Eigen::MatrixXd A(3, 3);
+ A << 1, 0, 0, 0, 1, 0, 0, 1, 1;
+ lmm::AllocationGenerator gen(std::move(A));
+ int i = 0;
+ std::vector<int> alloc;
+ while (gen.next(alloc))
+ i++;
+ REQUIRE(i == 1 * 2 * 1);
+ }
+}
\ No newline at end of file
Element& elem = var->cnsts_.back();
elem.consumption_weight = consumption_weight;
+ elem.max_consumption_weight = consumption_weight;
elem.constraint = cnst;
elem.variable = var;
if (var->sharing_penalty_ != 0.0)
elem.decrease_concurrency();
+ elem.max_consumption_weight = std::max(elem.max_consumption_weight, value);
if (cnst->sharing_policy_ != Constraint::SharingPolicy::FATPIPE)
elem.consumption_weight += value;
else
// - if CPU, then probably 1.
// - If network, then 1 in forward direction and 0.05 backward for the ACKs
double consumption_weight;
+ // maximum consumption weight (can be different from consumption_weight with subflows/ptasks)
+ double max_consumption_weight = 0;
};
class ConstraintLight {
std::unique_ptr<resource::Action::ModifiedSet> modified_set_ = nullptr;
+protected:
+ bool selective_update_active; /* flag to update partially the system only selecting changed portions */
+ boost::intrusive::list<Constraint, boost::intrusive::member_hook<Constraint, boost::intrusive::list_member_hook<>,
+ &Constraint::modified_constraint_set_hook_>>
+ modified_constraint_set;
+
private:
using dyn_light_t = std::vector<int>;
std::vector<ConstraintLight> 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, boost::intrusive::member_hook<Constraint, boost::intrusive::list_member_hook<>,
&Constraint::constraint_set_hook_>>
constraint_set;
- boost::intrusive::list<Constraint, boost::intrusive::member_hook<Constraint, boost::intrusive::list_member_hook<>,
- &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);
};
REQUIRE(double_equals(rho_3->get_value(), 2, sg_maxmin_precision));
}
+ Sys.variable_free_all();
+}
+
+TEST_CASE("kernel::lmm shared systems with crosstraffic", "[kernel-lmm-shared-crosstraffic]")
+{
+ lmm::System Sys(false);
+
+ SECTION("3 flows, 3 resource: crosstraffic")
+ {
+ /*
+ * 3 flows sharing 2 constraints, single
+ *
+ * In details:
+ * o System: a1 * \rho1 + a2 * \rho2 + epsilon * \rho3 < C1
+ * epsilon * \rho1 + epsilon * \rho2 + a3 * \rho3 < C2
+ * o consumption_weight: a1=1, a2=1, a3=1, epsilon=0.05
+ * o C1 = C2 = 1
+ *
+ * Expectations
+ * o rho1 = rho2 = rho3 = 1/2
+ */
+ lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1);
+ lmm::Constraint* sys_cnst2 = Sys.constraint_new(nullptr, 1);
+ lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1, -1, 2);
+ lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1, -1, 2);
+ lmm::Variable* rho_3 = Sys.variable_new(nullptr, 1, -1, 2);
+
+ double epsilon = 0.05;
+ Sys.expand(sys_cnst, rho_1, 1.0);
+ Sys.expand(sys_cnst2, rho_1, epsilon);
+ Sys.expand(sys_cnst, rho_2, 1.0);
+ Sys.expand(sys_cnst2, rho_2, epsilon);
+ Sys.expand(sys_cnst2, rho_3, 1.0);
+ Sys.expand(sys_cnst, rho_3, epsilon);
+ Sys.solve();
+
+ REQUIRE(double_equals(rho_1->get_value(), 1.0 / (2.0 + epsilon), sg_maxmin_precision));
+ REQUIRE(double_equals(rho_2->get_value(), 1.0 / (2.0 + epsilon), sg_maxmin_precision));
+ REQUIRE(double_equals(rho_3->get_value(), 1.0 / (2.0 + epsilon), sg_maxmin_precision));
+ }
+
Sys.variable_free_all();
}
\ No newline at end of file
"Maximum number of concurrent variables in the maxmim system. Also limits the number of "
"processes on each host, at higher level. (default: -1 means no such limitation)");
+ 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<bool>("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
#include <xbt/config.hpp>
#include "src/kernel/EngineImpl.hpp"
+#include "src/kernel/lmm/bmf.hpp"
#include "src/kernel/resource/profile/Event.hpp"
#include "src/surf/ptask_L07.hpp"
{
XBT_CINFO(xbt_cfg, "Switching to the L07 model to handle parallel tasks.");
- auto host_model = std::make_shared<simgrid::kernel::resource::HostL07Model>("Host_Ptask");
+ auto* system = new simgrid::kernel::lmm::FairBottleneck(true /* selective update */);
+ auto host_model = std::make_shared<simgrid::kernel::resource::HostL07Model>("Host_Ptask", system);
+ auto* engine = simgrid::kernel::EngineImpl::get_instance();
+ engine->add_model(host_model);
+ engine->get_netzone_root()->set_host_model(host_model);
+}
+
+void surf_host_model_init_ptask_BMF()
+{
+ XBT_CINFO(xbt_cfg, "Switching to the BMF model to handle parallel tasks.");
+
+ bool select = simgrid::config::get_value<bool>("bmf/selective-update");
+ auto* system = new simgrid::kernel::lmm::BmfSystem(select);
+ auto host_model = std::make_shared<simgrid::kernel::resource::HostL07Model>("Host_Ptask", system);
auto* engine = simgrid::kernel::EngineImpl::get_instance();
engine->add_model(host_model);
engine->get_netzone_root()->set_host_model(host_model);
namespace kernel {
namespace resource {
-HostL07Model::HostL07Model(const std::string& name) : HostModel(name)
+HostL07Model::HostL07Model(const std::string& name, lmm::System* sys) : HostModel(name)
{
- auto* maxmin_system = new lmm::FairBottleneck(true /* selective update */);
- set_maxmin_system(maxmin_system);
+ set_maxmin_system(sys);
- auto net_model = std::make_shared<NetworkL07Model>("Network_Ptask", this, maxmin_system);
+ auto net_model = std::make_shared<NetworkL07Model>("Network_Ptask", this, sys);
auto engine = EngineImpl::get_instance();
engine->add_model(net_model);
engine->get_netzone_root()->set_network_model(net_model);
- auto cpu_model = std::make_shared<CpuL07Model>("Cpu_Ptask", this, maxmin_system);
+ auto cpu_model = std::make_shared<CpuL07Model>("Cpu_Ptask", this, sys);
engine->add_model(cpu_model);
engine->get_netzone_root()->set_cpu_pm_model(cpu_model);
}
/* Expand it for the CPUs even if there is nothing to compute, to make sure that it gets expended even if there is no
* communication either */
for (size_t i = 0; i < host_list.size(); i++) {
- model->get_maxmin_system()->expand(host_list[i]->get_cpu()->get_constraint(), get_variable(),
- (flops_amount == nullptr ? 0.0 : flops_amount[i]));
+ model->get_maxmin_system()->expand_add(host_list[i]->get_cpu()->get_constraint(), get_variable(),
+ (flops_amount == nullptr ? 0.0 : flops_amount[i]));
}
if (bytes_amount != nullptr) {
*********/
class HostL07Model : public HostModel {
public:
- explicit HostL07Model(const std::string& name);
+ HostL07Model(const std::string& name, lmm::System* sys);
HostL07Model(const HostL07Model&) = delete;
HostL07Model& operator=(const HostL07Model&) = delete;
&surf_host_model_init_compound},
{"ptask_L07", "Host model somehow similar to Cas01+CM02 but allowing parallel tasks",
&surf_host_model_init_ptask_L07},
+ {"ptask_BMF", "Host model which implements BMF resource allocation and allows parallel tasks",
+ &surf_host_model_init_ptask_BMF},
};
const std::vector<surf_model_description_t> surf_optimization_mode_description = {
XBT_PUBLIC_DATA double sg_maxmin_precision;
XBT_PUBLIC_DATA double sg_surf_precision;
XBT_PUBLIC_DATA int sg_concurrency_limit;
+XBT_PUBLIC_DATA int sg_bmf_max_iterations;
extern XBT_PRIVATE double sg_latency_factor;
extern XBT_PRIVATE double sg_bandwidth_factor;
*/
XBT_PUBLIC void surf_host_model_init_ptask_L07();
+/** @ingroup SURF_models
+ * @brief Initializes the platform with the model BMF
+ *
+ * With this model, only parallel tasks can be used.
+ * Resource sharing is done by calculating a BMF (bottleneck max fairness) allocation
+ */
+XBT_PUBLIC void surf_host_model_init_ptask_BMF();
+
XBT_PUBLIC void surf_disk_model_init_default();
/* --------------------
-foreach(x cloud-sharing ptask_L07_usage wifi_usage wifi_usage_decay cm02-set-lat-bw)
+foreach(x cloud-sharing ptask_L07_usage ptask-subflows wifi_usage wifi_usage_decay cm02-set-lat-bw)
add_executable (${x} EXCLUDE_FROM_ALL ${x}/${x}.cpp)
target_link_libraries(${x} simgrid)
set_target_properties(${x} PROPERTIES RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/${x})
--- /dev/null
+/* Copyright (c) 2007-2022. 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. */
+
+#include <simgrid/s4u.hpp>
+
+namespace sg4 = simgrid::s4u;
+
+XBT_LOG_NEW_DEFAULT_CATEGORY(ptask_subflows_test, "Messages specific for this s4u example");
+
+static void ptask(sg4::Host* recv, sg4::Host* sender)
+{
+ XBT_INFO("TEST: 1 parallel task with 2 flows");
+ XBT_INFO("Parallel task sends 1.5B to other host.");
+ XBT_INFO("Same result for L07 and BMF since the ptask is alone.");
+ XBT_INFO("Should be done in 2.5 seconds: 1s latency and 1.5 second for transfer");
+
+ double start_time = sg4::Engine::get_clock();
+ sg4::Exec::init()
+ ->set_bytes_amounts(std::vector<double>({0.0, 0.0, 1.0, 0.0, 0.0, 0.5, 0.0, 0.0, 0.0}))
+ ->set_hosts(std::vector<sg4::Host*>({sender, sender, recv}))
+ ->wait();
+ double end_time = sg4::Engine::get_clock();
+ XBT_INFO("Parallel task finished after %lf seconds", end_time - start_time);
+
+ XBT_INFO("TEST: Same parallel task but with a noisy communication at the side");
+ XBT_INFO("Parallel task sends 1.5B to other host.");
+ XBT_INFO("With BMF: Should be done in 3.5 seconds: 1s latency and 2 second for transfer.");
+ XBT_INFO("With L07: Should be done in 4 seconds: 1s latency and 3 second for transfer.");
+ XBT_INFO("With BMF, ptask gets 50%% more bandwidth than the noisy flow (because of the sub).");
+ start_time = sg4::Engine::get_clock();
+ auto noisy = sg4::Comm::sendto_async(sender, recv, 10);
+ sg4::Exec::init()
+ ->set_bytes_amounts(std::vector<double>({0.0, 0.0, 1.0, 0.0, 0.0, 0.5, 0.0, 0.0, 0.0}))
+ ->set_hosts(std::vector<sg4::Host*>({sender, sender, recv}))
+ ->wait();
+ end_time = sg4::Engine::get_clock();
+ XBT_INFO("Parallel task finished after %lf seconds", end_time - start_time);
+ noisy->wait(); // gracefully wait the noisy flow
+}
+
+int main(int argc, char* argv[])
+{
+ sg4::Engine e(&argc, argv);
+
+ auto* rootzone = sg4::create_full_zone("root");
+ auto* hostA = rootzone->create_host("hostA", 1e9);
+ auto* hostB = rootzone->create_host("hostB", 1e9);
+ sg4::LinkInRoute link(rootzone->create_link("backbone", "1")->set_latency("1s")->seal());
+ rootzone->add_route(hostA->get_netpoint(), hostB->get_netpoint(), nullptr, nullptr, {link}, true);
+ rootzone->seal();
+
+ sg4::Actor::create("ptask", hostA, ptask, hostA, hostB);
+
+ e.run();
+
+ return 0;
+}
--- /dev/null
+p Test subflows with new BMF model
+$ ${bindir:=.}/ptask-subflows --cfg=host/model:ptask_BMF
+> [0.000000] [xbt_cfg/INFO] Configuration change: Set 'host/model' to 'ptask_BMF'
+> [0.000000] [xbt_cfg/INFO] Switching to the BMF model to handle parallel tasks.
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] TEST: 1 parallel task with 2 flows
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] Parallel task sends 1.5B to other host.
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] Same result for L07 and BMF since the ptask is alone.
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] Should be done in 2.5 seconds: 1s latency and 1.5 second for transfer
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] Parallel task finished after 2.500000 seconds
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] TEST: Same parallel task but with a noisy communication at the side
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] Parallel task sends 1.5B to other host.
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] With BMF: Should be done in 3.5 seconds: 1s latency and 2 second for transfer.
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] With L07: Should be done in 4 seconds: 1s latency and 3 second for transfer.
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] With BMF, ptask gets 50% more bandwidth than the noisy flow (because of the sub).
+> [hostA:ptask:(1) 6.000000] [ptask_subflows_test/INFO] Parallel task finished after 3.500000 seconds
+
+
+p Test subflows with old L07 model to verify the difference
+$ ${bindir:=.}/ptask-subflows --cfg=host/model:ptask_L07
+> [0.000000] [xbt_cfg/INFO] Configuration change: Set 'host/model' to 'ptask_L07'
+> [0.000000] [xbt_cfg/INFO] Switching to the L07 model to handle parallel tasks.
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] TEST: 1 parallel task with 2 flows
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] Parallel task sends 1.5B to other host.
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] Same result for L07 and BMF since the ptask is alone.
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] Should be done in 2.5 seconds: 1s latency and 1.5 second for transfer
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] Parallel task finished after 2.500000 seconds
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] TEST: Same parallel task but with a noisy communication at the side
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] Parallel task sends 1.5B to other host.
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] With BMF: Should be done in 3.5 seconds: 1s latency and 2 second for transfer.
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] With L07: Should be done in 4 seconds: 1s latency and 3 second for transfer.
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] With BMF, ptask gets 50% more bandwidth than the noisy flow (because of the sub).
+> [hostA:ptask:(1) 6.500000] [ptask_subflows_test/INFO] Parallel task finished after 4.000000 seconds
+
+p Test selective_update enable
+$ ${bindir:=.}/ptask-subflows --cfg=host/model:ptask_BMF --cfg=bmf/selective-update:true
+> [0.000000] [xbt_cfg/INFO] Configuration change: Set 'host/model' to 'ptask_BMF'
+> [0.000000] [xbt_cfg/INFO] Configuration change: Set 'bmf/selective-update' to 'true'
+> [0.000000] [xbt_cfg/INFO] Switching to the BMF model to handle parallel tasks.
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] TEST: 1 parallel task with 2 flows
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] Parallel task sends 1.5B to other host.
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] Same result for L07 and BMF since the ptask is alone.
+> [hostA:ptask:(1) 0.000000] [ptask_subflows_test/INFO] Should be done in 2.5 seconds: 1s latency and 1.5 second for transfer
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] Parallel task finished after 2.500000 seconds
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] TEST: Same parallel task but with a noisy communication at the side
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] Parallel task sends 1.5B to other host.
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] With BMF: Should be done in 3.5 seconds: 1s latency and 2 second for transfer.
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] With L07: Should be done in 4 seconds: 1s latency and 3 second for transfer.
+> [hostA:ptask:(1) 2.500000] [ptask_subflows_test/INFO] With BMF, ptask gets 50% more bandwidth than the noisy flow (because of the sub).
+> [hostA:ptask:(1) 6.000000] [ptask_subflows_test/INFO] Parallel task finished after 3.500000 seconds
src/surf/ns3/ns3_simulator.cpp )
set(SURF_SRC
+ src/kernel/lmm/bmf.hpp
+ src/kernel/lmm/bmf.cpp
src/kernel/lmm/fair_bottleneck.cpp
src/kernel/lmm/maxmin.hpp
src/kernel/lmm/maxmin.cpp
src/xbt/dynar_test.cpp
src/xbt/random_test.cpp
src/xbt/xbt_str_test.cpp
- src/kernel/lmm/maxmin_test.cpp)
+ src/kernel/lmm/bmf_test.cpp
+ src/kernel/lmm/maxmin_test.cpp)
if (SIMGRID_HAVE_MC)
set(UNIT_TESTS ${UNIT_TESTS} src/mc/sosp/Snapshot_test.cpp src/mc/sosp/PageStore_test.cpp)
else()
git \
valgrind \
libboost-dev libboost-all-dev \
+ libeigen3-dev \
cmake \
python3-pip \
doxygen fig2dev \
wget https://framagit.org/${DLURL} && \
tar xf simgrid-* && rm simgrid-*tar.gz && \
cd simgrid-* && \
- apt install -y g++ gcc git valgrind gfortran libboost-dev libboost-all-dev cmake dpkg-dev python3-dev pybind11-dev && \
+ apt install -y g++ gcc git valgrind gfortran libboost-dev libboost-all-dev libeigen3-dev cmake dpkg-dev python3-dev pybind11-dev && \
cmake -DCMAKE_INSTALL_PREFIX=/usr/ -Denable_documentation=OFF -Denable_smpi=ON -Denable_compile_optimizations=ON . && \
make -j4 && \
mkdir debian/ && touch debian/control && dpkg-shlibdeps --ignore-missing-info lib/*.so -llib/ -O/tmp/deps && \
make install && make clean && \
- apt remove -y g++ gcc git valgrind default-jdk gfortran libboost-dev libboost-all-dev cmake dpkg-dev wget python3-dev pybind11-dev && \
+ apt remove -y g++ gcc git valgrind default-jdk gfortran libboost-dev libboost-all-dev libeigen3-dev cmake dpkg-dev wget python3-dev pybind11-dev && \
apt install `sed -e 's/shlibs:Depends=//' -e 's/([^)]*)//g' -e 's/,//g' /tmp/deps` && \
apt autoremove -y && apt autoclean && apt clean
# - Get the tutorial files (with an empty makefile advising to run cmake before make, just in case)
# - Remove everything that was installed, and re-install what's needed by the SimGrid libraries before the Gran Final Cleanup
# - Keep g++ gcc gfortran as any MC user will use (some of) them
-RUN apt install -y g++ gcc git valgrind gfortran libboost-dev libboost-stacktrace-dev cmake dpkg-dev libunwind-dev libdw-dev libelf-dev libevent-dev python3-dev && \
+RUN apt install -y g++ gcc git valgrind gfortran libboost-dev libeigen3-dev libboost-stacktrace-dev cmake dpkg-dev libunwind-dev libdw-dev libelf-dev libevent-dev python3-dev && \
mkdir /source/ && cd /source && git clone --depth=1 https://framagit.org/simgrid/simgrid.git simgrid.git && \
cd simgrid.git && \
cmake -DCMAKE_INSTALL_PREFIX=/usr/ -Denable_model-checking=ON -Denable_documentation=OFF -Denable_java=OFF -Denable_smpi=ON -Denable_compile_optimizations=ON . && \
# - Clone simgrid-template-s4u, as it is needed by the tutorial
# - Add an empty makefile advising to run cmake before make, just in case
-RUN apt install -y python-is-python3 pajeng r-base r-cran-tidyverse r-cran-devtools cmake g++ git libboost-dev flex bison libfmt-dev && \
+RUN apt install -y python-is-python3 pajeng r-base r-cran-tidyverse r-cran-devtools cmake g++ git libboost-dev libeigen3-dev flex bison libfmt-dev && \
cd /source && \
git clone --depth=1 https://framagit.org/simgrid/simgrid-template-s4u.git simgrid-template-s4u.git && \
printf "master-workers ping-pong:\n\t@echo \"Please run the following command before make:\";echo \" cmake .\"; exit 1" > Makefile && \
RUN apt update && apt -y upgrade
# - Clone simgrid-template-smpi, as it is needed by the tutorial
-RUN apt install -y python3 pajeng libssl-dev r-base r-cran-devtools r-cran-tidyverse build-essential g++ gfortran git libboost-dev cmake flex bison libfmt-dev && \
+RUN apt install -y python3 pajeng libssl-dev r-base r-cran-devtools r-cran-tidyverse build-essential g++ gfortran git libboost-dev libeigen3-dev cmake flex bison libfmt-dev && \
cd /source && \
git clone --depth=1 https://framagit.org/simgrid/simgrid-template-smpi.git simgrid-template-smpi.git && \
apt autoremove -y && apt clean && apt autoclean
# - Compile and install SimGrid itself. Clean the tree.
# - Remove everything that was installed, and re-install what's needed by the SimGrid libraries before the Gran Final Cleanup
RUN apt-get --allow-releaseinfo-change update && apt -y upgrade && \
- apt install -y g++ gcc git valgrind gfortran libboost-dev libboost-all-dev cmake dpkg-dev python3-dev pybind11-dev && \
+ apt install -y g++ gcc git valgrind gfortran libboost-dev libboost-all-dev libeigen3-dev cmake dpkg-dev python3-dev pybind11-dev && \
mkdir /source/ && cd /source && git clone --depth=1 https://framagit.org/simgrid/simgrid.git simgrid.git && \
cd simgrid.git && \
cmake -DCMAKE_INSTALL_PREFIX=/usr/ -Denable_documentation=OFF -Denable_smpi=ON -Denable_compile_optimizations=ON . && \
make -j4 install && \
mkdir debian/ && touch debian/control && dpkg-shlibdeps --ignore-missing-info lib/*.so -llib/ -O/tmp/deps && \
git reset --hard master && git clean -dfx && \
- apt remove -y g++ gcc git valgrind default-jdk gfortran libboost-dev libboost-all-dev cmake dpkg-dev python3-dev pybind11-dev && \
+ apt remove -y g++ gcc git valgrind default-jdk gfortran libboost-dev libboost-all-dev libeigen3-dev cmake dpkg-dev python3-dev pybind11-dev && \
apt install `sed -e 's/shlibs:Depends=//' -e 's/([^)]*)//g' -e 's/,//g' /tmp/deps` && \
apt autoremove -y && apt autoclean && apt clean
