src/simdag/sd_task.cpp

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