src/simdag/sd_task.c

   1 /* Copyright (c) 2007-2009 Da SimGrid Team.  All rights reserved.           */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include "private.h"
   7 #include "simdag/simdag.h"
   8 #include "xbt/sysdep.h"
   9 #include "xbt/dynar.h"
  10
  11 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
  12                                 "Logging specific to SimDag (task)");
  13
  14 static void __SD_task_remove_dependencies(SD_task_t task);
  15 static void __SD_task_destroy_scheduling_data(SD_task_t task);
  16
  17 /**
  18  * \brief Creates a new task.
  19  *
  20  * \param name the name of the task (can be \c NULL)
  21  * \param data the user data you want to associate with the task (can be \c NULL)
  22  * \param amount amount of the task
  23  * \return the new task
  24  * \see SD_task_destroy()
  25  */
  26 SD_task_t SD_task_create(const char *name, void *data, double amount)
  27 {
  28
  29   SD_task_t task;
  30   SD_CHECK_INIT_DONE();
  31
  32   task = xbt_new(s_SD_task_t, 1);
  33
  34   /* general information */
  35   task->data = data;            /* user data */
  36   task->name = xbt_strdup(name);
  37   task->kind = 0;
  38   task->state_hookup.prev = NULL;
  39   task->state_hookup.next = NULL;
  40   task->state_set = sd_global->not_scheduled_task_set;
  41   task->state = SD_NOT_SCHEDULED;
  42   xbt_swag_insert(task, task->state_set);
  43
  44   task->amount = amount;
  45   task->remains = amount;
  46   task->start_time = -1.0;
  47   task->finish_time = -1.0;
  48   task->surf_action = NULL;
  49   task->watch_points = 0;
  50
  51   /* dependencies */
  52   task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
  53   task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
  54
  55   /* scheduling parameters */
  56   task->workstation_nb = 0;
  57   task->workstation_list = NULL;
  58   task->computation_amount = NULL;
  59   task->communication_amount = NULL;
  60   task->rate = 0;
  61
  62   sd_global->task_number++;
  63
  64   return task;
  65 }
  66
  67 /**
  68  * \brief Returns the user data of a task
  69  *
  70  * \param task a task
  71  * \return the user data associated with this task (can be \c NULL)
  72  * \see SD_task_set_data()
  73  */
  74 void *SD_task_get_data(SD_task_t task)
  75 {
  76   SD_CHECK_INIT_DONE();
  77   xbt_assert0(task != NULL, "Invalid parameter");
  78   return task->data;
  79 }
  80
  81 /**
  82  * \brief Sets the user data of a task
  83  *
  84  * The new data can be \c NULL. The old data should have been freed first
  85  * if it was not \c NULL.
  86  *
  87  * \param task a task
  88  * \param data the new data you want to associate with this task
  89  * \see SD_task_get_data()
  90  */
  91 void SD_task_set_data(SD_task_t task, void *data)
  92 {
  93   SD_CHECK_INIT_DONE();
  94   xbt_assert0(task != NULL, "Invalid parameter");
  95   task->data = data;
  96 }
  97
  98 /**
  99  * \brief Returns the state of a task
 100  *
 101  * \param task a task
 102  * \return the current \ref e_SD_task_state_t "state" of this task:
 103  * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_READY, #SD_RUNNING, #SD_DONE or #SD_FAILED
 104  * \see e_SD_task_state_t
 105  */
 106 e_SD_task_state_t SD_task_get_state(SD_task_t task)
 107 {
 108   SD_CHECK_INIT_DONE();
 109   xbt_assert0(task != NULL, "Invalid parameter");
 110   return task->state;
 111 }
 112
 113 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
 114  */
 115 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
 116 {
 117   xbt_swag_remove(task, task->state_set);
 118   switch (new_state) {
 119   case SD_NOT_SCHEDULED:
 120     task->state_set = sd_global->not_scheduled_task_set;
 121     break;
 122   case SD_SCHEDULED:
 123     task->state_set = sd_global->scheduled_task_set;
 124     break;
 125   case SD_READY:
 126     task->state_set = sd_global->ready_task_set;
 127     break;
 128   case SD_IN_FIFO:
 129     task->state_set = sd_global->in_fifo_task_set;
 130     break;
 131   case SD_RUNNING:
 132     task->state_set = sd_global->running_task_set;
 133     task->start_time =
 134       surf_workstation_model->action_get_start_time(task->surf_action);
 135     break;
 136   case SD_DONE:
 137     task->state_set = sd_global->done_task_set;
 138     task->finish_time =
 139       surf_workstation_model->action_get_finish_time(task->surf_action);
 140     task->remains = 0;
 141     break;
 142   case SD_FAILED:
 143     task->state_set = sd_global->failed_task_set;
 144     break;
 145   default:
 146     xbt_assert0(0, "Invalid state");
 147   }
 148   xbt_swag_insert(task, task->state_set);
 149   task->state = new_state;
 150
 151   if (task->watch_points & new_state) {
 152     INFO1("Watch point reached with task '%s'!", SD_task_get_name(task));
 153     sd_global->watch_point_reached = 1;
 154     SD_task_unwatch(task, new_state);   /* remove the watch point */
 155   }
 156 }
 157
 158 /**
 159  * \brief Returns the name of a task
 160  *
 161  * \param task a task
 162  * \return the name of this task (can be \c NULL)
 163  */
 164 const char *SD_task_get_name(SD_task_t task)
 165 {
 166   SD_CHECK_INIT_DONE();
 167   xbt_assert0(task != NULL, "Invalid parameter");
 168   return task->name;
 169 }
 170
 171 /** @brief Returns the dynar of the parents of a task
 172  *
 173  * \param task a task
 174  * \return a newly allocated dynar comprising the parents of this task
 175  */
 176
 177 xbt_dynar_t SD_task_get_parents(SD_task_t task)
 178 {
 179   unsigned int i;
 180   xbt_dynar_t parents;
 181   SD_dependency_t dep;
 182   SD_CHECK_INIT_DONE();
 183   xbt_assert0(task != NULL, "Invalid parameter");
 184
 185   parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
 186   xbt_dynar_foreach(task->tasks_before, i, dep){
 187     xbt_dynar_push(parents, &(dep->src));
 188   }
 189   return parents;
 190 }
 191
 192 /** @brief Returns the dynar of the parents of a task
 193  *
 194  * \param task a task
 195  * \return a newly allocated dynar comprising the parents of this task
 196  */
 197 xbt_dynar_t SD_task_get_children(SD_task_t task)
 198 {
 199   unsigned int i;
 200   xbt_dynar_t children;
 201   SD_dependency_t dep;
 202   SD_CHECK_INIT_DONE();
 203   xbt_assert0(task != NULL, "Invalid parameter");
 204
 205   children = xbt_dynar_new(sizeof(SD_task_t), NULL);
 206   xbt_dynar_foreach(task->tasks_after, i, dep){
 207     xbt_dynar_push(children, &(dep->dst));
 208   }
 209   return children;
 210 }
 211
 212 /**
 213  * \brief Returns the amount of workstations involved in a task
 214  *
 215  * Only call this on already scheduled tasks!
 216  * \param task a task
 217  */
 218 int SD_task_get_workstation_count(SD_task_t task)
 219 {
 220   SD_CHECK_INIT_DONE();
 221   xbt_assert0(task != NULL, "Invalid parameter");
 222   //  xbt_assert1( task->state_set != sd_global->scheduled_task_set,
 223   //           "Unscheduled task %s", task->name);
 224   return task->workstation_nb;
 225 }
 226
 227 /**
 228  * \brief Returns the list of workstations involved in a task
 229  *
 230  * Only call this on already scheduled tasks!
 231  * \param task a task
 232  */
 233 SD_workstation_t* SD_task_get_workstation_list(SD_task_t task)
 234 {
 235   SD_CHECK_INIT_DONE();
 236   xbt_assert0(task != NULL, "Invalid parameter");
 237   //xbt_assert1( task->state_set != sd_global->scheduled_task_set,
 238   //           "Unscheduled task %s", task->name);
 239   return task->workstation_list;
 240 }
 241
 242 /**
 243  * \brief Returns the total amount of a task
 244  *
 245  * \param task a task
 246  * \return the total amount of this task
 247  * \see SD_task_get_remaining_amount()
 248  */
 249 double SD_task_get_amount(SD_task_t task)
 250 {
 251   SD_CHECK_INIT_DONE();
 252   xbt_assert0(task != NULL, "Invalid parameter");
 253   return task->amount;
 254 }
 255
 256 /**
 257  * \brief Returns the remaining amount of a task
 258  *
 259  * \param task a task
 260  * \return the remaining amount of this task
 261  * \see SD_task_get_amount()
 262  */
 263 double SD_task_get_remaining_amount(SD_task_t task)
 264 {
 265   SD_CHECK_INIT_DONE();
 266   xbt_assert0(task != NULL, "Invalid parameter");
 267
 268   if (task->surf_action)
 269     return surf_workstation_model->get_remains(task->surf_action);
 270   else
 271     return task->remains;
 272 }
 273
 274 /* temporary function for debbuging */
 275 void SD_task_dump(SD_task_t task)
 276 {
 277   unsigned int counter;
 278   SD_dependency_t dependency;
 279
 280   INFO1("Displaying task %s",SD_task_get_name(task));
 281   INFO1("  - amount: %.0f",SD_task_get_amount(task));
 282   if (task->kind!=0) {
 283     switch(task->kind){
 284     case SD_TASK_COMM_E2E:
 285       INFO0("  - kind: end-to-end communication");
 286       break;
 287     case SD_TASK_COMP_SEQ:
 288       INFO0("  - kind: sequential computation");
 289       break;
 290     default:
 291       INFO1("  - (unknown kind %d)",task->kind);
 292     }
 293   }
 294   if (xbt_dynar_length(task->tasks_before)) {
 295     INFO0("  - pre-dependencies:");
 296     xbt_dynar_foreach(task->tasks_before,counter,dependency) {
 297       INFO1("    %s",SD_task_get_name(dependency->src));
 298     }
 299   }
 300   if (xbt_dynar_length(task->tasks_after)) {
 301     INFO0("  - post-dependencies:");
 302     xbt_dynar_foreach(task->tasks_after,counter,dependency) {
 303       INFO1("    %s",SD_task_get_name(dependency->dst));
 304     }
 305   }
 306 }
 307
 308 /* Destroys a dependency between two tasks.
 309  */
 310 static void __SD_task_dependency_destroy(void *dependency)
 311 {
 312   if (((SD_dependency_t) dependency)->name != NULL)
 313     xbt_free(((SD_dependency_t) dependency)->name);
 314   xbt_free(dependency);
 315 }
 316
 317 /**
 318  * \brief Adds a dependency between two tasks
 319  *
 320  * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
 321  * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_READY.
 322  *
 323  * \param name the name of the new dependency (can be \c NULL)
 324  * \param data the user data you want to associate with this dependency (can be \c NULL)
 325  * \param src the task which must be executed first
 326  * \param dst the task you want to make depend on \a src
 327  * \see SD_task_dependency_remove()
 328  */
 329 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
 330                             SD_task_t dst)
 331 {
 332   xbt_dynar_t dynar;
 333   int length;
 334   int found = 0;
 335   int i;
 336   SD_dependency_t dependency;
 337
 338   SD_CHECK_INIT_DONE();
 339   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
 340
 341   dynar = src->tasks_after;
 342   length = xbt_dynar_length(dynar);
 343
 344   if (src == dst)
 345     THROW1(arg_error, 0,
 346            "Cannot add a dependency between task '%s' and itself",
 347            SD_task_get_name(src));
 348
 349   if (!__SD_task_is_not_scheduled(src)
 350       && !__SD_task_is_scheduled_or_ready(src))
 351     THROW1(arg_error, 0,
 352            "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
 353            SD_task_get_name(src));
 354
 355   if (!__SD_task_is_not_scheduled(dst)
 356       && !__SD_task_is_scheduled_or_ready(dst))
 357     THROW1(arg_error, 0,
 358            "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
 359            SD_task_get_name(dst));
 360
 361   DEBUG2("SD_task_dependency_add: src = %s, dst = %s", SD_task_get_name(src),
 362          SD_task_get_name(dst));
 363   for (i = 0; i < length && !found; i++) {
 364     xbt_dynar_get_cpy(dynar, i, &dependency);
 365     found = (dependency->dst == dst);
 366     DEBUG2("Dependency %d: dependency->dst = %s", i,
 367            SD_task_get_name(dependency->dst));
 368   }
 369
 370   if (found)
 371     THROW2(arg_error, 0,
 372            "A dependency already exists between task '%s' and task '%s'",
 373            SD_task_get_name(src), SD_task_get_name(dst));
 374
 375   dependency = xbt_new(s_SD_dependency_t, 1);
 376
 377   dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
 378   dependency->data = data;
 379   dependency->src = src;
 380   dependency->dst = dst;
 381
 382   /* src must be executed before dst */
 383   xbt_dynar_push(src->tasks_after, &dependency);
 384   xbt_dynar_push(dst->tasks_before, &dependency);
 385
 386   /* if the task was ready, then dst->tasks_before is not empty anymore,
 387      so we must go back to state SD_SCHEDULED */
 388   if (__SD_task_is_ready(dst)) {
 389     DEBUG1("SD_task_dependency_add: %s was ready and becomes scheduled!",
 390            SD_task_get_name(dst));
 391     __SD_task_set_state(dst, SD_SCHEDULED);
 392   }
 393
 394   /*  __SD_print_dependencies(src);
 395      __SD_print_dependencies(dst); */
 396 }
 397
 398 /**
 399  * \brief Indacates whether there is a dependency between two tasks.
 400  *
 401  * \param src a task
 402  * \param dst a task depending on \a src
 403  *
 404  * If src is NULL, checks whether dst has any pre-dependency.
 405  * If dst is NULL, checks whether src has any post-dependency.
 406  */
 407 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
 408 {
 409   unsigned int counter;
 410   SD_dependency_t dependency;
 411
 412   SD_CHECK_INIT_DONE();
 413   xbt_assert0(src != NULL || dst != NULL, "Invalid parameter: both src and dst are NULL");
 414
 415   if (src) {
 416     if (dst) {
 417       xbt_dynar_foreach(src->tasks_after,counter,dependency) {
 418         if (dependency->dst == dst)
 419           return 1;
 420       }
 421     } else {
 422       return xbt_dynar_length(src->tasks_after);
 423     }
 424   } else {
 425     return xbt_dynar_length(dst->tasks_before);
 426   }
 427   return 0;
 428 }
 429
 430 /**
 431  * \brief Remove a dependency between two tasks
 432  *
 433  * \param src a task
 434  * \param dst a task depending on \a src
 435  * \see SD_task_dependency_add()
 436  */
 437 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
 438 {
 439
 440   xbt_dynar_t dynar;
 441   int length;
 442   int found = 0;
 443   int i;
 444   SD_dependency_t dependency;
 445
 446   SD_CHECK_INIT_DONE();
 447   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
 448
 449   /* remove the dependency from src->tasks_after */
 450   dynar = src->tasks_after;
 451   length = xbt_dynar_length(dynar);
 452
 453   for (i = 0; i < length && !found; i++) {
 454     xbt_dynar_get_cpy(dynar, i, &dependency);
 455     if (dependency->dst == dst) {
 456       xbt_dynar_remove_at(dynar, i, NULL);
 457       found = 1;
 458     }
 459   }
 460   if (!found)
 461     THROW4(arg_error, 0,
 462            "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
 463            SD_task_get_name(src), SD_task_get_name(dst),
 464            SD_task_get_name(dst), SD_task_get_name(src));
 465
 466   /* remove the dependency from dst->tasks_before */
 467   dynar = dst->tasks_before;
 468   length = xbt_dynar_length(dynar);
 469   found = 0;
 470
 471   for (i = 0; i < length && !found; i++) {
 472     xbt_dynar_get_cpy(dynar, i, &dependency);
 473     if (dependency->src == src) {
 474       xbt_dynar_remove_at(dynar, i, NULL);
 475       __SD_task_dependency_destroy(dependency);
 476       found = 1;
 477     }
 478   }
 479   /* should never happen... */
 480   xbt_assert4(found,
 481               "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
 482               SD_task_get_name(dst), SD_task_get_name(src),
 483               SD_task_get_name(src), SD_task_get_name(dst));
 484
 485   /* if the task was scheduled and dst->tasks_before is empty now, we can make it ready */
 486   if (xbt_dynar_length(dst->tasks_before) == 0 && __SD_task_is_scheduled(dst))
 487     __SD_task_set_state(dst, SD_READY);
 488
 489   /*  __SD_print_dependencies(src);
 490      __SD_print_dependencies(dst); */
 491 }
 492
 493 /**
 494  * \brief Returns the user data associated with a dependency between two tasks
 495  *
 496  * \param src a task
 497  * \param dst a task depending on \a src
 498  * \return the user data associated with this dependency (can be \c NULL)
 499  * \see SD_task_dependency_add()
 500  */
 501 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
 502 {
 503
 504   xbt_dynar_t dynar;
 505   int length;
 506   int found = 0;
 507   int i;
 508   SD_dependency_t dependency;
 509
 510
 511   SD_CHECK_INIT_DONE();
 512   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
 513
 514   dynar = src->tasks_after;
 515   length = xbt_dynar_length(dynar);
 516
 517   for (i = 0; i < length && !found; i++) {
 518     xbt_dynar_get_cpy(dynar, i, &dependency);
 519     found = (dependency->dst == dst);
 520   }
 521   if (!found)
 522     THROW2(arg_error, 0, "No dependency found between task '%s' and '%s'",
 523            SD_task_get_name(src), SD_task_get_name(dst));
 524   return dependency->data;
 525 }
 526
 527 /* temporary function for debugging */
 528 static void __SD_print_watch_points(SD_task_t task)
 529 {
 530   static const int state_masks[] =
 531     { SD_SCHEDULED, SD_RUNNING, SD_READY, SD_DONE, SD_FAILED };
 532   static const char *state_names[] =
 533     { "scheduled", "running", "ready", "done", "failed" };
 534   int i;
 535
 536   INFO2("Task '%s' watch points (%x): ", SD_task_get_name(task),
 537         task->watch_points);
 538
 539
 540   for (i = 0; i < 5; i++) {
 541     if (task->watch_points & state_masks[i])
 542       INFO1("%s ", state_names[i]);
 543   }
 544 }
 545
 546 /**
 547  * \brief Adds a watch point to a task
 548  *
 549  * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
 550  * task becomes the one given in argument. The
 551  * watch point is then automatically removed.
 552  *
 553  * \param task a task
 554  * \param state the \ref e_SD_task_state_t "state" you want to watch
 555  * (cannot be #SD_NOT_SCHEDULED)
 556  * \see SD_task_unwatch()
 557  */
 558 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
 559 {
 560   SD_CHECK_INIT_DONE();
 561   xbt_assert0(task != NULL, "Invalid parameter");
 562
 563   if (state & SD_NOT_SCHEDULED)
 564     THROW0(arg_error, 0,
 565            "Cannot add a watch point for state SD_NOT_SCHEDULED");
 566
 567   task->watch_points = task->watch_points | state;
 568   /*  __SD_print_watch_points(task); */
 569 }
 570
 571 /**
 572  * \brief Removes a watch point from a task
 573  *
 574  * \param task a task
 575  * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
 576  * \see SD_task_watch()
 577  */
 578 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
 579 {
 580   SD_CHECK_INIT_DONE();
 581   xbt_assert0(task != NULL, "Invalid parameter");
 582   xbt_assert0(state != SD_NOT_SCHEDULED,
 583               "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
 584
 585   task->watch_points = task->watch_points & ~state;
 586   /*  __SD_print_watch_points(task); */
 587 }
 588
 589 /**
 590  * \brief Returns an approximative estimation of the execution time of a task.
 591  *
 592  * The estimation is very approximative because the value returned is the time
 593  * the task would take if it was executed now and if it was the only task.
 594  *
 595  * \param task the task to evaluate
 596  * \param workstation_nb number of workstations on which the task would be executed
 597  * \param workstation_list the workstations on which the task would be executed
 598  * \param computation_amount computation amount for each workstation
 599  * \param communication_amount communication amount between each pair of workstations
 600  * \param rate task execution speed rate
 601  * \see SD_schedule()
 602  */
 603 double SD_task_get_execution_time(SD_task_t task,
 604                                   int workstation_nb,
 605                                   const SD_workstation_t * workstation_list,
 606                                   const double *computation_amount,
 607                                   const double *communication_amount,
 608                                   double rate)
 609 {
 610   double time, max_time = 0.0;
 611   int i, j;
 612   SD_CHECK_INIT_DONE();
 613   xbt_assert0(task != NULL && workstation_nb > 0 && workstation_list != NULL
 614               && computation_amount != NULL
 615               && communication_amount != NULL, "Invalid parameter");
 616
 617   /* the task execution time is the maximum execution time of the parallel tasks */
 618
 619   for (i = 0; i < workstation_nb; i++) {
 620     time =
 621       SD_workstation_get_computation_time(workstation_list[i],
 622                                           computation_amount[i]);
 623
 624     for (j = 0; j < workstation_nb; j++) {
 625       time +=
 626         SD_route_get_communication_time(workstation_list[i],
 627                                         workstation_list[j],
 628                                         communication_amount[i *
 629                                                              workstation_nb +
 630                                                              j]);
 631     }
 632
 633     if (time > max_time) {
 634       max_time = time;
 635     }
 636   }
 637   return max_time * SD_task_get_amount(task);
 638 }
 639
 640 /**
 641  * \brief Schedules a task
 642  *
 643  * The task state must be #SD_NOT_SCHEDULED.
 644  * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
 645  * i.e. when its dependencies are satisfied.
 646  *
 647  * \param task the task you want to schedule
 648  * \param workstation_nb number of workstations on which the task will be executed
 649  * \param workstation_list the workstations on which the task will be executed
 650  * \param computation_amount computation amount for each workstation
 651  * \param communication_amount communication amount between each pair of workstations
 652  * \param rate task execution speed rate
 653  * \see SD_task_unschedule()
 654  */
 655 void SD_task_schedule(SD_task_t task, int workstation_nb,
 656                       const SD_workstation_t * workstation_list,
 657                       const double *computation_amount,
 658                       const double *communication_amount, double rate)
 659 {
 660
 661   int communication_nb;
 662
 663   SD_CHECK_INIT_DONE();
 664   xbt_assert0(task != NULL, "Invalid parameter");
 665   xbt_assert0(workstation_nb > 0, "workstation_nb must be positive");
 666
 667   if (!__SD_task_is_not_scheduled(task))
 668     THROW1(arg_error, 0, "Task '%s' has already been scheduled",
 669            SD_task_get_name(task));
 670
 671   task->workstation_nb = workstation_nb;
 672   task->rate = rate;
 673
 674   task->computation_amount = xbt_new(double, workstation_nb);
 675   memcpy(task->computation_amount, computation_amount,
 676          sizeof(double) * workstation_nb);
 677
 678   communication_nb = workstation_nb * workstation_nb;
 679   task->communication_amount = xbt_new(double, communication_nb);
 680   memcpy(task->communication_amount, communication_amount,
 681          sizeof(double) * communication_nb);
 682
 683   task->workstation_list = xbt_new(SD_workstation_t, workstation_nb);
 684   memcpy(task->workstation_list, workstation_list,
 685          sizeof(SD_workstation_t) * workstation_nb);
 686
 687   /* update the task state */
 688   if (xbt_dynar_length(task->tasks_before) == 0)
 689     __SD_task_set_state(task, SD_READY);
 690   else
 691     __SD_task_set_state(task, SD_SCHEDULED);
 692 }
 693
 694 /**
 695  * \brief Unschedules a task
 696  *
 697  * The task state must be #SD_SCHEDULED, #SD_READY, #SD_RUNNING or #SD_FAILED.
 698  * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
 699  * Call SD_task_schedule() to schedule it again.
 700  *
 701  * \param task the task you want to unschedule
 702  * \see SD_task_schedule()
 703  */
 704 void SD_task_unschedule(SD_task_t task)
 705 {
 706   SD_CHECK_INIT_DONE();
 707   xbt_assert0(task != NULL, "Invalid parameter");
 708
 709   if (task->state_set != sd_global->scheduled_task_set &&
 710       task->state_set != sd_global->ready_task_set &&
 711       task->state_set != sd_global->running_task_set &&
 712       task->state_set != sd_global->failed_task_set)
 713     THROW1(arg_error, 0,
 714            "Task %s: the state must be SD_SCHEDULED, SD_READY, SD_RUNNING or SD_FAILED",
 715            SD_task_get_name(task));
 716
 717   if (__SD_task_is_scheduled_or_ready(task))    /* if the task is scheduled or ready */
 718     __SD_task_destroy_scheduling_data(task);
 719
 720   if (__SD_task_is_running(task))       /* the task should become SD_FAILED */
 721     surf_workstation_model->action_cancel(task->surf_action);
 722   else
 723     __SD_task_set_state(task, SD_NOT_SCHEDULED);
 724   task->remains = task->amount;
 725   task->start_time = -1.0;
 726 }
 727
 728 /* Destroys the data memorised by SD_task_schedule. Task state must be SD_SCHEDULED or SD_READY.
 729  */
 730 static void __SD_task_destroy_scheduling_data(SD_task_t task)
 731 {
 732   SD_CHECK_INIT_DONE();
 733   if (!__SD_task_is_scheduled_or_ready(task) && !__SD_task_is_in_fifo(task))
 734     THROW1(arg_error, 0,
 735            "Task '%s' must be SD_SCHEDULED, SD_READY or SD_IN_FIFO",
 736            SD_task_get_name(task));
 737
 738   xbt_free(task->computation_amount);
 739   xbt_free(task->communication_amount);
 740 }
 741
 742 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
 743  * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
 744  * the task gets out of its fifos.
 745  */
 746 void __SD_task_really_run(SD_task_t task)
 747 {
 748
 749   int i;
 750   void **surf_workstations;
 751
 752   SD_CHECK_INIT_DONE();
 753   xbt_assert0(task != NULL, "Invalid parameter");
 754   xbt_assert2(__SD_task_is_ready_or_in_fifo(task),
 755               "Task '%s' is not ready or in a fifo! Task state: %d",
 756               SD_task_get_name(task), SD_task_get_state(task));
 757   xbt_assert1(task->workstation_list != NULL,
 758               "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
 759
 760
 761
 762   DEBUG1("Really running task '%s'", SD_task_get_name(task));
 763
 764   /* set this task as current task for the workstations in sequential mode */
 765   for (i = 0; i < task->workstation_nb; i++) {
 766     if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
 767         SD_WORKSTATION_SEQUENTIAL_ACCESS) {
 768       task->workstation_list[i]->current_task = task;
 769       xbt_assert0(__SD_workstation_is_busy(task->workstation_list[i]),
 770                   "The workstation should be busy now");
 771     }
 772   }
 773
 774   DEBUG1("Task '%s' set as current task for its workstations",
 775          SD_task_get_name(task));
 776
 777   /* start the task */
 778
 779   /* we have to create a Surf workstation array instead of the SimDag workstation array */
 780   surf_workstations = xbt_new(void *, task->workstation_nb);
 781
 782   for (i = 0; i < task->workstation_nb; i++) {
 783     surf_workstations[i] = task->workstation_list[i]->surf_workstation;
 784   }
 785
 786   task->surf_action = NULL;
 787   if ((task->workstation_nb == 1) && (task->communication_amount[0] == 0.0)) {
 788     task->surf_action =
 789       surf_workstation_model->extension.
 790       workstation.execute(surf_workstations[0], task->computation_amount[0]);
 791   } else if ((task->workstation_nb == 1)
 792              && (task->computation_amount[0] == 0.0)) {
 793     task->surf_action =
 794       surf_workstation_model->extension.
 795       workstation.communicate(surf_workstations[0], surf_workstations[0],
 796                               task->communication_amount[0], task->rate);
 797   } else if ((task->workstation_nb == 2)
 798              && (task->computation_amount[0] == 0.0)
 799              && (task->computation_amount[1] == 0.0)) {
 800     int nb = 0;
 801     double value = 0.0;
 802
 803     for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
 804       if (task->communication_amount[i] > 0.0) {
 805         nb++;
 806         value = task->communication_amount[i];
 807       }
 808     }
 809     if (nb == 1) {
 810       task->surf_action =
 811         surf_workstation_model->extension.
 812         workstation.communicate(surf_workstations[0], surf_workstations[1],
 813                                 value, task->rate);
 814     }
 815   }
 816   if (!task->surf_action) {
 817     double *computation_amount = xbt_new(double, task->workstation_nb);
 818     double *communication_amount = xbt_new(double, task->workstation_nb *
 819                                            task->workstation_nb);
 820
 821     memcpy(computation_amount, task->computation_amount, sizeof(double) *
 822            task->workstation_nb);
 823     memcpy(communication_amount, task->communication_amount,
 824            sizeof(double) * task->workstation_nb * task->workstation_nb);
 825
 826     task->surf_action =
 827       surf_workstation_model->extension.
 828       workstation.execute_parallel_task(task->workstation_nb,
 829                                         surf_workstations, computation_amount,
 830                                         communication_amount, task->amount,
 831                                         task->rate);
 832   } else {
 833     xbt_free(surf_workstations);
 834   }
 835
 836   surf_workstation_model->action_data_set(task->surf_action, task);
 837
 838   DEBUG1("surf_action = %p", task->surf_action);
 839
 840   __SD_task_destroy_scheduling_data(task);      /* now the scheduling data are not useful anymore */
 841   __SD_task_set_state(task, SD_RUNNING);
 842   xbt_assert2(__SD_task_is_running(task), "Bad state of task '%s': %d",
 843               SD_task_get_name(task), SD_task_get_state(task));
 844
 845 }
 846
 847 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_READY
 848  * (ie when its dependencies are satisfied).
 849  * If one of the workstations where the task is scheduled on is busy (in sequential mode),
 850  * the task doesn't start.
 851  * Returns whether the task has started.
 852  */
 853 int __SD_task_try_to_run(SD_task_t task)
 854 {
 855
 856   int can_start = 1;
 857   int i;
 858   SD_workstation_t workstation;
 859
 860   SD_CHECK_INIT_DONE();
 861   xbt_assert0(task != NULL, "Invalid parameter");
 862   xbt_assert2(__SD_task_is_ready(task),
 863               "Task '%s' is not ready! Task state: %d",
 864               SD_task_get_name(task), SD_task_get_state(task));
 865
 866
 867   for (i = 0; i < task->workstation_nb; i++) {
 868     can_start = !__SD_workstation_is_busy(task->workstation_list[i]);
 869   }
 870
 871   DEBUG2("Task '%s' can start: %d", SD_task_get_name(task), can_start);
 872
 873   if (!can_start) {             /* if the task cannot start and is not in the fifos yet */
 874     for (i = 0; i < task->workstation_nb; i++) {
 875       workstation = task->workstation_list[i];
 876       if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
 877         DEBUG2("Pushing task '%s' in the fifo of workstation '%s'",
 878                SD_task_get_name(task), SD_workstation_get_name(workstation));
 879         xbt_fifo_push(workstation->task_fifo, task);
 880       }
 881     }
 882     __SD_task_set_state(task, SD_IN_FIFO);
 883     xbt_assert2(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
 884                 SD_task_get_name(task), SD_task_get_state(task));
 885     DEBUG1("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
 886   } else {
 887     __SD_task_really_run(task);
 888   }
 889
 890   return can_start;
 891 }
 892
 893 /* This function is called by SD_simulate when a task is done.
 894  * It updates task->state and task->action and executes if necessary the tasks
 895  * which were waiting in fifos for the end of `task'
 896  */
 897 void __SD_task_just_done(SD_task_t task)
 898 {
 899   int i, j;
 900   SD_workstation_t workstation;
 901
 902   SD_task_t candidate;
 903   int candidate_nb = 0;
 904   int candidate_capacity = 8;
 905   SD_task_t *candidates;
 906   int can_start = 1;
 907
 908   SD_CHECK_INIT_DONE();
 909   xbt_assert0(task != NULL, "Invalid parameter");
 910   xbt_assert1(__SD_task_is_running(task),
 911               "The task must be running! Task state: %d",
 912               SD_task_get_state(task));
 913   xbt_assert1(task->workstation_list != NULL,
 914               "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
 915
 916
 917   candidates = xbt_new(SD_task_t, 8);
 918
 919   __SD_task_set_state(task, SD_DONE);
 920   surf_workstation_model->action_unref(task->surf_action);
 921   task->surf_action = NULL;
 922
 923   DEBUG0("Looking for candidates");
 924
 925   /* if the task was executed on sequential workstations,
 926      maybe we can execute the next task of the fifo for each workstation */
 927   for (i = 0; i < task->workstation_nb; i++) {
 928     workstation = task->workstation_list[i];
 929     DEBUG2("Workstation '%s': access_mode = %d",
 930            SD_workstation_get_name(workstation), workstation->access_mode);
 931     if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
 932       xbt_assert1(workstation->task_fifo != NULL,
 933                   "Workstation '%s' has sequential access but no fifo!",
 934                   SD_workstation_get_name(workstation));
 935       xbt_assert2(workstation->current_task =
 936                   task, "Workstation '%s': current task should be '%s'",
 937                   SD_workstation_get_name(workstation),
 938                   SD_task_get_name(task));
 939
 940       /* the task is over so we can release the workstation */
 941       workstation->current_task = NULL;
 942
 943       DEBUG0("Getting candidate in fifo");
 944       candidate =
 945         xbt_fifo_get_item_content(xbt_fifo_get_first_item
 946                                   (workstation->task_fifo));
 947
 948       if (candidate != NULL) {
 949         DEBUG1("Candidate: '%s'", SD_task_get_name(candidate));
 950         xbt_assert2(__SD_task_is_in_fifo(candidate),
 951                     "Bad state of candidate '%s': %d",
 952                     SD_task_get_name(candidate),
 953                     SD_task_get_state(candidate));
 954       }
 955
 956       DEBUG1("Candidate in fifo: %p", candidate);
 957
 958       /* if there was a task waiting for my place */
 959       if (candidate != NULL) {
 960         /* Unfortunately, we are not sure yet that we can execute the task now,
 961            because the task can be waiting more deeply in some other workstation's fifos...
 962            So we memorize all candidate tasks, and then we will check for each candidate
 963            whether or not all its workstations are available. */
 964
 965         /* realloc if necessary */
 966         if (candidate_nb == candidate_capacity) {
 967           candidate_capacity *= 2;
 968           candidates =
 969             xbt_realloc(candidates, sizeof(SD_task_t) * candidate_capacity);
 970         }
 971
 972         /* register the candidate */
 973         candidates[candidate_nb++] = candidate;
 974         candidate->fifo_checked = 0;
 975       }
 976     }
 977   }
 978
 979   DEBUG1("Candidates found: %d", candidate_nb);
 980
 981   /* now we check every candidate task */
 982   for (i = 0; i < candidate_nb; i++) {
 983     candidate = candidates[i];
 984
 985     if (candidate->fifo_checked) {
 986       continue;                 /* we have already evaluated that task */
 987     }
 988
 989     xbt_assert2(__SD_task_is_in_fifo(candidate),
 990                 "Bad state of candidate '%s': %d",
 991                 SD_task_get_name(candidate), SD_task_get_state(candidate));
 992
 993     for (j = 0; j < candidate->workstation_nb && can_start; j++) {
 994       workstation = candidate->workstation_list[j];
 995
 996       /* I can start on this workstation if the workstation is shared
 997          or if I am the first task in the fifo */
 998       can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS ||
 999         candidate ==
1000         xbt_fifo_get_item_content(xbt_fifo_get_first_item
1001                                   (workstation->task_fifo));
1002     }
1003
1004     DEBUG2("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1005            can_start);
1006
1007     /* now we are sure that I can start! */
1008     if (can_start) {
1009       for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1010         workstation = candidate->workstation_list[j];
1011
1012         /* update the fifo */
1013         if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1014           candidate = xbt_fifo_shift(workstation->task_fifo);   /* the return value is stored just for debugging */
1015           DEBUG1("Head of the fifo: '%s'",
1016                  (candidate != NULL) ? SD_task_get_name(candidate) : "NULL");
1017           xbt_assert0(candidate == candidates[i],
1018                       "Error in __SD_task_just_done: bad first task in the fifo");
1019         }
1020       }                         /* for each workstation */
1021
1022       /* finally execute the task */
1023       DEBUG2("Task '%s' state: %d", SD_task_get_name(candidate),
1024              SD_task_get_state(candidate));
1025       __SD_task_really_run(candidate);
1026
1027       DEBUG4
1028         ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1029          SD_task_get_name(candidate), candidate->state_set,
1030          sd_global->running_task_set, __SD_task_is_running(candidate));
1031       xbt_assert2(__SD_task_is_running(candidate),
1032                   "Bad state of task '%s': %d", SD_task_get_name(candidate),
1033                   SD_task_get_state(candidate));
1034       DEBUG0("Okay, the task is running.");
1035
1036     }                           /* can start */
1037     candidate->fifo_checked = 1;
1038   }                             /* for each candidate */
1039
1040   xbt_free(candidates);
1041 }
1042
1043 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1044  */
1045 static void __SD_task_remove_dependencies(SD_task_t task)
1046 {
1047   /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1048      because each one is stored twice */
1049   SD_dependency_t dependency;
1050   while (xbt_dynar_length(task->tasks_before) > 0) {
1051     xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1052     SD_task_dependency_remove(dependency->src, dependency->dst);
1053   }
1054
1055   while (xbt_dynar_length(task->tasks_after) > 0) {
1056     xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1057     SD_task_dependency_remove(dependency->src, dependency->dst);
1058   }
1059 }
1060
1061 /**
1062  * \brief Returns the start time of a task
1063  *
1064  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1065  *
1066  * \param task: a task
1067  * \return the start time of this task
1068  */
1069 double SD_task_get_start_time(SD_task_t task)
1070 {
1071   SD_CHECK_INIT_DONE();
1072   xbt_assert0(task != NULL, "Invalid parameter");
1073   if (task->surf_action)
1074     return surf_workstation_model->action_get_start_time(task->surf_action);
1075   else
1076     return task->start_time;
1077 }
1078
1079 /**
1080  * \brief Returns the finish time of a task
1081  *
1082  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1083  * If the state is not completed yet, the returned value is an
1084  * estimation of the task finish time. This value can fluctuate
1085  * until the task is completed.
1086  *
1087  * \param task: a task
1088  * \return the start time of this task
1089  */
1090 double SD_task_get_finish_time(SD_task_t task)
1091 {
1092   SD_CHECK_INIT_DONE();
1093   xbt_assert0(task != NULL, "Invalid parameter");
1094
1095   if (task->surf_action)        /* should never happen as actions are destroyed right after their completion */
1096     return surf_workstation_model->action_get_finish_time(task->surf_action);
1097   else
1098     return task->finish_time;
1099 }
1100
1101 /**
1102  * \brief Destroys a task.
1103  *
1104  * The user data (if any) should have been destroyed first.
1105  *
1106  * \param task the task you want to destroy
1107  * \see SD_task_create()
1108  */
1109 void SD_task_destroy(SD_task_t task)
1110 {
1111   SD_CHECK_INIT_DONE();
1112   xbt_assert0(task != NULL, "Invalid parameter");
1113
1114   DEBUG1("Destroying task %s...", SD_task_get_name(task));
1115
1116   __SD_task_remove_dependencies(task);
1117
1118   /* if the task was scheduled or ready we have to free the scheduling parameters */
1119   if (__SD_task_is_scheduled_or_ready(task))
1120     __SD_task_destroy_scheduling_data(task);
1121
1122   if (task->name != NULL)
1123     xbt_free(task->name);
1124
1125   if (task->surf_action != NULL)
1126     surf_workstation_model->action_unref(task->surf_action);
1127
1128   if (task->workstation_list != NULL)
1129     xbt_free(task->workstation_list);
1130
1131   xbt_dynar_free(&task->tasks_before);
1132   xbt_dynar_free(&task->tasks_after);
1133   xbt_free(task);
1134
1135   sd_global->task_number--;
1136
1137   DEBUG0("Task destroyed.");
1138 }
1139
1140
1141 /** @brief create a end-to-end communication task that can then be auto-scheduled
1142  *
1143  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1144  * allows to specify the task costs at creation, and decorelate them from the
1145  * scheduling process where you just specify which resource should deliver the
1146  * mandatory power.
1147  *
1148  * A end-to-end communication must be scheduled on 2 hosts, and the amount
1149  * specified at creation is sent from hosts[0] to hosts[1].
1150  */
1151 SD_task_t SD_task_create_comm_e2e(const char*name, void *data, double amount) {
1152   SD_task_t res = SD_task_create(name,data,amount);
1153   res->kind=SD_TASK_COMM_E2E;
1154   return res;
1155 }
1156 /** @brief create a sequential computation task that can then be auto-scheduled
1157  *
1158  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1159  * allows to specify the task costs at creation, and decorelate them from the
1160  * scheduling process where you just specify which resource should deliver the
1161  * mandatory power.
1162  *
1163  * A sequential computation must be scheduled on 1 host, and the amount
1164  * specified at creation to be run on hosts[0].
1165  */
1166 SD_task_t SD_task_create_comp_seq(const char*name, void *data, double amount) {
1167   SD_task_t res = SD_task_create(name,data,amount);
1168   res->kind=SD_TASK_COMP_SEQ;
1169   return res;
1170 }
1171
1172 /** @brief Auto-schedules a task.
1173  *
1174  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1175  * allows to specify the task costs at creation, and decorelate them from the
1176  * scheduling process where you just specify which resource should deliver the
1177  * mandatory power.
1178  *
1179  * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1180  * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1181  * of them.
1182  *
1183  * @todo
1184  * We should create tasks kind for the following categories:
1185  *  - Point to point communication (done)
1186  *  - Sequential computation       (done)
1187  *  - group communication (redistribution, several kinds)
1188  *  - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1189  *  - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1190  */
1191 void SD_task_schedulev(SD_task_t task, int count, const SD_workstation_t*list) {
1192   xbt_assert1(task->kind != 0,"Task %s is not typed. Cannot automatically schedule it.",SD_task_get_name(task));
1193   double *comp,*comms;
1194   switch(task->kind) {
1195   case SD_TASK_COMM_E2E:
1196     xbt_assert2(count == 2,
1197           "Task %s is end to end communication, but scheduled with %d hosts",
1198           SD_task_get_name(task),count);
1199     comms=xbt_new(double,count);
1200     comms[0]=0;
1201     comms[1]=SD_task_get_amount(task);
1202     SD_task_schedule(task,count,list,NULL,comms,1);
1203     break;
1204   case SD_TASK_COMP_SEQ:
1205     xbt_assert2(count==1,
1206         "Task %s is sequential computation, but scheduled with %d hosts",
1207         SD_task_get_name(task),count);
1208     comp=xbt_new(double,count);
1209     comp[0]=SD_task_get_amount(task);
1210     SD_task_schedule(task,count,list,comp,NULL,1);
1211     break;
1212   default:
1213     xbt_die(bprintf("Kind of task %s not supported by SD_task_schedulev()",
1214           SD_task_get_name(task)));
1215   }
1216 }
1217 /** @brief autoschedule a task on a list of workstations
1218  *
1219  * This function is very similar to SD_task_schedulev(),
1220  * but takes the list of workstations to schedule onto as separate parameters.
1221  * It builds a proper vector of workstations and then call SD_task_schedulev()
1222  */
1223 void SD_task_schedulel(SD_task_t task, int count, ...) {
1224   va_list ap;
1225   SD_workstation_t *list=xbt_new(SD_workstation_t,count);
1226   int i;
1227   va_start(ap,count);
1228   for (i=0;i<count;i++) {
1229       list[i] = va_arg(ap,SD_workstation_t);
1230   }
1231   va_end(ap);
1232   SD_task_schedulev(task,count,list);
1233 }