src/simdag/sd_task.c

   1 /* Copyright (c) 2006-2016. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 #include "src/simdag/simdag_private.h"
   8 #include "simgrid/simdag.h"
   9 #include "xbt/sysdep.h"
  10 #include "xbt/dynar.h"
  11 #include "src/instr/instr_private.h"
  12
  13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
  14                                 "Logging specific to SimDag (task)");
  15
  16 static void __SD_task_remove_dependencies(SD_task_t task);
  17 static void __SD_task_destroy_scheduling_data(SD_task_t task);
  18
  19 void* SD_task_new_f(void)
  20 {
  21   SD_task_t task = xbt_new0(s_SD_task_t, 1);
  22   task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
  23   task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
  24
  25   return task;
  26 }
  27
  28 void SD_task_recycle_f(void *t)
  29 {
  30   SD_task_t task = (SD_task_t) t;
  31
  32   /* Reset the content */
  33   task->kind = SD_TASK_NOT_TYPED;
  34   task->state_hookup.prev = NULL;
  35   task->state_hookup.next = NULL;
  36   task->state_set = sd_global->not_scheduled_task_set;
  37   xbt_swag_insert(task, task->state_set);
  38   task->state = SD_NOT_SCHEDULED;
  39   task->return_hookup.prev = NULL;
  40   task->return_hookup.next = NULL;
  41
  42   task->marked = 0;
  43
  44   task->start_time = -1.0;
  45   task->finish_time = -1.0;
  46   task->surf_action = NULL;
  47   task->watch_points = 0;
  48
  49   /* dependencies */
  50   xbt_dynar_reset(task->tasks_before);
  51   xbt_dynar_reset(task->tasks_after);
  52   task->unsatisfied_dependencies = 0;
  53   task->is_not_ready = 0;
  54
  55   /* scheduling parameters */
  56   task->workstation_nb = 0;
  57   task->workstation_list = NULL;
  58   task->flops_amount = NULL;
  59   task->bytes_amount = NULL;
  60   task->rate = -1;
  61 }
  62
  63 void SD_task_free_f(void *t)
  64 {
  65   SD_task_t task = (SD_task_t)t;
  66
  67   xbt_dynar_free(&task->tasks_before);
  68   xbt_dynar_free(&task->tasks_after);
  69   xbt_free(task);
  70 }
  71
  72 /**
  73  * \brief Creates a new task.
  74  *
  75  * \param name the name of the task (can be \c NULL)
  76  * \param data the user data you want to associate with the task (can be \c NULL)
  77  * \param amount amount of the task
  78  * \return the new task
  79  * \see SD_task_destroy()
  80  */
  81 SD_task_t SD_task_create(const char *name, void *data, double amount)
  82 {
  83   SD_task_t task = xbt_mallocator_get(sd_global->task_mallocator);
  84
  85   /* general information */
  86   task->data = data;            /* user data */
  87   task->name = xbt_strdup(name);
  88   task->amount = amount;
  89   task->remains = amount;
  90
  91   sd_global->task_number++;
  92
  93   TRACE_sd_task_create(task);
  94
  95   return task;
  96 }
  97
  98 static XBT_INLINE SD_task_t SD_task_create_sized(const char *name,
  99                                                  void *data, double amount,
 100                                                  int ws_count)
 101 {
 102   SD_task_t task = SD_task_create(name, data, amount);
 103   task->bytes_amount = xbt_new0(double, ws_count * ws_count);
 104   task->flops_amount = xbt_new0(double, ws_count);
 105   task->workstation_nb = ws_count;
 106   task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
 107   return task;
 108 }
 109
 110 /** @brief create a end-to-end communication task that can then be auto-scheduled
 111  *
 112  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
 113  * allows to specify the task costs at creation, and decouple them from the
 114  * scheduling process where you just specify which resource should deliver the
 115  * mandatory power.
 116  *
 117  * A end-to-end communication must be scheduled on 2 hosts, and the amount
 118  * specified at creation is sent from hosts[0] to hosts[1].
 119  */
 120 SD_task_t SD_task_create_comm_e2e(const char *name, void *data,
 121                                   double amount)
 122 {
 123   SD_task_t res = SD_task_create_sized(name, data, amount, 2);
 124   res->bytes_amount[2] = amount;
 125   res->kind = SD_TASK_COMM_E2E;
 126
 127   TRACE_category("COMM_E2E");
 128   TRACE_sd_set_task_category(res, "COMM_E2E");
 129
 130   return res;
 131 }
 132
 133 /** @brief create a sequential computation task that can then be auto-scheduled
 134  *
 135  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
 136  * allows to specify the task costs at creation, and decouple them from the
 137  * scheduling process where you just specify which resource should deliver the
 138  * mandatory power.
 139  *
 140  * A sequential computation must be scheduled on 1 host, and the amount
 141  * specified at creation to be run on hosts[0].
 142  *
 143  * \param name the name of the task (can be \c NULL)
 144  * \param data the user data you want to associate with the task (can be \c NULL)
 145  * \param flops_amount amount of compute work to be done by the task
 146  * \return the new SD_TASK_COMP_SEQ typed task
 147  */
 148 SD_task_t SD_task_create_comp_seq(const char *name, void *data,
 149                                   double flops_amount)
 150 {
 151   SD_task_t res = SD_task_create_sized(name, data, flops_amount, 1);
 152   res->flops_amount[0] = flops_amount;
 153   res->kind = SD_TASK_COMP_SEQ;
 154
 155   TRACE_category("COMP_SEQ");
 156   TRACE_sd_set_task_category(res, "COMP_SEQ");
 157
 158   return res;
 159 }
 160
 161 /** @brief create a parallel computation task that can then be auto-scheduled
 162  *
 163  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
 164  * allows to specify the task costs at creation, and decouple them from the
 165  * scheduling process where you just specify which resource should deliver the
 166  * mandatory power.
 167  *
 168  * A parallel computation can be scheduled on any number of host.
 169  * The underlying speedup model is Amdahl's law.
 170  * To be auto-scheduled, \see SD_task_distribute_comp_amdahl has to be called
 171  * first.
 172  * \param name the name of the task (can be \c NULL)
 173  * \param data the user data you want to associate with the task (can be \c NULL)
 174  * \param flops_amount amount of compute work to be done by the task
 175  * \param alpha purely serial fraction of the work to be done (in [0.;1.[)
 176  * \return the new task
 177  */
 178 SD_task_t SD_task_create_comp_par_amdahl(const char *name, void *data,
 179                                   double flops_amount, double alpha)
 180 {
 181   xbt_assert(alpha < 1. && alpha >= 0.,
 182               "Invalid parameter: alpha must be in [0.;1.[");
 183
 184   SD_task_t res = SD_task_create(name, data, flops_amount);
 185   res->alpha = alpha;
 186   res->kind = SD_TASK_COMP_PAR_AMDAHL;
 187
 188   TRACE_category("COMP_PAR_AMDAHL");
 189   TRACE_sd_set_task_category(res, "COMP_PAR_AMDAHL");
 190
 191   return res;
 192 }
 193
 194 /** @brief create a complex data redistribution task that can then be
 195  * auto-scheduled
 196  *
 197  * Auto-scheduling mean that the task can be used with SD_task_schedulev().
 198  * This allows to specify the task costs at creation, and decouple them from
 199  * the scheduling process where you just specify which resource should
 200  * communicate.
 201  *
 202  * A data redistribution can be scheduled on any number of host.
 203  * The assumed distribution is a 1D block distribution. Each host owns the same
 204  * share of the \see amount.
 205  * To be auto-scheduled, \see SD_task_distribute_comm_mxn_1d_block has to be
 206  * called first.
 207  * \param name the name of the task (can be \c NULL)
 208  * \param data the user data you want to associate with the task (can be
 209  * \c NULL)
 210  * \param amount amount of data to redistribute by the task
 211  * \return the new task
 212  */
 213 SD_task_t SD_task_create_comm_par_mxn_1d_block(const char *name, void *data,
 214                                                double amount)
 215 {
 216   SD_task_t res = SD_task_create(name, data, amount);
 217   res->workstation_list=NULL;
 218   res->kind = SD_TASK_COMM_PAR_MXN_1D_BLOCK;
 219
 220   TRACE_category("COMM_PAR_MXN_1D_BLOCK");
 221   TRACE_sd_set_task_category(res, "COMM_PAR_MXN_1D_BLOCK");
 222
 223   return res;
 224 }
 225
 226 /**
 227  * \brief Destroys a task.
 228  *
 229  * The user data (if any) should have been destroyed first.
 230  *
 231  * \param task the task you want to destroy
 232  * \see SD_task_create()
 233  */
 234 void SD_task_destroy(SD_task_t task)
 235 {
 236   XBT_DEBUG("Destroying task %s...", SD_task_get_name(task));
 237
 238   __SD_task_remove_dependencies(task);
 239   /* if the task was scheduled or runnable we have to free the scheduling parameters */
 240   if (__SD_task_is_scheduled_or_runnable(task))
 241     __SD_task_destroy_scheduling_data(task);
 242   if (task->state_set != NULL) /* would be null if just created */
 243     xbt_swag_remove(task, task->state_set);
 244
 245   xbt_swag_remove(task, sd_global->return_set);
 246
 247   xbt_free(task->name);
 248
 249   if (task->surf_action != NULL)
 250         surf_action_unref(task->surf_action);
 251
 252   xbt_free(task->workstation_list);
 253   xbt_free(task->bytes_amount);
 254   xbt_free(task->flops_amount);
 255
 256   TRACE_sd_task_destroy(task);
 257
 258   xbt_mallocator_release(sd_global->task_mallocator,task);
 259   sd_global->task_number--;
 260
 261   XBT_DEBUG("Task destroyed.");
 262 }
 263
 264 /**
 265  * \brief Returns the user data of a task
 266  *
 267  * \param task a task
 268  * \return the user data associated with this task (can be \c NULL)
 269  * \see SD_task_set_data()
 270  */
 271 void *SD_task_get_data(SD_task_t task)
 272 {
 273   return task->data;
 274 }
 275
 276 /**
 277  * \brief Sets the user data of a task
 278  *
 279  * The new data can be \c NULL. The old data should have been freed first
 280  * if it was not \c NULL.
 281  *
 282  * \param task a task
 283  * \param data the new data you want to associate with this task
 284  * \see SD_task_get_data()
 285  */
 286 void SD_task_set_data(SD_task_t task, void *data)
 287 {
 288   task->data = data;
 289 }
 290
 291 /**
 292  * \brief Sets the rate of a task
 293  *
 294  * This will change the network bandwidth a task can use. This rate
 295  * cannot be dynamically changed. Once the task has started, this call
 296  * is ineffective. This rate depends on both the nominal bandwidth on
 297  * the route onto which the task is scheduled (\see
 298  * SD_task_get_current_bandwidth) and the amount of data to transfer.
 299  *
 300  * To divide the nominal bandwidth by 2, the rate then has to be :
 301  *    rate = bandwidth/(2*amount)
 302  *
 303  * \param task a \see SD_TASK_COMM_E2E task (end-to-end communication)
 304  * \param rate the new rate you want to associate with this task.
 305  */
 306 void SD_task_set_rate(SD_task_t task, double rate)
 307 {
 308   xbt_assert(task->kind == SD_TASK_COMM_E2E,
 309              "The rate can be modified for end-to-end communications only.");
 310   if(task->start_time<0) {
 311     task->rate = rate;
 312   } else {
 313     XBT_WARN("Task %p has started. Changing rate is ineffective.", task);
 314   }
 315 }
 316
 317 /**
 318  * \brief Returns the state of a task
 319  *
 320  * \param task a task
 321  * \return the current \ref e_SD_task_state_t "state" of this task:
 322  * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
 323  * \see e_SD_task_state_t
 324  */
 325 e_SD_task_state_t SD_task_get_state(SD_task_t task)
 326 {
 327   return task->state;
 328 }
 329
 330 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
 331  */
 332 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
 333 {
 334   xbt_swag_remove(task, task->state_set);
 335   switch (new_state) {
 336   case SD_NOT_SCHEDULED:
 337     task->state_set = sd_global->not_scheduled_task_set;
 338     break;
 339   case SD_SCHEDULABLE:
 340     task->state_set = sd_global->schedulable_task_set;
 341     break;
 342   case SD_SCHEDULED:
 343     task->state_set = sd_global->scheduled_task_set;
 344     break;
 345   case SD_RUNNABLE:
 346     task->state_set = sd_global->runnable_task_set;
 347     break;
 348   case SD_IN_FIFO:
 349     task->state_set = sd_global->in_fifo_task_set;
 350     break;
 351   case SD_RUNNING:
 352     task->state_set = sd_global->running_task_set;
 353     task->start_time = surf_action_get_start_time(task->surf_action);
 354     break;
 355   case SD_DONE:
 356     task->state_set = sd_global->done_task_set;
 357     task->finish_time = surf_action_get_finish_time(task->surf_action);
 358     task->remains = 0;
 359 #ifdef HAVE_JEDULE
 360     jedule_log_sd_event(task);
 361 #endif
 362     break;
 363   case SD_FAILED:
 364     task->state_set = sd_global->failed_task_set;
 365     break;
 366   default:
 367     xbt_die( "Invalid state");
 368   }
 369   xbt_swag_insert(task, task->state_set);
 370   task->state = new_state;
 371
 372   if (task->watch_points & new_state) {
 373     XBT_VERB("Watch point reached with task '%s'!", SD_task_get_name(task));
 374     sd_global->watch_point_reached = 1;
 375     SD_task_unwatch(task, new_state);   /* remove the watch point */
 376   }
 377 }
 378
 379 /**
 380  * \brief Returns the name of a task
 381  *
 382  * \param task a task
 383  * \return the name of this task (can be \c NULL)
 384  */
 385 const char *SD_task_get_name(SD_task_t task)
 386 {
 387   return task->name;
 388 }
 389
 390 /** @brief Allows to change the name of a task */
 391 void SD_task_set_name(SD_task_t task, const char *name)
 392 {
 393   xbt_free(task->name);
 394   task->name = xbt_strdup(name);
 395 }
 396
 397 /** @brief Returns the dynar of the parents of a task
 398  *
 399  * \param task a task
 400  * \return a newly allocated dynar comprising the parents of this task
 401  */
 402
 403 xbt_dynar_t SD_task_get_parents(SD_task_t task)
 404 {
 405   unsigned int i;
 406   xbt_dynar_t parents;
 407   SD_dependency_t dep;
 408
 409   parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
 410   xbt_dynar_foreach(task->tasks_before, i, dep) {
 411     xbt_dynar_push(parents, &(dep->src));
 412   }
 413   return parents;
 414 }
 415
 416 /** @brief Returns the dynar of the parents of a task
 417  *
 418  * \param task a task
 419  * \return a newly allocated dynar comprising the parents of this task
 420  */
 421 xbt_dynar_t SD_task_get_children(SD_task_t task)
 422 {
 423   unsigned int i;
 424   xbt_dynar_t children;
 425   SD_dependency_t dep;
 426
 427   children = xbt_dynar_new(sizeof(SD_task_t), NULL);
 428   xbt_dynar_foreach(task->tasks_after, i, dep) {
 429     xbt_dynar_push(children, &(dep->dst));
 430   }
 431   return children;
 432 }
 433
 434 /**
 435  * \brief Returns the amount of workstations involved in a task
 436  *
 437  * Only call this on already scheduled tasks!
 438  * \param task a task
 439  */
 440 int SD_task_get_workstation_count(SD_task_t task)
 441 {
 442   return task->workstation_nb;
 443 }
 444
 445 /**
 446  * \brief Returns the list of workstations involved in a task
 447  *
 448  * Only call this on already scheduled tasks!
 449  * \param task a task
 450  */
 451 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
 452 {
 453   return task->workstation_list;
 454 }
 455
 456 /**
 457  * \brief Returns the total amount of work contained in a task
 458  *
 459  * \param task a task
 460  * \return the total amount of work (computation or data transfer) for this task
 461  * \see SD_task_get_remaining_amount()
 462  */
 463 double SD_task_get_amount(SD_task_t task)
 464 {
 465   return task->amount;
 466 }
 467
 468 /**
 469  * \brief Sets the total amount of work of a task
 470  * For sequential typed tasks (COMP_SEQ and COMM_E2E), it also sets the
 471  * appropriate values in the flops_amount and bytes_amount arrays
 472  * respectively. Nothing more than modifying task->amount is done for paralle
 473  * typed tasks (COMP_PAR_AMDAHL and COMM_PAR_MXN_1D_BLOCK) as the distribution
 474  * of the amount of work is done at scheduling time.
 475  *
 476  * \param task a task
 477  * \param amount the new amount of work to execute
 478  */
 479 void SD_task_set_amount(SD_task_t task, double amount)
 480 {
 481   task->amount = amount;
 482   if (task->kind == SD_TASK_COMP_SEQ)
 483     task->flops_amount[0] = amount;
 484   if (task->kind == SD_TASK_COMM_E2E)
 485     task->bytes_amount[2] = amount;
 486 }
 487
 488 /**
 489  * \brief Returns the alpha parameter of a SD_TASK_COMP_PAR_AMDAHL task
 490  *
 491  * \param task a parallel task assuming Amdahl's law as speedup model
 492  * \return the alpha parameter (serial part of a task in percent) for this task
 493  */
 494 double SD_task_get_alpha(SD_task_t task)
 495 {
 496   xbt_assert(SD_task_get_kind(task) == SD_TASK_COMP_PAR_AMDAHL,
 497      "Alpha parameter is not defined for this kink of task");
 498   return task->alpha;
 499 }
 500
 501
 502 /**
 503  * \brief Returns the remaining amount work to do till the completion of a task
 504  *
 505  * \param task a task
 506  * \return the remaining amount of work (computation or data transfer) of this task
 507  * \see SD_task_get_amount()
 508  */
 509 double SD_task_get_remaining_amount(SD_task_t task)
 510 {
 511   if (task->surf_action)
 512         return surf_action_get_remains(task->surf_action);
 513   else
 514     return task->remains;
 515 }
 516
 517 int SD_task_get_kind(SD_task_t task)
 518 {
 519   return task->kind;
 520 }
 521
 522 /** @brief Displays debugging informations about a task */
 523 void SD_task_dump(SD_task_t task)
 524 {
 525   unsigned int counter;
 526   SD_dependency_t dependency;
 527   char *statename;
 528
 529   XBT_INFO("Displaying task %s", SD_task_get_name(task));
 530   statename = bprintf("%s %s %s %s %s %s %s %s",
 531                       (task->state == SD_NOT_SCHEDULED ? "not scheduled" :
 532                        ""),
 533                       (task->state == SD_SCHEDULABLE ? "schedulable" : ""),
 534                       (task->state == SD_SCHEDULED ? "scheduled" : ""),
 535                       (task->state == SD_RUNNABLE ? "runnable" :
 536                        "not runnable"),
 537                       (task->state == SD_IN_FIFO ? "in fifo" : ""),
 538                       (task->state == SD_RUNNING ? "running" : ""),
 539                       (task->state == SD_DONE ? "done" : ""),
 540                       (task->state == SD_FAILED ? "failed" : ""));
 541   XBT_INFO("  - state: %s", statename);
 542   free(statename);
 543
 544   if (task->kind != 0) {
 545     switch (task->kind) {
 546     case SD_TASK_COMM_E2E:
 547       XBT_INFO("  - kind: end-to-end communication");
 548       break;
 549     case SD_TASK_COMP_SEQ:
 550       XBT_INFO("  - kind: sequential computation");
 551       break;
 552     case SD_TASK_COMP_PAR_AMDAHL:
 553       XBT_INFO("  - kind: parallel computation following Amdahl's law");
 554       break;
 555     case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
 556       XBT_INFO("  - kind: MxN data redistribution assuming 1D block distribution");
 557       break;
 558     default:
 559       XBT_INFO("  - (unknown kind %d)", task->kind);
 560     }
 561   }
 562
 563   if (task->category)
 564     XBT_INFO("  - tracing category: %s", task->category);
 565
 566   XBT_INFO("  - amount: %.0f", SD_task_get_amount(task));
 567   if (task->kind == SD_TASK_COMP_PAR_AMDAHL)
 568     XBT_INFO("  - alpha: %.2f", task->alpha);
 569   XBT_INFO("  - Dependencies to satisfy: %d", task->unsatisfied_dependencies);
 570   if (!xbt_dynar_is_empty(task->tasks_before)) {
 571     XBT_INFO("  - pre-dependencies:");
 572     xbt_dynar_foreach(task->tasks_before, counter, dependency) {
 573       XBT_INFO("    %s", SD_task_get_name(dependency->src));
 574     }
 575   }
 576   if (!xbt_dynar_is_empty(task->tasks_after)) {
 577     XBT_INFO("  - post-dependencies:");
 578     xbt_dynar_foreach(task->tasks_after, counter, dependency) {
 579       XBT_INFO("    %s", SD_task_get_name(dependency->dst));
 580     }
 581   }
 582 }
 583
 584 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
 585 void SD_task_dotty(SD_task_t task, void *out)
 586 {
 587   unsigned int counter;
 588   SD_dependency_t dependency;
 589   fprintf(out, "  T%p [label=\"%.20s\"", task, task->name);
 590   switch (task->kind) {
 591   case SD_TASK_COMM_E2E:
 592   case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
 593     fprintf(out, ", shape=box");
 594     break;
 595   case SD_TASK_COMP_SEQ:
 596   case SD_TASK_COMP_PAR_AMDAHL:
 597     fprintf(out, ", shape=circle");
 598     break;
 599   default:
 600     xbt_die("Unknown task type!");
 601   }
 602   fprintf(out, "];\n");
 603   xbt_dynar_foreach(task->tasks_before, counter, dependency) {
 604     fprintf(out, " T%p -> T%p;\n", dependency->src, dependency->dst);
 605   }
 606 }
 607
 608 /* Destroys a dependency between two tasks.
 609  */
 610 static void __SD_task_dependency_destroy(void *dependency)
 611 {
 612   xbt_free(((SD_dependency_t)dependency)->name);
 613   xbt_free(dependency);
 614 }
 615
 616 /**
 617  * \brief Adds a dependency between two tasks
 618  *
 619  * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
 620  * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
 621  *
 622  * \param name the name of the new dependency (can be \c NULL)
 623  * \param data the user data you want to associate with this dependency (can be \c NULL)
 624  * \param src the task which must be executed first
 625  * \param dst the task you want to make depend on \a src
 626  * \see SD_task_dependency_remove()
 627  */
 628 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
 629                             SD_task_t dst)
 630 {
 631   xbt_dynar_t dynar;
 632   unsigned long length;
 633   int found = 0;
 634   unsigned long i;
 635   SD_dependency_t dependency;
 636
 637   dynar = src->tasks_after;
 638   length = xbt_dynar_length(dynar);
 639
 640   if (src == dst)
 641     THROWF(arg_error, 0,
 642            "Cannot add a dependency between task '%s' and itself",
 643            SD_task_get_name(src));
 644
 645   if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_schedulable(src)
 646       && !__SD_task_is_scheduled_or_runnable(src) && !__SD_task_is_running(src))
 647     THROWF(arg_error, 0,
 648            "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE"
 649      " or SD_RUNNING",
 650            SD_task_get_name(src));
 651
 652   if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_schedulable(dst)
 653       && !__SD_task_is_scheduled_or_runnable(dst))
 654     THROWF(arg_error, 0,
 655            "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
 656            SD_task_get_name(dst));
 657
 658   XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s",
 659          SD_task_get_name(src), SD_task_get_name(dst));
 660   for (i = 0; i < length && !found; i++) {
 661     xbt_dynar_get_cpy(dynar, i, &dependency);
 662     found = (dependency->dst == dst);
 663     XBT_DEBUG("Dependency %lu: dependency->dst = %s", i,
 664            SD_task_get_name(dependency->dst));
 665   }
 666
 667   if (found)
 668     THROWF(arg_error, 0,
 669            "A dependency already exists between task '%s' and task '%s'",
 670            SD_task_get_name(src), SD_task_get_name(dst));
 671
 672   dependency = xbt_new(s_SD_dependency_t, 1);
 673
 674   dependency->name = xbt_strdup(name);  /* xbt_strdup is cleaver enough to deal with NULL args itself */
 675   dependency->data = data;
 676   dependency->src = src;
 677   dependency->dst = dst;
 678
 679   /* src must be executed before dst */
 680   xbt_dynar_push(src->tasks_after, &dependency);
 681   xbt_dynar_push(dst->tasks_before, &dependency);
 682
 683   dst->unsatisfied_dependencies++;
 684   dst->is_not_ready++;
 685
 686   /* if the task was runnable, then dst->tasks_before is not empty anymore,
 687      so we must go back to state SD_SCHEDULED */
 688   if (__SD_task_is_runnable(dst)) {
 689     XBT_DEBUG
 690         ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
 691          SD_task_get_name(dst));
 692     __SD_task_set_state(dst, SD_SCHEDULED);
 693   }
 694 }
 695 /**
 696  * \brief Returns the name given as input when dependency has been created..
 697  *
 698  * \param src a task
 699  * \param dst a task depending on \a src
 700  *
 701  */
 702 const char *SD_task_dependency_get_name(SD_task_t src, SD_task_t dst){
 703   unsigned int i;
 704   SD_dependency_t dependency;
 705
 706   xbt_dynar_foreach(src->tasks_after, i, dependency){
 707     if (dependency->dst == dst)
 708       return dependency->name;
 709   }
 710   return NULL;
 711 }
 712
 713 /**
 714  * \brief Indicates whether there is a dependency between two tasks.
 715  *
 716  * \param src a task
 717  * \param dst a task depending on \a src
 718  *
 719  * If src is NULL, checks whether dst has any pre-dependency.
 720  * If dst is NULL, checks whether src has any post-dependency.
 721  */
 722 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
 723 {
 724   unsigned int counter;
 725   SD_dependency_t dependency;
 726
 727   xbt_assert(src != NULL
 728               || dst != NULL,
 729               "Invalid parameter: both src and dst are NULL");
 730
 731   if (src) {
 732     if (dst) {
 733       xbt_dynar_foreach(src->tasks_after, counter, dependency) {
 734         if (dependency->dst == dst)
 735           return 1;
 736       }
 737     } else {
 738       return xbt_dynar_length(src->tasks_after);
 739     }
 740   } else {
 741     return xbt_dynar_length(dst->tasks_before);
 742   }
 743   return 0;
 744 }
 745
 746 /**
 747  * \brief Remove a dependency between two tasks
 748  *
 749  * \param src a task
 750  * \param dst a task depending on \a src
 751  * \see SD_task_dependency_add()
 752  */
 753 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
 754 {
 755
 756   xbt_dynar_t dynar;
 757   unsigned long length;
 758   int found = 0;
 759   unsigned long i;
 760   SD_dependency_t dependency;
 761
 762   /* remove the dependency from src->tasks_after */
 763   dynar = src->tasks_after;
 764   length = xbt_dynar_length(dynar);
 765
 766   for (i = 0; i < length && !found; i++) {
 767     xbt_dynar_get_cpy(dynar, i, &dependency);
 768     if (dependency->dst == dst) {
 769       xbt_dynar_remove_at(dynar, i, NULL);
 770       found = 1;
 771     }
 772   }
 773   if (!found)
 774     THROWF(arg_error, 0,
 775            "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
 776            SD_task_get_name(src), SD_task_get_name(dst),
 777            SD_task_get_name(dst), SD_task_get_name(src));
 778
 779   /* remove the dependency from dst->tasks_before */
 780   dynar = dst->tasks_before;
 781   length = xbt_dynar_length(dynar);
 782   found = 0;
 783
 784   for (i = 0; i < length && !found; i++) {
 785     xbt_dynar_get_cpy(dynar, i, &dependency);
 786     if (dependency->src == src) {
 787       xbt_dynar_remove_at(dynar, i, NULL);
 788       __SD_task_dependency_destroy(dependency);
 789       dst->unsatisfied_dependencies--;
 790       dst->is_not_ready--;
 791       found = 1;
 792     }
 793   }
 794   /* should never happen... */
 795   xbt_assert(found,
 796               "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
 797               SD_task_get_name(dst), SD_task_get_name(src),
 798               SD_task_get_name(src), SD_task_get_name(dst));
 799
 800   /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
 801
 802   if (dst->unsatisfied_dependencies == 0) {
 803     if (__SD_task_is_scheduled(dst))
 804       __SD_task_set_state(dst, SD_RUNNABLE);
 805     else
 806       __SD_task_set_state(dst, SD_SCHEDULABLE);
 807   }
 808
 809   if (dst->is_not_ready == 0)
 810     __SD_task_set_state(dst, SD_SCHEDULABLE);
 811
 812   /*  __SD_print_dependencies(src);
 813      __SD_print_dependencies(dst); */
 814 }
 815
 816 /**
 817  * \brief Returns the user data associated with a dependency between two tasks
 818  *
 819  * \param src a task
 820  * \param dst a task depending on \a src
 821  * \return the user data associated with this dependency (can be \c NULL)
 822  * \see SD_task_dependency_add()
 823  */
 824 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
 825 {
 826
 827   xbt_dynar_t dynar;
 828   unsigned long length;
 829   int found = 0;
 830   unsigned long i;
 831   SD_dependency_t dependency;
 832
 833   dynar = src->tasks_after;
 834   length = xbt_dynar_length(dynar);
 835
 836   for (i = 0; i < length && !found; i++) {
 837     xbt_dynar_get_cpy(dynar, i, &dependency);
 838     found = (dependency->dst == dst);
 839   }
 840   if (!found)
 841     THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'",
 842            SD_task_get_name(src), SD_task_get_name(dst));
 843   return dependency->data;
 844 }
 845
 846 /* temporary function for debugging */
 847 static void __SD_print_watch_points(SD_task_t task)
 848 {
 849   static const int state_masks[] =
 850       { SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE,
 851     SD_FAILED
 852   };
 853   static const char *state_names[] =
 854       { "schedulable", "scheduled", "running", "runnable", "done",
 855     "failed"
 856   };
 857   int i;
 858
 859   XBT_INFO("Task '%s' watch points (%x): ", SD_task_get_name(task),
 860         task->watch_points);
 861
 862
 863   for (i = 0; i < 5; i++) {
 864     if (task->watch_points & state_masks[i])
 865       XBT_INFO("%s ", state_names[i]);
 866   }
 867 }
 868
 869 /**
 870  * \brief Adds a watch point to a task
 871  *
 872  * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
 873  * task becomes the one given in argument. The
 874  * watch point is then automatically removed.
 875  *
 876  * \param task a task
 877  * \param state the \ref e_SD_task_state_t "state" you want to watch
 878  * (cannot be #SD_NOT_SCHEDULED)
 879  * \see SD_task_unwatch()
 880  */
 881 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
 882 {
 883   if (state & SD_NOT_SCHEDULED)
 884     THROWF(arg_error, 0,
 885            "Cannot add a watch point for state SD_NOT_SCHEDULED");
 886
 887   task->watch_points = task->watch_points | state;
 888   /*  __SD_print_watch_points(task); */
 889 }
 890
 891 /**
 892  * \brief Removes a watch point from a task
 893  *
 894  * \param task a task
 895  * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
 896  * \see SD_task_watch()
 897  */
 898 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
 899 {
 900   xbt_assert(state != SD_NOT_SCHEDULED,
 901               "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
 902
 903   task->watch_points = task->watch_points & ~state;
 904   /*  __SD_print_watch_points(task); */
 905 }
 906
 907 /**
 908  * \brief Returns an approximative estimation of the execution time of a task.
 909  *
 910  * The estimation is very approximative because the value returned is the time
 911  * the task would take if it was executed now and if it was the only task.
 912  *
 913  * \param task the task to evaluate
 914  * \param workstation_nb number of workstations on which the task would be executed
 915  * \param workstation_list the workstations on which the task would be executed
 916  * \param flops_amount computation amount for each workstation
 917  * \param bytes_amount communication amount between each pair of workstations
 918  * \see SD_schedule()
 919  */
 920 double SD_task_get_execution_time(SD_task_t task,
 921                                   int workstation_nb,
 922                                   const SD_workstation_t *
 923                                   workstation_list,
 924                                   const double *flops_amount,
 925                                   const double *bytes_amount)
 926 {
 927   double time, max_time = 0.0;
 928   int i, j;
 929   xbt_assert(workstation_nb > 0, "Invalid parameter");
 930
 931   /* the task execution time is the maximum execution time of the parallel tasks */
 932
 933   for (i = 0; i < workstation_nb; i++) {
 934     time = 0.0;
 935     if (flops_amount != NULL)
 936       time =
 937           SD_workstation_get_computation_time(workstation_list[i],
 938                                               flops_amount[i]);
 939
 940     if (bytes_amount != NULL)
 941       for (j = 0; j < workstation_nb; j++) {
 942         time +=
 943             SD_route_get_communication_time(workstation_list[i],
 944                                             workstation_list[j],
 945                                             bytes_amount[i *
 946                                                                  workstation_nb
 947                                                                  + j]);
 948       }
 949
 950     if (time > max_time) {
 951       max_time = time;
 952     }
 953   }
 954   return max_time;
 955 }
 956
 957 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
 958 {
 959   if (!__SD_task_is_not_scheduled(task) && !__SD_task_is_schedulable(task))
 960     THROWF(arg_error, 0, "Task '%s' has already been scheduled",
 961            SD_task_get_name(task));
 962
 963   /* update the task state */
 964   if (task->unsatisfied_dependencies == 0)
 965     __SD_task_set_state(task, SD_RUNNABLE);
 966   else
 967     __SD_task_set_state(task, SD_SCHEDULED);
 968 }
 969
 970 /**
 971  * \brief Schedules a task
 972  *
 973  * The task state must be #SD_NOT_SCHEDULED.
 974  * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
 975  * i.e. when its dependencies are satisfied.
 976  *
 977  * \param task the task you want to schedule
 978  * \param workstation_count number of workstations on which the task will be executed
 979  * \param workstation_list the workstations on which the task will be executed
 980  * \param flops_amount computation amount for each workstation
 981  * \param bytes_amount communication amount between each pair of workstations
 982  * \param rate task execution speed rate
 983  * \see SD_task_unschedule()
 984  */
 985 void SD_task_schedule(SD_task_t task, int workstation_count,
 986                       const SD_workstation_t * workstation_list,
 987                       const double *flops_amount,
 988                       const double *bytes_amount, double rate)
 989 {
 990   int communication_nb;
 991   task->workstation_nb = 0;
 992   task->rate = -1;
 993   xbt_assert(workstation_count > 0, "workstation_nb must be positive");
 994
 995   task->workstation_nb = workstation_count;
 996   task->rate = rate;
 997
 998   if (flops_amount) {
 999     task->flops_amount = xbt_realloc(task->flops_amount,
1000                                            sizeof(double) * workstation_count);
1001     memcpy(task->flops_amount, flops_amount,
1002            sizeof(double) * workstation_count);
1003   } else {
1004     xbt_free(task->flops_amount);
1005     task->flops_amount = NULL;
1006   }
1007
1008   communication_nb = workstation_count * workstation_count;
1009   if (bytes_amount) {
1010     task->bytes_amount = xbt_realloc(task->bytes_amount,
1011                                              sizeof(double) * communication_nb);
1012     memcpy(task->bytes_amount, bytes_amount,
1013            sizeof(double) * communication_nb);
1014   } else {
1015     xbt_free(task->bytes_amount);
1016     task->bytes_amount = NULL;
1017   }
1018
1019   task->workstation_list =
1020     xbt_realloc(task->workstation_list,
1021                 sizeof(SD_workstation_t) * workstation_count);
1022   memcpy(task->workstation_list, workstation_list,
1023          sizeof(SD_workstation_t) * workstation_count);
1024
1025   SD_task_do_schedule(task);
1026 }
1027
1028 /**
1029  * \brief Unschedules a task
1030  *
1031  * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
1032  * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
1033  * Call SD_task_schedule() to schedule it again.
1034  *
1035  * \param task the task you want to unschedule
1036  * \see SD_task_schedule()
1037  */
1038 void SD_task_unschedule(SD_task_t task)
1039 {
1040   if (task->state_set != sd_global->scheduled_task_set &&
1041       task->state_set != sd_global->runnable_task_set &&
1042       task->state_set != sd_global->running_task_set &&
1043       task->state_set != sd_global->failed_task_set)
1044     THROWF(arg_error, 0,
1045            "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
1046            SD_task_get_name(task));
1047
1048   if (__SD_task_is_scheduled_or_runnable(task)  /* if the task is scheduled or runnable */
1049       && ((task->kind == SD_TASK_COMP_PAR_AMDAHL) ||
1050           (task->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK))) { /* Don't free scheduling data for typed tasks */
1051     __SD_task_destroy_scheduling_data(task);
1052     xbt_free(task->workstation_list);
1053     task->workstation_list=NULL;
1054     task->workstation_nb = 0;
1055   }
1056
1057   if (__SD_task_is_running(task))       /* the task should become SD_FAILED */
1058         surf_action_cancel(task->surf_action);
1059   else {
1060     if (task->unsatisfied_dependencies == 0)
1061       __SD_task_set_state(task, SD_SCHEDULABLE);
1062     else
1063       __SD_task_set_state(task, SD_NOT_SCHEDULED);
1064   }
1065   task->remains = task->amount;
1066   task->start_time = -1.0;
1067 }
1068
1069 /* Destroys the data memorized by SD_task_schedule.
1070  * Task state must be SD_SCHEDULED or SD_RUNNABLE.
1071  */
1072 static void __SD_task_destroy_scheduling_data(SD_task_t task)
1073 {
1074   if (!__SD_task_is_scheduled_or_runnable(task)
1075       && !__SD_task_is_in_fifo(task))
1076     THROWF(arg_error, 0,
1077            "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
1078            SD_task_get_name(task));
1079
1080   xbt_free(task->flops_amount);
1081   xbt_free(task->bytes_amount);
1082   task->flops_amount = task->bytes_amount = NULL;
1083 }
1084
1085 /* Runs a task. This function is directly called by __SD_task_try_to_run if
1086  * the task doesn't have to wait in FIFOs. Otherwise, it is called by
1087  * __SD_task_just_done when the task gets out of its FIFOs.
1088  */
1089 void __SD_task_really_run(SD_task_t task)
1090 {
1091
1092   int i;
1093   sg_host_t *hosts;
1094
1095   xbt_assert(__SD_task_is_runnable_or_in_fifo(task),
1096               "Task '%s' is not runnable or in a fifo! Task state: %d",
1097              SD_task_get_name(task), (int)SD_task_get_state(task));
1098   xbt_assert(task->workstation_list != NULL,
1099               "Task '%s': workstation_list is NULL!",
1100               SD_task_get_name(task));
1101
1102   XBT_DEBUG("Really running task '%s'", SD_task_get_name(task));
1103   int host_nb = task->workstation_nb;
1104
1105   /* set this task as current task for the workstations in sequential mode */
1106   for (i = 0; i < host_nb; i++) {
1107     if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
1108         SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1109         sg_host_sd(task->workstation_list[i])->current_task = task;
1110       xbt_assert(__SD_workstation_is_busy(task->workstation_list[i]),
1111                   "The workstation should be busy now");
1112     }
1113   }
1114
1115   XBT_DEBUG("Task '%s' set as current task for its workstations",
1116          SD_task_get_name(task));
1117
1118   /* start the task */
1119
1120   /* Copy the elements of the task into the action */
1121   hosts = xbt_new(sg_host_t, host_nb);
1122
1123   for (i = 0; i < host_nb; i++)
1124     hosts[i] =  task->workstation_list[i];
1125
1126   double *flops_amount = xbt_new0(double, host_nb);
1127   double *bytes_amount = xbt_new0(double, host_nb * host_nb);
1128
1129
1130   if(task->flops_amount)
1131     memcpy(flops_amount, task->flops_amount, sizeof(double) *
1132            host_nb);
1133   if(task->bytes_amount)
1134     memcpy(bytes_amount, task->bytes_amount,
1135            sizeof(double) * host_nb * host_nb);
1136
1137   task->surf_action = surf_host_model_execute_parallel_task((surf_host_model_t)surf_host_model,
1138                                                                      host_nb,
1139                                                                      hosts,
1140                                                                      flops_amount,
1141                                                                      bytes_amount,
1142                                                                      task->rate);
1143
1144   surf_action_set_data(task->surf_action, task);
1145
1146   XBT_DEBUG("surf_action = %p", task->surf_action);
1147
1148   if (task->category)
1149     TRACE_surf_action(task->surf_action, task->category);
1150
1151   __SD_task_destroy_scheduling_data(task);      /* now the scheduling data are not useful anymore */
1152   __SD_task_set_state(task, SD_RUNNING);
1153   xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
1154              SD_task_get_name(task), (int)SD_task_get_state(task));
1155
1156 }
1157
1158 /* Tries to run a task. This function is called by SD_simulate() when a
1159  * scheduled task becomes SD_RUNNABLE (i.e., when its dependencies are
1160  * satisfied).
1161  * If one of the workstations where the task is scheduled on is busy (in
1162  * sequential mode), the task doesn't start.
1163  * Returns whether the task has started.
1164  */
1165 int __SD_task_try_to_run(SD_task_t task)
1166 {
1167
1168   int can_start = 1;
1169   int i;
1170   SD_workstation_t workstation;
1171
1172   xbt_assert(__SD_task_is_runnable(task),
1173               "Task '%s' is not runnable! Task state: %d",
1174              SD_task_get_name(task), (int)SD_task_get_state(task));
1175
1176
1177   for (i = 0; i < task->workstation_nb; i++) {
1178     can_start = can_start &&
1179         !__SD_workstation_is_busy(task->workstation_list[i]);
1180   }
1181
1182   XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1183
1184   if (!can_start) {             /* if the task cannot start and is not in the FIFOs yet */
1185     for (i = 0; i < task->workstation_nb; i++) {
1186       workstation = task->workstation_list[i];
1187       if (sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1188         XBT_DEBUG("Pushing task '%s' in the FIFO of workstation '%s'",
1189                SD_task_get_name(task),
1190                SD_workstation_get_name(workstation));
1191         xbt_fifo_push(sg_host_sd(workstation)->task_fifo, task);
1192       }
1193     }
1194     __SD_task_set_state(task, SD_IN_FIFO);
1195     xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1196                SD_task_get_name(task), (int)SD_task_get_state(task));
1197     XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1198   } else {
1199     __SD_task_really_run(task);
1200   }
1201
1202   return can_start;
1203 }
1204
1205 /* This function is called by SD_simulate when a task is done.
1206  * It updates task->state and task->action and executes if necessary the tasks
1207  * which were waiting in FIFOs for the end of `task'
1208  */
1209 void __SD_task_just_done(SD_task_t task)
1210 {
1211   int i, j;
1212   SD_workstation_t workstation;
1213
1214   SD_task_t candidate;
1215   int candidate_nb = 0;
1216   int candidate_capacity = 8;
1217   SD_task_t *candidates;
1218   int can_start = 1;
1219
1220   xbt_assert(__SD_task_is_running(task),
1221               "The task must be running! Task state: %d",
1222               (int)SD_task_get_state(task));
1223   xbt_assert(task->workstation_list != NULL,
1224               "Task '%s': workstation_list is NULL!",
1225               SD_task_get_name(task));
1226
1227
1228   candidates = xbt_new(SD_task_t, 8);
1229
1230   __SD_task_set_state(task, SD_DONE);
1231   surf_action_unref(task->surf_action);
1232   task->surf_action = NULL;
1233
1234   XBT_DEBUG("Looking for candidates");
1235
1236   /* if the task was executed on sequential workstations,
1237      maybe we can execute the next task of the FIFO for each workstation */
1238   for (i = 0; i < task->workstation_nb; i++) {
1239     workstation = task->workstation_list[i];
1240     XBT_DEBUG("Workstation '%s': access_mode = %d",
1241               SD_workstation_get_name(workstation), (int)sg_host_sd(workstation)->access_mode);
1242     if (sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1243       xbt_assert(sg_host_sd(workstation)->task_fifo != NULL,
1244                   "Workstation '%s' has sequential access but no FIFO!",
1245                   SD_workstation_get_name(workstation));
1246       xbt_assert(sg_host_sd(workstation)->current_task =
1247                   task, "Workstation '%s': current task should be '%s'",
1248                   SD_workstation_get_name(workstation),
1249                   SD_task_get_name(task));
1250
1251       /* the task is over so we can release the workstation */
1252       sg_host_sd(workstation)->current_task = NULL;
1253
1254       XBT_DEBUG("Getting candidate in FIFO");
1255       candidate =
1256           xbt_fifo_get_item_content(xbt_fifo_get_first_item
1257                                     (sg_host_sd(workstation)->task_fifo));
1258
1259       if (candidate != NULL) {
1260         XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1261         xbt_assert(__SD_task_is_in_fifo(candidate),
1262                     "Bad state of candidate '%s': %d",
1263                     SD_task_get_name(candidate),
1264                     (int)SD_task_get_state(candidate));
1265       }
1266
1267       XBT_DEBUG("Candidate in fifo: %p", candidate);
1268
1269       /* if there was a task waiting for my place */
1270       if (candidate != NULL) {
1271         /* Unfortunately, we are not sure yet that we can execute the task now,
1272            because the task can be waiting more deeply in some other
1273            workstation's FIFOs ...
1274            So we memorize all candidate tasks, and then we will check for each
1275            candidate whether or not all its workstations are available. */
1276
1277         /* realloc if necessary */
1278         if (candidate_nb == candidate_capacity) {
1279           candidate_capacity *= 2;
1280           candidates =
1281               xbt_realloc(candidates,
1282                           sizeof(SD_task_t) * candidate_capacity);
1283         }
1284
1285         /* register the candidate */
1286         candidates[candidate_nb++] = candidate;
1287         candidate->fifo_checked = 0;
1288       }
1289     }
1290   }
1291
1292   XBT_DEBUG("Candidates found: %d", candidate_nb);
1293
1294   /* now we check every candidate task */
1295   for (i = 0; i < candidate_nb; i++) {
1296     candidate = candidates[i];
1297
1298     if (candidate->fifo_checked) {
1299       continue;                 /* we have already evaluated that task */
1300     }
1301
1302     xbt_assert(__SD_task_is_in_fifo(candidate),
1303                 "Bad state of candidate '%s': %d",
1304                SD_task_get_name(candidate), (int)SD_task_get_state(candidate));
1305
1306     for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1307       workstation = candidate->workstation_list[j];
1308
1309       /* I can start on this workstation if the workstation is shared
1310          or if I am the first task in the FIFO */
1311       can_start = sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SHARED_ACCESS
1312           || candidate ==
1313           xbt_fifo_get_item_content(xbt_fifo_get_first_item
1314                                     (sg_host_sd(workstation)->task_fifo));
1315     }
1316
1317     XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1318            can_start);
1319
1320     /* now we are sure that I can start! */
1321     if (can_start) {
1322       for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1323         workstation = candidate->workstation_list[j];
1324
1325         /* update the FIFO */
1326         if (sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1327           candidate = xbt_fifo_shift(sg_host_sd(workstation)->task_fifo);   /* the return value is stored just for debugging */
1328           XBT_DEBUG("Head of the FIFO: '%s'",
1329                  (candidate !=
1330                   NULL) ? SD_task_get_name(candidate) : "NULL");
1331           xbt_assert(candidate == candidates[i],
1332                       "Error in __SD_task_just_done: bad first task in the FIFO");
1333         }
1334       }                         /* for each workstation */
1335
1336       /* finally execute the task */
1337       XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1338              (int)SD_task_get_state(candidate));
1339       __SD_task_really_run(candidate);
1340
1341       XBT_DEBUG
1342           ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1343            SD_task_get_name(candidate), candidate->state_set,
1344            sd_global->running_task_set, __SD_task_is_running(candidate));
1345       xbt_assert(__SD_task_is_running(candidate),
1346                   "Bad state of task '%s': %d",
1347                   SD_task_get_name(candidate),
1348                  (int)SD_task_get_state(candidate));
1349       XBT_DEBUG("Okay, the task is running.");
1350
1351     }                           /* can start */
1352     candidate->fifo_checked = 1;
1353   }                             /* for each candidate */
1354
1355   xbt_free(candidates);
1356 }
1357
1358 /*
1359  * Remove all dependencies associated with a task. This function is called
1360  * when the task is destroyed.
1361  */
1362 static void __SD_task_remove_dependencies(SD_task_t task)
1363 {
1364   /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1365      because each one is stored twice */
1366   SD_dependency_t dependency;
1367   while (!xbt_dynar_is_empty(task->tasks_before)) {
1368     xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1369     SD_task_dependency_remove(dependency->src, dependency->dst);
1370   }
1371
1372   while (!xbt_dynar_is_empty(task->tasks_after)) {
1373     xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1374     SD_task_dependency_remove(dependency->src, dependency->dst);
1375   }
1376 }
1377
1378 /**
1379  * \brief Returns the start time of a task
1380  *
1381  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1382  *
1383  * \param task: a task
1384  * \return the start time of this task
1385  */
1386 double SD_task_get_start_time(SD_task_t task)
1387 {
1388   if (task->surf_action)
1389     return surf_action_get_start_time(task->surf_action);
1390   else
1391     return task->start_time;
1392 }
1393
1394 /**
1395  * \brief Returns the finish time of a task
1396  *
1397  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1398  * If the state is not completed yet, the returned value is an
1399  * estimation of the task finish time. This value can fluctuate
1400  * until the task is completed.
1401  *
1402  * \param task: a task
1403  * \return the start time of this task
1404  */
1405 double SD_task_get_finish_time(SD_task_t task)
1406 {
1407   if (task->surf_action)        /* should never happen as actions are destroyed right after their completion */
1408     return surf_action_get_finish_time(task->surf_action);
1409   else
1410     return task->finish_time;
1411 }
1412 /** @brief Blah
1413  *
1414  */
1415 void SD_task_distribute_comp_amdahl(SD_task_t task, int ws_count)
1416 {
1417   int i;
1418   xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1419               "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1420               "Cannot use this function.",
1421               SD_task_get_name(task));
1422   task->flops_amount = xbt_new0(double, ws_count);
1423   task->bytes_amount = xbt_new0(double, ws_count * ws_count);
1424   xbt_free(task->workstation_list);
1425   task->workstation_nb = ws_count;
1426   task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1427
1428   for(i=0;i<ws_count;i++){
1429     task->flops_amount[i] =
1430       (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1431   }
1432 }
1433
1434
1435 /** @brief Auto-schedules a task.
1436  *
1437  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1438  * allows to specify the task costs at creation, and decouple them from the
1439  * scheduling process where you just specify which resource should deliver the
1440  * mandatory power.
1441  *
1442  * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e()
1443  * or SD_task_create_comp_seq(). Check their definitions for the exact semantic
1444  * of each of them.
1445  *
1446  * @todo
1447  * We should create tasks kind for the following categories:
1448  *  - Point to point communication (done)
1449  *  - Sequential computation       (done)
1450  *  - group communication (redistribution, several kinds)
1451  *  - parallel tasks with no internal communication (one kind per speedup
1452  *    model such as Amdahl)
1453  *  - idem+ internal communication. Task type not enough since we cannot store
1454  *    comm cost alongside to comp one)
1455  */
1456 void SD_task_schedulev(SD_task_t task, int count,
1457                        const SD_workstation_t * list)
1458 {
1459   int i, j;
1460   SD_dependency_t dep;
1461   unsigned int cpt;
1462   xbt_assert(task->kind != 0,
1463               "Task %s is not typed. Cannot automatically schedule it.",
1464               SD_task_get_name(task));
1465   switch (task->kind) {
1466   case SD_TASK_COMP_PAR_AMDAHL:
1467     SD_task_distribute_comp_amdahl(task, count);
1468   case SD_TASK_COMM_E2E:
1469   case SD_TASK_COMP_SEQ:
1470     xbt_assert(task->workstation_nb == count,
1471                "Got %d locations, but were expecting %d locations",
1472                count,task->workstation_nb);
1473     for (i = 0; i < count; i++)
1474       task->workstation_list[i] = list[i];
1475     if (SD_task_get_kind(task)== SD_TASK_COMP_SEQ && !task->flops_amount){
1476       /*This task has failed and is rescheduled. Reset the flops_amount*/
1477       task->flops_amount = xbt_new0(double, 1);
1478       task->flops_amount[0] = task->remains;
1479     }
1480     SD_task_do_schedule(task);
1481     break;
1482   default:
1483     xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1484             SD_task_get_name(task));
1485   }
1486   if (task->kind == SD_TASK_COMM_E2E) {
1487     XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1488           SD_task_get_name(task),
1489           SD_workstation_get_name(task->workstation_list[0]),
1490           SD_workstation_get_name(task->workstation_list[1]),
1491           task->bytes_amount[2]);
1492
1493   }
1494
1495   /* Iterate over all children and parents being COMM_E2E to say where I am
1496    * located (and start them if runnable) */
1497   if (task->kind == SD_TASK_COMP_SEQ) {
1498     XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1499           SD_task_get_name(task),
1500           SD_workstation_get_name(task->workstation_list[0]),
1501           task->flops_amount[0]);
1502
1503     xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1504       SD_task_t before = dep->src;
1505       if (before->kind == SD_TASK_COMM_E2E) {
1506         before->workstation_list[1] = task->workstation_list[0];
1507
1508         if (before->workstation_list[0] &&
1509             (__SD_task_is_schedulable(before)
1510              || __SD_task_is_not_scheduled(before))) {
1511           SD_task_do_schedule(before);
1512           XBT_VERB
1513               ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1514                SD_task_get_name(before),
1515                SD_workstation_get_name(before->workstation_list[0]),
1516                SD_workstation_get_name(before->workstation_list[1]),
1517                before->bytes_amount[2]);
1518         }
1519       }
1520     }
1521     xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1522       SD_task_t after = dep->dst;
1523       if (after->kind == SD_TASK_COMM_E2E) {
1524         after->workstation_list[0] = task->workstation_list[0];
1525         if (after->workstation_list[1]
1526             && (__SD_task_is_not_scheduled(after)
1527                 || __SD_task_is_schedulable(after))) {
1528           SD_task_do_schedule(after);
1529           XBT_VERB
1530               ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1531                SD_task_get_name(after),
1532                SD_workstation_get_name(after->workstation_list[0]),
1533                SD_workstation_get_name(after->workstation_list[1]),
1534                after->bytes_amount[2]);
1535
1536         }
1537       }
1538     }
1539   }
1540   /* Iterate over all children and parents being MXN_1D_BLOCK to say where I am
1541    * located (and start them if runnable) */
1542   if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1543     XBT_VERB("Schedule computation task %s on %d workstations. %.f flops"
1544              " will be distributed following Amdahl's Law",
1545           SD_task_get_name(task), task->workstation_nb,
1546           task->flops_amount[0]);
1547     xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1548       SD_task_t before = dep->src;
1549       if (before->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1550         if (!before->workstation_list){
1551           XBT_VERB("Sender side of Task %s is not scheduled yet",
1552              SD_task_get_name(before));
1553           before->workstation_list = xbt_new0(SD_workstation_t, count);
1554           before->workstation_nb = count;
1555           XBT_VERB("Fill the workstation list with list of Task '%s'",
1556             SD_task_get_name(task));
1557           for (i=0;i<count;i++)
1558             before->workstation_list[i] = task->workstation_list[i];
1559         } else {
1560           XBT_VERB("Build communication matrix for task '%s'",
1561              SD_task_get_name(before));
1562           int src_nb, dst_nb;
1563           double src_start, src_end, dst_start, dst_end;
1564           src_nb = before->workstation_nb;
1565           dst_nb = count;
1566           before->workstation_list = (SD_workstation_t*) xbt_realloc(
1567              before->workstation_list,
1568              (before->workstation_nb+count)*sizeof(s_SD_workstation_t));
1569           for(i=0; i<count; i++)
1570             before->workstation_list[before->workstation_nb+i] =
1571                task->workstation_list[i];
1572
1573           before->workstation_nb += count;
1574           xbt_free(before->flops_amount);
1575           xbt_free(before->bytes_amount);
1576           before->flops_amount = xbt_new0(double,
1577                                                 before->workstation_nb);
1578           before->bytes_amount = xbt_new0(double,
1579                                                   before->workstation_nb*
1580                                                   before->workstation_nb);
1581
1582           for(i=0;i<src_nb;i++){
1583             src_start = i*before->amount/src_nb;
1584             src_end = src_start + before->amount/src_nb;
1585             for(j=0; j<dst_nb; j++){
1586               dst_start = j*before->amount/dst_nb;
1587               dst_end = dst_start + before->amount/dst_nb;
1588               XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)",
1589                   SD_workstation_get_name(before->workstation_list[i]),
1590                   SD_workstation_get_name(before->workstation_list[src_nb+j]),
1591                   src_start, src_end, dst_start, dst_end);
1592               if ((src_end <= dst_start) || (dst_end <= src_start)) {
1593                 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1594               } else {
1595                 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1596                   MIN(src_end, dst_end) - MAX(src_start, dst_start);
1597               }
1598               XBT_VERB("==> %.2f",
1599                  before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1600             }
1601           }
1602
1603           if (__SD_task_is_schedulable(before) ||
1604               __SD_task_is_not_scheduled(before)) {
1605             SD_task_do_schedule(before);
1606             XBT_VERB
1607               ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1608                   SD_task_get_name(before),before->amount, src_nb, dst_nb);
1609             }
1610         }
1611       }
1612     }
1613     xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1614       SD_task_t after = dep->dst;
1615       if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1616         if (!after->workstation_list){
1617           XBT_VERB("Receiver side of Task '%s' is not scheduled yet",
1618               SD_task_get_name(after));
1619           after->workstation_list = xbt_new0(SD_workstation_t, count);
1620           after->workstation_nb = count;
1621           XBT_VERB("Fill the workstation list with list of Task '%s'",
1622             SD_task_get_name(task));
1623           for (i=0;i<count;i++)
1624             after->workstation_list[i] = task->workstation_list[i];
1625         } else {
1626           int src_nb, dst_nb;
1627           double src_start, src_end, dst_start, dst_end;
1628           src_nb = count;
1629           dst_nb = after->workstation_nb;
1630           after->workstation_list = (SD_workstation_t*) xbt_realloc(
1631             after->workstation_list,
1632             (after->workstation_nb+count)*sizeof(s_SD_workstation_t));
1633           for(i=after->workstation_nb - 1; i>=0; i--)
1634             after->workstation_list[count+i] = after->workstation_list[i];
1635           for(i=0; i<count; i++)
1636             after->workstation_list[i] = task->workstation_list[i];
1637
1638           after->workstation_nb += count;
1639
1640           xbt_free(after->flops_amount);
1641           xbt_free(after->bytes_amount);
1642
1643           after->flops_amount = xbt_new0(double, after->workstation_nb);
1644           after->bytes_amount = xbt_new0(double,
1645                                                  after->workstation_nb*
1646                                                  after->workstation_nb);
1647
1648           for(i=0;i<src_nb;i++){
1649             src_start = i*after->amount/src_nb;
1650             src_end = src_start + after->amount/src_nb;
1651             for(j=0; j<dst_nb; j++){
1652               dst_start = j*after->amount/dst_nb;
1653               dst_end = dst_start + after->amount/dst_nb;
1654               XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)",
1655                   i, j, src_start, src_end, dst_start, dst_end);
1656               if ((src_end <= dst_start) || (dst_end <= src_start)) {
1657                 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1658               } else {
1659                 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1660                    MIN(src_end, dst_end)- MAX(src_start, dst_start);
1661               }
1662               XBT_VERB("==> %.2f",
1663                  after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1664             }
1665           }
1666
1667           if (__SD_task_is_schedulable(after) ||
1668               __SD_task_is_not_scheduled(after)) {
1669             SD_task_do_schedule(after);
1670             XBT_VERB
1671             ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1672               SD_task_get_name(after),after->amount, src_nb, dst_nb);
1673           }
1674          }
1675       }
1676     }
1677   }
1678 }
1679
1680 /** @brief autoschedule a task on a list of workstations
1681  *
1682  * This function is very similar to SD_task_schedulev(),
1683  * but takes the list of workstations to schedule onto as separate parameters.
1684  * It builds a proper vector of workstations and then call SD_task_schedulev()
1685  */
1686 void SD_task_schedulel(SD_task_t task, int count, ...)
1687 {
1688   va_list ap;
1689   SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1690   int i;
1691   va_start(ap, count);
1692   for (i = 0; i < count; i++) {
1693     list[i] = va_arg(ap, SD_workstation_t);
1694   }
1695   va_end(ap);
1696   SD_task_schedulev(task, count, list);
1697   free(list);
1698 }