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