Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
7660fb13778546398b5a95a905239a1b2f4dbf4e
[simgrid.git] / src / surf / maxmin.c
1 /* Authors: Arnaud Legrand                                                  */
2
3 /* This program is free software; you can redistribute it and/or modify it
4    under the terms of the license (GNU LGPL) which comes with this package. */
5
6 #include "xbt/sysdep.h"
7 #include "xbt/error.h"
8 #include "maxmin_private.h"
9 #include <stdlib.h>
10
11 /* extern lmm_system_t Sys; */
12 /* extern lmm_constraint_t L1; */
13 /* extern lmm_constraint_t L2; */
14 /* extern lmm_constraint_t L3; */
15
16 /* extern lmm_variable_t R_1_2_3; */
17 /* extern lmm_variable_t R_1; */
18 /* extern lmm_variable_t R_2; */
19 /* extern lmm_variable_t R_3; */
20
21
22 lmm_system_t lmm_system_new(void)
23 {
24   lmm_system_t l = NULL;
25   s_lmm_variable_t var;
26   s_lmm_constraint_t cnst;
27
28   l = xbt_new0(s_lmm_system_t, 1);
29
30   xbt_swag_init(&(l->variable_set),
31                 xbt_swag_offset(var, variable_set_hookup));
32   xbt_swag_init(&(l->constraint_set),
33                 xbt_swag_offset(cnst, constraint_set_hookup));
34
35   xbt_swag_init(&(l->active_constraint_set),
36                 xbt_swag_offset(cnst, active_constraint_set_hookup));
37
38   xbt_swag_init(&(l->saturated_variable_set),
39                 xbt_swag_offset(var, saturated_variable_set_hookup));
40   xbt_swag_init(&(l->saturated_constraint_set),
41                 xbt_swag_offset(cnst, saturated_constraint_set_hookup));
42
43   return l;
44 }
45
46 void lmm_system_free(lmm_system_t sys)
47 {
48   lmm_variable_t var = NULL;
49   lmm_constraint_t cnst = NULL;
50
51   while ((var = extract_variable(sys)))
52     lmm_var_free(sys, var);
53
54   while ((cnst = extract_constraint(sys)))
55     lmm_cnst_free(sys, cnst);
56
57   xbt_free(sys);
58 }
59
60 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var)
61 {
62   int i;
63   lmm_element_t elem = NULL;
64
65   for (i = 0; i < var->cnsts_number; i++) {
66     elem = &var->cnsts[i];
67     xbt_swag_extract(elem, &(elem->constraint->element_set));
68     if (xbt_swag_size(&(elem->constraint->element_set)))
69       make_constraint_inactive(sys, elem->constraint);
70   }
71   xbt_free(var->cnsts);
72   xbt_free(var);
73 }
74
75 static void lmm_cnst_free(lmm_system_t sys, lmm_constraint_t cnst)
76 {
77 /*   xbt_assert0(xbt_fifo_size(&(cnst->row)), */
78 /*               "This list should be empty!"); */
79   remove_active_constraint(sys, cnst);
80   xbt_free(cnst);
81 }
82
83 lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id,
84                                     xbt_maxmin_float_t bound_value)
85 {
86   lmm_constraint_t cnst = NULL;
87   s_lmm_element_t elem;
88
89   cnst = xbt_new0(s_lmm_constraint_t, 1);
90 /*   cnst->id = id; */
91   xbt_swag_init(&(cnst->element_set),
92                 xbt_swag_offset(elem, element_set_hookup));
93   xbt_swag_init(&(cnst->active_element_set),
94                 xbt_swag_offset(elem, active_element_set_hookup));
95
96   cnst->bound = bound_value;
97   cnst->usage = 0;
98   insert_constraint(sys, cnst);
99
100   cnst->id = id;
101
102   return cnst;
103 }
104
105 void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst)
106 {
107   remove_constraint(sys, cnst);
108   lmm_cnst_free(sys, cnst);
109 }
110
111 lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id,
112                                 xbt_maxmin_float_t weight,
113                                 xbt_maxmin_float_t bound,
114                                 int number_of_constraints)
115 {
116   lmm_variable_t var = NULL;
117
118   var = xbt_new0(s_lmm_variable_t, 1);
119 /*   var->id = id; */
120   var->cnsts = xbt_new0(s_lmm_element_t, number_of_constraints);
121   var->cnsts_size = number_of_constraints;
122   /* var->cnsts_number = 0; *//* Useless because of the calloc  */
123   var->weight = weight;
124   var->bound = bound;
125   var->value = -1;
126   insert_variable(sys, var);
127
128   var->id = id;
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 xbt_maxmin_float_t 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, xbt_maxmin_float_t value)
146 {
147   lmm_element_t elem = NULL;
148
149   if (var->cnsts_number >= var->cnsts_size)
150     abort();
151
152   elem = &(var->cnsts[var->cnsts_number++]);
153
154   elem->value = value;
155   elem->constraint = cnst;
156   elem->variable = var;
157
158   insert_elem_in_constraint(elem);
159
160   make_constraint_active(sys, cnst);
161 }
162
163 static void saturated_constraints_update(lmm_system_t sys,
164                                          lmm_constraint_t cnst,
165                                          xbt_maxmin_float_t * min_usage)
166 {
167   lmm_constraint_t useless_cnst = NULL;
168
169   if (cnst->remaining <= 0)
170     return;
171   if ((*min_usage < 0) || (*min_usage > cnst->remaining / cnst->usage)) {
172     xbt_swag_t active_elem_list = &(cnst->active_element_set);
173
174     *min_usage = cnst->remaining / cnst->usage;
175
176     while (xbt_swag_extract
177            (useless_cnst, &(sys->saturated_constraint_set))) {
178     }
179     xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
180   } else if (*min_usage == cnst->remaining / cnst->usage) {
181     xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
182   }
183 }
184
185 static void saturated_variables_update(lmm_system_t sys)
186 {
187   lmm_constraint_t cnst = NULL;
188   xbt_swag_t cnst_list = NULL;
189   lmm_element_t elem = NULL;
190   xbt_swag_t elem_list = NULL;
191
192   cnst_list = &(sys->saturated_constraint_set);
193   while ((cnst = xbt_swag_getFirst(cnst_list))) {
194 /*   xbt_swag_foreach(cnst, cnst_list) { */
195     elem_list = &(cnst->active_element_set);
196     xbt_swag_foreach(elem, elem_list)
197         xbt_swag_insert(elem->variable, &(sys->saturated_variable_set));
198     xbt_swag_extract(cnst, cnst_list);
199   }
200
201 }
202
203 void lmm_solve(lmm_system_t sys)
204 {
205   lmm_variable_t var = NULL;
206   lmm_constraint_t cnst = NULL;
207   lmm_element_t elem = NULL;
208   xbt_swag_t cnst_list = NULL;
209   xbt_swag_t var_list = NULL;
210   xbt_swag_t elem_list = NULL;
211   xbt_maxmin_float_t min_usage = -1;
212
213   /* Init */
214   var_list = &(sys->variable_set);
215   xbt_swag_foreach(var, var_list) {
216     var->value = -1;
217   }
218
219
220   /* Compute Usage and store the variables that reach the maximum */
221
222   cnst_list = &(sys->active_constraint_set);
223   xbt_swag_foreach(cnst, cnst_list) {
224     /* INIT */
225     elem_list = &(cnst->element_set);
226     cnst->remaining = cnst->bound;
227     cnst->usage = 0;
228     xbt_swag_foreach(elem, elem_list) {
229       cnst->usage += elem->value / elem->variable->weight;
230       insert_active_elem_in_constraint(elem);
231     }
232
233     /* Saturated constraints update */
234     saturated_constraints_update(sys, cnst, &min_usage);
235   }
236
237   saturated_variables_update(sys);
238
239   /* Saturated variables update */
240
241   do {
242     /* Fix the variables that have to be */
243     var_list = &(sys->saturated_variable_set);
244
245
246     xbt_swag_foreach(var, var_list) {
247       /* First check if some of these variables have reach their upper
248          bound and update min_usage accordingly. */
249       if ((var->bound > 0) && (var->bound / var->weight < min_usage)) {
250         min_usage = var->bound / var->weight;
251       }
252     }
253
254
255     while ((var = xbt_swag_getFirst(var_list))) {
256       int i;
257
258       var->value = min_usage / var->weight;
259
260       /* Update usage */
261
262       for (i = 0; i < var->cnsts_number; i++) {
263         elem = &var->cnsts[i];
264         cnst = elem->constraint;
265         cnst->remaining -= elem->value * var->value;
266         cnst->usage -= elem->value / var->weight;
267         remove_active_elem_in_constraint(elem);
268       }
269       xbt_swag_extract(var, var_list);
270     }
271
272     /* Find out which variables reach the maximum */
273     cnst_list = &(sys->active_constraint_set);
274     min_usage = -1;
275     xbt_swag_foreach(cnst, cnst_list) {
276       saturated_constraints_update(sys, cnst, &min_usage);
277     }
278     saturated_variables_update(sys);
279
280   } while (xbt_swag_size(&(sys->saturated_variable_set)));
281 }
282
283 /* Not a O(1) function */
284
285 void lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
286                 lmm_variable_t var, xbt_maxmin_float_t value)
287 {
288   int i;
289   lmm_element_t elem = NULL;
290
291   for (i = 0; i < var->cnsts_number; i++)
292     if (var->cnsts[i].constraint == cnst) {
293       elem->value = value;
294       return;
295     }
296 }
297
298 void lmm_update_variable_bound(lmm_variable_t var,
299                                xbt_maxmin_float_t bound)
300 {
301   var->bound = bound;
302 }
303
304 void lmm_update_variable_weight(lmm_variable_t var,
305                                 xbt_maxmin_float_t weight)
306 {
307   var->weight = weight;
308 }
309
310 void lmm_update_constraint_bound(lmm_constraint_t cnst,
311                                  xbt_maxmin_float_t bound)
312 {
313   cnst->bound = bound;
314 }
315
316
317
318 /* void lmm_print(lmm_system_t sys) */
319 /* { */
320 /*   lmm_variable_t var = NULL; */
321 /*   lmm_constraint_t cnst = NULL; */
322 /*   lmm_element_t elem = NULL; */
323 /*   xbt_swag_t cnst_list = NULL; */
324 /*   xbt_swag_t var_list = NULL; */
325 /*   xbt_swag_t elem_list = NULL; */
326
327 /*   var_list = &(sys->variable_set); */
328 /*   xbt_swag_foreach(var, var_list) { */
329 /*     printf("%s : {\n",var->id); */
330 /*     printf("\t %s : {\n",var->id); */
331 /*   } */
332 /* } */