src/surf/cpu_ti.cpp

   1 #include "cpu_ti.hpp"
   2 #include "solver.hpp"
   3
   4 #ifndef SURF_MODEL_CPUTI_H_
   5 #define SURF_MODEL_CPUTI_H_
   6
   7 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_cpu_tii, surf,
   8                                 "Logging specific to the SURF CPU TRACE INTEGRATION module");
   9
  10 static std::vector<CpuTiActionPtr>
  11     cpu_ti_running_action_set_that_does_not_need_being_checked;
  12 static std::vector<CpuTiPtr> cpu_ti_modified_cpu;
  13 static std::vector<CpuTiActionPtr> cpu_ti_action_heap;
  14
  15 /*********
  16  * Trace *
  17  *********/
  18 static double surf_cpu_ti_integrate_trace(surf_cpu_ti_tgmr_t trace,
  19                                           double a, double b);
  20
  21
  22 static double surf_cpu_ti_solve_trace(surf_cpu_ti_tgmr_t trace, double a,
  23                                       double amount);
  24 static double surf_cpu_ti_solve_trace_somewhat_simple(surf_cpu_ti_tgmr_t
  25                                                       trace, double a,
  26                                                       double amount);
  27
  28 static void surf_cpu_ti_free_tmgr(surf_cpu_ti_tgmr_t trace);
  29
  30 static double surf_cpu_ti_integrate_trace_simple(surf_cpu_ti_trace_t trace,
  31                                                  double a, double b);
  32 static double surf_cpu_ti_integrate_trace_simple_point(surf_cpu_ti_trace_t
  33                                                        trace, double a);
  34 static double surf_cpu_ti_solve_trace_simple(surf_cpu_ti_trace_t trace,
  35                                              double a, double amount);
  36 static int surf_cpu_ti_binary_search(double *array, double a, int low,
  37                                      int high);
  38
  39 static void surf_cpu_ti_free_trace(surf_cpu_ti_trace_t trace)
  40 {
  41   xbt_free(trace->time_points);
  42   xbt_free(trace->integral);
  43   xbt_free(trace);
  44 }
  45
  46 static void surf_cpu_ti_free_tmgr(surf_cpu_ti_tgmr_t trace)
  47 {
  48   if (trace->trace)
  49     surf_cpu_ti_free_trace(trace->trace);
  50   xbt_free(trace);
  51 }
  52
  53 static surf_cpu_ti_trace_t surf_cpu_ti_trace_new(tmgr_trace_t power_trace)
  54 {
  55   surf_cpu_ti_trace_t trace;
  56   s_tmgr_event_t val;
  57   unsigned int cpt;
  58   double integral = 0;
  59   double time = 0;
  60   int i = 0;
  61   trace = xbt_new0(s_surf_cpu_ti_trace_t, 1);
  62   trace->time_points = (double*) xbt_malloc0(sizeof(double) *
  63                   (xbt_dynar_length(power_trace->s_list.event_list) + 1));
  64   trace->integral = (double*) xbt_malloc0(sizeof(double) *
  65                   (xbt_dynar_length(power_trace->s_list.event_list) + 1));
  66   trace->nb_points = xbt_dynar_length(power_trace->s_list.event_list);
  67   xbt_dynar_foreach(power_trace->s_list.event_list, cpt, val) {
  68     trace->time_points[i] = time;
  69     trace->integral[i] = integral;
  70     integral += val.delta * val.value;
  71     time += val.delta;
  72     i++;
  73   }
  74   trace->time_points[i] = time;
  75   trace->integral[i] = integral;
  76   return trace;
  77 }
  78
  79 /**
  80 * \brief Integrate trace
  81 *
  82 * Wrapper around surf_cpu_integrate_trace_simple() to get
  83 * the cyclic effect.
  84 *
  85 * \param trace Trace structure.
  86 * \param a      Begin of interval
  87 * \param b      End of interval
  88 * \return the integrate value. -1 if an error occurs.
  89 */
  90 static double surf_cpu_ti_integrate_trace(surf_cpu_ti_tgmr_t trace,
  91                                           double a, double b)
  92 {
  93   double first_chunk;
  94   double middle_chunk;
  95   double last_chunk;
  96   int a_index, b_index;
  97
  98   if ((a < 0.0) || (a > b)) {
  99     XBT_CRITICAL
 100         ("Error, invalid integration interval [%.2f,%.2f]. You probably have a task executing with negative computation amount. Check your code.",
 101          a, b);
 102     xbt_abort();
 103   }
 104   if (a == b)
 105     return 0.0;
 106
 107   if (trace->type == TRACE_FIXED) {
 108     return ((b - a) * trace->value);
 109   }
 110
 111   if (ceil(a / trace->last_time) == a / trace->last_time)
 112     a_index = 1 + (int) (ceil(a / trace->last_time));
 113   else
 114     a_index = (int) (ceil(a / trace->last_time));
 115
 116   b_index = (int) (floor(b / trace->last_time));
 117
 118   if (a_index > b_index) {      /* Same chunk */
 119     return surf_cpu_ti_integrate_trace_simple(trace->trace,
 120                                               a - (a_index -
 121                                                    1) * trace->last_time,
 122                                               b -
 123                                               (b_index) *
 124                                               trace->last_time);
 125   }
 126
 127   first_chunk = surf_cpu_ti_integrate_trace_simple(trace->trace,
 128                                                    a - (a_index -
 129                                                         1) *
 130                                                    trace->last_time,
 131                                                    trace->last_time);
 132   middle_chunk = (b_index - a_index) * trace->total;
 133   last_chunk = surf_cpu_ti_integrate_trace_simple(trace->trace,
 134                                                   0.0,
 135                                                   b -
 136                                                   (b_index) *
 137                                                   trace->last_time);
 138
 139   XBT_DEBUG("first_chunk=%.2f  middle_chunk=%.2f  last_chunk=%.2f\n",
 140          first_chunk, middle_chunk, last_chunk);
 141
 142   return (first_chunk + middle_chunk + last_chunk);
 143 }
 144
 145 /**
 146  * \brief Auxiliary function to calculate the integral between a and b.
 147  *     It simply calculates the integral at point a and b and returns the difference
 148  *   between them.
 149  * \param trace    Trace structure
 150  * \param a        Initial point
 151  * \param b  Final point
 152  * \return  Integral
 153 */
 154 static double surf_cpu_ti_integrate_trace_simple(surf_cpu_ti_trace_t trace,
 155                                                  double a, double b)
 156 {
 157   return surf_cpu_ti_integrate_trace_simple_point(trace,
 158                                                   b) -
 159       surf_cpu_ti_integrate_trace_simple_point(trace, a);
 160 }
 161
 162 /**
 163  * \brief Auxiliary function to calculate the integral at point a.
 164  * \param trace    Trace structure
 165  * \param a        point
 166  * \return  Integral
 167 */
 168 static double surf_cpu_ti_integrate_trace_simple_point(surf_cpu_ti_trace_t
 169                                                        trace, double a)
 170 {
 171   double integral = 0;
 172   int ind;
 173   double a_aux = a;
 174   ind =
 175       surf_cpu_ti_binary_search(trace->time_points, a, 0,
 176                                 trace->nb_points - 1);
 177   integral += trace->integral[ind];
 178   XBT_DEBUG
 179       ("a %lf ind %d integral %lf ind + 1 %lf ind %lf time +1 %lf time %lf",
 180        a, ind, integral, trace->integral[ind + 1], trace->integral[ind],
 181        trace->time_points[ind + 1], trace->time_points[ind]);
 182   double_update(&a_aux, trace->time_points[ind]);
 183   if (a_aux > 0)
 184     integral +=
 185         ((trace->integral[ind + 1] -
 186           trace->integral[ind]) / (trace->time_points[ind + 1] -
 187                                    trace->time_points[ind])) * (a -
 188                                                                 trace->
 189                                                                 time_points
 190                                                                 [ind]);
 191   XBT_DEBUG("Integral a %lf = %lf", a, integral);
 192
 193   return integral;
 194 }
 195
 196 /**
 197 * \brief Calculate the time needed to execute "amount" on cpu.
 198 *
 199 * Here, amount can span multiple trace periods
 200 *
 201 * \param trace   CPU trace structure
 202 * \param a        Initial time
 203 * \param amount  Amount to be executed
 204 * \return  End time
 205 */
 206 static double surf_cpu_ti_solve_trace(surf_cpu_ti_tgmr_t trace, double a,
 207                                       double amount)
 208 {
 209   int quotient;
 210   double reduced_b;
 211   double reduced_amount;
 212   double reduced_a;
 213   double b;
 214
 215 /* Fix very small negative numbers */
 216   if ((a < 0.0) && (a > -EPSILON)) {
 217     a = 0.0;
 218   }
 219   if ((amount < 0.0) && (amount > -EPSILON)) {
 220     amount = 0.0;
 221   }
 222
 223 /* Sanity checks */
 224   if ((a < 0.0) || (amount < 0.0)) {
 225     XBT_CRITICAL
 226         ("Error, invalid parameters [a = %.2f, amount = %.2f]. You probably have a task executing with negative computation amount. Check your code.",
 227          a, amount);
 228     xbt_abort();
 229   }
 230
 231 /* At this point, a and amount are positive */
 232
 233   if (amount < EPSILON)
 234     return a;
 235
 236 /* Is the trace fixed ? */
 237   if (trace->type == TRACE_FIXED) {
 238     return (a + (amount / trace->value));
 239   }
 240
 241   XBT_DEBUG("amount %lf total %lf", amount, trace->total);
 242 /* Reduce the problem to one where amount <= trace_total */
 243   quotient = (int) (floor(amount / trace->total));
 244   reduced_amount = (trace->total) * ((amount / trace->total) -
 245                                      floor(amount / trace->total));
 246   reduced_a = a - (trace->last_time) * (int) (floor(a / trace->last_time));
 247
 248   XBT_DEBUG("Quotient: %d reduced_amount: %lf reduced_a: %lf", quotient,
 249          reduced_amount, reduced_a);
 250
 251 /* Now solve for new_amount which is <= trace_total */
 252 /*
 253    fprintf(stderr,"reduced_a = %.2f\n",reduced_a);
 254    fprintf(stderr,"reduced_amount = %.2f\n",reduced_amount);
 255  */
 256   reduced_b =
 257       surf_cpu_ti_solve_trace_somewhat_simple(trace, reduced_a,
 258                                               reduced_amount);
 259
 260 /* Re-map to the original b and amount */
 261   b = (trace->last_time) * (int) (floor(a / trace->last_time)) +
 262       (quotient * trace->last_time) + reduced_b;
 263   return b;
 264 }
 265
 266 /**
 267 * \brief Auxiliary function to solve integral
 268 *
 269 * Here, amount is <= trace->total
 270 * and a <=trace->last_time
 271 *
 272 */
 273 static double surf_cpu_ti_solve_trace_somewhat_simple(surf_cpu_ti_tgmr_t
 274                                                       trace, double a,
 275                                                       double amount)
 276 {
 277   double amount_till_end;
 278   double b;
 279
 280   XBT_DEBUG("Solve integral: [%.2f, amount=%.2f]", a, amount);
 281   amount_till_end =
 282       surf_cpu_ti_integrate_trace(trace, a, trace->last_time);
 283 /*
 284    fprintf(stderr,"amount_till_end=%.2f\n",amount_till_end);
 285  */
 286
 287   if (amount_till_end > amount) {
 288     b = surf_cpu_ti_solve_trace_simple(trace->trace, a, amount);
 289   } else {
 290     b = trace->last_time +
 291         surf_cpu_ti_solve_trace_simple(trace->trace, 0.0,
 292                                        amount - amount_till_end);
 293   }
 294   return b;
 295 }
 296
 297 /**
 298  * \brief Auxiliary function to solve integral.
 299  *  It returns the date when the requested amount of flops is available
 300  * \param trace    Trace structure
 301  * \param a        Initial point
 302  * \param amount  Amount of flops
 303  * \return The date when amount is available.
 304 */
 305 static double surf_cpu_ti_solve_trace_simple(surf_cpu_ti_trace_t trace,
 306                                              double a, double amount)
 307 {
 308   double integral_a;
 309   int ind;
 310   double time;
 311   integral_a = surf_cpu_ti_integrate_trace_simple_point(trace, a);
 312   ind =
 313       surf_cpu_ti_binary_search(trace->integral, integral_a + amount, 0,
 314                                 trace->nb_points - 1);
 315   time = trace->time_points[ind];
 316   time +=
 317       (integral_a + amount -
 318        trace->integral[ind]) / ((trace->integral[ind + 1] -
 319                                  trace->integral[ind]) /
 320                                 (trace->time_points[ind + 1] -
 321                                  trace->time_points[ind]));
 322
 323   return time;
 324 }
 325
 326 /**
 327 * \brief Creates a new integration trace from a tmgr_trace_t
 328 *
 329 * \param  power_trace    CPU availability trace
 330 * \param  value          Percentage of CPU power available (useful to fixed tracing)
 331 * \param  spacing        Initial spacing
 332 * \return  Integration trace structure
 333 */
 334 static surf_cpu_ti_tgmr_t cpu_ti_parse_trace(tmgr_trace_t power_trace,
 335                                              double value)
 336 {
 337   surf_cpu_ti_tgmr_t trace;
 338   double total_time = 0.0;
 339   s_tmgr_event_t val;
 340   unsigned int cpt;
 341   trace = xbt_new0(s_surf_cpu_ti_tgmr_t, 1);
 342
 343 /* no availability file, fixed trace */
 344   if (!power_trace) {
 345     trace->type = TRACE_FIXED;
 346     trace->value = value;
 347     XBT_DEBUG("No availabily trace. Constant value = %lf", value);
 348     return trace;
 349   }
 350
 351   /* only one point available, fixed trace */
 352   if (xbt_dynar_length(power_trace->s_list.event_list) == 1) {
 353     xbt_dynar_get_cpy(power_trace->s_list.event_list, 0, &val);
 354     trace->type = TRACE_FIXED;
 355     trace->value = val.value;
 356     return trace;
 357   }
 358
 359   trace->type = TRACE_DYNAMIC;
 360   trace->power_trace = power_trace;
 361
 362   /* count the total time of trace file */
 363   xbt_dynar_foreach(power_trace->s_list.event_list, cpt, val) {
 364     total_time += val.delta;
 365   }
 366   trace->trace = surf_cpu_ti_trace_new(power_trace);
 367   trace->last_time = total_time;
 368   trace->total =
 369       surf_cpu_ti_integrate_trace_simple(trace->trace, 0, total_time);
 370
 371   XBT_DEBUG("Total integral %lf, last_time %lf ",
 372          trace->total, trace->last_time);
 373
 374   return trace;
 375 }
 376
 377 /**
 378  * \brief Binary search in array.
 379  *  It returns the first point of the interval in which "a" is.
 380  * \param array    Array
 381  * \param a        Value to search
 382  * \param low     Low bound to search in array
 383  * \param high    Upper bound to search in array
 384  * \return Index of point
 385 */
 386 static int surf_cpu_ti_binary_search(double *array, double a, int low,
 387                                      int high)
 388 {
 389   xbt_assert(low < high, "Wrong parameters: low (%d) should be smaller than"
 390       " high (%d)", low, high);
 391
 392   int mid;
 393   do {
 394     mid = low + (high - low) / 2;
 395     XBT_DEBUG("a %lf low %d high %d mid %d value %lf", a, low, high, mid,
 396         array[mid]);
 397
 398     if (array[mid] > a)
 399       high = mid;
 400     else
 401       low = mid;
 402   }
 403   while (low < high - 1);
 404
 405   return low;
 406 }
 407
 408 /*********
 409  * Model *
 410  *********/
 411
 412 CpuTiModel::CpuTiModel() : CpuModel("cpu_ti")
 413 {
 414
 415 }
 416
 417 CpuTiPtr CpuTiModel::createResource(string name,
 418                            double powerPeak,
 419                            double powerScale,
 420                            tmgr_trace_t powerTrace,
 421                            int core,
 422                            e_surf_resource_state_t stateInitial,
 423                            tmgr_trace_t stateTrace,
 424                            xbt_dict_t cpuProperties)
 425 {
 426   tmgr_trace_t empty_trace;
 427   s_tmgr_event_t val;
 428   CpuTiActionPtr cpuAction;
 429   xbt_assert(core==1,"Multi-core not handled with this model yet");
 430   /*TOREPAIR: xbt_assert(!surf_cpu_resource_priv(surf_cpu_resource_by_name(name)),
 431               "Host '%s' declared several times in the platform file",
 432               name);*/
 433   CpuTiPtr cpu = new CpuTi(this, name, powerPeak, powerScale, powerTrace,
 434                            core, stateInitial, stateTrace, cpuProperties);
 435   xbt_lib_set(host_lib, name.c_str(), SURF_CPU_LEVEL, cpu);
 436   return (CpuTiPtr) xbt_lib_get_elm_or_null(host_lib, name.c_str());
 437 }
 438
 439 CpuTiActionPtr CpuTiModel::createAction(double cost, bool failed)
 440 {
 441   return NULL;//new CpuTiAction(this, cost, failed);
 442 }
 443
 444 void CpuTi::printCpuTiModel()
 445 {
 446   std::cout << getModel()->getName() << "<<plop"<< std::endl;
 447 };
 448
 449 /************
 450  * Resource *
 451  ************/
 452 CpuTi::CpuTi(CpuTiModelPtr model, string name, double powerPeak,
 453         double powerScale, tmgr_trace_t powerTrace, int core,
 454         e_surf_resource_state_t stateInitial, tmgr_trace_t stateTrace,
 455         xbt_dict_t properties) :
 456         Cpu(model, name, properties), m_powerPeak(powerPeak), m_powerScale(powerScale),
 457         m_stateCurrent(stateInitial) {
 458   tmgr_trace_t empty_trace;
 459   s_tmgr_event_t val;
 460   xbt_assert(core==1,"Multi-core not handled with this model yet");
 461   XBT_DEBUG("power scale %lf", powerScale);
 462   m_availTrace = cpu_ti_parse_trace(powerTrace, powerScale);
 463   if (stateTrace)
 464     /*TOREPAIR:m_stateEvent = tmgr_history_add_trace(history, stateTrace, 0.0, 0, this);*/
 465   if (powerTrace && xbt_dynar_length(powerTrace->s_list.event_list) > 1) {
 466     // add a fake trace event if periodicity == 0
 467     xbt_dynar_get_cpy(powerTrace->s_list.event_list,
 468                       xbt_dynar_length(powerTrace->s_list.event_list) - 1, &val);
 469     /*TOREPAIR:if (val.delta == 0) {
 470       empty_trace = tmgr_empty_trace_new();
 471        m_powerEvent =
 472         tmgr_history_add_trace(history, empty_trace,
 473                                m_availTrace->last_time, 0, this);
 474     }*/
 475   }
 476 };
 477
 478 CpuTiModelPtr CpuTi::getModel() {
 479   return static_cast<CpuTiModelPtr>(p_model);
 480 };
 481
 482 double CpuTi::getSpeed(double load)
 483 {
 484   return load * m_powerPeak;
 485 }
 486
 487 double CpuTi::getAvailableSpeed()
 488 {
 489   return 0;
 490 }
 491
 492 /**********
 493  * Action *
 494  **********/
 495
 496 double CpuTiAction::getRemains()
 497 {
 498   return 0;
 499 }
 500
 501 double CpuTiAction::getStartTime()
 502 {
 503   return 0;
 504 }
 505
 506 double CpuTiAction::getFinishTime()
 507 {
 508   return 0;
 509 }
 510
 511 #endif /* SURF_MODEL_CPUTI_H_ */
 512