src/surf/cpu_ti.c

   1
   2 /*      $Id$     */
   3
   4 /* Copyright (c) 2004 Arnaud Legrand. All rights reserved.                  */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #include "surf_private.h"
  10 #include "trace_mgr_private.h"
  11 #include "cpu_ti_private.h"
  12 #include "xbt/heap.h"
  13
  14
  15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_cpu_ti, surf,
  16                                 "Logging specific to the SURF CPU TRACE INTEGRATION module");
  17
  18
  19 static xbt_swag_t running_action_set_that_does_not_need_being_checked = NULL;
  20 static xbt_swag_t modified_cpu = NULL;
  21 static xbt_heap_t action_heap;
  22
  23 /* prototypes of new trace functions */
  24 static double surf_cpu_integrate_trace(surf_cpu_ti_tgmr_t trace, double a,
  25                                        double b);
  26 static double surf_cpu_integrate_trace_simple(surf_cpu_ti_tgmr_t trace,
  27                                               double a, double b);
  28
  29
  30 static double surf_cpu_solve_trace(surf_cpu_ti_tgmr_t trace, double a,
  31                                    double amount);
  32 static double surf_cpu_solve_trace_somewhat_simple(surf_cpu_ti_tgmr_t trace,
  33                                                    double a, double amount);
  34 static double surf_cpu_solve_trace_simple(surf_cpu_ti_tgmr_t trace, double a,
  35                                           double amount);
  36
  37 static void surf_cpu_free_trace(surf_cpu_ti_tgmr_t trace);
  38 static void surf_cpu_free_time_series(surf_cpu_ti_timeSeries_t timeSeries);
  39 static double surf_cpu_integrate_exactly(surf_cpu_ti_tgmr_t trace, int index,
  40                                          double a, double b);
  41 static double surf_cpu_solve_exactly(surf_cpu_ti_tgmr_t trace, int index,
  42                                      double a, double amount);
  43 /* end prototypes */
  44
  45 static void surf_cpu_free_time_series(surf_cpu_ti_timeSeries_t timeSeries)
  46 {
  47   xbt_free(timeSeries->values);
  48   xbt_free(timeSeries->trace_index);
  49   xbt_free(timeSeries->trace_value);
  50   xbt_free(timeSeries);
  51 }
  52
  53 static void surf_cpu_free_trace(surf_cpu_ti_tgmr_t trace)
  54 {
  55   int i;
  56
  57   for (i = 0; i < trace->nb_levels; i++)
  58     surf_cpu_free_time_series(trace->levels[i]);
  59
  60   xbt_free(trace->levels);
  61   xbt_free(trace);
  62 }
  63
  64 static surf_cpu_ti_timeSeries_t surf_cpu_ti_time_series_new(tmgr_trace_t
  65                                                             power_trace,
  66                                                             double spacing,
  67                                                             double total_time)
  68 {
  69   surf_cpu_ti_timeSeries_t series;
  70   double time = 0.0, value = 0.0, sum_delta = 0.0;
  71   double previous_time = 0.0, old_time = 0.0;
  72   int event_lost = 0, next_index = 0;
  73   double next_time = 0.0;
  74   int total_alloc = 0;
  75   s_tmgr_event_t val;
  76   unsigned int cpt;
  77
  78   series = xbt_new0(s_surf_cpu_ti_timeSeries_t, 1);
  79   series->spacing = spacing;
  80   series->power_trace = power_trace;
  81
  82   /* alloc memory only once, it's faster than doing realloc each time */
  83   total_alloc = (int) ceil((total_time / spacing));
  84   series->values = xbt_malloc0(sizeof(double) * total_alloc);
  85   series->trace_index = xbt_malloc0(sizeof(int) * total_alloc);
  86   series->trace_value = xbt_malloc0(sizeof(double) * total_alloc);
  87
  88 /* FIXME: it doesn't work with traces with only one point and periodicity = 0
  89  * if the trace is always cyclic and periodicity must be > 0 it works */
  90   xbt_dynar_foreach(power_trace->event_list, cpt, val) {
  91     /* delta = the next trace event
  92      * value = state until next event */
  93     time += val.delta;
  94
  95     /* ignore events until next spacing */
  96     if (time < (series->nb_points + 1) * spacing) {
  97       value += val.value * val.delta;
  98       sum_delta += val.delta;
  99       old_time = time;
 100       event_lost = 1;
 101       continue;
 102     }
 103
 104     /* update value and sum_delta with the space between last point in trace(old_time) and next spacing */
 105     value += val.value * ((series->nb_points + 1) * spacing - old_time);
 106     sum_delta += ((series->nb_points + 1) * spacing - old_time);
 107     /* calcule the value to next spacing */
 108     value /= sum_delta;
 109
 110     while (previous_time + spacing <= time) {
 111       /* update first spacing with mean of points.
 112        * others with the right value */
 113       if (event_lost) {
 114         series->values[series->nb_points] = value;
 115         series->trace_index[series->nb_points] = next_index;
 116         series->trace_value[series->nb_points] = next_time;
 117         event_lost = 0;
 118       } else {
 119         series->trace_index[series->nb_points] = -1;
 120         series->values[series->nb_points] = val.value;
 121       }
 122       (series->nb_points)++;
 123       previous_time += spacing;
 124     }
 125     /* update value and sum_delta, interval: [time, next spacing] */
 126     value = (time - previous_time) * val.value;
 127     sum_delta = (time - previous_time);
 128     old_time = time;
 129     next_index = (int) cpt + 1;
 130     next_time = time;
 131     event_lost = 1;
 132   }
 133   /* last spacing
 134    * ignore small amount at end */
 135   double_update(&time, (series->nb_points) * spacing);
 136   if (time > 0) {
 137     /* here the value is divided by spacing in order to have exactly the value of last chunk (independently of its size). After, when we calcule the integral, we multiply by actual_last_time insted of last_time */
 138     value /= spacing;
 139     series->values[series->nb_points] = value;
 140     /* update first spacing with mean of points
 141      * others with the right value */
 142     if (event_lost) {
 143       series->trace_index[series->nb_points] = next_index;
 144       series->trace_value[series->nb_points] = next_time;
 145     } else
 146       series->trace_index[series->nb_points] = -1;
 147     (series->nb_points)++;
 148   }
 149   return series;
 150 }
 151
 152 /**
 153 * \brief Create new levels of points.
 154 *
 155 * This function assumes that the input series is
 156 * evenly spaces, starting at time 0. That is the sort
 157 * of series produced by surf_cpu_ti_time_series_new()
 158 *
 159 * \param        original        Original timeSeries structure
 160 * \param        factor          New factor to spacing
 161 * \return                                       New timeSeries structure with spacing*factor
 162 */
 163 static surf_cpu_ti_timeSeries_t
 164 surf_cpu_ti_time_series_coarsen(surf_cpu_ti_timeSeries_t original, int factor)
 165 {
 166   surf_cpu_ti_timeSeries_t series;
 167   int j, i = 0;
 168   double dfactor = (double) (factor);
 169   double ave;
 170
 171   if (original->nb_points <= factor) {
 172     DEBUG0("Warning: Not enough data points to coarsen time series");
 173     return NULL;
 174   }
 175
 176   series = xbt_new0(s_surf_cpu_ti_timeSeries_t, 1);
 177   series->spacing = (original->spacing) * dfactor;
 178
 179   while (i + factor <= original->nb_points) {
 180     /* Averaging */
 181     ave = 0.0;
 182     for (j = i; j < i + factor; j++) {
 183       ave += original->values[j];
 184     }
 185     ave /= dfactor;
 186     /* Updating */
 187     series->values = xbt_realloc(series->values,
 188                                  (series->nb_points + 1) * sizeof(double));
 189     series->values[(series->nb_points)++] = ave;
 190     i += factor;
 191   }
 192
 193   return series;
 194 }
 195
 196 /**
 197 * \brief Create a new integration trace from a tmgr_trace_t
 198 *
 199 * \param        power_trace             CPU availability trace
 200 * \param        value                                   Percentage of CPU power disponible (usefull to fixed tracing)
 201 * \param        spacing                         Initial spacing
 202 * \return       Integration trace structure
 203 */
 204 static surf_cpu_ti_tgmr_t cpu_ti_parse_trace(tmgr_trace_t power_trace,
 205                                              double value)
 206 {
 207   surf_cpu_ti_tgmr_t trace;
 208   surf_cpu_ti_timeSeries_t series;
 209   int i;
 210   double total_time = 0.0;
 211   s_tmgr_event_t val;
 212   unsigned int cpt;
 213   trace = xbt_new0(s_surf_cpu_ti_tgmr_t, 1);
 214
 215 /* no availability file, fixed trace */
 216   if (!power_trace) {
 217     trace->type = TRACE_FIXED;
 218     trace->value = value;
 219     DEBUG1("No availabily trace. Constant value = %lf", value);
 220     return trace;
 221   }
 222
 223   /* only one point available, fixed trace */
 224   if (xbt_dynar_length(power_trace->event_list) == 1) {
 225     xbt_dynar_get_cpy(power_trace->event_list, 0, &val);
 226     trace->type = TRACE_FIXED;
 227     trace->value = val.value;
 228     return trace;
 229   }
 230
 231   /* count the total time of trace file */
 232   xbt_dynar_foreach(power_trace->event_list, cpt, val) {
 233     total_time += val.delta;
 234   }
 235   trace->actual_last_time = total_time;
 236
 237   DEBUG2("Value %lf, Spacing %lf", value, power_trace->timestep);
 238   series =
 239     surf_cpu_ti_time_series_new(power_trace, power_trace->timestep,
 240                                 total_time);
 241   if (!series)
 242     return NULL;
 243
 244   trace->type = TRACE_DYNAMIC;
 245
 246   trace->levels = xbt_new0(surf_cpu_ti_timeSeries_t, 1);
 247   trace->levels[(trace->nb_levels)++] = series;
 248
 249 /* Do the coarsening with some arbitrary factors */
 250   for (i = 1; i < TRACE_NB_LEVELS; i++) {
 251     series = surf_cpu_ti_time_series_coarsen(trace->levels[i - 1], 4 * i);
 252
 253     if (series) {               /* If coarsening was possible, add it */
 254       trace->levels = xbt_realloc(trace->levels,
 255                                   (trace->nb_levels +
 256                                    1) * sizeof(s_surf_cpu_ti_timeSeries_t));
 257       trace->levels[(trace->nb_levels)++] = series;
 258     } else {                    /* otherwise stop */
 259       break;
 260     }
 261   }
 262 /* calcul of initial integrate */
 263   trace->last_time =
 264     power_trace->timestep * ((double) (trace->levels[0]->nb_points));
 265
 266   trace->total =
 267     surf_cpu_integrate_trace(trace, 0.0, trace->actual_last_time);
 268
 269   DEBUG3("Total integral %lf, last_time %lf actual_last_time %lf",
 270          trace->total, trace->last_time, trace->actual_last_time);
 271
 272   return trace;
 273 }
 274
 275
 276 static cpu_ti_t cpu_new(char *name, double power_peak,
 277                         double power_scale,
 278                         tmgr_trace_t power_trace,
 279                         e_surf_resource_state_t state_initial,
 280                         tmgr_trace_t state_trace, xbt_dict_t cpu_properties)
 281 {
 282   tmgr_trace_t empty_trace;
 283   s_tmgr_event_t val;
 284   cpu_ti_t cpu = xbt_new0(s_cpu_ti_t, 1);
 285   s_surf_action_cpu_ti_t ti_action;
 286   xbt_assert1(!surf_model_resource_by_name(surf_cpu_model, name),
 287               "Host '%s' declared several times in the platform file", name);
 288   cpu->action_set = xbt_swag_new(xbt_swag_offset(ti_action, cpu_list_hookup));
 289   cpu->generic_resource.model = surf_cpu_model;
 290   cpu->generic_resource.name = name;
 291   cpu->generic_resource.properties = cpu_properties;
 292   cpu->power_peak = power_peak;
 293   xbt_assert0(cpu->power_peak > 0, "Power has to be >0");
 294   DEBUG1("power scale %lf", power_scale);
 295   cpu->power_scale = power_scale;
 296   cpu->avail_trace = cpu_ti_parse_trace(power_trace, power_scale);
 297   cpu->state_current = state_initial;
 298   if (state_trace)
 299     cpu->state_event =
 300       tmgr_history_add_trace(history, state_trace, 0.0, 0, cpu);
 301   if (power_trace && xbt_dynar_length(power_trace->event_list) > 1) {
 302     /* add a fake trace event if periodicity == 0 */
 303     xbt_dynar_get_cpy(power_trace->event_list,
 304                       xbt_dynar_length(power_trace->event_list) - 1, &val);
 305     if (val.delta == 0) {
 306       empty_trace = tmgr_empty_trace_new();
 307       cpu->power_event =
 308         tmgr_history_add_trace(history, empty_trace,
 309                                cpu->avail_trace->actual_last_time, 0, cpu);
 310     }
 311   }
 312   xbt_dict_set(surf_model_resource_set(surf_cpu_model), name, cpu,
 313                surf_resource_free);
 314
 315   return cpu;
 316 }
 317
 318
 319 static void parse_cpu_init(void)
 320 {
 321   double power_peak = 0.0;
 322   double power_scale = 0.0;
 323   tmgr_trace_t power_trace = NULL;
 324   e_surf_resource_state_t state_initial = SURF_RESOURCE_OFF;
 325   tmgr_trace_t state_trace = NULL;
 326
 327   power_peak = get_cpu_power(A_surfxml_host_power);
 328   surf_parse_get_double(&power_scale, A_surfxml_host_availability);
 329   power_trace = tmgr_trace_new(A_surfxml_host_availability_file);
 330
 331   xbt_assert0((A_surfxml_host_state == A_surfxml_host_state_ON) ||
 332               (A_surfxml_host_state == A_surfxml_host_state_OFF),
 333               "Invalid state");
 334   if (A_surfxml_host_state == A_surfxml_host_state_ON)
 335     state_initial = SURF_RESOURCE_ON;
 336   if (A_surfxml_host_state == A_surfxml_host_state_OFF)
 337     state_initial = SURF_RESOURCE_OFF;
 338   state_trace = tmgr_trace_new(A_surfxml_host_state_file);
 339
 340   current_property_set = xbt_dict_new();
 341   cpu_new(xbt_strdup(A_surfxml_host_id), power_peak, power_scale,
 342           power_trace, state_initial, state_trace, current_property_set);
 343
 344 }
 345
 346 static void add_traces_cpu(void)
 347 {
 348   xbt_dict_cursor_t cursor = NULL;
 349   char *trace_name, *elm;
 350
 351   static int called = 0;
 352
 353   if (called)
 354     return;
 355   called = 1;
 356
 357 /* connect all traces relative to hosts */
 358   xbt_dict_foreach(trace_connect_list_host_avail, cursor, trace_name, elm) {
 359     tmgr_trace_t trace = xbt_dict_get_or_null(traces_set_list, trace_name);
 360     cpu_ti_t cpu = surf_model_resource_by_name(surf_cpu_model, elm);
 361
 362     xbt_assert1(cpu, "Host %s undefined", elm);
 363     xbt_assert1(trace, "Trace %s undefined", trace_name);
 364
 365     if (cpu->state_event) {
 366       DEBUG1("Trace already configured for this CPU(%s), ignoring it", elm);
 367       continue;
 368     }
 369     DEBUG2("Add state trace: %s to CPU(%s)", trace_name, elm);
 370     cpu->state_event = tmgr_history_add_trace(history, trace, 0.0, 0, cpu);
 371   }
 372
 373   xbt_dict_foreach(trace_connect_list_power, cursor, trace_name, elm) {
 374     tmgr_trace_t trace = xbt_dict_get_or_null(traces_set_list, trace_name);
 375     cpu_ti_t cpu = surf_model_resource_by_name(surf_cpu_model, elm);
 376
 377     xbt_assert1(cpu, "Host %s undefined", elm);
 378     xbt_assert1(trace, "Trace %s undefined", trace_name);
 379
 380     DEBUG2("Add power trace: %s to CPU(%s)", trace_name, elm);
 381     if (cpu->avail_trace)
 382       surf_cpu_free_trace(cpu->avail_trace);
 383
 384     cpu->avail_trace = cpu_ti_parse_trace(trace, cpu->power_scale);
 385   }
 386 }
 387
 388 static void define_callbacks(const char *file)
 389 {
 390   surf_parse_reset_parser();
 391   surfxml_add_callback(STag_surfxml_host_cb_list, parse_cpu_init);
 392   surfxml_add_callback(ETag_surfxml_platform_cb_list, &add_traces_cpu);
 393 }
 394
 395 static int resource_used(void *resource_id)
 396 {
 397   cpu_ti_t cpu = resource_id;
 398   return xbt_swag_size(cpu->action_set);
 399 }
 400
 401 static int action_unref(surf_action_t action)
 402 {
 403   action->refcount--;
 404   if (!action->refcount) {
 405     xbt_swag_remove(action, action->state_set);
 406     /* remove from action_set */
 407     xbt_swag_remove(action, ACTION_GET_CPU(action)->action_set);
 408     /* remove from heap */
 409     xbt_heap_remove(action_heap, ((surf_action_cpu_ti_t) action)->index_heap);
 410     xbt_swag_insert(ACTION_GET_CPU(action), modified_cpu);
 411     free(action);
 412     return 1;
 413   }
 414   return 0;
 415 }
 416
 417 static void action_cancel(surf_action_t action)
 418 {
 419   surf_action_state_set(action, SURF_ACTION_FAILED);
 420   xbt_heap_remove(action_heap, ((surf_action_cpu_ti_t) action)->index_heap);
 421   xbt_swag_insert(ACTION_GET_CPU(action), modified_cpu);
 422   return;
 423 }
 424
 425 static void cpu_action_state_set(surf_action_t action,
 426                                  e_surf_action_state_t state)
 427 {
 428   surf_action_state_set(action, state);
 429   xbt_swag_insert(ACTION_GET_CPU(action), modified_cpu);
 430   return;
 431 }
 432
 433 /**
 434 * \brief Update the remaning amount of actions
 435 *
 436 * \param        cpu             Cpu on which the actions are running
 437 * \param        now             Current time
 438 */
 439 static void cpu_update_remaining_amount(cpu_ti_t cpu, double now)
 440 {
 441 #define GENERIC_ACTION(action) action->generic_action
 442   double area_total;
 443   surf_action_cpu_ti_t action;
 444
 445 /* already updated */
 446   if (cpu->last_update >= now)
 447     return;
 448
 449 /* calcule the surface */
 450   area_total =
 451     surf_cpu_integrate_trace(cpu->avail_trace, cpu->last_update,
 452                              now) * cpu->power_peak;
 453   DEBUG2("Flops total: %lf, Last update %lf", area_total, cpu->last_update);
 454
 455   xbt_swag_foreach(action, cpu->action_set) {
 456     /* action not running, skip it */
 457     if (GENERIC_ACTION(action).state_set !=
 458         surf_cpu_model->states.running_action_set)
 459       continue;
 460
 461     /* bogus priority, skip it */
 462     if (GENERIC_ACTION(action).priority <= 0)
 463       continue;
 464
 465     /* action suspended, skip it */
 466     if (action->suspended != 0)
 467       continue;
 468
 469     /* action don't need update */
 470     if (GENERIC_ACTION(action).start >= now)
 471       continue;
 472
 473     /* skip action that are finishing now */
 474     if (GENERIC_ACTION(action).finish >= 0
 475         && GENERIC_ACTION(action).finish <= now)
 476       continue;
 477
 478     /* update remaining */
 479     double_update(&(GENERIC_ACTION(action).remains),
 480                   area_total / (cpu->sum_priority *
 481                                 GENERIC_ACTION(action).priority));
 482     DEBUG2("Update remaining action(%p) remaining %lf", action,
 483            GENERIC_ACTION(action).remains);
 484   }
 485   cpu->last_update = now;
 486 #undef GENERIC_ACTION
 487 }
 488
 489 /**
 490 * \brief Update the finish date of action if necessary
 491 *
 492 * \param        cpu             Cpu on which the actions are running
 493 * \param        now             Current time
 494 */
 495 static void cpu_update_action_finish_date(cpu_ti_t cpu, double now)
 496 {
 497 #define GENERIC_ACTION(action) action->generic_action
 498   surf_action_cpu_ti_t action;
 499   double sum_priority = 0.0, total_area, min_finish = -1;
 500
 501 /* update remaning amount of actions */
 502   cpu_update_remaining_amount(cpu, now);
 503
 504   xbt_swag_foreach(action, cpu->action_set) {
 505     /* action not running, skip it */
 506     if (GENERIC_ACTION(action).state_set !=
 507         surf_cpu_model->states.running_action_set)
 508       continue;
 509
 510     /* bogus priority, skip it */
 511     if (GENERIC_ACTION(action).priority <= 0)
 512       continue;
 513
 514     /* action suspended, skip it */
 515     if (action->suspended != 0)
 516       continue;
 517
 518     sum_priority += 1.0 / GENERIC_ACTION(action).priority;
 519   }
 520   cpu->sum_priority = sum_priority;
 521
 522   xbt_swag_foreach(action, cpu->action_set) {
 523     /* action not running, skip it */
 524     if (GENERIC_ACTION(action).state_set !=
 525         surf_cpu_model->states.running_action_set)
 526       continue;
 527
 528     /* verify if the action is really running on cpu */
 529     if (action->suspended == 0 && GENERIC_ACTION(action).priority > 0) {
 530       /* total area needed to finish the action. Used in trace integration */
 531       total_area =
 532         (GENERIC_ACTION(action).remains) * sum_priority *
 533         GENERIC_ACTION(action).priority;
 534
 535       total_area /= cpu->power_peak;
 536
 537       GENERIC_ACTION(action).finish =
 538         surf_cpu_solve_trace(cpu->avail_trace, now, total_area);
 539       /* verify which event will happen before (max_duration or finish time) */
 540       if ((GENERIC_ACTION(action).max_duration != NO_MAX_DURATION) &&
 541           (GENERIC_ACTION(action).start +
 542            GENERIC_ACTION(action).max_duration <
 543            GENERIC_ACTION(action).finish))
 544         min_finish = GENERIC_ACTION(action).start +
 545           GENERIC_ACTION(action).max_duration;
 546       else
 547         min_finish = GENERIC_ACTION(action).finish;
 548     } else {
 549       /* put the max duration time on heap */
 550       if (GENERIC_ACTION(action).max_duration != NO_MAX_DURATION)
 551         min_finish =
 552           (GENERIC_ACTION(action).start +
 553            GENERIC_ACTION(action).max_duration);
 554     }
 555     /* add in action heap */
 556     DEBUG2("action(%p) index %d", action, action->index_heap);
 557     if (action->index_heap >= 0) {
 558       surf_action_cpu_ti_t heap_act =
 559         xbt_heap_remove(action_heap, action->index_heap);
 560       if (heap_act != action)
 561         DIE_IMPOSSIBLE;
 562     }
 563     if (min_finish != NO_MAX_DURATION)
 564       xbt_heap_push(action_heap, action, min_finish);
 565
 566     DEBUG5
 567       ("Update finish time: Cpu(%s) Action: %p, Start Time: %lf Finish Time: %lf Max duration %lf",
 568        cpu->generic_resource.name, action, GENERIC_ACTION(action).start,
 569        GENERIC_ACTION(action).finish, GENERIC_ACTION(action).max_duration);
 570   }
 571 /* remove from modified cpu */
 572   xbt_swag_remove(cpu, modified_cpu);
 573 #undef GENERIC_ACTION
 574 }
 575
 576 static double share_resources(double now)
 577 {
 578   cpu_ti_t cpu, cpu_next;
 579   double min_action_duration = -1;
 580
 581 /* iterates over modified cpus to update share resources */
 582   xbt_swag_foreach_safe(cpu, cpu_next, modified_cpu) {
 583     cpu_update_action_finish_date(cpu, now);
 584   }
 585 /* get the min next event if heap not empty */
 586   if (xbt_heap_size(action_heap) > 0)
 587     min_action_duration = xbt_heap_maxkey(action_heap) - now;
 588
 589   DEBUG1("Share resources, min next event date: %lf", min_action_duration);
 590
 591   return min_action_duration;
 592 }
 593
 594 static void update_actions_state(double now, double delta)
 595 {
 596 #define GENERIC_ACTION(action) action->generic_action
 597   surf_action_cpu_ti_t action;
 598   while ((xbt_heap_size(action_heap) > 0)
 599          && (xbt_heap_maxkey(action_heap) <= now)) {
 600     DEBUG1("Action %p: finish", action);
 601     action = xbt_heap_pop(action_heap);
 602     GENERIC_ACTION(action).finish = surf_get_clock();
 603     /* set the remains to 0 due to precision problems when updating the remaining amount */
 604     GENERIC_ACTION(action).remains = 0;
 605     cpu_action_state_set((surf_action_t) action, SURF_ACTION_DONE);
 606     /* update remaining amout of all actions */
 607     cpu_update_remaining_amount(action->cpu, surf_get_clock());
 608   }
 609 #undef GENERIC_ACTION
 610 }
 611
 612 static void update_resource_state(void *id,
 613                                   tmgr_trace_event_t event_type,
 614                                   double value, double date)
 615 {
 616   cpu_ti_t cpu = id;
 617   surf_action_cpu_ti_t action;
 618
 619   if (event_type == cpu->power_event) {
 620     tmgr_trace_t power_trace;
 621     surf_cpu_ti_tgmr_t trace;
 622     s_tmgr_event_t val;
 623
 624     DEBUG3("Finish trace date: %lf value %lf date %lf", surf_get_clock(),
 625            value, date);
 626     /* update remaining of actions and put in modified cpu swag */
 627     cpu_update_remaining_amount(cpu, date);
 628     xbt_swag_insert(cpu, modified_cpu);
 629
 630     power_trace = cpu->avail_trace->levels[0]->power_trace;
 631     xbt_dynar_get_cpy(power_trace->event_list,
 632                       xbt_dynar_length(power_trace->event_list) - 1, &val);
 633     /* free old trace */
 634     surf_cpu_free_trace(cpu->avail_trace);
 635     cpu->power_scale = val.value;
 636
 637     trace = xbt_new0(s_surf_cpu_ti_tgmr_t, 1);
 638     trace->type = TRACE_FIXED;
 639     trace->value = val.value;
 640     DEBUG1("value %lf", val.value);
 641
 642     cpu->avail_trace = trace;
 643
 644     if (tmgr_trace_event_free(event_type))
 645       cpu->power_event = NULL;
 646   } else if (event_type == cpu->state_event) {
 647     if (value > 0)
 648       cpu->state_current = SURF_RESOURCE_ON;
 649     else {
 650       cpu->state_current = SURF_RESOURCE_OFF;
 651
 652       /* put all action running on cpu to failed */
 653       xbt_swag_foreach(action, cpu->action_set) {
 654         if (surf_action_state_get((surf_action_t) action) ==
 655             SURF_ACTION_RUNNING
 656             || surf_action_state_get((surf_action_t) action) ==
 657             SURF_ACTION_READY
 658             || surf_action_state_get((surf_action_t) action) ==
 659             SURF_ACTION_NOT_IN_THE_SYSTEM) {
 660           action->generic_action.finish = date;
 661           cpu_action_state_set((surf_action_t) action, SURF_ACTION_FAILED);
 662           if (action->index_heap >= 0) {
 663             surf_action_cpu_ti_t heap_act =
 664               xbt_heap_remove(action_heap, action->index_heap);
 665             if (heap_act != action)
 666               DIE_IMPOSSIBLE;
 667           }
 668         }
 669       }
 670     }
 671     if (tmgr_trace_event_free(event_type))
 672       cpu->state_event = NULL;
 673   } else {
 674     CRITICAL0("Unknown event ! \n");
 675     xbt_abort();
 676   }
 677
 678   return;
 679 }
 680
 681 static surf_action_t execute(void *cpu, double size)
 682 {
 683   surf_action_cpu_ti_t action = NULL;
 684   cpu_ti_t CPU = cpu;
 685
 686   XBT_IN2("(%s,%g)", surf_resource_name(CPU), size);
 687   action =
 688     surf_action_new(sizeof(s_surf_action_cpu_ti_t), size, surf_cpu_model,
 689                     CPU->state_current != SURF_RESOURCE_ON);
 690   action->cpu = cpu;
 691   action->index_heap = -1;
 692
 693   xbt_swag_insert(CPU, modified_cpu);
 694
 695   xbt_swag_insert(action, CPU->action_set);
 696
 697   action->suspended = 0;        /* Should be useless because of the
 698                                    calloc but it seems to help valgrind... */
 699
 700   XBT_OUT;
 701   return (surf_action_t) action;
 702 }
 703
 704 static void action_update_index_heap(void *action, int i)
 705 {
 706   ((surf_action_cpu_ti_t) action)->index_heap = i;
 707 }
 708
 709 static surf_action_t action_sleep(void *cpu, double duration)
 710 {
 711   surf_action_cpu_ti_t action = NULL;
 712
 713   if (duration > 0)
 714     duration = MAX(duration, MAXMIN_PRECISION);
 715
 716   XBT_IN2("(%s,%g)", surf_resource_name(cpu), duration);
 717   action = (surf_action_cpu_ti_t) execute(cpu, 1.0);
 718   action->generic_action.max_duration = duration;
 719   action->suspended = 2;
 720   if (duration == NO_MAX_DURATION) {
 721     /* Move to the *end* of the corresponding action set. This convention
 722        is used to speed up update_resource_state  */
 723     xbt_swag_remove(action, ((surf_action_t) action)->state_set);
 724     ((surf_action_t) action)->state_set =
 725       running_action_set_that_does_not_need_being_checked;
 726     xbt_swag_insert(action, ((surf_action_t) action)->state_set);
 727   }
 728   XBT_OUT;
 729   return (surf_action_t) action;
 730 }
 731
 732 static void action_suspend(surf_action_t action)
 733 {
 734   XBT_IN1("(%p)", action);
 735   if (((surf_action_cpu_ti_t) action)->suspended != 2) {
 736     ((surf_action_cpu_ti_t) action)->suspended = 1;
 737     xbt_swag_insert(ACTION_GET_CPU(action), modified_cpu);
 738   }
 739   XBT_OUT;
 740 }
 741
 742 static void action_resume(surf_action_t action)
 743 {
 744   XBT_IN1("(%p)", action);
 745   if (((surf_action_cpu_ti_t) action)->suspended != 2) {
 746     ((surf_action_cpu_ti_t) action)->suspended = 0;
 747     xbt_swag_insert(ACTION_GET_CPU(action), modified_cpu);
 748   }
 749   XBT_OUT;
 750 }
 751
 752 static int action_is_suspended(surf_action_t action)
 753 {
 754   return (((surf_action_cpu_ti_t) action)->suspended == 1);
 755 }
 756
 757 static void action_set_max_duration(surf_action_t action, double duration)
 758 {
 759   surf_action_cpu_ti_t ACT = (surf_action_cpu_ti_t) action;
 760   double min_finish;
 761
 762   XBT_IN2("(%p,%g)", action, duration);
 763
 764   action->max_duration = duration;
 765
 766   if (duration >= 0)
 767     min_finish =
 768       (action->start + action->max_duration) <
 769       action->finish ? (action->start +
 770                         action->max_duration) : action->finish;
 771   else
 772     min_finish = action->finish;
 773
 774 /* add in action heap */
 775   if (ACT->index_heap >= 0) {
 776     surf_action_cpu_ti_t heap_act =
 777       xbt_heap_remove(action_heap, ACT->index_heap);
 778     if (heap_act != ACT)
 779       DIE_IMPOSSIBLE;
 780   }
 781   xbt_heap_push(action_heap, ACT, min_finish);
 782
 783   XBT_OUT;
 784 }
 785
 786 static void action_set_priority(surf_action_t action, double priority)
 787 {
 788   XBT_IN2("(%p,%g)", action, priority);
 789   action->priority = priority;
 790   xbt_swag_insert(ACTION_GET_CPU(action), modified_cpu);
 791   XBT_OUT;
 792 }
 793
 794 static double action_get_remains(surf_action_t action)
 795 {
 796   XBT_IN1("(%p)", action);
 797   cpu_update_remaining_amount((cpu_ti_t) ((surf_action_cpu_ti_t) action)->cpu,
 798                               surf_get_clock());
 799   return action->remains;
 800   XBT_OUT;
 801 }
 802
 803 static e_surf_resource_state_t get_state(void *cpu)
 804 {
 805   return ((cpu_ti_t) cpu)->state_current;
 806 }
 807
 808 static double get_speed(void *cpu, double load)
 809 {
 810   return load * (((cpu_ti_t) cpu)->power_peak);
 811 }
 812
 813 /**
 814 * \brief Auxiliar function to update the cpu power scale.
 815 *
 816 *       This function uses the trace structure to return the power scale at the determined time a.
 817 * \param trace          Trace structure to search the updated power scale
 818 * \param a                              Time
 819 * \return Cpu power scale
 820 */
 821 static double surf_cpu_get_power_scale(surf_cpu_ti_tgmr_t trace, double a)
 822 {
 823   double reduced_a;
 824   int point;
 825
 826   reduced_a = a - floor(a / trace->last_time) * trace->last_time;
 827   point = (int) (reduced_a / trace->levels[0]->spacing);
 828   return trace->levels[0]->values[point];
 829 }
 830
 831 static double get_available_speed(void *cpu)
 832 {
 833   cpu_ti_t CPU = cpu;
 834   CPU->power_scale =
 835     surf_cpu_get_power_scale(CPU->avail_trace, surf_get_clock());
 836 /* number between 0 and 1 */
 837   return CPU->power_scale;
 838 }
 839
 840 static void finalize(void)
 841 {
 842   void *cpu;
 843   xbt_dict_cursor_t cursor;
 844   char *key;
 845   xbt_dict_foreach(surf_model_resource_set(surf_cpu_model), cursor, key, cpu) {
 846     cpu_ti_t CPU = cpu;
 847     xbt_swag_free(CPU->action_set);
 848     surf_cpu_free_trace(CPU->avail_trace);
 849   }
 850
 851   surf_model_exit(surf_cpu_model);
 852   surf_cpu_model = NULL;
 853
 854   xbt_swag_free(running_action_set_that_does_not_need_being_checked);
 855   xbt_swag_free(modified_cpu);
 856   running_action_set_that_does_not_need_being_checked = NULL;
 857   xbt_heap_free(action_heap);
 858 }
 859
 860 static void surf_cpu_model_init_internal(void)
 861 {
 862   s_surf_action_t action;
 863   s_cpu_ti_t cpu;
 864
 865   surf_cpu_model = surf_model_init();
 866
 867   running_action_set_that_does_not_need_being_checked =
 868     xbt_swag_new(xbt_swag_offset(action, state_hookup));
 869
 870   modified_cpu = xbt_swag_new(xbt_swag_offset(cpu, modified_cpu_hookup));
 871
 872   surf_cpu_model->name = "CPU_TI";
 873
 874   surf_cpu_model->action_unref = action_unref;
 875   surf_cpu_model->action_cancel = action_cancel;
 876   surf_cpu_model->action_state_set = cpu_action_state_set;
 877
 878   surf_cpu_model->model_private->resource_used = resource_used;
 879   surf_cpu_model->model_private->share_resources = share_resources;
 880   surf_cpu_model->model_private->update_actions_state = update_actions_state;
 881   surf_cpu_model->model_private->update_resource_state =
 882     update_resource_state;
 883   surf_cpu_model->model_private->finalize = finalize;
 884
 885   surf_cpu_model->suspend = action_suspend;
 886   surf_cpu_model->resume = action_resume;
 887   surf_cpu_model->is_suspended = action_is_suspended;
 888   surf_cpu_model->set_max_duration = action_set_max_duration;
 889   surf_cpu_model->set_priority = action_set_priority;
 890   surf_cpu_model->get_remains = action_get_remains;
 891
 892   surf_cpu_model->extension.cpu.execute = execute;
 893   surf_cpu_model->extension.cpu.sleep = action_sleep;
 894
 895   surf_cpu_model->extension.cpu.get_state = get_state;
 896   surf_cpu_model->extension.cpu.get_speed = get_speed;
 897   surf_cpu_model->extension.cpu.get_available_speed = get_available_speed;
 898
 899   action_heap = xbt_heap_new(8, NULL);
 900   xbt_heap_set_update_callback(action_heap, action_update_index_heap);
 901
 902 }
 903
 904 void surf_cpu_model_init_ti(const char *filename)
 905 {
 906   if (surf_cpu_model)
 907     return;
 908   surf_cpu_model_init_internal();
 909   define_callbacks(filename);
 910   xbt_dynar_push(model_list, &surf_cpu_model);
 911 }
 912
 913
 914 ///////////////// BEGIN INTEGRAL //////////////
 915
 916 /**
 917 * \brief Integrate trace
 918 *
 919 * Wrapper around surf_cpu_integrate_trace_simple() to get
 920 * the cyclic effect.
 921 *
 922 * \param trace Trace structure.
 923 * \param a                      Begin of interval
 924 * \param b                      End of interval
 925 * \return the integrate value. -1 if an error occurs.
 926 */
 927 static double surf_cpu_integrate_trace(surf_cpu_ti_tgmr_t trace, double a,
 928                                        double b)
 929 {
 930   double first_chunk;
 931   double middle_chunk;
 932   double last_chunk;
 933   int a_index, b_index;
 934
 935   if ((a < 0.0) || (a > b)) {
 936     CRITICAL2
 937       ("Error, invalid integration interval [%.2f,%.2f]. You probably have a task executing with negative computation amount. Check your code.",
 938        a, b);
 939     xbt_abort();
 940   }
 941   if (a == b)
 942     return 0.0;
 943
 944   if (trace->type == TRACE_FIXED) {
 945     return ((b - a) * trace->value);
 946   }
 947
 948   if (ceil(a / trace->last_time) == a / trace->last_time)
 949     a_index = 1 + (int) (ceil(a / trace->last_time));
 950   else
 951     a_index = (int) (ceil(a / trace->last_time));
 952
 953   b_index = (int) (floor(b / trace->last_time));
 954
 955   if (a_index > b_index) {      /* Same chunk */
 956     return surf_cpu_integrate_trace_simple(trace,
 957                                            a - (a_index -
 958                                                 1) * trace->last_time,
 959                                            b - (b_index) * trace->last_time);
 960   }
 961
 962   first_chunk = surf_cpu_integrate_trace_simple(trace,
 963                                                 a - (a_index -
 964                                                      1) * trace->last_time,
 965                                                 trace->last_time);
 966   middle_chunk = (b_index - a_index) * trace->total;
 967   last_chunk = surf_cpu_integrate_trace_simple(trace,
 968                                                0.0,
 969                                                b -
 970                                                (b_index) * trace->last_time);
 971
 972   DEBUG3("first_chunk=%.2f  middle_chunk=%.2f  last_chunk=%.2f\n",
 973          first_chunk, middle_chunk, last_chunk);
 974
 975   return (first_chunk + middle_chunk + last_chunk);
 976 }
 977
 978 /**
 979 * \brief Integrate the trace between a and b.
 980 *
 981 *  integrates without taking cyclic-traces into account.
 982 *  [a,b] \subset [0,last_time]
 983 *
 984 * \param trace Trace structure.
 985 * \param a                      Begin of interval
 986 * \param b                      End of interval
 987 * \return the integrate value. -1 if an error occurs.
 988 */
 989 static double surf_cpu_integrate_trace_simple(surf_cpu_ti_tgmr_t trace,
 990                                               double a, double b)
 991 {
 992   double integral = 0.0;
 993   int i;
 994   long index;
 995   int top_level = 0;
 996   long l_bounds[TRACE_NB_LEVELS];
 997   long u_bounds[TRACE_NB_LEVELS];
 998   double a_divided_by_spacing;
 999   double current_spacing;
1000   DEBUG2("Computing simple integral on [%.2f , %.2f]\n", a, b);
1001
1002 /* Sanity checks */
1003   if ((a < 0.0) || (b < a) || (a > trace->last_time)
1004       || (b > trace->last_time)) {
1005     CRITICAL2
1006       ("Error, invalid integration interval [%.2f,%.2f]. You probably have a task executing with negative computation amount. Check your code.",
1007        a, b);
1008     xbt_abort();
1009   }
1010   if (b == a) {
1011     return 0.0;
1012   }
1013
1014   for (i = 0; i < trace->nb_levels; i++) {
1015     a_divided_by_spacing = a / trace->levels[i]->spacing;
1016     if (ceil(a_divided_by_spacing) == a_divided_by_spacing)
1017       l_bounds[i] = 1 + (long) ceil(a_divided_by_spacing);
1018     else
1019       l_bounds[i] = (long) (ceil(a_divided_by_spacing));
1020     if (b == trace->last_time) {
1021       u_bounds[i] = (long) (floor(b / trace->levels[i]->spacing)) - 1;
1022     } else {
1023       u_bounds[i] = (long) (floor(b / trace->levels[i]->spacing));
1024     }
1025     DEBUG3("level %d: l%ld  u%ld\n", i, l_bounds[i], u_bounds[i]);
1026
1027     if (l_bounds[i] <= u_bounds[i])
1028       top_level = i;
1029   }
1030   DEBUG1("top_level=%d\n", top_level);
1031
1032 /* Are a and b BOTH in the same chunk of level 0 ? */
1033   if (l_bounds[0] > u_bounds[0]) {
1034     return surf_cpu_integrate_exactly(trace, u_bounds[0], a, b);
1035 #if 0
1036     return (b - a) * (trace->levels[0]->values[u_bounds[0]]);
1037 #endif
1038   }
1039
1040 /* first sub-level amount */
1041   integral += ((l_bounds[0]) * (trace->levels[0]->spacing) - a) *
1042     (trace->levels[0]->values[l_bounds[0] - 1]);
1043
1044   DEBUG1("Initial level 0 amount is %.2f\n", integral);
1045
1046 /* first n-1 levels */
1047   for (i = 0; i < top_level; i++) {
1048
1049     if (l_bounds[i] >= u_bounds[i])
1050       break;
1051
1052     current_spacing = trace->levels[i]->spacing;
1053     index = l_bounds[i];
1054
1055     DEBUG1("L%d:", i);
1056
1057     while (double_positive
1058            (l_bounds[i + 1] * trace->levels[i + 1]->spacing -
1059             index * current_spacing)) {
1060       integral += current_spacing * trace->levels[i]->values[index];
1061       DEBUG2("%.2f->%.2f|",
1062              index * (trace->levels[i]->spacing),
1063              (index + 1) * (trace->levels[i]->spacing));
1064       index++;
1065     }
1066
1067     DEBUG0("\n");
1068   }
1069
1070   DEBUG1("After going up: %.2f\n", integral);
1071
1072 /* n-th level */
1073   current_spacing = trace->levels[top_level]->spacing;
1074   index = l_bounds[top_level];
1075
1076   DEBUG1("L%d:", top_level);
1077
1078   while (index < u_bounds[top_level]) {
1079     integral += current_spacing * trace->levels[top_level]->values[index];
1080
1081     DEBUG2("%.2f->%.2f|",
1082            index * (trace->levels[top_level]->spacing),
1083            (index + 1) * (trace->levels[top_level]->spacing));
1084
1085     index++;
1086   }
1087
1088   DEBUG0("\n");
1089   DEBUG1("After steady : %.2f\n", integral);
1090
1091 /* And going back down */
1092   for (i = top_level - 1; i >= 0; i--) {
1093     if (l_bounds[i] > u_bounds[i])
1094       break;
1095
1096     current_spacing = trace->levels[i]->spacing;
1097     index = rint(u_bounds[i + 1] * (trace->levels[i + 1]->spacing /
1098                                     current_spacing));
1099     DEBUG1("L%d:", i);
1100     while (double_positive
1101            ((u_bounds[i]) * current_spacing - index * current_spacing)) {
1102       integral += current_spacing * trace->levels[i]->values[index];
1103       DEBUG2("%.2f->%.2f|",
1104              index * (trace->levels[i]->spacing),
1105              (index + 1) * (trace->levels[i]->spacing));
1106       index++;
1107     }
1108   }
1109
1110   DEBUG1("After going down : %.2f", integral);
1111
1112
1113 /* Little piece at the end */
1114 #if 0
1115   integral += (b - u_bounds[0] * (trace->levels[0]->spacing)) *
1116     (trace->levels[0]->values[u_bounds[0]]);
1117 #endif
1118   integral +=
1119     surf_cpu_integrate_exactly(trace, u_bounds[0],
1120                                u_bounds[0] * (trace->levels[0]->spacing), b);
1121   DEBUG1("After last bit : %.2f", integral);
1122
1123   return integral;
1124 }
1125
1126
1127 /**
1128 * \brief Calcul the time needed to execute "amount" on cpu.
1129 *
1130 * Here, amount can span multiple trace periods
1131 *
1132 * \param trace  CPU trace structure
1133 * \param a                              Initial time
1134 * \param amount Amount of calcul to be executed
1135 * \return       End time
1136 */
1137 static double surf_cpu_solve_trace(surf_cpu_ti_tgmr_t trace, double a,
1138                                    double amount)
1139 {
1140   int quotient;
1141   double reduced_b;
1142   double reduced_amount;
1143   double reduced_a;
1144   double b;
1145
1146 /* Fix very small negative numbers */
1147   if ((a < 0.0) && (a > -EPSILON)) {
1148     a = 0.0;
1149   }
1150   if ((amount < 0.0) && (amount > -EPSILON)) {
1151     amount = 0.0;
1152   }
1153
1154 /* Sanity checks */
1155   if ((a < 0.0) || (amount < 0.0)) {
1156     CRITICAL2
1157       ("Error, invalid parameters [a = %.2f, amount = %.2f]. You probably have a task executing with negative computation amount. Check your code.",
1158        a, amount);
1159     xbt_abort();
1160   }
1161
1162 /* At this point, a and amount are positive */
1163
1164   if (amount < EPSILON)
1165     return a;
1166
1167 /* Is the trace fixed ? */
1168   if (trace->type == TRACE_FIXED) {
1169     return (a + (amount / trace->value));
1170   }
1171
1172   DEBUG2("amount %lf total %lf", amount, trace->total);
1173 /* Reduce the problem to one where amount <= trace_total */
1174   quotient = (int) (floor(amount / trace->total));
1175   reduced_amount = (trace->total) * ((amount / trace->total) -
1176                                      floor(amount / trace->total));
1177   reduced_a = a - (trace->last_time) * (int) (floor(a / trace->last_time));
1178
1179   DEBUG3("Quotient: %d reduced_amount: %lf reduced_a: %lf", quotient,
1180          reduced_amount, reduced_a);
1181
1182 /* Now solve for new_amount which is <= trace_total */
1183 /*
1184          fprintf(stderr,"reduced_a = %.2f\n",reduced_a);
1185          fprintf(stderr,"reduced_amount = %.2f\n",reduced_amount);
1186  */
1187   reduced_b =
1188     surf_cpu_solve_trace_somewhat_simple(trace, reduced_a, reduced_amount);
1189
1190 /* Re-map to the original b and amount */
1191   b = (trace->last_time) * (int) (floor(a / trace->last_time)) +
1192     (quotient * trace->actual_last_time) + reduced_b;
1193   return b;
1194 }
1195
1196 /**
1197 * \brief Auxiliar function to solve integral
1198 *
1199 * Here, amount is <= trace->total
1200 * and a <=trace->last_time
1201 *
1202 */
1203 static double surf_cpu_solve_trace_somewhat_simple(surf_cpu_ti_tgmr_t trace,
1204                                                    double a, double amount)
1205 {
1206   double amount_till_end;
1207   double b;
1208
1209   DEBUG2("Solve integral: [%.2f, amount=%.2f]", a, amount);
1210
1211   amount_till_end = surf_cpu_integrate_trace(trace, a, trace->last_time);
1212 /*
1213          fprintf(stderr,"amount_till_end=%.2f\n",amount_till_end);
1214  */
1215
1216   if (amount_till_end > amount) {
1217     b = surf_cpu_solve_trace_simple(trace, a, amount);
1218   } else {
1219     b = trace->last_time +
1220       surf_cpu_solve_trace_simple(trace, 0.0, amount - amount_till_end);
1221   }
1222
1223   return b;
1224 }
1225
1226 /**
1227 * \brief Auxiliar function to solve integral
1228 * surf_cpu_solve_trace_simple()
1229 *
1230 *  solve for the upper bound without taking
1231 *  cyclic-traces into account.
1232 *
1233 *  [a,y] \subset [0,last_time]
1234 *
1235 */
1236 static double surf_cpu_solve_trace_simple(surf_cpu_ti_tgmr_t trace, double a,
1237                                           double amount)
1238 {
1239   double next_chunk;
1240   double remains;
1241   int i;
1242   long index;
1243   int top_level;
1244   double b;
1245   int done;
1246   long l_bounds[TRACE_NB_LEVELS];       /* May be too bgi for this trace */
1247   double a_divided_by_spacing;
1248   double current_spacing;
1249
1250   DEBUG2("Solving simple integral [x=%.2f,amount=%.2f]", a, amount);
1251
1252 /* Sanity checks */
1253   if ((a < 0.0) || (amount < 0.0) || (a > trace->last_time)) {
1254     CRITICAL2
1255       ("Error, invalid parameters [a = %.2f, amount = %.2f]. You probably have a task executing with negative computation amount. Check your code.",
1256        a, amount);
1257     xbt_abort();
1258   }
1259   if (amount == 0.0) {
1260     /* fprintf(stderr,"Warning: trivial integral solve\n"); */
1261     return a;
1262   }
1263
1264   for (i = 0; i < trace->nb_levels; i++) {
1265     a_divided_by_spacing = a / trace->levels[i]->spacing;
1266     if (ceil(a_divided_by_spacing) == a_divided_by_spacing)
1267       l_bounds[i] = 1 + (long) ceil(a_divided_by_spacing);
1268     else
1269       l_bounds[i] = (long) (ceil(a_divided_by_spacing));
1270
1271     if ((l_bounds[i] + 1) * trace->levels[i]->spacing > trace->last_time)
1272       break;
1273
1274     DEBUG2("level %d: l%ld", i, l_bounds[i]);
1275   }
1276   if (i == trace->nb_levels)
1277     top_level = trace->nb_levels - 1;
1278   else {
1279     top_level = i;
1280   }
1281
1282   remains = amount;
1283 /* first sub-level amount */
1284 /* old code, keep here for a while */
1285 #if 0
1286   next_chunk = ((l_bounds[0]) * (trace->levels[0]->spacing) - a) *
1287     (trace->levels[0]->values[l_bounds[0] - 1]);
1288 #endif
1289   next_chunk =
1290     surf_cpu_integrate_exactly(trace, l_bounds[0] - 1, a,
1291                                (l_bounds[0]) * (trace->levels[0]->spacing));
1292
1293   if (remains - next_chunk < 0.0) {
1294 #if 0
1295     b = a + (amount / trace->levels[0]->values[l_bounds[0] - 1]);
1296 #endif
1297     b = a + surf_cpu_solve_exactly(trace, l_bounds[0] - 1, a, amount);
1298     DEBUG1("Returning sub-level[0] result %.2f", b);
1299
1300     return b;
1301   } else {
1302     b = (l_bounds[0]) * (trace->levels[0]->spacing);
1303     remains -= next_chunk;
1304   }
1305   DEBUG2("After sub-0 stuff: remains %.2f (b=%.2f)", remains, b);
1306
1307 /* first n-1 levels */
1308   DEBUG0("Going up levels");
1309
1310   done = 0;
1311   for (i = 0; i < top_level; i++) {
1312
1313     current_spacing = trace->levels[i]->spacing;
1314     index = l_bounds[i];
1315
1316     DEBUG1("L%d:", i);
1317
1318     while (double_positive
1319            (l_bounds[i + 1] * trace->levels[i + 1]->spacing -
1320             index * current_spacing)
1321            && ((index + 1) * (current_spacing) < trace->last_time)) {
1322
1323       next_chunk = current_spacing * trace->levels[i]->values[index];
1324
1325       DEBUG3("%.2f next_chunk= %.2f remains=%.2f",
1326              (index + 1) * (trace->levels[i]->spacing), next_chunk, remains);
1327
1328       if (remains - next_chunk < 0.0) { /* Too far */
1329         done = 1;
1330         break;
1331       } else {                  /* Keep going */
1332         DEBUG2("%.2f->%.2f|",
1333                index * (trace->levels[i]->spacing),
1334                (index + 1) * (trace->levels[i]->spacing));
1335
1336         remains -= next_chunk;
1337         b = (index + 1) * (current_spacing);
1338       }
1339       index++;
1340     }
1341     if (done) {
1342       /* found chunk, fix the index to top level */
1343       i++;
1344       break;
1345     }
1346   }
1347
1348   DEBUG0("Steady");
1349   top_level = i;
1350
1351 /* n-th level */
1352   current_spacing = trace->levels[top_level]->spacing;
1353   index = l_bounds[top_level];
1354
1355   DEBUG1("L%d:", top_level);
1356
1357 /* iterate over the last level only if it hasn't found the chunk where the amount is */
1358   if (!done) {
1359     while (index < trace->levels[top_level]->nb_points) {
1360       next_chunk = current_spacing * trace->levels[top_level]->values[index];
1361       if (remains - next_chunk <= 0.0) {        /* Too far */
1362         break;
1363       } else {
1364         DEBUG2("%.2f->%.2f|",
1365                index * (trace->levels[top_level]->spacing),
1366                (index + 1) * (trace->levels[top_level]->spacing));
1367
1368         remains -= next_chunk;
1369         b = (index + 1) * (current_spacing);
1370       }
1371       index++;
1372     }
1373   }
1374   DEBUG2("remains = %.2f b=%.2f", remains, b);
1375
1376 /* And going back down */
1377   DEBUG0("Going back down");
1378   for (i = top_level - 1; i >= 0; i--) {
1379
1380     current_spacing = trace->levels[i]->spacing;
1381     /* use rint to trunc index due to precision problems */
1382     index = rint(b / trace->levels[i]->spacing);
1383
1384     DEBUG1("L%d:", i);
1385
1386     while (index < trace->levels[i]->nb_points) {
1387       next_chunk = current_spacing * trace->levels[i]->values[index];
1388       DEBUG3("remains %lf nextchu %lf value %lf", remains, next_chunk,
1389              trace->levels[i]->values[index]);
1390       if (remains - next_chunk <= 0.0) {        /* Too far */
1391         break;
1392       } else {
1393         DEBUG3("%.2f->%.2f| b %lf",
1394                index * (current_spacing), (index + 1) * (current_spacing), b);
1395
1396         remains -= next_chunk;
1397         b += current_spacing;
1398       }
1399       index++;
1400     }
1401   }
1402
1403   DEBUG2("remains = %.2f b=%.2f\n", remains, b);
1404   DEBUG1("Last bit index=%ld\n", index);
1405
1406 /* Little piece at the end */
1407 #if 0
1408   b += (remains) / (trace->levels[0]->values[index]);
1409 #endif
1410   b += surf_cpu_solve_exactly(trace, index, b, remains);
1411   DEBUG1("Total b %lf", b);
1412   return b;
1413 }
1414
1415 /**
1416 * \brief This function calcules the exactly value of integral between a and b. It uses directly the tmgr_trace_t strucure.
1417 * It works only if the two points are in the same timestep.
1418 * \param trace  Trace structure
1419 * \param index  Index of timestep where the points are located
1420 * \param a                      First point of interval
1421 * \param b                      Second point
1422 * \return       the integral value
1423 */
1424 static double surf_cpu_integrate_exactly(surf_cpu_ti_tgmr_t trace, int index,
1425                                          double a, double b)
1426 {
1427   int tmgr_index;
1428   double integral = 0.0;
1429   double time = a;
1430   double tmgr_date;
1431   s_tmgr_event_t elem;
1432
1433   /* already at the end */
1434   if (index >= trace->levels[0]->nb_points && !double_positive(b - a))
1435     return 0.0;
1436   tmgr_index = trace->levels[0]->trace_index[index];
1437   tmgr_date = trace->levels[0]->trace_value[index];
1438
1439   DEBUG6
1440     ("Start time: %lf End time: %lf index %d tmgr_index %d tmgr_date %lf value %lf",
1441      a, b, index, tmgr_index, tmgr_date, trace->levels[0]->values[index]);
1442
1443   if (tmgr_index < 0)
1444     return (b - a) * (trace->levels[0]->values[index]);
1445
1446   while (a > tmgr_date) {
1447     xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list, tmgr_index,
1448                       &elem);
1449     tmgr_date += elem.delta;
1450     tmgr_index++;
1451   }
1452   /* sum first slice [a, tmgr_date[ */
1453   if (a < tmgr_date) {
1454     xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list,
1455                       tmgr_index - 1, &elem);
1456     if (b < tmgr_date) {
1457       return (b - a) * elem.value;
1458     }
1459
1460     integral = (tmgr_date - a) * elem.value;
1461     time = tmgr_date;
1462   }
1463
1464   while (tmgr_index <
1465          xbt_dynar_length(trace->levels[0]->power_trace->event_list)) {
1466     xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list, tmgr_index,
1467                       &elem);
1468     if (b <= time + elem.delta) {
1469       integral += (b - time) * elem.value;
1470       break;
1471     }
1472     integral += elem.delta * elem.value;
1473     time += elem.delta;
1474     tmgr_index++;
1475   }
1476
1477   return integral;
1478 }
1479
1480 /**
1481 * \brief This function calcules the exactly time needed to compute amount flops. It uses directly the tmgr_trace_t structure.
1482 * It works only if the two points are in the same timestep.
1483 * \param trace  Trace structure
1484 * \param index  Index of timestep where the points are located
1485 * \param a                      Start time
1486 * \param amount                 Total amount
1487 * \return       number of seconds needed to compute amount flops
1488 */
1489 static double surf_cpu_solve_exactly(surf_cpu_ti_tgmr_t trace, int index,
1490                                      double a, double amount)
1491 {
1492   int tmgr_index;
1493   double remains;
1494   double time, tmgr_date;
1495   double slice_amount;
1496   s_tmgr_event_t elem;
1497
1498
1499   tmgr_index = trace->levels[0]->trace_index[index];
1500   tmgr_date = trace->levels[0]->trace_value[index];
1501   remains = amount;
1502   time = a;
1503
1504   DEBUG6
1505     ("Start time: %lf Amount: %lf index %d tmgr_index %d tmgr_date %lf value %lf",
1506      a, amount, index, tmgr_index, tmgr_date,
1507      trace->levels[0]->values[index]);
1508   if (tmgr_index < 0)
1509     return amount / (trace->levels[0]->values[index]);
1510
1511   while (a > tmgr_date) {
1512     xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list, tmgr_index,
1513                       &elem);
1514     tmgr_date += elem.delta;
1515     tmgr_index++;
1516   }
1517   /* sum first slice [a, tmgr_date[ */
1518   if (a < tmgr_date) {
1519     xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list,
1520                       tmgr_index - 1, &elem);
1521     slice_amount = (tmgr_date - a) * elem.value;
1522     DEBUG5("slice amount %lf a %lf tmgr_date %lf elem_value %lf delta %lf",
1523            slice_amount, a, tmgr_date, elem.value, elem.delta);
1524     if (remains <= slice_amount) {
1525       return (remains / elem.value);
1526     }
1527
1528     remains -= (tmgr_date - a) * elem.value;
1529     time = tmgr_date;
1530   }
1531
1532   while (1) {
1533     xbt_dynar_get_cpy(trace->levels[0]->power_trace->event_list, tmgr_index,
1534                       &elem);
1535     slice_amount = elem.delta * elem.value;
1536     DEBUG5("slice amount %lf a %lf tmgr_date %lf elem_value %lf delta %lf",
1537            slice_amount, a, tmgr_date, elem.value, elem.delta);
1538     if (remains <= slice_amount) {
1539       time += remains / elem.value;
1540       break;
1541     }
1542     time += elem.delta;
1543     remains -= elem.delta * elem.value;
1544     tmgr_index++;
1545   }
1546
1547   return time - a;
1548 }
1549
1550 //////////// END INTEGRAL /////////////////