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