Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
cosmetic
[simgrid.git] / src / surf / maxmin.c
1 /*      $Id$     */
2
3 /* Copyright (c) 2004 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/error.h"
11 #include "maxmin_private.h"
12 #include <stdlib.h>
13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(maxmin, surf,
14                                 "Logging specific to the SURF maxmin module");
15
16 lmm_system_t lmm_system_new(void)
17 {
18   lmm_system_t l = NULL;
19   s_lmm_variable_t var;
20   s_lmm_constraint_t cnst;
21
22   l = xbt_new0(s_lmm_system_t, 1);
23
24   l->modified = 0;
25   xbt_swag_init(&(l->variable_set),
26                 xbt_swag_offset(var, variable_set_hookup));
27   xbt_swag_init(&(l->constraint_set),
28                 xbt_swag_offset(cnst, constraint_set_hookup));
29
30   xbt_swag_init(&(l->active_constraint_set),
31                 xbt_swag_offset(cnst, active_constraint_set_hookup));
32
33   xbt_swag_init(&(l->saturated_variable_set),
34                 xbt_swag_offset(var, saturated_variable_set_hookup));
35   xbt_swag_init(&(l->saturated_constraint_set),
36                 xbt_swag_offset(cnst, saturated_constraint_set_hookup));
37
38   return l;
39 }
40
41 void lmm_system_free(lmm_system_t sys)
42 {
43   lmm_variable_t var = NULL;
44   lmm_constraint_t cnst = NULL;
45
46   while ((var = extract_variable(sys)))
47     lmm_var_free(sys, var);
48
49   while ((cnst = extract_constraint(sys)))
50     lmm_cnst_free(sys, cnst);
51
52   xbt_free(sys);
53 }
54
55 void lmm_variable_disable(lmm_system_t sys, lmm_variable_t var)
56 {
57   int i;
58   lmm_element_t elem = NULL;
59
60   sys->modified = 1;
61
62   for (i = 0; i < var->cnsts_number; i++) {
63     elem = &var->cnsts[i];
64     xbt_swag_remove(elem, &(elem->constraint->element_set));
65     if (xbt_swag_size(&(elem->constraint->element_set)))
66       make_constraint_inactive(sys, elem->constraint);
67   }
68   var->cnsts_number = 0;
69 }
70
71 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var)
72 {
73
74   lmm_variable_disable(sys, var);
75
76   xbt_free(var->cnsts);
77   xbt_free(var);
78 }
79
80 static void lmm_cnst_free(lmm_system_t sys, lmm_constraint_t cnst)
81 {
82   xbt_assert0(xbt_swag_size(&(cnst->element_set)),
83               "This list should be empty!");
84   remove_active_constraint(sys, cnst);
85   xbt_free(cnst);
86 }
87
88 lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id,
89                                     double bound_value)
90 {
91   lmm_constraint_t cnst = NULL;
92   s_lmm_element_t elem;
93
94   cnst = xbt_new0(s_lmm_constraint_t, 1);
95   cnst->id = id;
96   xbt_swag_init(&(cnst->element_set),
97                 xbt_swag_offset(elem, element_set_hookup));
98   xbt_swag_init(&(cnst->active_element_set),
99                 xbt_swag_offset(elem, active_element_set_hookup));
100
101   cnst->bound = bound_value;
102   cnst->usage = 0;
103   insert_constraint(sys, cnst);
104
105   return cnst;
106 }
107
108 void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst)
109 {
110   remove_constraint(sys, cnst);
111   lmm_cnst_free(sys, cnst);
112 }
113
114 lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id,
115                                 double weight,
116                                 double bound, int number_of_constraints)
117 {
118   lmm_variable_t var = NULL;
119
120   var = xbt_new0(s_lmm_variable_t, 1);
121   var->id = id;
122   var->cnsts = xbt_new0(s_lmm_element_t, number_of_constraints);
123   var->cnsts_size = number_of_constraints;
124   /* var->cnsts_number = 0; *//* Useless because of the calloc  */
125   var->weight = weight;
126   var->bound = bound;
127   var->value = 0.0;
128   insert_variable(sys, var);
129
130   return var;
131 }
132
133 void lmm_variable_free(lmm_system_t sys, lmm_variable_t var)
134 {
135   remove_variable(sys, var);
136   lmm_var_free(sys, var);
137 }
138
139 double lmm_variable_getvalue(lmm_variable_t var)
140 {
141   return (var->value);
142 }
143
144 void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
145                 lmm_variable_t var, double value)
146 {
147   lmm_element_t elem = NULL;
148
149   sys->modified = 1;
150
151   xbt_assert0(var->cnsts_number >= var->cnsts_size,
152               "Too much constraints");
153
154   elem = &(var->cnsts[var->cnsts_number++]);
155
156   elem->value = value;
157   elem->constraint = cnst;
158   elem->variable = var;
159
160   insert_elem_in_constraint(elem);
161
162   make_constraint_active(sys, cnst);
163 }
164
165 lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys,
166                                        lmm_variable_t var, int num)
167 {
168   if (num < var->cnsts_number)
169     return (var->cnsts[num].constraint);
170   else
171     return NULL;
172 }
173
174 int lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var)
175 {
176   return (var->cnsts_number);
177 }
178
179 lmm_variable_t lmm_get_var_from_cnst(lmm_system_t sys,
180                                      lmm_constraint_t cnst,
181                                      lmm_variable_t * var)
182 {
183   if (!(*var))
184     xbt_swag_getFirst(&(cnst->element_set));
185   else
186     *var = xbt_swag_getNext(*var, cnst->element_set.offset);
187   return *var;
188 }
189
190 void *lmm_constraint_id(lmm_constraint_t cnst)
191 {
192   return cnst->id;
193 }
194
195 void *lmm_variable_id(lmm_variable_t var)
196 {
197   return var->id;
198 }
199
200 static void saturated_constraint_set_update(lmm_system_t sys,
201                                             lmm_constraint_t cnst,
202                                             double *min_usage)
203 {
204   lmm_constraint_t useless_cnst = NULL;
205
206   if (cnst->usage <= 0)
207     return;
208   if (cnst->remaining <= 0)
209     return;
210   if ((*min_usage < 0) || (*min_usage > cnst->remaining / cnst->usage)) {
211     *min_usage = cnst->remaining / cnst->usage;
212
213     while ((useless_cnst =
214             xbt_swag_getFirst(&(sys->saturated_constraint_set))))
215       xbt_swag_remove(useless_cnst, &(sys->saturated_constraint_set));
216
217     xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
218   } else if (*min_usage == cnst->remaining / cnst->usage) {
219     xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
220   }
221 }
222
223 static void saturated_variable_set_update(lmm_system_t sys)
224 {
225   lmm_constraint_t cnst = NULL;
226   xbt_swag_t cnst_list = NULL;
227   lmm_element_t elem = NULL;
228   xbt_swag_t elem_list = NULL;
229
230   cnst_list = &(sys->saturated_constraint_set);
231   while ((cnst = xbt_swag_getFirst(cnst_list))) {
232     elem_list = &(cnst->active_element_set);
233     xbt_swag_foreach(elem, elem_list)
234         if ((elem->value > 0) && (elem->variable->weight > 0))
235       xbt_swag_insert(elem->variable, &(sys->saturated_variable_set));
236     xbt_swag_remove(cnst, cnst_list);
237   }
238
239 }
240
241 void lmm_solve(lmm_system_t sys)
242 {
243   lmm_variable_t var = NULL;
244   lmm_constraint_t cnst = NULL;
245   lmm_element_t elem = NULL;
246   xbt_swag_t cnst_list = NULL;
247   xbt_swag_t var_list = NULL;
248   xbt_swag_t elem_list = NULL;
249   double min_usage = -1;
250
251   if (!(sys->modified))
252     return;
253
254   /* Init */
255   var_list = &(sys->variable_set);
256   xbt_swag_foreach(var, var_list) {
257     var->value = 0.0;
258   }
259
260
261   /* Compute Usage and store the variables that reach the maximum */
262
263   cnst_list = &(sys->active_constraint_set);
264   xbt_swag_foreach(cnst, cnst_list) {
265     /* INIT */
266     elem_list = &(cnst->element_set);
267     cnst->remaining = cnst->bound;
268     cnst->usage = 0;
269     xbt_swag_foreach(elem, elem_list) {
270       if ((elem->value > 0) && (elem->variable->weight > 0)) {
271         cnst->usage += elem->value / elem->variable->weight;
272         insert_active_elem_in_constraint(elem);
273       }
274     }
275
276     /* Saturated constraints update */
277     saturated_constraint_set_update(sys, cnst, &min_usage);
278   }
279
280   saturated_variable_set_update(sys);
281
282   /* Saturated variables update */
283
284   do {
285     /* Fix the variables that have to be */
286     var_list = &(sys->saturated_variable_set);
287
288
289     xbt_swag_foreach(var, var_list) {
290       /* First check if some of these variables have reach their upper
291          bound and update min_usage accordingly. */
292       if ((var->bound > 0) && (var->bound / var->weight < min_usage)) {
293         min_usage = var->bound / var->weight;
294       }
295     }
296
297
298     while ((var = xbt_swag_getFirst(var_list))) {
299       int i;
300
301       var->value = min_usage / var->weight;
302
303       /* Update usage */
304
305       for (i = 0; i < var->cnsts_number; i++) {
306         elem = &var->cnsts[i];
307         cnst = elem->constraint;
308         cnst->remaining -= elem->value * var->value;
309         cnst->usage -= elem->value / var->weight;
310         remove_active_elem_in_constraint(elem);
311       }
312       xbt_swag_remove(var, var_list);
313     }
314
315     /* Find out which variables reach the maximum */
316     cnst_list = &(sys->active_constraint_set);
317     min_usage = -1;
318     xbt_swag_foreach(cnst, cnst_list) {
319       saturated_constraint_set_update(sys, cnst, &min_usage);
320     }
321     saturated_variable_set_update(sys);
322
323   } while (xbt_swag_size(&(sys->saturated_variable_set)));
324
325   sys->modified = 0;
326 }
327
328 /* Not a O(1) function */
329
330 void lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
331                 lmm_variable_t var, double value)
332 {
333   int i;
334
335   sys->modified = 1;
336   for (i = 0; i < var->cnsts_number; i++)
337     if (var->cnsts[i].constraint == cnst) {
338       var->cnsts[i].value = value;
339       return;
340     }
341 }
342
343 void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
344                                double bound)
345 {
346   sys->modified = 1;
347   var->bound = bound;
348 }
349
350 void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var,
351                                 double weight)
352 {
353   sys->modified = 1;
354   var->weight = weight;
355 }
356
357 void lmm_update_constraint_bound(lmm_system_t sys, lmm_constraint_t cnst,
358                                  double bound)
359 {
360   sys->modified = 1;
361   cnst->bound = bound;
362 }
363
364 int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst)
365 {
366   return xbt_swag_belongs(cnst, &(sys->active_constraint_set));
367 }
368
369
370 /* void lmm_print(lmm_system_t sys) */
371 /* { */
372 /*   lmm_variable_t var = NULL; */
373 /*   lmm_constraint_t cnst = NULL; */
374 /*   lmm_element_t elem = NULL; */
375 /*   xbt_swag_t cnst_list = NULL; */
376 /*   xbt_swag_t var_list = NULL; */
377 /*   xbt_swag_t elem_list = NULL; */
378
379 /*   var_list = &(sys->variable_set); */
380 /*   xbt_swag_foreach(var, var_list) { */
381 /*     printf("%s : {\n",var->id); */
382 /*     printf("\t %s : {\n",var->id); */
383 /*   } */
384 /* } */