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