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