1 /* Copyright (c) 2007-2011, 2013-2017. The SimGrid Team.
2 * All rights reserved. */
4 /* This program is free software; you can redistribute it and/or modify it
5 * under the terms of the license (GNU LGPL) which comes with this package. */
7 #include "src/kernel/lmm/maxmin.hpp"
9 #include "xbt/sysdep.h"
15 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_maxmin);
16 #define SHOW_EXPR_G(expr) XBT_DEBUG(#expr " = %g", expr);
17 #define SHOW_EXPR_D(expr) XBT_DEBUG(#expr " = %d", expr);
18 #define SHOW_EXPR_P(expr) XBT_DEBUG(#expr " = %p", expr);
20 void simgrid::kernel::lmm::bottleneck_solve(lmm_system_t sys)
25 lmm_variable_t var = nullptr;
26 lmm_element_t elem = nullptr;
27 xbt_swag_t var_list = nullptr;
28 xbt_swag_t elem_list = nullptr;
30 if (not sys->modified)
33 var_list = &(sys->variable_set);
34 XBT_DEBUG("Variable set : %d", xbt_swag_size(var_list));
35 xbt_swag_foreach(_var, var_list)
37 var = static_cast<lmm_variable_t>(_var);
39 XBT_DEBUG("Handling variable %p", var);
40 if (var->sharing_weight > 0.0 && std::find_if(begin(var->cnsts), end(var->cnsts), [](s_lmm_element_t const& x) {
41 return x.consumption_weight != 0.0;
42 }) != end(var->cnsts)) {
43 xbt_swag_insert(var, &(sys->saturated_variable_set));
45 XBT_DEBUG("Err, finally, there is no need to take care of variable %p", var);
46 if (var->sharing_weight > 0.0)
50 var_list = &(sys->saturated_variable_set);
52 XBT_DEBUG("Active constraints : %zu", sys->active_constraint_set.size());
53 for (s_lmm_constraint_t& cnst : sys->active_constraint_set) {
54 sys->saturated_constraint_set.push_back(cnst);
56 for (s_lmm_constraint_t& cnst : sys->saturated_constraint_set) {
57 cnst.remaining = cnst.bound;
61 XBT_DEBUG("Fair bottleneck Initialized");
64 * Compute Usage and store the variables that reach the maximum.
66 auto& cnst_list = sys->saturated_constraint_set;
68 if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
69 XBT_DEBUG("Fair bottleneck done");
72 XBT_DEBUG("******* Constraints to process: %zu *******", cnst_list.size());
73 for (auto iter = std::begin(cnst_list); iter != std::end(cnst_list);) {
74 s_lmm_constraint_t& cnst = *iter;
76 XBT_DEBUG("Processing cnst %p ", &cnst);
77 elem_list = &cnst.enabled_element_set;
79 xbt_swag_foreach(_elem, elem_list)
81 elem = static_cast<lmm_element_t>(_elem);
82 xbt_assert(elem->variable->sharing_weight > 0);
83 if ((elem->consumption_weight > 0) && xbt_swag_belongs(elem->variable, var_list))
86 XBT_DEBUG("\tThere are %d variables", nb);
87 if (nb > 0 && not cnst.sharing_policy)
92 iter = cnst_list.erase(iter);
94 cnst.usage = cnst.remaining / nb;
95 XBT_DEBUG("\tConstraint Usage %p : %f with %d variables", &cnst, cnst.usage, nb);
100 xbt_swag_foreach_safe(_var, _var_next, var_list)
102 var = static_cast<lmm_variable_t>(_var);
103 double min_inc = DBL_MAX;
104 for (s_lmm_element_t const& elm : var->cnsts) {
105 if (elm.consumption_weight > 0)
106 min_inc = std::min(min_inc, elm.constraint->usage / elm.consumption_weight);
109 min_inc = std::min(min_inc, var->bound - var->value);
111 XBT_DEBUG("Updating variable %p maximum increment: %g", var, var->mu);
112 var->value += var->mu;
113 if (var->value == var->bound) {
114 xbt_swag_remove(var, var_list);
118 for (auto iter = std::begin(cnst_list); iter != std::end(cnst_list);) {
119 s_lmm_constraint_t& cnst = *iter;
120 XBT_DEBUG("Updating cnst %p ", &cnst);
121 elem_list = &cnst.enabled_element_set;
122 xbt_swag_foreach(_elem, elem_list)
124 elem = static_cast<lmm_element_t>(_elem);
125 xbt_assert(elem->variable->sharing_weight > 0);
126 if (cnst.sharing_policy) {
127 XBT_DEBUG("\tUpdate constraint %p (%g) with variable %p by %g", &cnst, cnst.remaining, elem->variable,
129 double_update(&cnst.remaining, elem->consumption_weight * elem->variable->mu, sg_maxmin_precision);
131 XBT_DEBUG("\tNon-Shared variable. Update constraint usage of %p (%g) with variable %p by %g", &cnst,
132 cnst.usage, elem->variable, elem->variable->mu);
133 cnst.usage = std::min(cnst.usage, elem->consumption_weight * elem->variable->mu);
136 if (not cnst.sharing_policy) {
137 XBT_DEBUG("\tUpdate constraint %p (%g) by %g", &cnst, cnst.remaining, cnst.usage);
139 double_update(&cnst.remaining, cnst.usage, sg_maxmin_precision);
142 XBT_DEBUG("\tRemaining for %p : %g", &cnst, cnst.remaining);
143 if (cnst.remaining <= 0.0) {
144 XBT_DEBUG("\tGet rid of constraint %p", &cnst);
146 iter = cnst_list.erase(iter);
147 xbt_swag_foreach(_elem, elem_list)
149 elem = static_cast<lmm_element_t>(_elem);
150 if (elem->variable->sharing_weight <= 0)
152 if (elem->consumption_weight > 0) {
153 XBT_DEBUG("\t\tGet rid of variable %p", elem->variable);
154 xbt_swag_remove(elem->variable, var_list);
161 } while (xbt_swag_size(var_list));
164 sys->modified = true;
165 if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
166 XBT_DEBUG("Fair bottleneck done");