src/simdag/sd_task.cpp

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