Logo AND Algorithmique Numérique Distribuée

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