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_remove(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   return cnst;
 101 }
 102
 103 void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst)
 104 {
 105   remove_constraint(sys, cnst);
 106   lmm_cnst_free(sys, cnst);
 107 }
 108
 109 lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id,
 110                                 xbt_maxmin_float_t weight,
 111                                 xbt_maxmin_float_t bound,
 112                                 int number_of_constraints)
 113 {
 114   lmm_variable_t var = NULL;
 115
 116   var = xbt_new0(s_lmm_variable_t, 1);
 117   var->id = id;
 118   var->cnsts = xbt_new0(s_lmm_element_t, number_of_constraints);
 119   var->cnsts_size = number_of_constraints;
 120   /* var->cnsts_number = 0; *//* Useless because of the calloc  */
 121   var->weight = weight;
 122   var->bound = bound;
 123   var->value = -1;
 124   insert_variable(sys, var);
 125
 126   return var;
 127 }
 128
 129 void lmm_variable_free(lmm_system_t sys, lmm_variable_t var)
 130 {
 131   remove_variable(sys, var);
 132   lmm_var_free(sys, var);
 133 }
 134
 135 xbt_maxmin_float_t lmm_variable_getvalue(lmm_variable_t var)
 136 {
 137   return (var->value);
 138 }
 139
 140 void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
 141                 lmm_variable_t var, xbt_maxmin_float_t value)
 142 {
 143   lmm_element_t elem = NULL;
 144
 145   if (var->cnsts_number >= var->cnsts_size)
 146     abort();
 147
 148   elem = &(var->cnsts[var->cnsts_number++]);
 149
 150   elem->value = value;
 151   elem->constraint = cnst;
 152   elem->variable = var;
 153
 154   insert_elem_in_constraint(elem);
 155
 156   make_constraint_active(sys, cnst);
 157 }
 158
 159 static void saturated_constraints_update(lmm_system_t sys,
 160                                          lmm_constraint_t cnst,
 161                                          xbt_maxmin_float_t * min_usage)
 162 {
 163   lmm_constraint_t useless_cnst = NULL;
 164
 165   if (cnst->remaining <= 0)
 166     return;
 167   if ((*min_usage < 0) || (*min_usage > cnst->remaining / cnst->usage)) {
 168     xbt_swag_t active_elem_list = &(cnst->active_element_set);
 169
 170     *min_usage = cnst->remaining / cnst->usage;
 171
 172     while ((useless_cnst = xbt_swag_getFirst(&(sys->saturated_constraint_set))))
 173       xbt_swag_remove(useless_cnst, &(sys->saturated_constraint_set));
 174
 175     xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
 176   } else if (*min_usage == cnst->remaining / cnst->usage) {
 177     xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
 178   }
 179 }
 180
 181 static void saturated_variables_update(lmm_system_t sys)
 182 {
 183   lmm_constraint_t cnst = NULL;
 184   xbt_swag_t cnst_list = NULL;
 185   lmm_element_t elem = NULL;
 186   xbt_swag_t elem_list = NULL;
 187
 188   cnst_list = &(sys->saturated_constraint_set);
 189   while ((cnst = xbt_swag_getFirst(cnst_list))) {
 190 /*   xbt_swag_foreach(cnst, cnst_list) { */
 191     elem_list = &(cnst->active_element_set);
 192     xbt_swag_foreach(elem, elem_list)
 193         xbt_swag_insert(elem->variable, &(sys->saturated_variable_set));
 194     xbt_swag_remove(cnst, cnst_list);
 195   }
 196
 197 }
 198
 199 void lmm_solve(lmm_system_t sys)
 200 {
 201   lmm_variable_t var = NULL;
 202   lmm_constraint_t cnst = NULL;
 203   lmm_element_t elem = NULL;
 204   xbt_swag_t cnst_list = NULL;
 205   xbt_swag_t var_list = NULL;
 206   xbt_swag_t elem_list = NULL;
 207   xbt_maxmin_float_t min_usage = -1;
 208
 209   /* Init */
 210   var_list = &(sys->variable_set);
 211   xbt_swag_foreach(var, var_list) {
 212     var->value = -1;
 213   }
 214
 215
 216   /* Compute Usage and store the variables that reach the maximum */
 217
 218   cnst_list = &(sys->active_constraint_set);
 219   xbt_swag_foreach(cnst, cnst_list) {
 220     /* INIT */
 221     elem_list = &(cnst->element_set);
 222     cnst->remaining = cnst->bound;
 223     cnst->usage = 0;
 224     xbt_swag_foreach(elem, elem_list) {
 225       cnst->usage += elem->value / elem->variable->weight;
 226       insert_active_elem_in_constraint(elem);
 227     }
 228
 229     /* Saturated constraints update */
 230     saturated_constraints_update(sys, cnst, &min_usage);
 231   }
 232
 233   saturated_variables_update(sys);
 234
 235   /* Saturated variables update */
 236
 237   do {
 238     /* Fix the variables that have to be */
 239     var_list = &(sys->saturated_variable_set);
 240
 241
 242     xbt_swag_foreach(var, var_list) {
 243       /* First check if some of these variables have reach their upper
 244          bound and update min_usage accordingly. */
 245       if ((var->bound > 0) && (var->bound / var->weight < min_usage)) {
 246         min_usage = var->bound / var->weight;
 247       }
 248     }
 249
 250
 251     while ((var = xbt_swag_getFirst(var_list))) {
 252       int i;
 253
 254       var->value = min_usage / var->weight;
 255
 256       /* Update usage */
 257
 258       for (i = 0; i < var->cnsts_number; i++) {
 259         elem = &var->cnsts[i];
 260         cnst = elem->constraint;
 261         cnst->remaining -= elem->value * var->value;
 262         cnst->usage -= elem->value / var->weight;
 263         remove_active_elem_in_constraint(elem);
 264       }
 265       xbt_swag_remove(var, var_list);
 266     }
 267
 268     /* Find out which variables reach the maximum */
 269     cnst_list = &(sys->active_constraint_set);
 270     min_usage = -1;
 271     xbt_swag_foreach(cnst, cnst_list) {
 272       saturated_constraints_update(sys, cnst, &min_usage);
 273     }
 274     saturated_variables_update(sys);
 275
 276   } while (xbt_swag_size(&(sys->saturated_variable_set)));
 277 }
 278
 279 /* Not a O(1) function */
 280
 281 void lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
 282                 lmm_variable_t var, xbt_maxmin_float_t value)
 283 {
 284   int i;
 285   lmm_element_t elem = NULL;
 286
 287   for (i = 0; i < var->cnsts_number; i++)
 288     if (var->cnsts[i].constraint == cnst) {
 289       elem->value = value;
 290       return;
 291     }
 292 }
 293
 294 void lmm_update_variable_bound(lmm_variable_t var,
 295                                xbt_maxmin_float_t bound)
 296 {
 297   var->bound = bound;
 298 }
 299
 300 void lmm_update_variable_weight(lmm_variable_t var,
 301                                 xbt_maxmin_float_t weight)
 302 {
 303   var->weight = weight;
 304 }
 305
 306 void lmm_update_constraint_bound(lmm_constraint_t cnst,
 307                                  xbt_maxmin_float_t bound)
 308 {
 309   cnst->bound = bound;
 310 }
 311
 312 int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst)
 313 {
 314   return xbt_swag_belongs(cnst,&(sys->active_constraint_set));
 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 /* } */