src/simdag/sd_task.c

   1 /* Copyright (c) 2006-2014. 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 "private.h"
   8 #include "simgrid/simdag.h"
   9 #include "xbt/sysdep.h"
  10 #include "xbt/dynar.h"
  11 #include "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   void **surf_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   /* we have to create a Surf workstation array instead of the SimDag
1121    * workstation array */
1122   surf_hosts = xbt_new(void *, host_nb);
1123
1124   for (i = 0; i < host_nb; i++)
1125     surf_hosts[i] =  surf_host_resource_priv(task->workstation_list[i]);
1126
1127   double *flops_amount = xbt_new0(double, host_nb);
1128   double *bytes_amount = xbt_new0(double, host_nb * host_nb);
1129
1130
1131   if(task->flops_amount)
1132     memcpy(flops_amount, task->flops_amount, sizeof(double) *
1133            host_nb);
1134   if(task->bytes_amount)
1135     memcpy(bytes_amount, task->bytes_amount,
1136            sizeof(double) * host_nb * host_nb);
1137
1138   task->surf_action = surf_host_model_execute_parallel_task((surf_host_model_t)surf_host_model,
1139                                                                      host_nb,
1140                                                                      surf_hosts,
1141                                                                      flops_amount,
1142                                                                      bytes_amount,
1143                                                                      task->rate);
1144
1145   surf_action_set_data(task->surf_action, task);
1146
1147   XBT_DEBUG("surf_action = %p", task->surf_action);
1148
1149   if (task->category)
1150     TRACE_surf_action(task->surf_action, task->category);
1151
1152   __SD_task_destroy_scheduling_data(task);      /* now the scheduling data are not useful anymore */
1153   __SD_task_set_state(task, SD_RUNNING);
1154   xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
1155              SD_task_get_name(task), (int)SD_task_get_state(task));
1156
1157 }
1158
1159 /* Tries to run a task. This function is called by SD_simulate() when a
1160  * scheduled task becomes SD_RUNNABLE (i.e., when its dependencies are
1161  * satisfied).
1162  * If one of the workstations where the task is scheduled on is busy (in
1163  * sequential mode), the task doesn't start.
1164  * Returns whether the task has started.
1165  */
1166 int __SD_task_try_to_run(SD_task_t task)
1167 {
1168
1169   int can_start = 1;
1170   int i;
1171   SD_workstation_t workstation;
1172
1173   xbt_assert(__SD_task_is_runnable(task),
1174               "Task '%s' is not runnable! Task state: %d",
1175              SD_task_get_name(task), (int)SD_task_get_state(task));
1176
1177
1178   for (i = 0; i < task->workstation_nb; i++) {
1179     can_start = can_start &&
1180         !__SD_workstation_is_busy(task->workstation_list[i]);
1181   }
1182
1183   XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1184
1185   if (!can_start) {             /* if the task cannot start and is not in the FIFOs yet */
1186     for (i = 0; i < task->workstation_nb; i++) {
1187       workstation = task->workstation_list[i];
1188       if (sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1189         XBT_DEBUG("Pushing task '%s' in the FIFO of workstation '%s'",
1190                SD_task_get_name(task),
1191                SD_workstation_get_name(workstation));
1192         xbt_fifo_push(sg_host_sd(workstation)->task_fifo, task);
1193       }
1194     }
1195     __SD_task_set_state(task, SD_IN_FIFO);
1196     xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1197                SD_task_get_name(task), (int)SD_task_get_state(task));
1198     XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1199   } else {
1200     __SD_task_really_run(task);
1201   }
1202
1203   return can_start;
1204 }
1205
1206 /* This function is called by SD_simulate when a task is done.
1207  * It updates task->state and task->action and executes if necessary the tasks
1208  * which were waiting in FIFOs for the end of `task'
1209  */
1210 void __SD_task_just_done(SD_task_t task)
1211 {
1212   int i, j;
1213   SD_workstation_t workstation;
1214
1215   SD_task_t candidate;
1216   int candidate_nb = 0;
1217   int candidate_capacity = 8;
1218   SD_task_t *candidates;
1219   int can_start = 1;
1220
1221   xbt_assert(__SD_task_is_running(task),
1222               "The task must be running! Task state: %d",
1223               (int)SD_task_get_state(task));
1224   xbt_assert(task->workstation_list != NULL,
1225               "Task '%s': workstation_list is NULL!",
1226               SD_task_get_name(task));
1227
1228
1229   candidates = xbt_new(SD_task_t, 8);
1230
1231   __SD_task_set_state(task, SD_DONE);
1232   surf_action_unref(task->surf_action);
1233   task->surf_action = NULL;
1234
1235   XBT_DEBUG("Looking for candidates");
1236
1237   /* if the task was executed on sequential workstations,
1238      maybe we can execute the next task of the FIFO for each workstation */
1239   for (i = 0; i < task->workstation_nb; i++) {
1240     workstation = task->workstation_list[i];
1241     XBT_DEBUG("Workstation '%s': access_mode = %d",
1242               SD_workstation_get_name(workstation), (int)sg_host_sd(workstation)->access_mode);
1243     if (sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1244       xbt_assert(sg_host_sd(workstation)->task_fifo != NULL,
1245                   "Workstation '%s' has sequential access but no FIFO!",
1246                   SD_workstation_get_name(workstation));
1247       xbt_assert(sg_host_sd(workstation)->current_task =
1248                   task, "Workstation '%s': current task should be '%s'",
1249                   SD_workstation_get_name(workstation),
1250                   SD_task_get_name(task));
1251
1252       /* the task is over so we can release the workstation */
1253       sg_host_sd(workstation)->current_task = NULL;
1254
1255       XBT_DEBUG("Getting candidate in FIFO");
1256       candidate =
1257           xbt_fifo_get_item_content(xbt_fifo_get_first_item
1258                                     (sg_host_sd(workstation)->task_fifo));
1259
1260       if (candidate != NULL) {
1261         XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1262         xbt_assert(__SD_task_is_in_fifo(candidate),
1263                     "Bad state of candidate '%s': %d",
1264                     SD_task_get_name(candidate),
1265                     (int)SD_task_get_state(candidate));
1266       }
1267
1268       XBT_DEBUG("Candidate in fifo: %p", candidate);
1269
1270       /* if there was a task waiting for my place */
1271       if (candidate != NULL) {
1272         /* Unfortunately, we are not sure yet that we can execute the task now,
1273            because the task can be waiting more deeply in some other
1274            workstation's FIFOs ...
1275            So we memorize all candidate tasks, and then we will check for each
1276            candidate whether or not all its workstations are available. */
1277
1278         /* realloc if necessary */
1279         if (candidate_nb == candidate_capacity) {
1280           candidate_capacity *= 2;
1281           candidates =
1282               xbt_realloc(candidates,
1283                           sizeof(SD_task_t) * candidate_capacity);
1284         }
1285
1286         /* register the candidate */
1287         candidates[candidate_nb++] = candidate;
1288         candidate->fifo_checked = 0;
1289       }
1290     }
1291   }
1292
1293   XBT_DEBUG("Candidates found: %d", candidate_nb);
1294
1295   /* now we check every candidate task */
1296   for (i = 0; i < candidate_nb; i++) {
1297     candidate = candidates[i];
1298
1299     if (candidate->fifo_checked) {
1300       continue;                 /* we have already evaluated that task */
1301     }
1302
1303     xbt_assert(__SD_task_is_in_fifo(candidate),
1304                 "Bad state of candidate '%s': %d",
1305                SD_task_get_name(candidate), (int)SD_task_get_state(candidate));
1306
1307     for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1308       workstation = candidate->workstation_list[j];
1309
1310       /* I can start on this workstation if the workstation is shared
1311          or if I am the first task in the FIFO */
1312       can_start = sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SHARED_ACCESS
1313           || candidate ==
1314           xbt_fifo_get_item_content(xbt_fifo_get_first_item
1315                                     (sg_host_sd(workstation)->task_fifo));
1316     }
1317
1318     XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1319            can_start);
1320
1321     /* now we are sure that I can start! */
1322     if (can_start) {
1323       for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1324         workstation = candidate->workstation_list[j];
1325
1326         /* update the FIFO */
1327         if (sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1328           candidate = xbt_fifo_shift(sg_host_sd(workstation)->task_fifo);   /* the return value is stored just for debugging */
1329           XBT_DEBUG("Head of the FIFO: '%s'",
1330                  (candidate !=
1331                   NULL) ? SD_task_get_name(candidate) : "NULL");
1332           xbt_assert(candidate == candidates[i],
1333                       "Error in __SD_task_just_done: bad first task in the FIFO");
1334         }
1335       }                         /* for each workstation */
1336
1337       /* finally execute the task */
1338       XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1339              (int)SD_task_get_state(candidate));
1340       __SD_task_really_run(candidate);
1341
1342       XBT_DEBUG
1343           ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1344            SD_task_get_name(candidate), candidate->state_set,
1345            sd_global->running_task_set, __SD_task_is_running(candidate));
1346       xbt_assert(__SD_task_is_running(candidate),
1347                   "Bad state of task '%s': %d",
1348                   SD_task_get_name(candidate),
1349                  (int)SD_task_get_state(candidate));
1350       XBT_DEBUG("Okay, the task is running.");
1351
1352     }                           /* can start */
1353     candidate->fifo_checked = 1;
1354   }                             /* for each candidate */
1355
1356   xbt_free(candidates);
1357 }
1358
1359 /*
1360  * Remove all dependencies associated with a task. This function is called
1361  * when the task is destroyed.
1362  */
1363 static void __SD_task_remove_dependencies(SD_task_t task)
1364 {
1365   /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1366      because each one is stored twice */
1367   SD_dependency_t dependency;
1368   while (!xbt_dynar_is_empty(task->tasks_before)) {
1369     xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1370     SD_task_dependency_remove(dependency->src, dependency->dst);
1371   }
1372
1373   while (!xbt_dynar_is_empty(task->tasks_after)) {
1374     xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1375     SD_task_dependency_remove(dependency->src, dependency->dst);
1376   }
1377 }
1378
1379 /**
1380  * \brief Returns the start time of a task
1381  *
1382  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1383  *
1384  * \param task: a task
1385  * \return the start time of this task
1386  */
1387 double SD_task_get_start_time(SD_task_t task)
1388 {
1389   if (task->surf_action)
1390     return surf_action_get_start_time(task->surf_action);
1391   else
1392     return task->start_time;
1393 }
1394
1395 /**
1396  * \brief Returns the finish time of a task
1397  *
1398  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1399  * If the state is not completed yet, the returned value is an
1400  * estimation of the task finish time. This value can fluctuate
1401  * until the task is completed.
1402  *
1403  * \param task: a task
1404  * \return the start time of this task
1405  */
1406 double SD_task_get_finish_time(SD_task_t task)
1407 {
1408   if (task->surf_action)        /* should never happen as actions are destroyed right after their completion */
1409     return surf_action_get_finish_time(task->surf_action);
1410   else
1411     return task->finish_time;
1412 }
1413 /** @brief Blah
1414  *
1415  */
1416 void SD_task_distribute_comp_amdahl(SD_task_t task, int ws_count)
1417 {
1418   int i;
1419   xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1420               "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1421               "Cannot use this function.",
1422               SD_task_get_name(task));
1423   task->flops_amount = xbt_new0(double, ws_count);
1424   task->bytes_amount = xbt_new0(double, ws_count * ws_count);
1425   xbt_free(task->workstation_list);
1426   task->workstation_nb = ws_count;
1427   task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1428
1429   for(i=0;i<ws_count;i++){
1430     task->flops_amount[i] =
1431       (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1432   }
1433 }
1434
1435
1436 /** @brief Auto-schedules a task.
1437  *
1438  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1439  * allows to specify the task costs at creation, and decouple them from the
1440  * scheduling process where you just specify which resource should deliver the
1441  * mandatory power.
1442  *
1443  * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e()
1444  * or SD_task_create_comp_seq(). Check their definitions for the exact semantic
1445  * of each of them.
1446  *
1447  * @todo
1448  * We should create tasks kind for the following categories:
1449  *  - Point to point communication (done)
1450  *  - Sequential computation       (done)
1451  *  - group communication (redistribution, several kinds)
1452  *  - parallel tasks with no internal communication (one kind per speedup
1453  *    model such as Amdahl)
1454  *  - idem+ internal communication. Task type not enough since we cannot store
1455  *    comm cost alongside to comp one)
1456  */
1457 void SD_task_schedulev(SD_task_t task, int count,
1458                        const SD_workstation_t * list)
1459 {
1460   int i, j;
1461   SD_dependency_t dep;
1462   unsigned int cpt;
1463   xbt_assert(task->kind != 0,
1464               "Task %s is not typed. Cannot automatically schedule it.",
1465               SD_task_get_name(task));
1466   switch (task->kind) {
1467   case SD_TASK_COMP_PAR_AMDAHL:
1468     SD_task_distribute_comp_amdahl(task, count);
1469   case SD_TASK_COMM_E2E:
1470   case SD_TASK_COMP_SEQ:
1471     xbt_assert(task->workstation_nb == count,
1472                "Got %d locations, but were expecting %d locations",
1473                count,task->workstation_nb);
1474     for (i = 0; i < count; i++)
1475       task->workstation_list[i] = list[i];
1476     if (SD_task_get_kind(task)== SD_TASK_COMP_SEQ && !task->flops_amount){
1477       /*This task has failed and is rescheduled. Reset the flops_amount*/
1478       task->flops_amount = xbt_new0(double, 1);
1479       task->flops_amount[0] = task->remains;
1480     }
1481     SD_task_do_schedule(task);
1482     break;
1483   default:
1484     xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1485             SD_task_get_name(task));
1486   }
1487   if (task->kind == SD_TASK_COMM_E2E) {
1488     XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1489           SD_task_get_name(task),
1490           SD_workstation_get_name(task->workstation_list[0]),
1491           SD_workstation_get_name(task->workstation_list[1]),
1492           task->bytes_amount[2]);
1493
1494   }
1495
1496   /* Iterate over all children and parents being COMM_E2E to say where I am
1497    * located (and start them if runnable) */
1498   if (task->kind == SD_TASK_COMP_SEQ) {
1499     XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1500           SD_task_get_name(task),
1501           SD_workstation_get_name(task->workstation_list[0]),
1502           task->flops_amount[0]);
1503
1504     xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1505       SD_task_t before = dep->src;
1506       if (before->kind == SD_TASK_COMM_E2E) {
1507         before->workstation_list[1] = task->workstation_list[0];
1508
1509         if (before->workstation_list[0] &&
1510             (__SD_task_is_schedulable(before)
1511              || __SD_task_is_not_scheduled(before))) {
1512           SD_task_do_schedule(before);
1513           XBT_VERB
1514               ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1515                SD_task_get_name(before),
1516                SD_workstation_get_name(before->workstation_list[0]),
1517                SD_workstation_get_name(before->workstation_list[1]),
1518                before->bytes_amount[2]);
1519         }
1520       }
1521     }
1522     xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1523       SD_task_t after = dep->dst;
1524       if (after->kind == SD_TASK_COMM_E2E) {
1525         after->workstation_list[0] = task->workstation_list[0];
1526         if (after->workstation_list[1]
1527             && (__SD_task_is_not_scheduled(after)
1528                 || __SD_task_is_schedulable(after))) {
1529           SD_task_do_schedule(after);
1530           XBT_VERB
1531               ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1532                SD_task_get_name(after),
1533                SD_workstation_get_name(after->workstation_list[0]),
1534                SD_workstation_get_name(after->workstation_list[1]),
1535                after->bytes_amount[2]);
1536
1537         }
1538       }
1539     }
1540   }
1541   /* Iterate over all children and parents being MXN_1D_BLOCK to say where I am
1542    * located (and start them if runnable) */
1543   if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1544     XBT_VERB("Schedule computation task %s on %d workstations. %.f flops"
1545              " will be distributed following Amdahl's Law",
1546           SD_task_get_name(task), task->workstation_nb,
1547           task->flops_amount[0]);
1548     xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1549       SD_task_t before = dep->src;
1550       if (before->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1551         if (!before->workstation_list){
1552           XBT_VERB("Sender side of Task %s is not scheduled yet",
1553              SD_task_get_name(before));
1554           before->workstation_list = xbt_new0(SD_workstation_t, count);
1555           before->workstation_nb = count;
1556           XBT_VERB("Fill the workstation list with list of Task '%s'",
1557             SD_task_get_name(task));
1558           for (i=0;i<count;i++)
1559             before->workstation_list[i] = task->workstation_list[i];
1560         } else {
1561           XBT_VERB("Build communication matrix for task '%s'",
1562              SD_task_get_name(before));
1563           int src_nb, dst_nb;
1564           double src_start, src_end, dst_start, dst_end;
1565           src_nb = before->workstation_nb;
1566           dst_nb = count;
1567           before->workstation_list = (SD_workstation_t*) xbt_realloc(
1568              before->workstation_list,
1569              (before->workstation_nb+count)*sizeof(s_SD_workstation_t));
1570           for(i=0; i<count; i++)
1571             before->workstation_list[before->workstation_nb+i] =
1572                task->workstation_list[i];
1573
1574           before->workstation_nb += count;
1575           xbt_free(before->flops_amount);
1576           xbt_free(before->bytes_amount);
1577           before->flops_amount = xbt_new0(double,
1578                                                 before->workstation_nb);
1579           before->bytes_amount = xbt_new0(double,
1580                                                   before->workstation_nb*
1581                                                   before->workstation_nb);
1582
1583           for(i=0;i<src_nb;i++){
1584             src_start = i*before->amount/src_nb;
1585             src_end = src_start + before->amount/src_nb;
1586             for(j=0; j<dst_nb; j++){
1587               dst_start = j*before->amount/dst_nb;
1588               dst_end = dst_start + before->amount/dst_nb;
1589               XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)",
1590                   SD_workstation_get_name(before->workstation_list[i]),
1591                   SD_workstation_get_name(before->workstation_list[src_nb+j]),
1592                   src_start, src_end, dst_start, dst_end);
1593               if ((src_end <= dst_start) || (dst_end <= src_start)) {
1594                 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1595               } else {
1596                 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1597                   MIN(src_end, dst_end) - MAX(src_start, dst_start);
1598               }
1599               XBT_VERB("==> %.2f",
1600                  before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1601             }
1602           }
1603
1604           if (__SD_task_is_schedulable(before) ||
1605               __SD_task_is_not_scheduled(before)) {
1606             SD_task_do_schedule(before);
1607             XBT_VERB
1608               ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1609                   SD_task_get_name(before),before->amount, src_nb, dst_nb);
1610             }
1611         }
1612       }
1613     }
1614     xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1615       SD_task_t after = dep->dst;
1616       if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1617         if (!after->workstation_list){
1618           XBT_VERB("Receiver side of Task '%s' is not scheduled yet",
1619               SD_task_get_name(after));
1620           after->workstation_list = xbt_new0(SD_workstation_t, count);
1621           after->workstation_nb = count;
1622           XBT_VERB("Fill the workstation list with list of Task '%s'",
1623             SD_task_get_name(task));
1624           for (i=0;i<count;i++)
1625             after->workstation_list[i] = task->workstation_list[i];
1626         } else {
1627           int src_nb, dst_nb;
1628           double src_start, src_end, dst_start, dst_end;
1629           src_nb = count;
1630           dst_nb = after->workstation_nb;
1631           after->workstation_list = (SD_workstation_t*) xbt_realloc(
1632             after->workstation_list,
1633             (after->workstation_nb+count)*sizeof(s_SD_workstation_t));
1634           for(i=after->workstation_nb - 1; i>=0; i--)
1635             after->workstation_list[count+i] = after->workstation_list[i];
1636           for(i=0; i<count; i++)
1637             after->workstation_list[i] = task->workstation_list[i];
1638
1639           after->workstation_nb += count;
1640
1641           xbt_free(after->flops_amount);
1642           xbt_free(after->bytes_amount);
1643
1644           after->flops_amount = xbt_new0(double, after->workstation_nb);
1645           after->bytes_amount = xbt_new0(double,
1646                                                  after->workstation_nb*
1647                                                  after->workstation_nb);
1648
1649           for(i=0;i<src_nb;i++){
1650             src_start = i*after->amount/src_nb;
1651             src_end = src_start + after->amount/src_nb;
1652             for(j=0; j<dst_nb; j++){
1653               dst_start = j*after->amount/dst_nb;
1654               dst_end = dst_start + after->amount/dst_nb;
1655               XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)",
1656                   i, j, src_start, src_end, dst_start, dst_end);
1657               if ((src_end <= dst_start) || (dst_end <= src_start)) {
1658                 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1659               } else {
1660                 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1661                    MIN(src_end, dst_end)- MAX(src_start, dst_start);
1662               }
1663               XBT_VERB("==> %.2f",
1664                  after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1665             }
1666           }
1667
1668           if (__SD_task_is_schedulable(after) ||
1669               __SD_task_is_not_scheduled(after)) {
1670             SD_task_do_schedule(after);
1671             XBT_VERB
1672             ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1673               SD_task_get_name(after),after->amount, src_nb, dst_nb);
1674           }
1675          }
1676       }
1677     }
1678   }
1679 }
1680
1681 /** @brief autoschedule a task on a list of workstations
1682  *
1683  * This function is very similar to SD_task_schedulev(),
1684  * but takes the list of workstations to schedule onto as separate parameters.
1685  * It builds a proper vector of workstations and then call SD_task_schedulev()
1686  */
1687 void SD_task_schedulel(SD_task_t task, int count, ...)
1688 {
1689   va_list ap;
1690   SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1691   int i;
1692   va_start(ap, count);
1693   for (i = 0; i < count; i++) {
1694     list[i] = va_arg(ap, SD_workstation_t);
1695   }
1696   va_end(ap);
1697   SD_task_schedulev(task, count, list);
1698   free(list);
1699 }