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