Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
debug + fixed many bugs due to too fast coding... :(
[simgrid.git] / src / surf / fair_bottleneck.c
1 /*      $Id$ */
2
3 /* Copyright (c) 2007 Arnaud Legrand. All rights reserved.               */
4
5 /* This program is free software; you can redistribute it and/or modify it
6  * under the terms of the license (GNU LGPL) which comes with this package. */
7
8
9 #include "xbt/sysdep.h"
10 #include "xbt/log.h"
11 #include "maxmin_private.h"
12 #include <stdlib.h>
13 #include <math.h>
14
15 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_maxmin);
16
17 void bottleneck_solve(lmm_system_t sys)
18 {
19   lmm_variable_t var = NULL;
20   lmm_constraint_t cnst = NULL;
21   lmm_constraint_t useless_cnst = NULL;
22   s_lmm_constraint_t s_cnst;
23   lmm_constraint_t cnst_next = NULL;
24   lmm_element_t elem = NULL;
25   xbt_swag_t cnst_list = NULL;
26   xbt_swag_t var_list = NULL;
27   xbt_swag_t elem_list = NULL;
28   double min_usage = -1;
29   int i;
30
31   static s_xbt_swag_t cnst_to_update;
32
33   if (!(sys->modified))
34     return;
35
36   /* Init */
37   xbt_swag_init(&(cnst_to_update),
38                 xbt_swag_offset(s_cnst, saturated_constraint_set_hookup));
39
40   var_list = &(sys->variable_set);
41   DEBUG1("Variable set : %d", xbt_swag_size(var_list));
42   xbt_swag_foreach(var, var_list) {
43     int nb=0;
44     var->value = 0.0;
45     for (i = 0; i < var->cnsts_number; i++) {
46       if(var->cnsts[i].value==0.0) nb++;
47     }
48     if((nb==var->cnsts_number) && (var->weight>0.0))
49       var->value = 1.0;
50   }
51
52   cnst_list = &(sys->active_constraint_set);
53   DEBUG1("Active constraints : %d", xbt_swag_size(cnst_list));
54   xbt_swag_foreach(cnst, cnst_list) {
55     xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
56   }
57   cnst_list = &(sys->saturated_constraint_set);
58   xbt_swag_foreach(cnst, cnst_list) {
59     cnst->remaining = cnst->bound;
60     cnst->usage = 0.0;
61   }
62
63   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
64     DEBUG0("Fair bottleneck Init");
65     lmm_print(sys);
66   }
67
68   /* 
69    * Compute Usage and store the variables that reach the maximum.
70    */
71   while (1) {
72     DEBUG1("******* Constraints to process: %d *******", xbt_swag_size(cnst_list));
73     xbt_swag_foreach_safe(cnst, cnst_next, cnst_list) {
74       int nb = 0;
75       double max_elem = 0.0;
76       DEBUG1("Processing cnst %p ", cnst);
77       elem_list = &(cnst->element_set);
78       cnst->usage = 0.0;
79       xbt_swag_foreach(elem, elem_list) {
80         if (elem->variable->weight <= 0)
81           break;
82         if ((elem->value > 0)) {
83           nb++;
84           if (max_elem > 0)
85             max_elem =
86                 MAX(max_elem, elem->value / elem->variable->weight);
87           else
88             max_elem = elem->value / elem->variable->weight;
89         }
90         //      make_elem_active(elem);
91       }
92       DEBUG2("\tmax_elem : %g with %d variables",  max_elem,nb);
93       if(nb>0 && !cnst->shared)
94         nb = 1;
95       cnst->usage = max_elem * nb;
96       DEBUG3("\tConstraint Usage %p : %f with %d variables", cnst, cnst->usage,nb);
97       if(!nb) {
98         xbt_swag_remove(cnst, cnst_list);
99         continue;
100       }
101       /* Saturated constraints update */
102       if (min_usage < 0 || min_usage > cnst->remaining / cnst->usage) {
103         DEBUG3("Update min_usage (%g) with cnst %p -> %g",min_usage, cnst,
104                cnst->remaining / cnst->usage);
105
106         min_usage = cnst->remaining / cnst->usage;
107         while ((useless_cnst = xbt_swag_extract(&(cnst_to_update)))) {
108           xbt_swag_insert_at_head(useless_cnst, cnst_list);
109         }
110         xbt_swag_remove(cnst, cnst_list);
111         xbt_swag_insert(cnst, &(cnst_to_update));
112       } else if (min_usage == cnst->remaining / cnst->usage) {
113         DEBUG2("Keep   min_usage (%g) with cnst %p",min_usage, cnst);
114         xbt_swag_remove(cnst, cnst_list);
115         xbt_swag_insert(cnst, &(cnst_to_update));
116       }
117     }
118
119     if (!xbt_swag_size(&cnst_to_update))
120       break;
121
122     while ((cnst_next = xbt_swag_extract(&cnst_to_update))) {
123       int nb = 0;
124       elem_list = &(cnst_next->element_set);
125       xbt_swag_foreach(elem, elem_list) {
126         if (elem->variable->weight <= 0)
127           break;
128         if ((elem->value > 0))
129           nb++;
130       }
131       if(nb>0 && !(cnst_next->shared))
132         nb = 1;
133
134       DEBUG1("Updating for cnst %p",cnst_next);
135
136       xbt_swag_foreach(elem, elem_list) {
137         var = elem->variable;
138         if (var->weight <= 0)
139           break;
140         if (var->value == 0.0) {
141           var->value = var->weight * cnst_next->remaining / (nb * elem->value);
142
143           /* Update usage */
144
145           DEBUG1("\tUpdating var %p",var);
146           for (i = 0; i < var->cnsts_number; i++) {
147             lmm_element_t elm = &var->cnsts[i];
148             cnst = elm->constraint;
149             DEBUG1("\t\tUpdating cnst %p",cnst);
150             double_update(&(cnst->remaining), elm->value * var->value);
151             double_update(&(cnst->usage), elm->value / var->weight);
152             //              make_elem_inactive(elm);
153           }
154         }
155       }
156     }
157   }
158
159   sys->modified = 0;
160   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
161     lmm_print(sys);
162   }
163 }