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