src/simdag/sd_task.c

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