src/surf/cpu_ti.c

   1
   2 /* Copyright (c) 2009, 2010. The SimGrid Team.
   3  * All rights reserved.                                                     */
   4
   5 /* This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the license (GNU LGPL) which comes with this package. */
   7
   8 /*
   9         commit: e2d6799c4182f00443b3013aadb1c2412372460f
  10         This commit retrieves the old implementation of CPU_TI with multi-levels.
  11 */
  12
  13 #include "surf_private.h"
  14 #include "trace_mgr_private.h"
  15 #include "cpu_ti_private.h"
  16 #include "xbt/heap.h"
  17
  18
  19 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_cpu_ti, surf,
  20                                 "Logging specific to the SURF CPU TRACE INTEGRATION module");
  21
  22
  23 static xbt_swag_t
  24     cpu_ti_running_action_set_that_does_not_need_being_checked = NULL;
  25 static xbt_swag_t cpu_ti_modified_cpu = NULL;
  26 static xbt_heap_t cpu_ti_action_heap;
  27
  28 /* prototypes of new trace functions */
  29 static double surf_cpu_ti_integrate_trace(surf_cpu_ti_tgmr_t trace,
  30                                           double a, double b);
  31
  32
  33 static double surf_cpu_ti_solve_trace(surf_cpu_ti_tgmr_t trace, double a,
  34                                       double amount);
  35 static double surf_cpu_ti_solve_trace_somewhat_simple(surf_cpu_ti_tgmr_t
  36                                                       trace, double a,
  37                                                       double amount);
  38
  39 static void surf_cpu_ti_free_tmgr(surf_cpu_ti_tgmr_t trace);
  40
  41 static double surf_cpu_ti_integrate_trace_simple(surf_cpu_ti_trace_t trace,
  42                                                  double a, double b);
  43 static double surf_cpu_ti_integrate_trace_simple_point(surf_cpu_ti_trace_t
  44                                                        trace, double a);
  45 static double surf_cpu_ti_solve_trace_simple(surf_cpu_ti_trace_t trace,
  46                                              double a, double amount);
  47 static int surf_cpu_ti_binary_search(double *array, double a, int low,
  48                                      int high);
  49 /* end prototypes */
  50
  51 static void surf_cpu_ti_free_trace(surf_cpu_ti_trace_t trace)
  52 {
  53   if (trace->time_points)
  54     xbt_free(trace->time_points);
  55   if (trace->integral)
  56     xbt_free(trace->integral);
  57   xbt_free(trace);
  58 }
  59
  60 static void surf_cpu_ti_free_tmgr(surf_cpu_ti_tgmr_t trace)
  61 {
  62   if (trace->trace)
  63     surf_cpu_ti_free_trace(trace->trace);
  64   xbt_free(trace);
  65 }
  66
  67 static surf_cpu_ti_trace_t surf_cpu_ti_trace_new(tmgr_trace_t power_trace)
  68 {
  69   surf_cpu_ti_trace_t trace;
  70   s_tmgr_event_t val;
  71   unsigned int cpt;
  72   double integral = 0;
  73   double time = 0;
  74   int i = 0;
  75   trace = xbt_new0(s_surf_cpu_ti_trace_t, 1);
  76   trace->time_points =
  77       xbt_malloc0(sizeof(double) *
  78                   (xbt_dynar_length(power_trace->event_list) + 1));
  79   trace->integral =
  80       xbt_malloc0(sizeof(double) *
  81                   (xbt_dynar_length(power_trace->event_list) + 1));
  82   trace->nb_points = xbt_dynar_length(power_trace->event_list);
  83   xbt_dynar_foreach(power_trace->event_list, cpt, val) {
  84     trace->time_points[i] = time;
  85     trace->integral[i] = integral;
  86     integral += val.delta * val.value;
  87     time += val.delta;
  88     i++;
  89   }
  90   trace->time_points[i] = time;
  91   trace->integral[i] = integral;
  92   return trace;
  93 }
  94
  95 /**
  96 * \brief Creates a new integration trace from a tmgr_trace_t
  97 *
  98 * \param        power_trace             CPU availability trace
  99 * \param        value                                   Percentage of CPU power available (useful to fixed tracing)
 100 * \param        spacing                         Initial spacing
 101 * \return       Integration trace structure
 102 */
 103 static surf_cpu_ti_tgmr_t cpu_ti_parse_trace(tmgr_trace_t power_trace,
 104                                              double value)
 105 {
 106   surf_cpu_ti_tgmr_t trace;
 107   double total_time = 0.0;
 108   s_tmgr_event_t val;
 109   unsigned int cpt;
 110   trace = xbt_new0(s_surf_cpu_ti_tgmr_t, 1);
 111
 112 /* no availability file, fixed trace */
 113   if (!power_trace) {
 114     trace->type = TRACE_FIXED;
 115     trace->value = value;
 116     DEBUG1("No availabily trace. Constant value = %lf", value);
 117     return trace;
 118   }
 119
 120   /* only one point available, fixed trace */
 121   if (xbt_dynar_length(power_trace->event_list) == 1) {
 122     xbt_dynar_get_cpy(power_trace->event_list, 0, &val);
 123     trace->type = TRACE_FIXED;
 124     trace->value = val.value;
 125     return trace;
 126   }
 127
 128   trace->type = TRACE_DYNAMIC;
 129   trace->power_trace = power_trace;
 130
 131   /* count the total time of trace file */
 132   xbt_dynar_foreach(power_trace->event_list, cpt, val) {
 133     total_time += val.delta;
 134   }
 135   trace->trace = surf_cpu_ti_trace_new(power_trace);
 136   trace->last_time = total_time;
 137   trace->total =
 138       surf_cpu_ti_integrate_trace_simple(trace->trace, 0, total_time);
 139
 140   DEBUG2("Total integral %lf, last_time %lf ",
 141          trace->total, trace->last_time);
 142
 143   return trace;
 144 }
 145
 146
 147 static cpu_ti_t cpu_ti_new(char *name, double power_peak,
 148                            double power_scale,
 149                            tmgr_trace_t power_trace,
 150                            e_surf_resource_state_t state_initial,
 151                            tmgr_trace_t state_trace,
 152                            xbt_dict_t cpu_properties)
 153 {
 154   tmgr_trace_t empty_trace;
 155   s_tmgr_event_t val;
 156   cpu_ti_t cpu = xbt_new0(s_cpu_ti_t, 1);
 157   s_surf_action_cpu_ti_t ti_action;
 158   xbt_assert1(!surf_model_resource_by_name(surf_cpu_model, name),
 159               "Host '%s' declared several times in the platform file",
 160               name);
 161   cpu->action_set =
 162       xbt_swag_new(xbt_swag_offset(ti_action, cpu_list_hookup));
 163   cpu->generic_resource.model = surf_cpu_model;
 164   cpu->generic_resource.name = name;
 165   cpu->generic_resource.properties = cpu_properties;
 166   cpu->power_peak = power_peak;
 167   xbt_assert0(cpu->power_peak > 0, "Power has to be >0");
 168   DEBUG1("power scale %lf", power_scale);
 169   cpu->power_scale = power_scale;
 170   cpu->avail_trace = cpu_ti_parse_trace(power_trace, power_scale);
 171   cpu->state_current = state_initial;
 172   if (state_trace)
 173     cpu->state_event =
 174         tmgr_history_add_trace(history, state_trace, 0.0, 0, cpu);
 175   if (power_trace && xbt_dynar_length(power_trace->event_list) > 1) {
 176     /* add a fake trace event if periodicity == 0 */
 177     xbt_dynar_get_cpy(power_trace->event_list,
 178                       xbt_dynar_length(power_trace->event_list) - 1, &val);
 179     if (val.delta == 0) {
 180       empty_trace = tmgr_empty_trace_new();
 181       cpu->power_event =
 182           tmgr_history_add_trace(history, empty_trace,
 183                                  cpu->avail_trace->last_time, 0, cpu);
 184     }
 185   }
 186   xbt_dict_set(surf_model_resource_set(surf_cpu_model), name, cpu,
 187                surf_resource_free);
 188
 189   return cpu;
 190 }
 191
 192
 193 static void parse_cpu_ti_init(void)
 194 {
 195   double power_peak = 0.0;
 196   double power_scale = 0.0;
 197   tmgr_trace_t power_trace = NULL;
 198   e_surf_resource_state_t state_initial = SURF_RESOURCE_OFF;
 199   tmgr_trace_t state_trace = NULL;
 200
 201   power_peak = get_cpu_power(A_surfxml_host_power);
 202   surf_parse_get_double(&power_scale, A_surfxml_host_availability);
 203   power_trace = tmgr_trace_new(A_surfxml_host_availability_file);
 204
 205   xbt_assert0((A_surfxml_host_state == A_surfxml_host_state_ON) ||
 206               (A_surfxml_host_state == A_surfxml_host_state_OFF),
 207               "Invalid state");
 208   if (A_surfxml_host_state == A_surfxml_host_state_ON)
 209     state_initial = SURF_RESOURCE_ON;
 210   if (A_surfxml_host_state == A_surfxml_host_state_OFF)
 211     state_initial = SURF_RESOURCE_OFF;
 212   state_trace = tmgr_trace_new(A_surfxml_host_state_file);
 213
 214   current_property_set = xbt_dict_new();
 215   cpu_ti_new(xbt_strdup(A_surfxml_host_id), power_peak, power_scale,
 216              power_trace, state_initial, state_trace,
 217              current_property_set);
 218
 219 }
 220
 221 static void add_traces_cpu_ti(void)
 222 {
 223   xbt_dict_cursor_t cursor = NULL;
 224   char *trace_name, *elm;
 225
 226   static int called = 0;
 227
 228   if (called)
 229     return;
 230   called = 1;
 231
 232 /* connect all traces relative to hosts */
 233   xbt_dict_foreach(trace_connect_list_host_avail, cursor, trace_name, elm) {
 234     tmgr_trace_t trace = xbt_dict_get_or_null(traces_set_list, trace_name);
 235     cpu_ti_t cpu = surf_model_resource_by_name(surf_cpu_model, elm);
 236
 237     xbt_assert1(cpu, "Host %s undefined", elm);
 238     xbt_assert1(trace, "Trace %s undefined", trace_name);
 239
 240     if (cpu->state_event) {
 241       DEBUG1("Trace already configured for this CPU(%s), ignoring it",
 242              elm);
 243       continue;
 244     }
 245     DEBUG2("Add state trace: %s to CPU(%s)", trace_name, elm);
 246     cpu->state_event = tmgr_history_add_trace(history, trace, 0.0, 0, cpu);
 247   }
 248
 249   xbt_dict_foreach(trace_connect_list_power, cursor, trace_name, elm) {
 250     tmgr_trace_t trace = xbt_dict_get_or_null(traces_set_list, trace_name);
 251     cpu_ti_t cpu = surf_model_resource_by_name(surf_cpu_model, elm);
 252
 253     xbt_assert1(cpu, "Host %s undefined", elm);
 254     xbt_assert1(trace, "Trace %s undefined", trace_name);
 255
 256     DEBUG2("Add power trace: %s to CPU(%s)", trace_name, elm);
 257     if (cpu->avail_trace)
 258       surf_cpu_ti_free_tmgr(cpu->avail_trace);
 259
 260     cpu->avail_trace = cpu_ti_parse_trace(trace, cpu->power_scale);
 261
 262     /* add a fake trace event if periodicity == 0 */
 263     if (trace && xbt_dynar_length(trace->event_list) > 1) {
 264       s_tmgr_event_t val;
 265       xbt_dynar_get_cpy(trace->event_list,
 266                         xbt_dynar_length(trace->event_list) - 1, &val);
 267       if (val.delta == 0) {
 268         tmgr_trace_t empty_trace;
 269         empty_trace = tmgr_empty_trace_new();
 270         cpu->power_event =
 271             tmgr_history_add_trace(history, empty_trace,
 272                                    cpu->avail_trace->last_time, 0, cpu);
 273       }
 274     }
 275   }
 276 }
 277
 278 static void cpu_ti_define_callbacks(const char *file)
 279 {
 280   surf_parse_reset_parser();
 281   surfxml_add_callback(STag_surfxml_host_cb_list, parse_cpu_ti_init);
 282   surfxml_add_callback(ETag_surfxml_platform_cb_list, &add_traces_cpu_ti);
 283 }
 284
 285 static int cpu_ti_resource_used(void *resource_id)
 286 {
 287   cpu_ti_t cpu = resource_id;
 288   return xbt_swag_size(cpu->action_set);
 289 }
 290
 291 static int cpu_ti_action_unref(surf_action_t action)
 292 {
 293   action->refcount--;
 294   if (!action->refcount) {
 295     xbt_swag_remove(action, action->state_set);
 296     /* remove from action_set */
 297     xbt_swag_remove(action, ACTION_GET_CPU(action)->action_set);
 298     /* remove from heap */
 299     xbt_heap_remove(cpu_ti_action_heap,
 300                     ((surf_action_cpu_ti_t) action)->index_heap);
 301     xbt_swag_insert(ACTION_GET_CPU(action), cpu_ti_modified_cpu);
 302     free(action);
 303     return 1;
 304   }
 305   return 0;
 306 }
 307
 308 static void cpu_ti_action_cancel(surf_action_t action)
 309 {
 310   surf_action_state_set(action, SURF_ACTION_FAILED);
 311   xbt_heap_remove(cpu_ti_action_heap,
 312                   ((surf_action_cpu_ti_t) action)->index_heap);
 313   xbt_swag_insert(ACTION_GET_CPU(action), cpu_ti_modified_cpu);
 314   return;
 315 }
 316
 317 static void cpu_ti_action_state_set(surf_action_t action,
 318                                     e_surf_action_state_t state)
 319 {
 320   surf_action_state_set(action, state);
 321   xbt_swag_insert(ACTION_GET_CPU(action), cpu_ti_modified_cpu);
 322   return;
 323 }
 324
 325 /**
 326 * \brief Update the remaining amount of actions
 327 *
 328 * \param        cpu             Cpu on which the actions are running
 329 * \param        now             Current time
 330 */
 331 static void cpu_ti_update_remaining_amount(cpu_ti_t cpu, double now)
 332 {
 333 #define GENERIC_ACTION(action) action->generic_action
 334   double area_total;
 335   surf_action_cpu_ti_t action;
 336
 337 /* already updated */
 338   if (cpu->last_update >= now)
 339     return;
 340
 341 /* calcule the surface */
 342   area_total =
 343       surf_cpu_ti_integrate_trace(cpu->avail_trace, cpu->last_update,
 344                                   now) * cpu->power_peak;
 345   DEBUG2("Flops total: %lf, Last update %lf", area_total,
 346          cpu->last_update);
 347
 348   xbt_swag_foreach(action, cpu->action_set) {
 349     /* action not running, skip it */
 350     if (GENERIC_ACTION(action).state_set !=
 351         surf_cpu_model->states.running_action_set)
 352       continue;
 353
 354     /* bogus priority, skip it */
 355     if (GENERIC_ACTION(action).priority <= 0)
 356       continue;
 357
 358     /* action suspended, skip it */
 359     if (action->suspended != 0)
 360       continue;
 361
 362     /* action don't need update */
 363     if (GENERIC_ACTION(action).start >= now)
 364       continue;
 365
 366     /* skip action that are finishing now */
 367     if (GENERIC_ACTION(action).finish >= 0
 368         && GENERIC_ACTION(action).finish <= now)
 369       continue;
 370
 371     /* update remaining */
 372     double_update(&(GENERIC_ACTION(action).remains),
 373                   area_total / (cpu->sum_priority *
 374                                 GENERIC_ACTION(action).priority));
 375     DEBUG2("Update remaining action(%p) remaining %lf", action,
 376            GENERIC_ACTION(action).remains);
 377   }
 378   cpu->last_update = now;
 379 #undef GENERIC_ACTION
 380 }
 381
 382 /**
 383 * \brief Update the finish date of action if necessary
 384 *
 385 * \param        cpu             Cpu on which the actions are running
 386 * \param        now             Current time
 387 */
 388 static void cpu_ti_update_action_finish_date(cpu_ti_t cpu, double now)
 389 {
 390 #define GENERIC_ACTION(action) action->generic_action
 391   surf_action_cpu_ti_t action;
 392   double sum_priority = 0.0, total_area, min_finish = -1;
 393
 394 /* update remaning amount of actions */
 395   cpu_ti_update_remaining_amount(cpu, now);
 396
 397   xbt_swag_foreach(action, cpu->action_set) {
 398     /* action not running, skip it */
 399     if (GENERIC_ACTION(action).state_set !=
 400         surf_cpu_model->states.running_action_set)
 401       continue;
 402
 403     /* bogus priority, skip it */
 404     if (GENERIC_ACTION(action).priority <= 0)
 405       continue;
 406
 407     /* action suspended, skip it */
 408     if (action->suspended != 0)
 409       continue;
 410
 411     sum_priority += 1.0 / GENERIC_ACTION(action).priority;
 412   }
 413   cpu->sum_priority = sum_priority;
 414
 415   xbt_swag_foreach(action, cpu->action_set) {
 416     min_finish = -1;
 417     /* action not running, skip it */
 418     if (GENERIC_ACTION(action).state_set !=
 419         surf_cpu_model->states.running_action_set)
 420       continue;
 421
 422     /* verify if the action is really running on cpu */
 423     if (action->suspended == 0 && GENERIC_ACTION(action).priority > 0) {
 424       /* total area needed to finish the action. Used in trace integration */
 425       total_area =
 426           (GENERIC_ACTION(action).remains) * sum_priority *
 427           GENERIC_ACTION(action).priority;
 428
 429       total_area /= cpu->power_peak;
 430
 431       GENERIC_ACTION(action).finish =
 432           surf_cpu_ti_solve_trace(cpu->avail_trace, now, total_area);
 433       /* verify which event will happen before (max_duration or finish time) */
 434       if ((GENERIC_ACTION(action).max_duration != NO_MAX_DURATION) &&
 435           (GENERIC_ACTION(action).start +
 436            GENERIC_ACTION(action).max_duration <
 437            GENERIC_ACTION(action).finish))
 438         min_finish = GENERIC_ACTION(action).start +
 439             GENERIC_ACTION(action).max_duration;
 440       else
 441         min_finish = GENERIC_ACTION(action).finish;
 442     } else {
 443       /* put the max duration time on heap */
 444       if (GENERIC_ACTION(action).max_duration != NO_MAX_DURATION)
 445         min_finish =
 446             (GENERIC_ACTION(action).start +
 447              GENERIC_ACTION(action).max_duration);
 448     }
 449     /* add in action heap */
 450     DEBUG2("action(%p) index %d", action, action->index_heap);
 451     if (action->index_heap >= 0) {
 452       surf_action_cpu_ti_t heap_act =
 453           xbt_heap_remove(cpu_ti_action_heap, action->index_heap);
 454       if (heap_act != action)
 455         DIE_IMPOSSIBLE;
 456     }
 457     if (min_finish != NO_MAX_DURATION)
 458       xbt_heap_push(cpu_ti_action_heap, action, min_finish);
 459
 460     DEBUG5
 461         ("Update finish time: Cpu(%s) Action: %p, Start Time: %lf Finish Time: %lf Max duration %lf",
 462          cpu->generic_resource.name, action, GENERIC_ACTION(action).start,
 463          GENERIC_ACTION(action).finish,
 464          GENERIC_ACTION(action).max_duration);
 465   }
 466 /* remove from modified cpu */
 467   xbt_swag_remove(cpu, cpu_ti_modified_cpu);
 468 #undef GENERIC_ACTION
 469 }
 470
 471 static double cpu_ti_share_resources(double now)
 472 {
 473   cpu_ti_t cpu, cpu_next;
 474   double min_action_duration = -1;
 475
 476 /* iterates over modified cpus to update share resources */
 477   xbt_swag_foreach_safe(cpu, cpu_next, cpu_ti_modified_cpu) {
 478     cpu_ti_update_action_finish_date(cpu, now);
 479   }
 480 /* get the min next event if heap not empty */
 481   if (xbt_heap_size(cpu_ti_action_heap) > 0)
 482     min_action_duration = xbt_heap_maxkey(cpu_ti_action_heap) - now;
 483
 484   DEBUG1("Share resources, min next event date: %lf", min_action_duration);
 485
 486   return min_action_duration;
 487 }
 488
 489 static void cpu_ti_update_actions_state(double now, double delta)
 490 {
 491 #define GENERIC_ACTION(action) action->generic_action
 492   surf_action_cpu_ti_t action;
 493   while ((xbt_heap_size(cpu_ti_action_heap) > 0)
 494          && (xbt_heap_maxkey(cpu_ti_action_heap) <= now)) {
 495     action = xbt_heap_pop(cpu_ti_action_heap);
 496     DEBUG1("Action %p: finish", action);
 497     GENERIC_ACTION(action).finish = surf_get_clock();
 498     /* set the remains to 0 due to precision problems when updating the remaining amount */
 499     GENERIC_ACTION(action).remains = 0;
 500     cpu_ti_action_state_set((surf_action_t) action, SURF_ACTION_DONE);
 501     /* update remaining amout of all actions */
 502     cpu_ti_update_remaining_amount(action->cpu, surf_get_clock());
 503   }
 504 #undef GENERIC_ACTION
 505 }
 506
 507 static void cpu_ti_update_resource_state(void *id,
 508                                          tmgr_trace_event_t event_type,
 509                                          double value, double date)
 510 {
 511   cpu_ti_t cpu = id;
 512   surf_action_cpu_ti_t action;
 513
 514   if (event_type == cpu->power_event) {
 515     tmgr_trace_t power_trace;
 516     surf_cpu_ti_tgmr_t trace;
 517     s_tmgr_event_t val;
 518
 519     DEBUG3("Finish trace date: %lf value %lf date %lf", surf_get_clock(),
 520            value, date);
 521     /* update remaining of actions and put in modified cpu swag */
 522     cpu_ti_update_remaining_amount(cpu, date);
 523     xbt_swag_insert(cpu, cpu_ti_modified_cpu);
 524
 525     power_trace = cpu->avail_trace->power_trace;
 526     xbt_dynar_get_cpy(power_trace->event_list,
 527                       xbt_dynar_length(power_trace->event_list) - 1, &val);
 528     /* free old trace */
 529     surf_cpu_ti_free_tmgr(cpu->avail_trace);
 530     cpu->power_scale = val.value;
 531
 532     trace = xbt_new0(s_surf_cpu_ti_tgmr_t, 1);
 533     trace->type = TRACE_FIXED;
 534     trace->value = val.value;
 535     DEBUG1("value %lf", val.value);
 536
 537     cpu->avail_trace = trace;
 538
 539     if (tmgr_trace_event_free(event_type))
 540       cpu->power_event = NULL;
 541
 542   } else if (event_type == cpu->state_event) {
 543     if (value > 0)
 544       cpu->state_current = SURF_RESOURCE_ON;
 545     else {
 546       cpu->state_current = SURF_RESOURCE_OFF;
 547
 548       /* put all action running on cpu to failed */
 549       xbt_swag_foreach(action, cpu->action_set) {
 550         if (surf_action_state_get((surf_action_t) action) ==
 551             SURF_ACTION_RUNNING
 552             || surf_action_state_get((surf_action_t) action) ==
 553             SURF_ACTION_READY
 554             || surf_action_state_get((surf_action_t) action) ==
 555             SURF_ACTION_NOT_IN_THE_SYSTEM) {
 556           action->generic_action.finish = date;
 557           cpu_ti_action_state_set((surf_action_t) action,
 558                                   SURF_ACTION_FAILED);
 559           if (action->index_heap >= 0) {
 560             surf_action_cpu_ti_t heap_act =
 561                 xbt_heap_remove(cpu_ti_action_heap, action->index_heap);
 562             if (heap_act != action)
 563               DIE_IMPOSSIBLE;
 564           }
 565         }
 566       }
 567     }
 568     if (tmgr_trace_event_free(event_type))
 569       cpu->state_event = NULL;
 570   } else {
 571     CRITICAL0("Unknown event ! \n");
 572     xbt_abort();
 573   }
 574
 575   return;
 576 }
 577
 578 static surf_action_t cpu_ti_execute(void *cpu, double size)
 579 {
 580   surf_action_cpu_ti_t action = NULL;
 581   cpu_ti_t CPU = cpu;
 582
 583   XBT_IN2("(%s,%g)", surf_resource_name(CPU), size);
 584   action =
 585       surf_action_new(sizeof(s_surf_action_cpu_ti_t), size, surf_cpu_model,
 586                       CPU->state_current != SURF_RESOURCE_ON);
 587   action->cpu = cpu;
 588   action->index_heap = -1;
 589
 590   xbt_swag_insert(CPU, cpu_ti_modified_cpu);
 591
 592   xbt_swag_insert(action, CPU->action_set);
 593
 594   action->suspended = 0;        /* Should be useless because of the
 595                                    calloc but it seems to help valgrind... */
 596
 597   XBT_OUT;
 598   return (surf_action_t) action;
 599 }
 600
 601 static void cpu_ti_action_update_index_heap(void *action, int i)
 602 {
 603   ((surf_action_cpu_ti_t) action)->index_heap = i;
 604 }
 605
 606 static surf_action_t cpu_ti_action_sleep(void *cpu, double duration)
 607 {
 608   surf_action_cpu_ti_t action = NULL;
 609
 610   if (duration > 0)
 611     duration = MAX(duration, MAXMIN_PRECISION);
 612
 613   XBT_IN2("(%s,%g)", surf_resource_name(cpu), duration);
 614   action = (surf_action_cpu_ti_t) cpu_ti_execute(cpu, 1.0);
 615   action->generic_action.max_duration = duration;
 616   action->suspended = 2;
 617   if (duration == NO_MAX_DURATION) {
 618     /* Move to the *end* of the corresponding action set. This convention
 619        is used to speed up update_resource_state  */
 620     xbt_swag_remove(action, ((surf_action_t) action)->state_set);
 621     ((surf_action_t) action)->state_set =
 622         cpu_ti_running_action_set_that_does_not_need_being_checked;
 623     xbt_swag_insert(action, ((surf_action_t) action)->state_set);
 624   }
 625   XBT_OUT;
 626   return (surf_action_t) action;
 627 }
 628
 629 static void cpu_ti_action_suspend(surf_action_t action)
 630 {
 631   XBT_IN1("(%p)", action);
 632   if (((surf_action_cpu_ti_t) action)->suspended != 2) {
 633     ((surf_action_cpu_ti_t) action)->suspended = 1;
 634     xbt_heap_remove(cpu_ti_action_heap,
 635                     ((surf_action_cpu_ti_t) action)->index_heap);
 636     xbt_swag_insert(ACTION_GET_CPU(action), cpu_ti_modified_cpu);
 637   }
 638   XBT_OUT;
 639 }
 640
 641 static void cpu_ti_action_resume(surf_action_t action)
 642 {
 643   XBT_IN1("(%p)", action);
 644   if (((surf_action_cpu_ti_t) action)->suspended != 2) {
 645     ((surf_action_cpu_ti_t) action)->suspended = 0;
 646     xbt_swag_insert(ACTION_GET_CPU(action), cpu_ti_modified_cpu);
 647   }
 648   XBT_OUT;
 649 }
 650
 651 static int cpu_ti_action_is_suspended(surf_action_t action)
 652 {
 653   return (((surf_action_cpu_ti_t) action)->suspended == 1);
 654 }
 655
 656 static void cpu_ti_action_set_max_duration(surf_action_t action,
 657                                            double duration)
 658 {
 659   surf_action_cpu_ti_t ACT = (surf_action_cpu_ti_t) action;
 660   double min_finish;
 661
 662   XBT_IN2("(%p,%g)", action, duration);
 663
 664   action->max_duration = duration;
 665
 666   if (duration >= 0)
 667     min_finish =
 668         (action->start + action->max_duration) <
 669         action->finish ? (action->start +
 670                           action->max_duration) : action->finish;
 671   else
 672     min_finish = action->finish;
 673
 674 /* add in action heap */
 675   if (ACT->index_heap >= 0) {
 676     surf_action_cpu_ti_t heap_act =
 677         xbt_heap_remove(cpu_ti_action_heap, ACT->index_heap);
 678     if (heap_act != ACT)
 679       DIE_IMPOSSIBLE;
 680   }
 681   xbt_heap_push(cpu_ti_action_heap, ACT, min_finish);
 682
 683   XBT_OUT;
 684 }
 685
 686 static void cpu_ti_action_set_priority(surf_action_t action,
 687                                        double priority)
 688 {
 689   XBT_IN2("(%p,%g)", action, priority);
 690   action->priority = priority;
 691   xbt_swag_insert(ACTION_GET_CPU(action), cpu_ti_modified_cpu);
 692   XBT_OUT;
 693 }
 694
 695 static double cpu_ti_action_get_remains(surf_action_t action)
 696 {
 697   XBT_IN1("(%p)", action);
 698   cpu_ti_update_remaining_amount((cpu_ti_t)
 699                                  ((surf_action_cpu_ti_t) action)->cpu,
 700                                  surf_get_clock());
 701   return action->remains;
 702   XBT_OUT;
 703 }
 704
 705 static e_surf_resource_state_t cpu_ti_get_state(void *cpu)
 706 {
 707   return ((cpu_ti_t) cpu)->state_current;
 708 }
 709
 710 static double cpu_ti_get_speed(void *cpu, double load)
 711 {
 712   return load * (((cpu_ti_t) cpu)->power_peak);
 713 }
 714
 715 /**
 716 * \brief Auxiliary function to update the CPU power scale.
 717 *
 718 *       This function uses the trace structure to return the power scale at the determined time a.
 719 * \param trace          Trace structure to search the updated power scale
 720 * \param a                              Time
 721 * \return CPU power scale
 722 */
 723 static double surf_cpu_ti_get_power_scale(surf_cpu_ti_tgmr_t trace,
 724                                           double a)
 725 {
 726   double reduced_a;
 727   int point;
 728   s_tmgr_event_t val;
 729
 730   reduced_a = a - floor(a / trace->last_time) * trace->last_time;
 731   point =
 732       surf_cpu_ti_binary_search(trace->trace->time_points, reduced_a, 0,
 733                                 trace->trace->nb_points - 1);
 734   xbt_dynar_get_cpy(trace->power_trace->event_list, 0, &val);
 735   return val.value;
 736 }
 737
 738 static double cpu_ti_get_available_speed(void *cpu)
 739 {
 740   cpu_ti_t CPU = cpu;
 741   CPU->power_scale =
 742       surf_cpu_ti_get_power_scale(CPU->avail_trace, surf_get_clock());
 743 /* number between 0 and 1 */
 744   return CPU->power_scale;
 745 }
 746
 747 static void cpu_ti_create_resource(char *name, double power_peak,
 748                                    double power_scale,
 749                                    tmgr_trace_t power_trace,
 750                                    e_surf_resource_state_t state_initial,
 751                                    tmgr_trace_t state_trace,
 752                                    xbt_dict_t cpu_properties)
 753 {
 754   cpu_ti_new(name, power_peak, power_scale, power_trace,
 755              state_initial, state_trace, cpu_properties);
 756 }
 757
 758 static void cpu_ti_finalize(void)
 759 {
 760   void *cpu;
 761   xbt_dict_cursor_t cursor;
 762   char *key;
 763   xbt_dict_foreach(surf_model_resource_set(surf_cpu_model), cursor, key,
 764                    cpu) {
 765     cpu_ti_t CPU = cpu;
 766     xbt_swag_free(CPU->action_set);
 767     surf_cpu_ti_free_tmgr(CPU->avail_trace);
 768   }
 769
 770   surf_model_exit(surf_cpu_model);
 771   surf_cpu_model = NULL;
 772
 773   xbt_swag_free
 774       (cpu_ti_running_action_set_that_does_not_need_being_checked);
 775   xbt_swag_free(cpu_ti_modified_cpu);
 776   cpu_ti_running_action_set_that_does_not_need_being_checked = NULL;
 777   xbt_heap_free(cpu_ti_action_heap);
 778 }
 779
 780 static void surf_cpu_ti_model_init_internal(void)
 781 {
 782   s_surf_action_t action;
 783   s_cpu_ti_t cpu;
 784
 785   surf_cpu_model = surf_model_init();
 786
 787   cpu_ti_running_action_set_that_does_not_need_being_checked =
 788       xbt_swag_new(xbt_swag_offset(action, state_hookup));
 789
 790   cpu_ti_modified_cpu =
 791       xbt_swag_new(xbt_swag_offset(cpu, modified_cpu_hookup));
 792
 793   surf_cpu_model->name = "CPU_TI";
 794
 795   surf_cpu_model->action_unref = cpu_ti_action_unref;
 796   surf_cpu_model->action_cancel = cpu_ti_action_cancel;
 797   surf_cpu_model->action_state_set = cpu_ti_action_state_set;
 798
 799   surf_cpu_model->model_private->resource_used = cpu_ti_resource_used;
 800   surf_cpu_model->model_private->share_resources = cpu_ti_share_resources;
 801   surf_cpu_model->model_private->update_actions_state =
 802       cpu_ti_update_actions_state;
 803   surf_cpu_model->model_private->update_resource_state =
 804       cpu_ti_update_resource_state;
 805   surf_cpu_model->model_private->finalize = cpu_ti_finalize;
 806
 807   surf_cpu_model->suspend = cpu_ti_action_suspend;
 808   surf_cpu_model->resume = cpu_ti_action_resume;
 809   surf_cpu_model->is_suspended = cpu_ti_action_is_suspended;
 810   surf_cpu_model->set_max_duration = cpu_ti_action_set_max_duration;
 811   surf_cpu_model->set_priority = cpu_ti_action_set_priority;
 812   surf_cpu_model->get_remains = cpu_ti_action_get_remains;
 813
 814   surf_cpu_model->extension.cpu.execute = cpu_ti_execute;
 815   surf_cpu_model->extension.cpu.sleep = cpu_ti_action_sleep;
 816
 817   surf_cpu_model->extension.cpu.get_state = cpu_ti_get_state;
 818   surf_cpu_model->extension.cpu.get_speed = cpu_ti_get_speed;
 819   surf_cpu_model->extension.cpu.get_available_speed =
 820       cpu_ti_get_available_speed;
 821   surf_cpu_model->extension.cpu.create_resource = cpu_ti_create_resource;
 822   surf_cpu_model->extension.cpu.add_traces = add_traces_cpu_ti;
 823
 824   cpu_ti_action_heap = xbt_heap_new(8, NULL);
 825   xbt_heap_set_update_callback(cpu_ti_action_heap,
 826                                cpu_ti_action_update_index_heap);
 827
 828 }
 829
 830 void surf_cpu_model_init_ti(const char *filename)
 831 {
 832   if (surf_cpu_model)
 833     return;
 834   surf_cpu_ti_model_init_internal();
 835   cpu_ti_define_callbacks(filename);
 836   xbt_dynar_push(model_list, &surf_cpu_model);
 837 }
 838
 839
 840 /**
 841 * \brief Integrate trace
 842 *
 843 * Wrapper around surf_cpu_integrate_trace_simple() to get
 844 * the cyclic effect.
 845 *
 846 * \param trace Trace structure.
 847 * \param a                      Begin of interval
 848 * \param b                      End of interval
 849 * \return the integrate value. -1 if an error occurs.
 850 */
 851 static double surf_cpu_ti_integrate_trace(surf_cpu_ti_tgmr_t trace,
 852                                           double a, double b)
 853 {
 854   double first_chunk;
 855   double middle_chunk;
 856   double last_chunk;
 857   int a_index, b_index;
 858
 859   if ((a < 0.0) || (a > b)) {
 860     CRITICAL2
 861         ("Error, invalid integration interval [%.2f,%.2f]. You probably have a task executing with negative computation amount. Check your code.",
 862          a, b);
 863     xbt_abort();
 864   }
 865   if (a == b)
 866     return 0.0;
 867
 868   if (trace->type == TRACE_FIXED) {
 869     return ((b - a) * trace->value);
 870   }
 871
 872   if (ceil(a / trace->last_time) == a / trace->last_time)
 873     a_index = 1 + (int) (ceil(a / trace->last_time));
 874   else
 875     a_index = (int) (ceil(a / trace->last_time));
 876
 877   b_index = (int) (floor(b / trace->last_time));
 878
 879   if (a_index > b_index) {      /* Same chunk */
 880     return surf_cpu_ti_integrate_trace_simple(trace->trace,
 881                                               a - (a_index -
 882                                                    1) * trace->last_time,
 883                                               b -
 884                                               (b_index) *
 885                                               trace->last_time);
 886   }
 887
 888   first_chunk = surf_cpu_ti_integrate_trace_simple(trace->trace,
 889                                                    a - (a_index -
 890                                                         1) *
 891                                                    trace->last_time,
 892                                                    trace->last_time);
 893   middle_chunk = (b_index - a_index) * trace->total;
 894   last_chunk = surf_cpu_ti_integrate_trace_simple(trace->trace,
 895                                                   0.0,
 896                                                   b -
 897                                                   (b_index) *
 898                                                   trace->last_time);
 899
 900   DEBUG3("first_chunk=%.2f  middle_chunk=%.2f  last_chunk=%.2f\n",
 901          first_chunk, middle_chunk, last_chunk);
 902
 903   return (first_chunk + middle_chunk + last_chunk);
 904 }
 905
 906 /**
 907  * \brief Auxiliary function to calculate the integral between a and b.
 908  *              It simply calculates the integral at point a and b and returns the difference
 909  *      between them.
 910  * \param trace         Trace structure
 911  * \param a                             Initial point
 912  * \param b     Final point
 913  * \return      Integral
 914 */
 915 static double surf_cpu_ti_integrate_trace_simple(surf_cpu_ti_trace_t trace,
 916                                                  double a, double b)
 917 {
 918   return surf_cpu_ti_integrate_trace_simple_point(trace,
 919                                                   b) -
 920       surf_cpu_ti_integrate_trace_simple_point(trace, a);
 921 }
 922
 923 /**
 924  * \brief Auxiliary function to calculate the integral at point a.
 925  * \param trace         Trace structure
 926  * \param a                             point
 927  * \return      Integral
 928 */
 929 static double surf_cpu_ti_integrate_trace_simple_point(surf_cpu_ti_trace_t
 930                                                        trace, double a)
 931 {
 932   double integral = 0;
 933   int ind;
 934   double a_aux = a;
 935   ind =
 936       surf_cpu_ti_binary_search(trace->time_points, a, 0,
 937                                 trace->nb_points - 1);
 938   integral += trace->integral[ind];
 939   DEBUG7
 940       ("a %lf ind %d integral %lf ind + 1 %lf ind %lf time +1 %lf time %lf",
 941        a, ind, integral, trace->integral[ind + 1], trace->integral[ind],
 942        trace->time_points[ind + 1], trace->time_points[ind]);
 943   double_update(&a_aux, trace->time_points[ind]);
 944   if (a_aux > 0)
 945     integral +=
 946         ((trace->integral[ind + 1] -
 947           trace->integral[ind]) / (trace->time_points[ind + 1] -
 948                                    trace->time_points[ind])) * (a -
 949                                                                 trace->
 950                                                                 time_points
 951                                                                 [ind]);
 952   DEBUG2("Integral a %lf = %lf", a, integral);
 953
 954   return integral;
 955 }
 956
 957 /**
 958 * \brief Calculate the time needed to execute "amount" on cpu.
 959 *
 960 * Here, amount can span multiple trace periods
 961 *
 962 * \param trace  CPU trace structure
 963 * \param a                              Initial time
 964 * \param amount Amount to be executed
 965 * \return       End time
 966 */
 967 static double surf_cpu_ti_solve_trace(surf_cpu_ti_tgmr_t trace, double a,
 968                                       double amount)
 969 {
 970   int quotient;
 971   double reduced_b;
 972   double reduced_amount;
 973   double reduced_a;
 974   double b;
 975
 976 /* Fix very small negative numbers */
 977   if ((a < 0.0) && (a > -EPSILON)) {
 978     a = 0.0;
 979   }
 980   if ((amount < 0.0) && (amount > -EPSILON)) {
 981     amount = 0.0;
 982   }
 983
 984 /* Sanity checks */
 985   if ((a < 0.0) || (amount < 0.0)) {
 986     CRITICAL2
 987         ("Error, invalid parameters [a = %.2f, amount = %.2f]. You probably have a task executing with negative computation amount. Check your code.",
 988          a, amount);
 989     xbt_abort();
 990   }
 991
 992 /* At this point, a and amount are positive */
 993
 994   if (amount < EPSILON)
 995     return a;
 996
 997 /* Is the trace fixed ? */
 998   if (trace->type == TRACE_FIXED) {
 999     return (a + (amount / trace->value));
1000   }
1001
1002   DEBUG2("amount %lf total %lf", amount, trace->total);
1003 /* Reduce the problem to one where amount <= trace_total */
1004   quotient = (int) (floor(amount / trace->total));
1005   reduced_amount = (trace->total) * ((amount / trace->total) -
1006                                      floor(amount / trace->total));
1007   reduced_a = a - (trace->last_time) * (int) (floor(a / trace->last_time));
1008
1009   DEBUG3("Quotient: %d reduced_amount: %lf reduced_a: %lf", quotient,
1010          reduced_amount, reduced_a);
1011
1012 /* Now solve for new_amount which is <= trace_total */
1013 /*
1014          fprintf(stderr,"reduced_a = %.2f\n",reduced_a);
1015          fprintf(stderr,"reduced_amount = %.2f\n",reduced_amount);
1016  */
1017   reduced_b =
1018       surf_cpu_ti_solve_trace_somewhat_simple(trace, reduced_a,
1019                                               reduced_amount);
1020
1021 /* Re-map to the original b and amount */
1022   b = (trace->last_time) * (int) (floor(a / trace->last_time)) +
1023       (quotient * trace->last_time) + reduced_b;
1024   return b;
1025 }
1026
1027 /**
1028 * \brief Auxiliary function to solve integral
1029 *
1030 * Here, amount is <= trace->total
1031 * and a <=trace->last_time
1032 *
1033 */
1034 static double surf_cpu_ti_solve_trace_somewhat_simple(surf_cpu_ti_tgmr_t
1035                                                       trace, double a,
1036                                                       double amount)
1037 {
1038   double amount_till_end;
1039   double b;
1040
1041   DEBUG2("Solve integral: [%.2f, amount=%.2f]", a, amount);
1042   amount_till_end =
1043       surf_cpu_ti_integrate_trace(trace, a, trace->last_time);
1044 /*
1045          fprintf(stderr,"amount_till_end=%.2f\n",amount_till_end);
1046  */
1047
1048   if (amount_till_end > amount) {
1049     b = surf_cpu_ti_solve_trace_simple(trace->trace, a, amount);
1050   } else {
1051     b = trace->last_time +
1052         surf_cpu_ti_solve_trace_simple(trace->trace, 0.0,
1053                                        amount - amount_till_end);
1054   }
1055   return b;
1056 }
1057
1058 /**
1059  * \brief Auxiliary function to solve integral.
1060  *      It returns the date when the requested amount of flops is available
1061  * \param trace         Trace structure
1062  * \param a                             Initial point
1063  * \param amount        Amount of flops
1064  * \return The date when amount is available.
1065 */
1066 static double surf_cpu_ti_solve_trace_simple(surf_cpu_ti_trace_t trace,
1067                                              double a, double amount)
1068 {
1069   double integral_a;
1070   int ind;
1071   double time;
1072   integral_a = surf_cpu_ti_integrate_trace_simple_point(trace, a);
1073   ind =
1074       surf_cpu_ti_binary_search(trace->integral, integral_a + amount, 0,
1075                                 trace->nb_points - 1);
1076   time = trace->time_points[ind];
1077   time +=
1078       (integral_a + amount -
1079        trace->integral[ind]) / ((trace->integral[ind + 1] -
1080                                  trace->integral[ind]) /
1081                                 (trace->time_points[ind + 1] -
1082                                  trace->time_points[ind]));
1083
1084   return time;
1085 }
1086
1087 /**
1088  * \brief Binary search in array.
1089  *      It returns the first point of the interval in which "a" is.
1090  * \param array         Array
1091  * \param a                             Value to search
1092  * \param low           Low bound to search in array
1093  * \param high          Upper bound to search in array
1094  * \return Index of point
1095 */
1096 static int surf_cpu_ti_binary_search(double *array, double a, int low,
1097                                      int high)
1098 {
1099   int mid = low + (high - low) / 2;
1100   DEBUG5("a %lf low %d high %d mid %d value %lf", a, low, high, mid,
1101          array[mid]);
1102   /* a == array[mid] */
1103   if (array[mid] == a)
1104     return mid;
1105   /* a is between mid and mid+1 */
1106   if (array[mid] < a && array[mid + 1] > a)
1107     return mid;
1108
1109   if (array[mid] < a)
1110     return surf_cpu_ti_binary_search(array, a, mid + 1, high);
1111   else
1112     return surf_cpu_ti_binary_search(array, a, low, mid - 1);
1113 }