Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Merge branch 'hypervisor' into surf++
[simgrid.git] / src / surf / fair_bottleneck.cpp
1 /* Copyright (c) 2007, 2008, 2009, 2010. The SimGrid Team.
2  * All rights reserved.                                                     */
3
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. */
6
7 #include "xbt/sysdep.h"
8 #include "xbt/log.h"
9 #include "solver.hpp"
10 #include <stdlib.h>
11 #include <math.h>
12
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);
17
18 void bottleneck_solve(lmm_system_t sys)
19 {
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;
25   
26   xbt_swag_t elem_list = NULL;
27   int i;
28
29   static s_xbt_swag_t cnst_to_update;
30   vector<ConstraintPtr> cnstToUpdate;
31
32   if (!(lmm_system_modified(sys)))
33     return;
34
35   /* Init */
36
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;
45
46   varList = &(sys->m_variableSet);  
47   XBT_DEBUG("Variable set : %d", varList->size());
48   for (varIt=varList->begin(); varIt!=varList->end(); ++varIt) {
49     int nb = 0;
50     var = *varIt;
51     var->m_value = 0.0;
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)
56         nb++; 
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",
59                var);
60       sys->m_saturatedVariableSet.erase(std::find(sys->m_saturatedVariableSet.begin(), sys->m_saturatedVariableSet.end(), var));
61       var->m_value = 1.0;
62     }
63     if (var->m_weight <= 0.0) {
64       XBT_DEBUG("Err, finally, there is no need to take care of variable %p",
65              var);
66       sys->m_saturatedVariableSet.erase(std::find(sys->m_saturatedVariableSet.begin(), sys->m_saturatedVariableSet.end(), var));      
67     }
68   }
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;
77   }
78   XBT_DEBUG("Fair bottleneck Initialized");
79
80   /* 
81    * Compute Usage and store the variables that reach the maximum.
82    */
83
84   do {
85     if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
86       XBT_DEBUG("Fair bottleneck done");
87       lmm_print(sys);
88     }
89     XBT_DEBUG("******* Constraints to process: %d *******",
90            cnstList->size());
91     for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end();){
92       cnst = *cnstIt;
93       int nb = 0;
94       XBT_DEBUG("Processing cnst %p ", cnst);
95       elemList = &(cnst->m_elementSet);
96       cnst->m_usage = 0.0;
97       for(elemIt=elemList->begin(); elemIt!=elemList->end(); elemIt++) {
98         if (elem->p_variable->m_weight <= 0)
99           break;
100         if ((elem->m_value > 0)
101             && std::find(varList->begin(), varList->end(), elem->p_variable)!=varList->end());
102           nb++;
103       }
104       XBT_DEBUG("\tThere are %d variables", nb);
105       if (nb > 0 && !cnst->m_shared)
106         nb = 1;
107       if (!nb) {
108         cnst->m_remaining = 0.0;
109         cnst->m_usage = cnst->m_remaining;
110         cnstList->erase(std::find(cnstList->begin(), cnstList->end(), *cnstIt));        
111         continue;
112       }
113       cnst->m_usage = cnst->m_remaining / nb;
114       XBT_DEBUG("\tConstraint Usage %p : %f with %d variables", cnst,
115              cnst->m_usage, nb);
116       ++cnstIt;      
117     }
118
119     for (varIt=varList->begin(); varIt!=varList->end();){
120       var = *varIt;
121       double minInc =
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) {
124         elem = (*elemIt);
125         minInc = MIN(minInc, elem->p_constraint->m_usage / elem->m_value);
126       }
127       if (var->m_bound > 0)
128         minInc = MIN(minInc, var->m_bound - var->m_value);
129       var->m_mu = minInc;
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));       
134       } else 
135         ++varIt;
136     }
137
138     for (cnstIt=cnstList->begin(); cnstIt!=cnstList->end();) {
139       cnst = *cnstIt;
140       XBT_DEBUG("Updating cnst %p ", cnst);
141       elemList = &(cnst->m_elementSet);
142       for (elemIt=elemList->begin(); elemIt!=elemList->end();++elemIt) {
143         elem = *elemIt;
144         if (elem->p_variable->m_weight <= 0)
145           break;
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);
152         } else {
153           XBT_DEBUG
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);
157         }
158       }
159
160       if (!cnst->m_shared) {
161         XBT_DEBUG("\tUpdate constraint %p (%g) by %g",
162                cnst, cnst->m_remaining, cnst->m_usage);
163
164         double_update(&(cnst->m_remaining), cnst->m_usage);
165       }
166
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);
170
171         cnstList->erase(std::find(cnstList->begin(), cnstList->end(), cnst));
172
173         for (elemIt=elemList->begin(); elemIt!=elemList->end();++elemIt) {
174           if (elem->p_variable->m_weight <= 0)
175             break;
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));      
179           }
180         }
181       } else
182         ++cnstIt;
183     }
184   } while (!varList->empty());
185   
186   cnstList->clear();
187   sys->m_modified = 0;
188   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
189     XBT_DEBUG("Fair bottleneck done");
190     sys->print();
191   }
192 }