1 /* Copyright (c) 2007, 2008, 2009, 2010. 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 "xbt/sysdep.h"
13 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_maxmin);
14 #define SHOW_EXPR_G(expr) XBT_DEBUG(#expr " = %g",expr);
15 #define SHOW_EXPR_D(expr) XBT_DEBUG(#expr " = %d",expr);
16 #define SHOW_EXPR_P(expr) XBT_DEBUG(#expr " = %p",expr);
18 void bottleneck_solve(lmm_system_t sys)
20 lmm_variable_t var_next = NULL;
21 lmm_constraint_t cnst = NULL;
22 //s_lmm_constraint_t s_cnst;
23 lmm_constraint_t cnst_next = NULL;
24 xbt_swag_t cnst_list = NULL;
26 xbt_swag_t elem_list = NULL;
29 static s_xbt_swag_t cnst_to_update;
30 vector<ConstraintPtr> cnstToUpdate;
32 if (!(lmm_system_modified(sys)))
37 lmm_variable_t var = NULL;
38 lmm_element_t elem = NULL;
39 std::vector<VariablePtr> *varList;
40 std::vector<VariablePtr>::iterator varIt;
41 std::vector<ElementPtr> *elemList;
42 std::vector<ElementPtr>::iterator elemIt;
43 std::vector<ConstraintPtr> *cnstList;
44 std::vector<ConstraintPtr>::iterator cnstIt;
46 varList = &(sys->m_variableSet);
47 XBT_DEBUG("Variable set : %d", varList->size());
48 for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) {
52 XBT_DEBUG("Handling variable %p", var);
53 sys->m_saturatedVariableSet.push_back(var);
54 for (elemIt=var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt)
55 if ((*elemIt)->m_value == 0.0)
57 if ((nb == var->getNumberOfCnst()) && (var->m_weight > 0.0)) {
58 XBT_DEBUG("Err, finally, there is no need to take care of variable %p",
60 sys->m_saturatedVariableSet.erase(std::find(sys->m_saturatedVariableSet.begin(), sys->m_saturatedVariableSet.end(), var));
63 if (var->m_weight <= 0.0) {
64 XBT_DEBUG("Err, finally, there is no need to take care of variable %p",
66 sys->m_saturatedVariableSet.erase(std::find(sys->m_saturatedVariableSet.begin(), sys->m_saturatedVariableSet.end(), var));
69 varList = &(sys->m_saturatedVariableSet);
70 cnstList = &(sys->m_activeConstraintSet);
71 XBT_DEBUG("Active constraints : %d", cnstList->size());
72 sys->m_saturatedConstraintSet.insert(sys->m_saturatedConstraintSet.end(), cnstList->begin(), cnstList->end());
73 cnstList = &(sys->m_saturatedConstraintSet);
74 for(cnstIt=cnstList->begin(); cnstIt!=cnstList->end(); ++cnstIt) {
75 (*cnstIt)->m_remaining = (*cnstIt)->m_bound;
76 (*cnstIt)->m_usage = 0.0;
78 XBT_DEBUG("Fair bottleneck Initialized");
81 * Compute Usage and store the variables that reach the maximum.
85 if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
86 XBT_DEBUG("Fair bottleneck done");
89 XBT_DEBUG("******* Constraints to process: %d *******",
91 for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end();){
94 XBT_DEBUG("Processing cnst %p ", cnst);
95 elemList = &(cnst->m_elementSet);
97 for(elemIt=elemList->begin(); elemIt!=elemList->end(); elemIt++) {
98 if (elem->p_variable->m_weight <= 0)
100 if ((elem->m_value > 0)
101 && std::find(varList->begin(), varList->end(), elem->p_variable)!=varList->end());
104 XBT_DEBUG("\tThere are %d variables", nb);
105 if (nb > 0 && !cnst->m_shared)
108 cnst->m_remaining = 0.0;
109 cnst->m_usage = cnst->m_remaining;
110 cnstList->erase(std::find(cnstList->begin(), cnstList->end(), *cnstIt));
113 cnst->m_usage = cnst->m_remaining / nb;
114 XBT_DEBUG("\tConstraint Usage %p : %f with %d variables", cnst,
119 for (varIt=varList->begin(); varIt!=varList->end();){
122 var->m_cnsts.front()->p_constraint->m_usage / var->m_cnsts.front()->m_value;
123 for (elemIt=++var->m_cnsts.begin(); elemIt!=var->m_cnsts.end(); ++elemIt) {
125 minInc = MIN(minInc, elem->p_constraint->m_usage / elem->m_value);
127 if (var->m_bound > 0)
128 minInc = MIN(minInc, var->m_bound - var->m_value);
130 XBT_DEBUG("Updating variable %p maximum increment: %g", var, var->m_mu);
131 var->m_value += var->m_mu;
132 if (var->m_value == var->m_bound) {
133 varList->erase(std::find(varList->begin(), varList->end(), var));
138 for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end();) {
140 XBT_DEBUG("Updating cnst %p ", cnst);
141 elemList = &(cnst->m_elementSet);
142 for (elemIt=elemList->begin(); elemIt!=elemList->end();++elemIt) {
144 if (elem->p_variable->m_weight <= 0)
146 if (cnst->m_shared) {
147 XBT_DEBUG("\tUpdate constraint %p (%g) with variable %p by %g",
148 cnst, cnst->m_remaining, elem->p_variable,
149 elem->p_variable->m_mu);
150 double_update(&(cnst->m_remaining),
151 elem->m_value * elem->p_variable->m_mu);
154 ("\tNon-Shared variable. Update constraint usage of %p (%g) with variable %p by %g",
155 cnst, cnst->m_usage, elem->p_variable, elem->p_variable->m_mu);
156 cnst->m_usage = MIN(cnst->m_usage, elem->m_value * elem->p_variable->m_mu);
160 if (!cnst->m_shared) {
161 XBT_DEBUG("\tUpdate constraint %p (%g) by %g",
162 cnst, cnst->m_remaining, cnst->m_usage);
164 double_update(&(cnst->m_remaining), cnst->m_usage);
167 XBT_DEBUG("\tRemaining for %p : %g", cnst, cnst->m_remaining);
168 if (cnst->m_remaining == 0.0) {
169 XBT_DEBUG("\tGet rid of constraint %p", cnst);
171 cnstList->erase(std::find(cnstList->begin(), cnstList->end(), cnst));
173 for (elemIt=elemList->begin(); elemIt!=elemList->end();++elemIt) {
174 if (elem->p_variable->m_weight <= 0)
176 if (elem->m_value > 0) {
177 XBT_DEBUG("\t\tGet rid of variable %p", elem->p_variable);
178 varList->erase(std::find(varList->begin(), varList->end(), elem->p_variable));
184 } while (!varList->empty());
188 if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
189 XBT_DEBUG("Fair bottleneck done");