src/simdag/sd_task.c

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