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_NOT_TYPED)        /* Don't free scheduling data for typed tasks */
 969     __SD_task_destroy_scheduling_data(task);
 970
 971   if (__SD_task_is_running(task))       /* the task should become SD_FAILED */
 972     surf_workstation_model->action_cancel(task->surf_action);
 973   else {
 974     if (task->unsatisfied_dependencies == 0)
 975       __SD_task_set_state(task, SD_SCHEDULABLE);
 976     else
 977       __SD_task_set_state(task, SD_NOT_SCHEDULED);
 978   }
 979   task->remains = task->amount;
 980   task->start_time = -1.0;
 981 }
 982
 983 /* Destroys the data memorized by SD_task_schedule. Task state must be SD_SCHEDULED or SD_RUNNABLE.
 984  */
 985 static void __SD_task_destroy_scheduling_data(SD_task_t task)
 986 {
 987   if (!__SD_task_is_scheduled_or_runnable(task)
 988       && !__SD_task_is_in_fifo(task))
 989     THROWF(arg_error, 0,
 990            "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
 991            SD_task_get_name(task));
 992
 993   xbt_free(task->computation_amount);
 994   xbt_free(task->communication_amount);
 995   task->computation_amount = task->communication_amount = NULL;
 996 }
 997
 998 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
 999  * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
1000  * the task gets out of its fifos.
1001  */
1002 void __SD_task_really_run(SD_task_t task)
1003 {
1004
1005   int i;
1006   void **surf_workstations;
1007
1008   xbt_assert(__SD_task_is_runnable_or_in_fifo(task),
1009               "Task '%s' is not runnable or in a fifo! Task state: %d",
1010              SD_task_get_name(task), (int)SD_task_get_state(task));
1011   xbt_assert(task->workstation_list != NULL,
1012               "Task '%s': workstation_list is NULL!",
1013               SD_task_get_name(task));
1014
1015
1016
1017   XBT_DEBUG("Really running task '%s'", SD_task_get_name(task));
1018
1019   /* set this task as current task for the workstations in sequential mode */
1020   for (i = 0; i < task->workstation_nb; i++) {
1021     if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
1022         SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1023       task->workstation_list[i]->current_task = task;
1024       xbt_assert(__SD_workstation_is_busy(task->workstation_list[i]),
1025                   "The workstation should be busy now");
1026     }
1027   }
1028
1029   XBT_DEBUG("Task '%s' set as current task for its workstations",
1030          SD_task_get_name(task));
1031
1032   /* start the task */
1033
1034   /* we have to create a Surf workstation array instead of the SimDag
1035    * workstation array */
1036   surf_workstations = xbt_new(void *, task->workstation_nb);
1037
1038   for (i = 0; i < task->workstation_nb; i++)
1039     surf_workstations[i] = task->workstation_list[i]->surf_workstation;
1040
1041   /* It's allowed to pass a NULL vector as cost to mean vector of 0.0 (easing
1042    * user's life). Let's deal with it */
1043 #define cost_or_zero(array,pos) ((array)?(array)[pos]:0.0)
1044
1045   task->surf_action = NULL;
1046   if ((task->workstation_nb == 1)
1047       && (cost_or_zero(task->communication_amount, 0) == 0.0)) {
1048     task->surf_action =
1049         surf_workstation_model->extension.
1050         workstation.execute(surf_workstations[0],
1051                             cost_or_zero(task->computation_amount, 0));
1052   } else if ((task->workstation_nb == 1)
1053              && (cost_or_zero(task->computation_amount, 0) == 0.0)) {
1054
1055     task->surf_action =
1056         surf_workstation_model->extension.
1057         workstation.communicate(surf_workstations[0], surf_workstations[0],
1058                                 cost_or_zero(task->communication_amount,
1059                                              0), task->rate);
1060   } else if ((task->workstation_nb == 2)
1061              && (cost_or_zero(task->computation_amount, 0) == 0.0)
1062              && (cost_or_zero(task->computation_amount, 1) == 0.0)) {
1063     int nb = 0;
1064     double value = 0.0;
1065
1066     for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
1067       if (cost_or_zero(task->communication_amount, i) > 0.0) {
1068         nb++;
1069         value = cost_or_zero(task->communication_amount, i);
1070       }
1071     }
1072     if (nb == 1) {
1073       task->surf_action =
1074           surf_workstation_model->extension.
1075           workstation.communicate(surf_workstations[0],
1076                                   surf_workstations[1], value, task->rate);
1077     }
1078   }
1079 #undef cost_or_zero
1080
1081   if (!task->surf_action) {
1082     double *computation_amount = xbt_new(double, task->workstation_nb);
1083     double *communication_amount = xbt_new(double, task->workstation_nb *
1084                                            task->workstation_nb);
1085
1086     memcpy(computation_amount, task->computation_amount, sizeof(double) *
1087            task->workstation_nb);
1088     memcpy(communication_amount, task->communication_amount,
1089            sizeof(double) * task->workstation_nb * task->workstation_nb);
1090
1091     task->surf_action =
1092         surf_workstation_model->extension.
1093         workstation.execute_parallel_task(task->workstation_nb,
1094                                           surf_workstations,
1095                                           computation_amount,
1096                                           communication_amount,
1097                                           task->rate);
1098   } else {
1099     xbt_free(surf_workstations);
1100   }
1101
1102   surf_workstation_model->action_data_set(task->surf_action, task);
1103
1104   XBT_DEBUG("surf_action = %p", task->surf_action);
1105
1106 #ifdef HAVE_TRACING
1107   if (task->category)
1108     TRACE_surf_action(task->surf_action, task->category);
1109 #endif
1110
1111   __SD_task_destroy_scheduling_data(task);      /* now the scheduling data are not useful anymore */
1112   __SD_task_set_state(task, SD_RUNNING);
1113   xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
1114              SD_task_get_name(task), (int)SD_task_get_state(task));
1115
1116 }
1117
1118 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_RUNNABLE
1119  * (ie when its dependencies are satisfied).
1120  * If one of the workstations where the task is scheduled on is busy (in sequential mode),
1121  * the task doesn't start.
1122  * Returns whether the task has started.
1123  */
1124 int __SD_task_try_to_run(SD_task_t task)
1125 {
1126
1127   int can_start = 1;
1128   int i;
1129   SD_workstation_t workstation;
1130
1131   xbt_assert(__SD_task_is_runnable(task),
1132               "Task '%s' is not runnable! Task state: %d",
1133              SD_task_get_name(task), (int)SD_task_get_state(task));
1134
1135
1136   for (i = 0; i < task->workstation_nb; i++) {
1137     can_start = can_start &&
1138         !__SD_workstation_is_busy(task->workstation_list[i]);
1139   }
1140
1141   XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1142
1143   if (!can_start) {             /* if the task cannot start and is not in the fifos yet */
1144     for (i = 0; i < task->workstation_nb; i++) {
1145       workstation = task->workstation_list[i];
1146       if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1147         XBT_DEBUG("Pushing task '%s' in the fifo of workstation '%s'",
1148                SD_task_get_name(task),
1149                SD_workstation_get_name(workstation));
1150         xbt_fifo_push(workstation->task_fifo, task);
1151       }
1152     }
1153     __SD_task_set_state(task, SD_IN_FIFO);
1154     xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1155                SD_task_get_name(task), (int)SD_task_get_state(task));
1156     XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1157   } else {
1158     __SD_task_really_run(task);
1159   }
1160
1161   return can_start;
1162 }
1163
1164 /* This function is called by SD_simulate when a task is done.
1165  * It updates task->state and task->action and executes if necessary the tasks
1166  * which were waiting in fifos for the end of `task'
1167  */
1168 void __SD_task_just_done(SD_task_t task)
1169 {
1170   int i, j;
1171   SD_workstation_t workstation;
1172
1173   SD_task_t candidate;
1174   int candidate_nb = 0;
1175   int candidate_capacity = 8;
1176   SD_task_t *candidates;
1177   int can_start = 1;
1178
1179   xbt_assert(__SD_task_is_running(task),
1180               "The task must be running! Task state: %d",
1181               (int)SD_task_get_state(task));
1182   xbt_assert(task->workstation_list != NULL,
1183               "Task '%s': workstation_list is NULL!",
1184               SD_task_get_name(task));
1185
1186
1187   candidates = xbt_new(SD_task_t, 8);
1188
1189   __SD_task_set_state(task, SD_DONE);
1190   surf_workstation_model->action_unref(task->surf_action);
1191   task->surf_action = NULL;
1192
1193   XBT_DEBUG("Looking for candidates");
1194
1195   /* if the task was executed on sequential workstations,
1196      maybe we can execute the next task of the fifo for each workstation */
1197   for (i = 0; i < task->workstation_nb; i++) {
1198     workstation = task->workstation_list[i];
1199     XBT_DEBUG("Workstation '%s': access_mode = %d",
1200               SD_workstation_get_name(workstation), (int)workstation->access_mode);
1201     if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1202       xbt_assert(workstation->task_fifo != NULL,
1203                   "Workstation '%s' has sequential access but no fifo!",
1204                   SD_workstation_get_name(workstation));
1205       xbt_assert(workstation->current_task =
1206                   task, "Workstation '%s': current task should be '%s'",
1207                   SD_workstation_get_name(workstation),
1208                   SD_task_get_name(task));
1209
1210       /* the task is over so we can release the workstation */
1211       workstation->current_task = NULL;
1212
1213       XBT_DEBUG("Getting candidate in fifo");
1214       candidate =
1215           xbt_fifo_get_item_content(xbt_fifo_get_first_item
1216                                     (workstation->task_fifo));
1217
1218       if (candidate != NULL) {
1219         XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1220         xbt_assert(__SD_task_is_in_fifo(candidate),
1221                     "Bad state of candidate '%s': %d",
1222                     SD_task_get_name(candidate),
1223                     (int)SD_task_get_state(candidate));
1224       }
1225
1226       XBT_DEBUG("Candidate in fifo: %p", candidate);
1227
1228       /* if there was a task waiting for my place */
1229       if (candidate != NULL) {
1230         /* Unfortunately, we are not sure yet that we can execute the task now,
1231            because the task can be waiting more deeply in some other workstation's fifos...
1232            So we memorize all candidate tasks, and then we will check for each candidate
1233            whether or not all its workstations are available. */
1234
1235         /* realloc if necessary */
1236         if (candidate_nb == candidate_capacity) {
1237           candidate_capacity *= 2;
1238           candidates =
1239               xbt_realloc(candidates,
1240                           sizeof(SD_task_t) * candidate_capacity);
1241         }
1242
1243         /* register the candidate */
1244         candidates[candidate_nb++] = candidate;
1245         candidate->fifo_checked = 0;
1246       }
1247     }
1248   }
1249
1250   XBT_DEBUG("Candidates found: %d", candidate_nb);
1251
1252   /* now we check every candidate task */
1253   for (i = 0; i < candidate_nb; i++) {
1254     candidate = candidates[i];
1255
1256     if (candidate->fifo_checked) {
1257       continue;                 /* we have already evaluated that task */
1258     }
1259
1260     xbt_assert(__SD_task_is_in_fifo(candidate),
1261                 "Bad state of candidate '%s': %d",
1262                SD_task_get_name(candidate), (int)SD_task_get_state(candidate));
1263
1264     for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1265       workstation = candidate->workstation_list[j];
1266
1267       /* I can start on this workstation if the workstation is shared
1268          or if I am the first task in the fifo */
1269       can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS
1270           || candidate ==
1271           xbt_fifo_get_item_content(xbt_fifo_get_first_item
1272                                     (workstation->task_fifo));
1273     }
1274
1275     XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1276            can_start);
1277
1278     /* now we are sure that I can start! */
1279     if (can_start) {
1280       for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1281         workstation = candidate->workstation_list[j];
1282
1283         /* update the fifo */
1284         if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1285           candidate = xbt_fifo_shift(workstation->task_fifo);   /* the return value is stored just for debugging */
1286           XBT_DEBUG("Head of the fifo: '%s'",
1287                  (candidate !=
1288                   NULL) ? SD_task_get_name(candidate) : "NULL");
1289           xbt_assert(candidate == candidates[i],
1290                       "Error in __SD_task_just_done: bad first task in the fifo");
1291         }
1292       }                         /* for each workstation */
1293
1294       /* finally execute the task */
1295       XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1296              (int)SD_task_get_state(candidate));
1297       __SD_task_really_run(candidate);
1298
1299       XBT_DEBUG
1300           ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1301            SD_task_get_name(candidate), candidate->state_set,
1302            sd_global->running_task_set, __SD_task_is_running(candidate));
1303       xbt_assert(__SD_task_is_running(candidate),
1304                   "Bad state of task '%s': %d",
1305                   SD_task_get_name(candidate),
1306                  (int)SD_task_get_state(candidate));
1307       XBT_DEBUG("Okay, the task is running.");
1308
1309     }                           /* can start */
1310     candidate->fifo_checked = 1;
1311   }                             /* for each candidate */
1312
1313   xbt_free(candidates);
1314 }
1315
1316 /*
1317  * Remove all dependencies associated with a task. This function is called
1318  * when the task is destroyed.
1319  */
1320 static void __SD_task_remove_dependencies(SD_task_t task)
1321 {
1322   /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1323      because each one is stored twice */
1324   SD_dependency_t dependency;
1325   while (!xbt_dynar_is_empty(task->tasks_before)) {
1326     xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1327     SD_task_dependency_remove(dependency->src, dependency->dst);
1328   }
1329
1330   while (!xbt_dynar_is_empty(task->tasks_after)) {
1331     xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1332     SD_task_dependency_remove(dependency->src, dependency->dst);
1333   }
1334 }
1335
1336 /**
1337  * \brief Returns the start time of a task
1338  *
1339  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1340  *
1341  * \param task: a task
1342  * \return the start time of this task
1343  */
1344 double SD_task_get_start_time(SD_task_t task)
1345 {
1346   if (task->surf_action)
1347     return surf_workstation_model->
1348         action_get_start_time(task->surf_action);
1349   else
1350     return task->start_time;
1351 }
1352
1353 /**
1354  * \brief Returns the finish time of a task
1355  *
1356  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1357  * If the state is not completed yet, the returned value is an
1358  * estimation of the task finish time. This value can fluctuate
1359  * until the task is completed.
1360  *
1361  * \param task: a task
1362  * \return the start time of this task
1363  */
1364 double SD_task_get_finish_time(SD_task_t task)
1365 {
1366   if (task->surf_action)        /* should never happen as actions are destroyed right after their completion */
1367     return surf_workstation_model->
1368         action_get_finish_time(task->surf_action);
1369   else
1370     return task->finish_time;
1371 }
1372 /** @brief Blah
1373  *
1374  */
1375 void SD_task_distribute_comp_amdhal(SD_task_t task, int ws_count)
1376 {
1377   int i;
1378   xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1379               "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1380               "Cannot use this function.",
1381               SD_task_get_name(task));
1382
1383   task->computation_amount = xbt_new0(double, ws_count);
1384   task->communication_amount = xbt_new0(double, ws_count * ws_count);
1385   task->workstation_nb = ws_count;
1386   task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1387
1388   for(i=0;i<ws_count;i++){
1389     task->computation_amount[i] =
1390       (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1391   }
1392 }
1393
1394
1395 /** @brief Auto-schedules a task.
1396  *
1397  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1398  * allows to specify the task costs at creation, and decorelate them from the
1399  * scheduling process where you just specify which resource should deliver the
1400  * mandatory power.
1401  *
1402  * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1403  * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1404  * of them.
1405  *
1406  * @todo
1407  * We should create tasks kind for the following categories:
1408  *  - Point to point communication (done)
1409  *  - Sequential computation       (done)
1410  *  - group communication (redistribution, several kinds)
1411  *  - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1412  *  - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1413  */
1414 void SD_task_schedulev(SD_task_t task, int count,
1415                        const SD_workstation_t * list)
1416 {
1417   int i, j;
1418   SD_dependency_t dep;
1419   unsigned int cpt;
1420   xbt_assert(task->kind != 0,
1421               "Task %s is not typed. Cannot automatically schedule it.",
1422               SD_task_get_name(task));
1423   switch (task->kind) {
1424   case SD_TASK_COMP_PAR_AMDAHL:
1425     SD_task_distribute_comp_amdhal(task, count);
1426   case SD_TASK_COMM_E2E:
1427   case SD_TASK_COMP_SEQ:
1428     xbt_assert(task->workstation_nb == count,"Got %d locations, but were expecting %d locations",count,task->workstation_nb);
1429     for (i = 0; i < count; i++)
1430       task->workstation_list[i] = list[i];
1431     SD_task_do_schedule(task);
1432     break;
1433   default:
1434     xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1435             SD_task_get_name(task));
1436   }
1437   if (task->kind == SD_TASK_COMM_E2E) {
1438     XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1439           SD_task_get_name(task),
1440           SD_workstation_get_name(task->workstation_list[0]),
1441           SD_workstation_get_name(task->workstation_list[1]),
1442           task->communication_amount[2]);
1443
1444   }
1445  if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1446    XBT_VERB("Schedule computation task %s on %d hosts. It costs %.f flops on each host",
1447             SD_task_get_name(task),
1448             task->workstation_nb,
1449             task->computation_amount[0]);
1450  }
1451
1452   /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if runnable) */
1453   if (task->kind == SD_TASK_COMP_SEQ) {
1454     XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1455           SD_task_get_name(task),
1456           SD_workstation_get_name(task->workstation_list[0]),
1457           task->computation_amount[0]);
1458
1459     xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1460       SD_task_t before = dep->src;
1461       if (before->kind == SD_TASK_COMM_E2E) {
1462         before->workstation_list[1] = task->workstation_list[0];
1463
1464         if (before->workstation_list[0] &&
1465             (__SD_task_is_schedulable(before)
1466              || __SD_task_is_not_scheduled(before))) {
1467           SD_task_do_schedule(before);
1468           XBT_VERB
1469               ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1470                SD_task_get_name(before),
1471                SD_workstation_get_name(before->workstation_list[0]),
1472                SD_workstation_get_name(before->workstation_list[1]),
1473                before->communication_amount[2]);
1474         }
1475       } else if (before->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1476           if (!before->workstation_list){
1477             before->workstation_list = xbt_new0(SD_workstation_t, count);
1478             for (i=0;i<count;i++)
1479               before->workstation_list[i] = task->workstation_list[i];
1480           } else {
1481             int src_nb, dst_nb, src_start, src_end, dst_start, dst_end;
1482             src_nb = before->workstation_nb;
1483             dst_nb = count;
1484             before->workstation_list = (SD_workstation_t*) xbt_realloc(
1485                before->workstation_list,
1486               (before->workstation_nb+count)*sizeof(s_SD_workstation_t));
1487             for(i=0; i<count; i++)
1488               before->workstation_list[before->workstation_nb+i] =
1489                 task->workstation_list[i];
1490
1491             before->workstation_nb += count;
1492
1493             before->computation_amount = xbt_new0(double,
1494                                                   before->workstation_nb);
1495             before->communication_amount = xbt_new0(double,
1496                                                     before->workstation_nb*
1497                                                     before->workstation_nb);
1498
1499             for(i=0;i<src_nb;i++){
1500               src_start = i*before->amount/src_nb;
1501               src_end = src_start + before->amount/src_nb;
1502               for(j=0; j<dst_nb; j++){
1503                 dst_start = j*before->amount/dst_nb;
1504                 dst_end = dst_start + before->amount/dst_nb;
1505                 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1506                   before->communication_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1507                 } else {
1508                   before->communication_amount[i*(src_nb+dst_nb)+src_nb+j] =
1509                     MIN(src_end, dst_end)- MAX(src_start, dst_start);
1510                 }
1511               }
1512             }
1513
1514             if (__SD_task_is_schedulable(before) ||
1515                 __SD_task_is_not_scheduled(before)) {
1516               SD_task_do_schedule(before);
1517               XBT_VERB
1518               ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1519                   SD_task_get_name(before),
1520                   before->amount,
1521                   src_nb, dst_nb);
1522             }
1523           }
1524       }
1525     }
1526     xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1527       SD_task_t after = dep->dst;
1528       if (after->kind == SD_TASK_COMM_E2E) {
1529         after->workstation_list[0] = task->workstation_list[0];
1530         if (after->workstation_list[1]
1531             && (__SD_task_is_not_scheduled(after)
1532                 || __SD_task_is_schedulable(after))) {
1533           SD_task_do_schedule(after);
1534           XBT_VERB
1535               ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1536                SD_task_get_name(after),
1537                SD_workstation_get_name(after->workstation_list[0]),
1538                SD_workstation_get_name(after->workstation_list[1]),
1539                after->communication_amount[2]);
1540
1541         }
1542       } else if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1543           if (!after->workstation_list){
1544               after->workstation_list = xbt_new0(SD_workstation_t, count);
1545             for (i=0;i<count;i++)
1546               after->workstation_list[i] = task->workstation_list[i];
1547           } else {
1548             int src_nb, dst_nb, src_start, src_end, dst_start, dst_end;
1549             src_nb = count;;
1550             dst_nb = after->workstation_nb;
1551             after->workstation_list = (SD_workstation_t*) xbt_realloc(
1552               after->workstation_list,
1553               (after->workstation_nb+count)*sizeof(s_SD_workstation_t));
1554             for(i=after->workstation_nb - 1; i>=0; i--)
1555               after->workstation_list[count+i] = after->workstation_list[i];
1556
1557             for(i=0; i<count; i++)
1558               after->workstation_list[i] = task->workstation_list[i];
1559
1560             after->workstation_nb += count;
1561
1562             after->computation_amount = xbt_new0(double, after->workstation_nb);
1563             after->communication_amount = xbt_new0(double,
1564                                                    after->workstation_nb*
1565                                                    after->workstation_nb);
1566
1567             for(i=0;i<src_nb;i++){
1568               src_start = i*after->amount/src_nb;
1569               src_end = src_start + after->amount/src_nb;
1570               for(j=0; j<dst_nb; j++){
1571                 dst_start = j*after->amount/dst_nb;
1572                 dst_end = dst_start + after->amount/dst_nb;
1573                 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1574                    after->communication_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1575                 } else {
1576                   after->communication_amount[i*(src_nb+dst_nb)+src_nb+j] =
1577                      MIN(src_end, dst_end)- MAX(src_start, dst_start);
1578                 }
1579               }
1580             }
1581
1582             if (__SD_task_is_schedulable(after) ||
1583                 __SD_task_is_not_scheduled(after)) {
1584               SD_task_do_schedule(after);
1585               XBT_VERB
1586               ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1587                 SD_task_get_name(after),after->amount, src_nb, dst_nb);
1588             }
1589          }
1590       }
1591     }
1592   }
1593 }
1594
1595 /** @brief autoschedule a task on a list of workstations
1596  *
1597  * This function is very similar to SD_task_schedulev(),
1598  * but takes the list of workstations to schedule onto as separate parameters.
1599  * It builds a proper vector of workstations and then call SD_task_schedulev()
1600  */
1601 void SD_task_schedulel(SD_task_t task, int count, ...)
1602 {
1603   va_list ap;
1604   SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1605   int i;
1606   va_start(ap, count);
1607   for (i = 0; i < count; i++) {
1608     list[i] = va_arg(ap, SD_workstation_t);
1609   }
1610   va_end(ap);
1611   SD_task_schedulev(task, count, list);
1612   free(list);
1613 }
1614
1615 /**
1616  * \brief Sets the tracing category of a task.
1617  *
1618  * This function should be called after the creation of a
1619  * SimDAG task, to define the category of that task. The first
1620  * parameter must contain a task that was created with the
1621  * function #SD_task_create. The second parameter must contain
1622  * a category that was previously declared with the function
1623  * #TRACE_category.
1624  *
1625  * \param task The task to be considered
1626  * \param category the name of the category to be associated to the task
1627  *
1628  * \see SD_task_get_category, TRACE_category, TRACE_category_with_color
1629  */
1630 void SD_task_set_category (SD_task_t task, const char *category)
1631 {
1632 #ifdef HAVE_TRACING
1633   if (!TRACE_is_enabled()) return;
1634   if (task == NULL) return;
1635   if (category == NULL){
1636     if (task->category) xbt_free (task->category);
1637     task->category = NULL;
1638   }else{
1639     task->category = xbt_strdup (category);
1640   }
1641 #endif
1642 }
1643
1644 /**
1645  * \brief Gets the current tracing category of a task.
1646  *
1647  * \param task The task to be considered
1648  *
1649  * \see SD_task_set_category
1650  *
1651  * \return Returns the name of the tracing category of the given task, NULL otherwise
1652  */
1653 const char *SD_task_get_category (SD_task_t task)
1654 {
1655 #ifdef HAVE_TRACING
1656   return task->category;
1657 #else
1658   return NULL;
1659 #endif
1660 }