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