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