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   int length;
 625   int found = 0;
 626   int 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 %d: 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   int length;
 750   int found = 0;
 751   int 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   int length;
 821   int found = 0;
 822   int 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     task->workstation_list=NULL;
1045     task->workstation_nb = 0;
1046   }
1047
1048   if (__SD_task_is_running(task))       /* the task should become SD_FAILED */
1049     surf_workstation_model->action_cancel(task->surf_action);
1050   else {
1051     if (task->unsatisfied_dependencies == 0)
1052       __SD_task_set_state(task, SD_SCHEDULABLE);
1053     else
1054       __SD_task_set_state(task, SD_NOT_SCHEDULED);
1055   }
1056   task->remains = task->amount;
1057   task->start_time = -1.0;
1058 }
1059
1060 /* Destroys the data memorized by SD_task_schedule.
1061  * Task state must be SD_SCHEDULED or SD_RUNNABLE.
1062  */
1063 static void __SD_task_destroy_scheduling_data(SD_task_t task)
1064 {
1065   if (!__SD_task_is_scheduled_or_runnable(task)
1066       && !__SD_task_is_in_fifo(task))
1067     THROWF(arg_error, 0,
1068            "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
1069            SD_task_get_name(task));
1070
1071   xbt_free(task->computation_amount);
1072   xbt_free(task->communication_amount);
1073   task->computation_amount = task->communication_amount = NULL;
1074 }
1075
1076 /* Runs a task. This function is directly called by __SD_task_try_to_run if
1077  * the task doesn't have to wait in FIFOs. Otherwise, it is called by
1078  * __SD_task_just_done when the task gets out of its FIFOs.
1079  */
1080 void __SD_task_really_run(SD_task_t task)
1081 {
1082
1083   int i;
1084   void **surf_workstations;
1085
1086   xbt_assert(__SD_task_is_runnable_or_in_fifo(task),
1087               "Task '%s' is not runnable or in a fifo! Task state: %d",
1088              SD_task_get_name(task), (int)SD_task_get_state(task));
1089   xbt_assert(task->workstation_list != NULL,
1090               "Task '%s': workstation_list is NULL!",
1091               SD_task_get_name(task));
1092
1093   XBT_DEBUG("Really running task '%s'", SD_task_get_name(task));
1094   int workstation_nb = task->workstation_nb;
1095
1096   /* set this task as current task for the workstations in sequential mode */
1097   for (i = 0; i < workstation_nb; i++) {
1098     if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
1099         SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1100       SD_workstation_priv(task->workstation_list[i])->current_task = task;
1101       xbt_assert(__SD_workstation_is_busy(task->workstation_list[i]),
1102                   "The workstation should be busy now");
1103     }
1104   }
1105
1106   XBT_DEBUG("Task '%s' set as current task for its workstations",
1107          SD_task_get_name(task));
1108
1109   /* start the task */
1110
1111   /* we have to create a Surf workstation array instead of the SimDag
1112    * workstation array */
1113   surf_workstations = xbt_new(void *, workstation_nb);
1114
1115   for (i = 0; i < workstation_nb; i++)
1116     surf_workstations[i] = task->workstation_list[i];
1117
1118   double *computation_amount = xbt_new0(double, workstation_nb);
1119   double *communication_amount = xbt_new0(double, workstation_nb * workstation_nb);
1120
1121
1122   if(task->computation_amount)
1123     memcpy(computation_amount, task->computation_amount, sizeof(double) *
1124            workstation_nb);
1125   if(task->communication_amount)
1126     memcpy(communication_amount, task->communication_amount,
1127            sizeof(double) * workstation_nb * workstation_nb);
1128
1129   task->surf_action =
1130         surf_workstation_model->extension.
1131         workstation.execute_parallel_task(workstation_nb,
1132                                           surf_workstations,
1133                                           computation_amount,
1134                                           communication_amount,
1135                                           task->rate);
1136
1137   surf_workstation_model->action_data_set(task->surf_action, task);
1138
1139   XBT_DEBUG("surf_action = %p", task->surf_action);
1140
1141 #ifdef HAVE_TRACING
1142   if (task->category)
1143     TRACE_surf_action(task->surf_action, task->category);
1144 #endif
1145
1146   __SD_task_destroy_scheduling_data(task);      /* now the scheduling data are not useful anymore */
1147   __SD_task_set_state(task, SD_RUNNING);
1148   xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
1149              SD_task_get_name(task), (int)SD_task_get_state(task));
1150
1151 }
1152
1153 /* Tries to run a task. This function is called by SD_simulate() when a
1154  * scheduled task becomes SD_RUNNABLE (i.e., when its dependencies are
1155  * satisfied).
1156  * If one of the workstations where the task is scheduled on is busy (in
1157  * sequential mode), the task doesn't start.
1158  * Returns whether the task has started.
1159  */
1160 int __SD_task_try_to_run(SD_task_t task)
1161 {
1162
1163   int can_start = 1;
1164   int i;
1165   SD_workstation_t workstation;
1166
1167   xbt_assert(__SD_task_is_runnable(task),
1168               "Task '%s' is not runnable! Task state: %d",
1169              SD_task_get_name(task), (int)SD_task_get_state(task));
1170
1171
1172   for (i = 0; i < task->workstation_nb; i++) {
1173     can_start = can_start &&
1174         !__SD_workstation_is_busy(task->workstation_list[i]);
1175   }
1176
1177   XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1178
1179   if (!can_start) {             /* if the task cannot start and is not in the FIFOs yet */
1180     for (i = 0; i < task->workstation_nb; i++) {
1181       workstation = task->workstation_list[i];
1182       if (SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1183         XBT_DEBUG("Pushing task '%s' in the FIFO of workstation '%s'",
1184                SD_task_get_name(task),
1185                SD_workstation_get_name(workstation));
1186         xbt_fifo_push(SD_workstation_priv(workstation)->task_fifo, task);
1187       }
1188     }
1189     __SD_task_set_state(task, SD_IN_FIFO);
1190     xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1191                SD_task_get_name(task), (int)SD_task_get_state(task));
1192     XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1193   } else {
1194     __SD_task_really_run(task);
1195   }
1196
1197   return can_start;
1198 }
1199
1200 /* This function is called by SD_simulate when a task is done.
1201  * It updates task->state and task->action and executes if necessary the tasks
1202  * which were waiting in FIFOs for the end of `task'
1203  */
1204 void __SD_task_just_done(SD_task_t task)
1205 {
1206   int i, j;
1207   SD_workstation_t workstation;
1208
1209   SD_task_t candidate;
1210   int candidate_nb = 0;
1211   int candidate_capacity = 8;
1212   SD_task_t *candidates;
1213   int can_start = 1;
1214
1215   xbt_assert(__SD_task_is_running(task),
1216               "The task must be running! Task state: %d",
1217               (int)SD_task_get_state(task));
1218   xbt_assert(task->workstation_list != NULL,
1219               "Task '%s': workstation_list is NULL!",
1220               SD_task_get_name(task));
1221
1222
1223   candidates = xbt_new(SD_task_t, 8);
1224
1225   __SD_task_set_state(task, SD_DONE);
1226   surf_workstation_model->action_unref(task->surf_action);
1227   task->surf_action = NULL;
1228
1229   XBT_DEBUG("Looking for candidates");
1230
1231   /* if the task was executed on sequential workstations,
1232      maybe we can execute the next task of the FIFO for each workstation */
1233   for (i = 0; i < task->workstation_nb; i++) {
1234     workstation = task->workstation_list[i];
1235     XBT_DEBUG("Workstation '%s': access_mode = %d",
1236               SD_workstation_get_name(workstation), (int)SD_workstation_priv(workstation)->access_mode);
1237     if (SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1238       xbt_assert(SD_workstation_priv(workstation)->task_fifo != NULL,
1239                   "Workstation '%s' has sequential access but no FIFO!",
1240                   SD_workstation_get_name(workstation));
1241       xbt_assert(SD_workstation_priv(workstation)->current_task =
1242                   task, "Workstation '%s': current task should be '%s'",
1243                   SD_workstation_get_name(workstation),
1244                   SD_task_get_name(task));
1245
1246       /* the task is over so we can release the workstation */
1247       SD_workstation_priv(workstation)->current_task = NULL;
1248
1249       XBT_DEBUG("Getting candidate in FIFO");
1250       candidate =
1251           xbt_fifo_get_item_content(xbt_fifo_get_first_item
1252                                     (SD_workstation_priv(workstation)->task_fifo));
1253
1254       if (candidate != NULL) {
1255         XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1256         xbt_assert(__SD_task_is_in_fifo(candidate),
1257                     "Bad state of candidate '%s': %d",
1258                     SD_task_get_name(candidate),
1259                     (int)SD_task_get_state(candidate));
1260       }
1261
1262       XBT_DEBUG("Candidate in fifo: %p", candidate);
1263
1264       /* if there was a task waiting for my place */
1265       if (candidate != NULL) {
1266         /* Unfortunately, we are not sure yet that we can execute the task now,
1267            because the task can be waiting more deeply in some other
1268            workstation's FIFOs ...
1269            So we memorize all candidate tasks, and then we will check for each
1270            candidate whether or not all its workstations are available. */
1271
1272         /* realloc if necessary */
1273         if (candidate_nb == candidate_capacity) {
1274           candidate_capacity *= 2;
1275           candidates =
1276               xbt_realloc(candidates,
1277                           sizeof(SD_task_t) * candidate_capacity);
1278         }
1279
1280         /* register the candidate */
1281         candidates[candidate_nb++] = candidate;
1282         candidate->fifo_checked = 0;
1283       }
1284     }
1285   }
1286
1287   XBT_DEBUG("Candidates found: %d", candidate_nb);
1288
1289   /* now we check every candidate task */
1290   for (i = 0; i < candidate_nb; i++) {
1291     candidate = candidates[i];
1292
1293     if (candidate->fifo_checked) {
1294       continue;                 /* we have already evaluated that task */
1295     }
1296
1297     xbt_assert(__SD_task_is_in_fifo(candidate),
1298                 "Bad state of candidate '%s': %d",
1299                SD_task_get_name(candidate), (int)SD_task_get_state(candidate));
1300
1301     for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1302       workstation = candidate->workstation_list[j];
1303
1304       /* I can start on this workstation if the workstation is shared
1305          or if I am the first task in the FIFO */
1306       can_start = SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SHARED_ACCESS
1307           || candidate ==
1308           xbt_fifo_get_item_content(xbt_fifo_get_first_item
1309                                     (SD_workstation_priv(workstation)->task_fifo));
1310     }
1311
1312     XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1313            can_start);
1314
1315     /* now we are sure that I can start! */
1316     if (can_start) {
1317       for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1318         workstation = candidate->workstation_list[j];
1319
1320         /* update the FIFO */
1321         if (SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1322           candidate = xbt_fifo_shift(SD_workstation_priv(workstation)->task_fifo);   /* the return value is stored just for debugging */
1323           XBT_DEBUG("Head of the FIFO: '%s'",
1324                  (candidate !=
1325                   NULL) ? SD_task_get_name(candidate) : "NULL");
1326           xbt_assert(candidate == candidates[i],
1327                       "Error in __SD_task_just_done: bad first task in the FIFO");
1328         }
1329       }                         /* for each workstation */
1330
1331       /* finally execute the task */
1332       XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1333              (int)SD_task_get_state(candidate));
1334       __SD_task_really_run(candidate);
1335
1336       XBT_DEBUG
1337           ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1338            SD_task_get_name(candidate), candidate->state_set,
1339            sd_global->running_task_set, __SD_task_is_running(candidate));
1340       xbt_assert(__SD_task_is_running(candidate),
1341                   "Bad state of task '%s': %d",
1342                   SD_task_get_name(candidate),
1343                  (int)SD_task_get_state(candidate));
1344       XBT_DEBUG("Okay, the task is running.");
1345
1346     }                           /* can start */
1347     candidate->fifo_checked = 1;
1348   }                             /* for each candidate */
1349
1350   xbt_free(candidates);
1351 }
1352
1353 /*
1354  * Remove all dependencies associated with a task. This function is called
1355  * when the task is destroyed.
1356  */
1357 static void __SD_task_remove_dependencies(SD_task_t task)
1358 {
1359   /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1360      because each one is stored twice */
1361   SD_dependency_t dependency;
1362   while (!xbt_dynar_is_empty(task->tasks_before)) {
1363     xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1364     SD_task_dependency_remove(dependency->src, dependency->dst);
1365   }
1366
1367   while (!xbt_dynar_is_empty(task->tasks_after)) {
1368     xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1369     SD_task_dependency_remove(dependency->src, dependency->dst);
1370   }
1371 }
1372
1373 /**
1374  * \brief Returns the start time of a task
1375  *
1376  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1377  *
1378  * \param task: a task
1379  * \return the start time of this task
1380  */
1381 double SD_task_get_start_time(SD_task_t task)
1382 {
1383   if (task->surf_action)
1384     return surf_workstation_model->
1385         action_get_start_time(task->surf_action);
1386   else
1387     return task->start_time;
1388 }
1389
1390 /**
1391  * \brief Returns the finish time of a task
1392  *
1393  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1394  * If the state is not completed yet, the returned value is an
1395  * estimation of the task finish time. This value can fluctuate
1396  * until the task is completed.
1397  *
1398  * \param task: a task
1399  * \return the start time of this task
1400  */
1401 double SD_task_get_finish_time(SD_task_t task)
1402 {
1403   if (task->surf_action)        /* should never happen as actions are destroyed right after their completion */
1404     return surf_workstation_model->
1405         action_get_finish_time(task->surf_action);
1406   else
1407     return task->finish_time;
1408 }
1409 /** @brief Blah
1410  *
1411  */
1412 void SD_task_distribute_comp_amdhal(SD_task_t task, int ws_count)
1413 {
1414   int i;
1415   xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1416               "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1417               "Cannot use this function.",
1418               SD_task_get_name(task));
1419   task->computation_amount = xbt_new0(double, ws_count);
1420   task->communication_amount = xbt_new0(double, ws_count * ws_count);
1421   if (task->workstation_list)
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           if (before->computation_amount)
1573             xbt_free(before->computation_amount);
1574           if (before->communication_amount)
1575             xbt_free(before->communication_amount);
1576
1577           before->computation_amount = xbt_new0(double,
1578                                                 before->workstation_nb);
1579           before->communication_amount = xbt_new0(double,
1580                                                   before->workstation_nb*
1581                                                   before->workstation_nb);
1582
1583           for(i=0;i<src_nb;i++){
1584             src_start = i*before->amount/src_nb;
1585             src_end = src_start + before->amount/src_nb;
1586             for(j=0; j<dst_nb; j++){
1587               dst_start = j*before->amount/dst_nb;
1588               dst_end = dst_start + before->amount/dst_nb;
1589               XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)",
1590                   SD_workstation_get_name(before->workstation_list[i]),
1591                   SD_workstation_get_name(before->workstation_list[src_nb+j]),
1592                   src_start, src_end, dst_start, dst_end);
1593               if ((src_end <= dst_start) || (dst_end <= src_start)) {
1594                 before->communication_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1595               } else {
1596                 before->communication_amount[i*(src_nb+dst_nb)+src_nb+j] =
1597                   MIN(src_end, dst_end) - MAX(src_start, dst_start);
1598               }
1599               XBT_VERB("==> %.2f",
1600                  before->communication_amount[i*(src_nb+dst_nb)+src_nb+j]);
1601             }
1602           }
1603
1604           if (__SD_task_is_schedulable(before) ||
1605               __SD_task_is_not_scheduled(before)) {
1606             SD_task_do_schedule(before);
1607             XBT_VERB
1608               ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1609                   SD_task_get_name(before),before->amount, src_nb, dst_nb);
1610             }
1611         }
1612       }
1613     }
1614     xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1615       SD_task_t after = dep->dst;
1616       if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1617         if (!after->workstation_list){
1618           XBT_VERB("Receiver side of Task '%s' is not scheduled yet",
1619               SD_task_get_name(after));
1620           after->workstation_list = xbt_new0(SD_workstation_t, count);
1621           after->workstation_nb = count;
1622           XBT_VERB("Fill the workstation list with list of Task '%s'",
1623             SD_task_get_name(task));
1624           for (i=0;i<count;i++)
1625             after->workstation_list[i] = task->workstation_list[i];
1626         } else {
1627           int src_nb, dst_nb;
1628           double src_start, src_end, dst_start, dst_end;
1629           src_nb = count;
1630           dst_nb = after->workstation_nb;
1631           after->workstation_list = (SD_workstation_t*) xbt_realloc(
1632             after->workstation_list,
1633             (after->workstation_nb+count)*sizeof(s_SD_workstation_t));
1634           for(i=after->workstation_nb - 1; i>=0; i--)
1635             after->workstation_list[count+i] = after->workstation_list[i];
1636           for(i=0; i<count; i++)
1637             after->workstation_list[i] = task->workstation_list[i];
1638
1639           after->workstation_nb += count;
1640
1641           if (after->computation_amount)
1642             xbt_free(after->computation_amount);
1643           if (after->communication_amount)
1644             xbt_free(after->communication_amount);
1645
1646           after->computation_amount = xbt_new0(double, after->workstation_nb);
1647           after->communication_amount = xbt_new0(double,
1648                                                  after->workstation_nb*
1649                                                  after->workstation_nb);
1650
1651           for(i=0;i<src_nb;i++){
1652             src_start = i*after->amount/src_nb;
1653             src_end = src_start + after->amount/src_nb;
1654             for(j=0; j<dst_nb; j++){
1655               dst_start = j*after->amount/dst_nb;
1656               dst_end = dst_start + after->amount/dst_nb;
1657               XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)",
1658                   i, j, src_start, src_end, dst_start, dst_end);
1659               if ((src_end <= dst_start) || (dst_end <= src_start)) {
1660                 after->communication_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1661               } else {
1662                 after->communication_amount[i*(src_nb+dst_nb)+src_nb+j] =
1663                    MIN(src_end, dst_end)- MAX(src_start, dst_start);
1664               }
1665               XBT_VERB("==> %.2f",
1666                  after->communication_amount[i*(src_nb+dst_nb)+src_nb+j]);
1667             }
1668           }
1669
1670           if (__SD_task_is_schedulable(after) ||
1671               __SD_task_is_not_scheduled(after)) {
1672             SD_task_do_schedule(after);
1673             XBT_VERB
1674             ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1675               SD_task_get_name(after),after->amount, src_nb, dst_nb);
1676           }
1677          }
1678       }
1679     }
1680   }
1681 }
1682
1683 /** @brief autoschedule a task on a list of workstations
1684  *
1685  * This function is very similar to SD_task_schedulev(),
1686  * but takes the list of workstations to schedule onto as separate parameters.
1687  * It builds a proper vector of workstations and then call SD_task_schedulev()
1688  */
1689 void SD_task_schedulel(SD_task_t task, int count, ...)
1690 {
1691   va_list ap;
1692   SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1693   int i;
1694   va_start(ap, count);
1695   for (i = 0; i < count; i++) {
1696     list[i] = va_arg(ap, SD_workstation_t);
1697   }
1698   va_end(ap);
1699   SD_task_schedulev(task, count, list);
1700   free(list);
1701 }