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         if (bytes_amount[i * workstation_nb + j] !=0 ) {
 908           time += (SD_route_get_latency(workstation_list[i],
 909                                         workstation_list[j]) +
 910                    bytes_amount[i * workstation_nb + j] /
 911                    SD_route_get_bandwidth(workstation_list[i],
 912                                           workstation_list[j]));
 913         }
 914       }
 915
 916     if (time > max_time) {
 917       max_time = time;
 918     }
 919   }
 920   return max_time;
 921 }
 922
 923 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
 924 {
 925   if (SD_task_get_state(task) > SD_SCHEDULABLE)
 926     THROWF(arg_error, 0, "Task '%s' has already been scheduled",
 927            SD_task_get_name(task));
 928
 929   /* update the task state */
 930   if (task->unsatisfied_dependencies == 0)
 931     SD_task_set_state(task, SD_RUNNABLE);
 932   else
 933     SD_task_set_state(task, SD_SCHEDULED);
 934 }
 935
 936 /**
 937  * \brief Schedules a task
 938  *
 939  * The task state must be #SD_NOT_SCHEDULED.
 940  * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
 941  * i.e. when its dependencies are satisfied.
 942  *
 943  * \param task the task you want to schedule
 944  * \param workstation_count number of workstations on which the task will be executed
 945  * \param workstation_list the workstations on which the task will be executed
 946  * \param flops_amount computation amount for each workstation
 947  * \param bytes_amount communication amount between each pair of workstations
 948  * \param rate task execution speed rate
 949  * \see SD_task_unschedule()
 950  */
 951 void SD_task_schedule(SD_task_t task, int workstation_count,
 952                       const sg_host_t * workstation_list,
 953                       const double *flops_amount,
 954                       const double *bytes_amount, double rate)
 955 {
 956   xbt_assert(workstation_count > 0, "workstation_nb must be positive");
 957
 958   task->host_count = workstation_count;
 959   task->rate = rate;
 960
 961   if (flops_amount) {
 962     task->flops_amount = (double*)xbt_realloc(task->flops_amount,
 963                                            sizeof(double) * workstation_count);
 964     memcpy(task->flops_amount, flops_amount,
 965            sizeof(double) * workstation_count);
 966   } else {
 967     xbt_free(task->flops_amount);
 968     task->flops_amount = NULL;
 969   }
 970
 971   int communication_nb = workstation_count * workstation_count;
 972   if (bytes_amount) {
 973     task->bytes_amount = (double*)xbt_realloc(task->bytes_amount,
 974                                              sizeof(double) * communication_nb);
 975     memcpy(task->bytes_amount, bytes_amount,
 976            sizeof(double) * communication_nb);
 977   } else {
 978     xbt_free(task->bytes_amount);
 979     task->bytes_amount = NULL;
 980   }
 981
 982   task->host_list = (sg_host_t*)
 983     xbt_realloc(task->host_list,
 984                 sizeof(sg_host_t) * workstation_count);
 985   memcpy(task->host_list, workstation_list,
 986          sizeof(sg_host_t) * workstation_count);
 987
 988   SD_task_do_schedule(task);
 989 }
 990
 991 /**
 992  * \brief Unschedules a task
 993  *
 994  * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
 995  * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
 996  * Call SD_task_schedule() to schedule it again.
 997  *
 998  * \param task the task you want to unschedule
 999  * \see SD_task_schedule()
1000  */
1001 void SD_task_unschedule(SD_task_t task)
1002 {
1003   if (task->state != SD_SCHEDULED &&
1004       task->state != SD_RUNNABLE &&
1005       task->state != SD_RUNNING &&
1006       task->state != SD_FAILED)
1007     THROWF(arg_error, 0,
1008            "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
1009            SD_task_get_name(task));
1010
1011   if (__SD_task_is_scheduled_or_runnable(task)  /* if the task is scheduled or runnable */
1012       && ((task->kind == SD_TASK_COMP_PAR_AMDAHL) ||
1013           (task->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK))) { /* Don't free scheduling data for typed tasks */
1014     __SD_task_destroy_scheduling_data(task);
1015     xbt_free(task->host_list);
1016     task->host_list=NULL;
1017     task->host_count = 0;
1018   }
1019
1020   if (SD_task_get_state(task) == SD_RUNNING)
1021     /* the task should become SD_FAILED */
1022     task->surf_action->cancel();
1023   else {
1024     if (task->unsatisfied_dependencies == 0)
1025       SD_task_set_state(task, SD_SCHEDULABLE);
1026     else
1027       SD_task_set_state(task, SD_NOT_SCHEDULED);
1028   }
1029   task->remains = task->amount;
1030   task->start_time = -1.0;
1031 }
1032
1033 /* Destroys the data memorized by SD_task_schedule.
1034  * Task state must be SD_SCHEDULED or SD_RUNNABLE.
1035  */
1036 static void __SD_task_destroy_scheduling_data(SD_task_t task)
1037 {
1038   if (!__SD_task_is_scheduled_or_runnable(task))
1039     THROWF(arg_error, 0,
1040            "Task '%s' must be SD_SCHEDULED or SD_RUNNABLE",
1041            SD_task_get_name(task));
1042
1043   xbt_free(task->flops_amount);
1044   xbt_free(task->bytes_amount);
1045   task->flops_amount = task->bytes_amount = NULL;
1046 }
1047
1048 /* Runs a task. This function is directly called by __SD_task_try_to_run if
1049  * the task doesn't have to wait in FIFOs. Otherwise, it is called by
1050  * __SD_task_just_done when the task gets out of its FIFOs.
1051  */
1052 void SD_task_run(SD_task_t task)
1053 {
1054
1055   int i;
1056   sg_host_t *hosts;
1057
1058   xbt_assert(SD_task_get_state(task) == SD_RUNNABLE,
1059              "Task '%s' is not runnable! Task state: %d",
1060              SD_task_get_name(task), (int)SD_task_get_state(task));
1061   xbt_assert(task->host_list != NULL,
1062               "Task '%s': workstation_list is NULL!",
1063               SD_task_get_name(task));
1064
1065   XBT_DEBUG("Running task '%s'", SD_task_get_name(task));
1066
1067   /* Copy the elements of the task into the action */
1068   int host_nb = task->host_count;
1069   hosts = xbt_new(sg_host_t, host_nb);
1070
1071   for (i = 0; i < host_nb; i++)
1072     hosts[i] =  task->host_list[i];
1073
1074   double *flops_amount = xbt_new0(double, host_nb);
1075   double *bytes_amount = xbt_new0(double, host_nb * host_nb);
1076
1077   if(task->flops_amount)
1078     memcpy(flops_amount, task->flops_amount, sizeof(double) * host_nb);
1079   if(task->bytes_amount)
1080     memcpy(bytes_amount, task->bytes_amount,
1081            sizeof(double) * host_nb * host_nb);
1082
1083   task->surf_action = surf_host_model->executeParallelTask(
1084     host_nb, hosts, flops_amount, bytes_amount, task->rate);
1085
1086   task->surf_action->setData(task);
1087
1088   XBT_DEBUG("surf_action = %p", task->surf_action);
1089
1090   if (task->category)
1091     TRACE_surf_action(task->surf_action, task->category);
1092
1093   __SD_task_destroy_scheduling_data(task);      /* now the scheduling data are not useful anymore */
1094   SD_task_set_state(task, SD_RUNNING);
1095   xbt_assert(SD_task_get_state(task) == SD_RUNNING,
1096              "Bad state of task '%s': %d",
1097              SD_task_get_name(task), (int)SD_task_get_state(task));
1098
1099 }
1100
1101 /*
1102  * Remove all dependencies associated with a task. This function is called
1103  * when the task is destroyed.
1104  */
1105 static void __SD_task_remove_dependencies(SD_task_t task)
1106 {
1107   /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1108      because each one is stored twice */
1109   SD_dependency_t dependency;
1110   while (!xbt_dynar_is_empty(task->tasks_before)) {
1111     xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1112     SD_task_dependency_remove(dependency->src, dependency->dst);
1113   }
1114
1115   while (!xbt_dynar_is_empty(task->tasks_after)) {
1116     xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1117     SD_task_dependency_remove(dependency->src, dependency->dst);
1118   }
1119 }
1120
1121 /**
1122  * \brief Returns the start time of a task
1123  *
1124  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1125  *
1126  * \param task: a task
1127  * \return the start time of this task
1128  */
1129 double SD_task_get_start_time(SD_task_t task)
1130 {
1131   if (task->surf_action)
1132     return task->surf_action->getStartTime();
1133   else
1134     return task->start_time;
1135 }
1136
1137 /**
1138  * \brief Returns the finish time of a task
1139  *
1140  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1141  * If the state is not completed yet, the returned value is an
1142  * estimation of the task finish time. This value can fluctuate
1143  * until the task is completed.
1144  *
1145  * \param task: a task
1146  * \return the start time of this task
1147  */
1148 double SD_task_get_finish_time(SD_task_t task)
1149 {
1150   if (task->surf_action)        /* should never happen as actions are destroyed right after their completion */
1151     return task->surf_action->getFinishTime();
1152   else
1153     return task->finish_time;
1154 }
1155 /** @brief Blah
1156  *
1157  */
1158 void SD_task_distribute_comp_amdahl(SD_task_t task, int ws_count)
1159 {
1160   int i;
1161   xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1162               "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1163               "Cannot use this function.",
1164               SD_task_get_name(task));
1165   task->flops_amount = xbt_new0(double, ws_count);
1166   task->bytes_amount = xbt_new0(double, ws_count * ws_count);
1167   xbt_free(task->host_list);
1168   task->host_count = ws_count;
1169   task->host_list = xbt_new0(sg_host_t, ws_count);
1170
1171   for(i=0;i<ws_count;i++){
1172     task->flops_amount[i] =
1173       (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1174   }
1175 }
1176
1177
1178 /** @brief Auto-schedules a task.
1179  *
1180  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1181  * allows to specify the task costs at creation, and decouple them from the
1182  * scheduling process where you just specify which resource should deliver the
1183  * mandatory power.
1184  *
1185  * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e()
1186  * or SD_task_create_comp_seq(). Check their definitions for the exact semantic
1187  * of each of them.
1188  *
1189  * @todo
1190  * We should create tasks kind for the following categories:
1191  *  - Point to point communication (done)
1192  *  - Sequential computation       (done)
1193  *  - group communication (redistribution, several kinds)
1194  *  - parallel tasks with no internal communication (one kind per speedup
1195  *    model such as Amdahl)
1196  *  - idem+ internal communication. Task type not enough since we cannot store
1197  *    comm cost alongside to comp one)
1198  */
1199 void SD_task_schedulev(SD_task_t task, int count,
1200                        const sg_host_t * list)
1201 {
1202   int i, j;
1203   SD_dependency_t dep;
1204   unsigned int cpt;
1205   xbt_assert(task->kind != 0,
1206               "Task %s is not typed. Cannot automatically schedule it.",
1207               SD_task_get_name(task));
1208   switch (task->kind) {
1209   case SD_TASK_COMP_PAR_AMDAHL:
1210     SD_task_distribute_comp_amdahl(task, count);
1211   case SD_TASK_COMM_E2E:
1212   case SD_TASK_COMP_SEQ:
1213     xbt_assert(task->host_count == count,
1214                "Got %d locations, but were expecting %d locations",
1215                count,task->host_count);
1216     for (i = 0; i < count; i++)
1217       task->host_list[i] = list[i];
1218     if (SD_task_get_kind(task)== SD_TASK_COMP_SEQ && !task->flops_amount){
1219       /*This task has failed and is rescheduled. Reset the flops_amount*/
1220       task->flops_amount = xbt_new0(double, 1);
1221       task->flops_amount[0] = task->remains;
1222     }
1223     SD_task_do_schedule(task);
1224     break;
1225   default:
1226     xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1227             SD_task_get_name(task));
1228   }
1229   if (task->kind == SD_TASK_COMM_E2E) {
1230     XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1231           SD_task_get_name(task),
1232           sg_host_get_name(task->host_list[0]),
1233           sg_host_get_name(task->host_list[1]),
1234           task->bytes_amount[2]);
1235
1236   }
1237
1238   /* Iterate over all children and parents being COMM_E2E to say where I am
1239    * located (and start them if runnable) */
1240   if (task->kind == SD_TASK_COMP_SEQ) {
1241     XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1242           SD_task_get_name(task),
1243           sg_host_get_name(task->host_list[0]),
1244           task->flops_amount[0]);
1245
1246     xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1247       SD_task_t before = dep->src;
1248       if (before->kind == SD_TASK_COMM_E2E) {
1249         before->host_list[1] = task->host_list[0];
1250
1251         if (before->host_list[0] &&
1252             (SD_task_get_state(before)< SD_SCHEDULED)) {
1253           SD_task_do_schedule(before);
1254           XBT_VERB
1255               ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1256                SD_task_get_name(before),
1257                sg_host_get_name(before->host_list[0]),
1258                sg_host_get_name(before->host_list[1]),
1259                before->bytes_amount[2]);
1260         }
1261       }
1262     }
1263     xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1264       SD_task_t after = dep->dst;
1265       if (after->kind == SD_TASK_COMM_E2E) {
1266         after->host_list[0] = task->host_list[0];
1267         if (after->host_list[1]
1268             && (SD_task_get_state(after)< SD_SCHEDULED)) {
1269           SD_task_do_schedule(after);
1270           XBT_VERB
1271               ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1272                SD_task_get_name(after),
1273                sg_host_get_name(after->host_list[0]),
1274                sg_host_get_name(after->host_list[1]),
1275                after->bytes_amount[2]);
1276
1277         }
1278       }
1279     }
1280   }
1281   /* Iterate over all children and parents being MXN_1D_BLOCK to say where I am
1282    * located (and start them if runnable) */
1283   if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1284     XBT_VERB("Schedule computation task %s on %d workstations. %.f flops"
1285              " will be distributed following Amdahl's Law",
1286           SD_task_get_name(task), task->host_count,
1287           task->flops_amount[0]);
1288     xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1289       SD_task_t before = dep->src;
1290       if (before->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1291         if (!before->host_list){
1292           XBT_VERB("Sender side of Task %s is not scheduled yet",
1293              SD_task_get_name(before));
1294           before->host_list = xbt_new0(sg_host_t, count);
1295           before->host_count = count;
1296           XBT_VERB("Fill the workstation list with list of Task '%s'",
1297             SD_task_get_name(task));
1298           for (i=0;i<count;i++)
1299             before->host_list[i] = task->host_list[i];
1300         } else {
1301           XBT_VERB("Build communication matrix for task '%s'",
1302              SD_task_get_name(before));
1303           int src_nb, dst_nb;
1304           double src_start, src_end, dst_start, dst_end;
1305           src_nb = before->host_count;
1306           dst_nb = count;
1307           before->host_list = (sg_host_t*) xbt_realloc(
1308              before->host_list,
1309              (before->host_count+count)*sizeof(sg_host_t));
1310           for(i=0; i<count; i++)
1311             before->host_list[before->host_count+i] =
1312                task->host_list[i];
1313
1314           before->host_count += count;
1315           xbt_free(before->flops_amount);
1316           xbt_free(before->bytes_amount);
1317           before->flops_amount = xbt_new0(double,
1318                                                 before->host_count);
1319           before->bytes_amount = xbt_new0(double,
1320                                                   before->host_count*
1321                                                   before->host_count);
1322
1323           for(i=0;i<src_nb;i++){
1324             src_start = i*before->amount/src_nb;
1325             src_end = src_start + before->amount/src_nb;
1326             for(j=0; j<dst_nb; j++){
1327               dst_start = j*before->amount/dst_nb;
1328               dst_end = dst_start + before->amount/dst_nb;
1329               XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)",
1330                   sg_host_get_name(before->host_list[i]),
1331                   sg_host_get_name(before->host_list[src_nb+j]),
1332                   src_start, src_end, dst_start, dst_end);
1333               if ((src_end <= dst_start) || (dst_end <= src_start)) {
1334                 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1335               } else {
1336                 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1337                   MIN(src_end, dst_end) - MAX(src_start, dst_start);
1338               }
1339               XBT_VERB("==> %.2f",
1340                  before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1341             }
1342           }
1343
1344           if (SD_task_get_state(before)< SD_SCHEDULED) {
1345             SD_task_do_schedule(before);
1346             XBT_VERB
1347               ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1348                   SD_task_get_name(before),before->amount, src_nb, dst_nb);
1349             }
1350         }
1351       }
1352     }
1353     xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1354       SD_task_t after = dep->dst;
1355       if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1356         if (!after->host_list){
1357           XBT_VERB("Receiver side of Task '%s' is not scheduled yet",
1358               SD_task_get_name(after));
1359           after->host_list = xbt_new0(sg_host_t, count);
1360           after->host_count = count;
1361           XBT_VERB("Fill the workstation list with list of Task '%s'",
1362             SD_task_get_name(task));
1363           for (i=0;i<count;i++)
1364             after->host_list[i] = task->host_list[i];
1365         } else {
1366           int src_nb, dst_nb;
1367           double src_start, src_end, dst_start, dst_end;
1368           src_nb = count;
1369           dst_nb = after->host_count;
1370           after->host_list = (sg_host_t*) xbt_realloc(
1371             after->host_list,
1372             (after->host_count+count)*sizeof(sg_host_t));
1373           for(i=after->host_count - 1; i>=0; i--)
1374             after->host_list[count+i] = after->host_list[i];
1375           for(i=0; i<count; i++)
1376             after->host_list[i] = task->host_list[i];
1377
1378           after->host_count += count;
1379
1380           xbt_free(after->flops_amount);
1381           xbt_free(after->bytes_amount);
1382
1383           after->flops_amount = xbt_new0(double, after->host_count);
1384           after->bytes_amount = xbt_new0(double,
1385                                                  after->host_count*
1386                                                  after->host_count);
1387
1388           for(i=0;i<src_nb;i++){
1389             src_start = i*after->amount/src_nb;
1390             src_end = src_start + after->amount/src_nb;
1391             for(j=0; j<dst_nb; j++){
1392               dst_start = j*after->amount/dst_nb;
1393               dst_end = dst_start + after->amount/dst_nb;
1394               XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)",
1395                   i, j, src_start, src_end, dst_start, dst_end);
1396               if ((src_end <= dst_start) || (dst_end <= src_start)) {
1397                 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1398               } else {
1399                 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1400                    MIN(src_end, dst_end)- MAX(src_start, dst_start);
1401               }
1402               XBT_VERB("==> %.2f",
1403                  after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1404             }
1405           }
1406
1407           if (SD_task_get_state(after)< SD_SCHEDULED) {
1408             SD_task_do_schedule(after);
1409             XBT_VERB
1410             ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1411               SD_task_get_name(after),after->amount, src_nb, dst_nb);
1412           }
1413          }
1414       }
1415     }
1416   }
1417 }
1418
1419 /** @brief autoschedule a task on a list of workstations
1420  *
1421  * This function is very similar to SD_task_schedulev(),
1422  * but takes the list of workstations to schedule onto as separate parameters.
1423  * It builds a proper vector of workstations and then call SD_task_schedulev()
1424  */
1425 void SD_task_schedulel(SD_task_t task, int count, ...)
1426 {
1427   va_list ap;
1428   sg_host_t *list = xbt_new(sg_host_t, count);
1429   int i;
1430   va_start(ap, count);
1431   for (i = 0; i < count; i++) {
1432     list[i] = va_arg(ap, sg_host_t);
1433   }
1434   va_end(ap);
1435   SD_task_schedulev(task, count, list);
1436   free(list);
1437 }