1 /* Copyright (c) 2006-2016. The SimGrid Team.
2 * All rights reserved. */
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. */
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"
15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
16 "Logging specific to SimDag (task)");
18 static void __SD_task_remove_dependencies(SD_task_t task);
19 static void __SD_task_destroy_scheduling_data(SD_task_t task);
21 void* SD_task_new_f(void)
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);
30 void SD_task_recycle_f(void *t)
32 SD_task_t task = (SD_task_t) t;
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);
41 task->start_time = -1.0;
42 task->finish_time = -1.0;
43 task->surf_action = NULL;
44 task->watch_points = 0;
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;
52 /* scheduling parameters */
53 task->workstation_nb = 0;
54 task->workstation_list = NULL;
55 task->flops_amount = NULL;
56 task->bytes_amount = NULL;
60 void SD_task_free_f(void *t)
62 SD_task_t task = (SD_task_t)t;
64 xbt_dynar_free(&task->tasks_before);
65 xbt_dynar_free(&task->tasks_after);
70 * \brief Creates a new task.
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()
78 SD_task_t SD_task_create(const char *name, void *data, double amount)
80 SD_task_t task = (SD_task_t)xbt_mallocator_get(sd_global->task_mallocator);
82 /* general information */
83 task->data = data; /* user data */
84 task->name = xbt_strdup(name);
85 task->amount = amount;
86 task->remains = amount;
88 sd_global->task_number++;
93 static XBT_INLINE SD_task_t SD_task_create_sized(const char *name,
94 void *data, double amount,
97 SD_task_t task = SD_task_create(name, data, amount);
98 task->bytes_amount = xbt_new0(double, ws_count * ws_count);
99 task->flops_amount = xbt_new0(double, ws_count);
100 task->workstation_nb = ws_count;
101 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
105 /** @brief create a end-to-end communication task that can then be auto-scheduled
107 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
108 * allows to specify the task costs at creation, and decouple them from the
109 * scheduling process where you just specify which resource should deliver the
112 * A end-to-end communication must be scheduled on 2 hosts, and the amount
113 * specified at creation is sent from hosts[0] to hosts[1].
115 SD_task_t SD_task_create_comm_e2e(const char *name, void *data,
118 SD_task_t res = SD_task_create_sized(name, data, amount, 2);
119 res->bytes_amount[2] = amount;
120 res->kind = SD_TASK_COMM_E2E;
125 /** @brief create a sequential computation task that can then be auto-scheduled
127 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
128 * allows to specify the task costs at creation, and decouple them from the
129 * scheduling process where you just specify which resource should deliver the
132 * A sequential computation must be scheduled on 1 host, and the amount
133 * specified at creation to be run on hosts[0].
135 * \param name the name of the task (can be \c NULL)
136 * \param data the user data you want to associate with the task (can be \c NULL)
137 * \param flops_amount amount of compute work to be done by the task
138 * \return the new SD_TASK_COMP_SEQ typed task
140 SD_task_t SD_task_create_comp_seq(const char *name, void *data,
143 SD_task_t res = SD_task_create_sized(name, data, flops_amount, 1);
144 res->flops_amount[0] = flops_amount;
145 res->kind = SD_TASK_COMP_SEQ;
150 /** @brief create a parallel computation task that can then be auto-scheduled
152 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
153 * allows to specify the task costs at creation, and decouple them from the
154 * scheduling process where you just specify which resource should deliver the
157 * A parallel computation can be scheduled on any number of host.
158 * The underlying speedup model is Amdahl's law.
159 * To be auto-scheduled, \see SD_task_distribute_comp_amdahl has to be called
161 * \param name the name of the task (can be \c NULL)
162 * \param data the user data you want to associate with the task (can be \c NULL)
163 * \param flops_amount amount of compute work to be done by the task
164 * \param alpha purely serial fraction of the work to be done (in [0.;1.[)
165 * \return the new task
167 SD_task_t SD_task_create_comp_par_amdahl(const char *name, void *data,
168 double flops_amount, double alpha)
170 xbt_assert(alpha < 1. && alpha >= 0.,
171 "Invalid parameter: alpha must be in [0.;1.[");
173 SD_task_t res = SD_task_create(name, data, flops_amount);
175 res->kind = SD_TASK_COMP_PAR_AMDAHL;
180 /** @brief create a complex data redistribution task that can then be
183 * Auto-scheduling mean that the task can be used with SD_task_schedulev().
184 * This allows to specify the task costs at creation, and decouple them from
185 * the scheduling process where you just specify which resource should
188 * A data redistribution can be scheduled on any number of host.
189 * The assumed distribution is a 1D block distribution. Each host owns the same
190 * share of the \see amount.
191 * To be auto-scheduled, \see SD_task_distribute_comm_mxn_1d_block has to be
193 * \param name the name of the task (can be \c NULL)
194 * \param data the user data you want to associate with the task (can be
196 * \param amount amount of data to redistribute by the task
197 * \return the new task
199 SD_task_t SD_task_create_comm_par_mxn_1d_block(const char *name, void *data,
202 SD_task_t res = SD_task_create(name, data, amount);
203 res->workstation_list=NULL;
204 res->kind = SD_TASK_COMM_PAR_MXN_1D_BLOCK;
210 * \brief Destroys a task.
212 * The user data (if any) should have been destroyed first.
214 * \param task the task you want to destroy
215 * \see SD_task_create()
217 void SD_task_destroy(SD_task_t task)
220 XBT_DEBUG("Destroying task %s...", SD_task_get_name(task));
222 __SD_task_remove_dependencies(task);
223 /* if the task was scheduled or runnable we have to free the scheduling parameters */
224 if (__SD_task_is_scheduled_or_runnable(task))
225 __SD_task_destroy_scheduling_data(task);
227 idx = xbt_dynar_search_or_negative(sd_global->return_set, &task);
229 xbt_dynar_remove_at(sd_global->return_set, idx, NULL);
232 xbt_free(task->name);
234 if (task->surf_action != NULL)
235 task->surf_action->unref();
237 xbt_free(task->workstation_list);
238 xbt_free(task->bytes_amount);
239 xbt_free(task->flops_amount);
241 xbt_mallocator_release(sd_global->task_mallocator,task);
242 sd_global->task_number--;
244 XBT_DEBUG("Task destroyed.");
248 * \brief Returns the user data of a task
251 * \return the user data associated with this task (can be \c NULL)
252 * \see SD_task_set_data()
254 void *SD_task_get_data(SD_task_t task)
260 * \brief Sets the user data of a task
262 * The new data can be \c NULL. The old data should have been freed first
263 * if it was not \c NULL.
266 * \param data the new data you want to associate with this task
267 * \see SD_task_get_data()
269 void SD_task_set_data(SD_task_t task, void *data)
275 * \brief Sets the rate of a task
277 * This will change the network bandwidth a task can use. This rate
278 * cannot be dynamically changed. Once the task has started, this call
279 * is ineffective. This rate depends on both the nominal bandwidth on
280 * the route onto which the task is scheduled (\see
281 * SD_task_get_current_bandwidth) and the amount of data to transfer.
283 * To divide the nominal bandwidth by 2, the rate then has to be :
284 * rate = bandwidth/(2*amount)
286 * \param task a \see SD_TASK_COMM_E2E task (end-to-end communication)
287 * \param rate the new rate you want to associate with this task.
289 void SD_task_set_rate(SD_task_t task, double rate)
291 xbt_assert(task->kind == SD_TASK_COMM_E2E,
292 "The rate can be modified for end-to-end communications only.");
293 if(task->start_time<0) {
296 XBT_WARN("Task %p has started. Changing rate is ineffective.", task);
301 * \brief Returns the state of a task
304 * \return the current \ref e_SD_task_state_t "state" of this task:
305 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
306 * \see e_SD_task_state_t
308 e_SD_task_state_t SD_task_get_state(SD_task_t task)
313 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
315 void SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
319 case SD_NOT_SCHEDULED:
321 if (SD_task_get_state(task) == SD_FAILED){
322 xbt_dynar_remove_at(sd_global->completed_task_set,
323 xbt_dynar_search(sd_global->completed_task_set, &task), NULL);
324 xbt_dynar_push(sd_global->initial_task_set,&task);
328 if (SD_task_get_state(task) == SD_RUNNABLE){
329 xbt_dynar_remove_at(sd_global->executable_task_set,
330 xbt_dynar_search(sd_global->executable_task_set, &task), NULL);
331 xbt_dynar_push(sd_global->initial_task_set,&task);
335 idx = xbt_dynar_search_or_negative(sd_global->initial_task_set, &task);
337 xbt_dynar_remove_at(sd_global->initial_task_set, idx, NULL);
338 xbt_dynar_push(sd_global->executable_task_set,&task);
342 xbt_dynar_remove_at(sd_global->executable_task_set,
343 xbt_dynar_search(sd_global->executable_task_set, &task), NULL);
346 xbt_dynar_push(sd_global->completed_task_set,&task);
347 task->finish_time = task->surf_action->getFinishTime();
350 jedule_log_sd_event(task);
354 xbt_dynar_push(sd_global->completed_task_set,&task);
357 xbt_die( "Invalid state");
360 task->state = new_state;
362 if (task->watch_points & new_state) {
363 XBT_VERB("Watch point reached with task '%s'!", SD_task_get_name(task));
364 sd_global->watch_point_reached = 1;
365 SD_task_unwatch(task, new_state); /* remove the watch point */
370 * \brief Returns the name of a task
373 * \return the name of this task (can be \c NULL)
375 const char *SD_task_get_name(SD_task_t task)
380 /** @brief Allows to change the name of a task */
381 void SD_task_set_name(SD_task_t task, const char *name)
383 xbt_free(task->name);
384 task->name = xbt_strdup(name);
387 /** @brief Returns the dynar of the parents of a task
390 * \return a newly allocated dynar comprising the parents of this task
393 xbt_dynar_t SD_task_get_parents(SD_task_t task)
399 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
400 xbt_dynar_foreach(task->tasks_before, i, dep) {
401 xbt_dynar_push(parents, &(dep->src));
406 /** @brief Returns the dynar of the parents of a task
409 * \return a newly allocated dynar comprising the parents of this task
411 xbt_dynar_t SD_task_get_children(SD_task_t task)
414 xbt_dynar_t children;
417 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
418 xbt_dynar_foreach(task->tasks_after, i, dep) {
419 xbt_dynar_push(children, &(dep->dst));
425 * \brief Returns the amount of workstations involved in a task
427 * Only call this on already scheduled tasks!
430 int SD_task_get_workstation_count(SD_task_t task)
432 return task->workstation_nb;
436 * \brief Returns the list of workstations involved in a task
438 * Only call this on already scheduled tasks!
441 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
443 return task->workstation_list;
447 * \brief Returns the total amount of work contained in a task
450 * \return the total amount of work (computation or data transfer) for this task
451 * \see SD_task_get_remaining_amount()
453 double SD_task_get_amount(SD_task_t task)
459 * \brief Sets the total amount of work of a task
460 * For sequential typed tasks (COMP_SEQ and COMM_E2E), it also sets the
461 * appropriate values in the flops_amount and bytes_amount arrays
462 * respectively. Nothing more than modifying task->amount is done for paralle
463 * typed tasks (COMP_PAR_AMDAHL and COMM_PAR_MXN_1D_BLOCK) as the distribution
464 * of the amount of work is done at scheduling time.
467 * \param amount the new amount of work to execute
469 void SD_task_set_amount(SD_task_t task, double amount)
471 task->amount = amount;
472 if (task->kind == SD_TASK_COMP_SEQ)
473 task->flops_amount[0] = amount;
474 if (task->kind == SD_TASK_COMM_E2E)
475 task->bytes_amount[2] = amount;
479 * \brief Returns the alpha parameter of a SD_TASK_COMP_PAR_AMDAHL task
481 * \param task a parallel task assuming Amdahl's law as speedup model
482 * \return the alpha parameter (serial part of a task in percent) for this task
484 double SD_task_get_alpha(SD_task_t task)
486 xbt_assert(SD_task_get_kind(task) == SD_TASK_COMP_PAR_AMDAHL,
487 "Alpha parameter is not defined for this kink of task");
493 * \brief Returns the remaining amount work to do till the completion of a task
496 * \return the remaining amount of work (computation or data transfer) of this task
497 * \see SD_task_get_amount()
499 double SD_task_get_remaining_amount(SD_task_t task)
501 if (task->surf_action)
502 return surf_action_get_remains(task->surf_action);
504 return task->remains;
507 e_SD_task_kind_t SD_task_get_kind(SD_task_t task)
512 /** @brief Displays debugging informations about a task */
513 void SD_task_dump(SD_task_t task)
515 unsigned int counter;
516 SD_dependency_t dependency;
519 XBT_INFO("Displaying task %s", SD_task_get_name(task));
520 statename = bprintf("%s%s%s%s%s%s%s",
521 (task->state == SD_NOT_SCHEDULED ? " not scheduled" :
523 (task->state == SD_SCHEDULABLE ? " schedulable" : ""),
524 (task->state == SD_SCHEDULED ? " scheduled" : ""),
525 (task->state == SD_RUNNABLE ? " runnable" :
527 (task->state == SD_RUNNING ? " running" : ""),
528 (task->state == SD_DONE ? " done" : ""),
529 (task->state == SD_FAILED ? " failed" : ""));
530 XBT_INFO(" - state:%s", statename);
533 if (task->kind != 0) {
534 switch (task->kind) {
535 case SD_TASK_COMM_E2E:
536 XBT_INFO(" - kind: end-to-end communication");
538 case SD_TASK_COMP_SEQ:
539 XBT_INFO(" - kind: sequential computation");
541 case SD_TASK_COMP_PAR_AMDAHL:
542 XBT_INFO(" - kind: parallel computation following Amdahl's law");
544 case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
545 XBT_INFO(" - kind: MxN data redistribution assuming 1D block distribution");
548 XBT_INFO(" - (unknown kind %d)", task->kind);
553 XBT_INFO(" - tracing category: %s", task->category);
555 XBT_INFO(" - amount: %.0f", SD_task_get_amount(task));
556 if (task->kind == SD_TASK_COMP_PAR_AMDAHL)
557 XBT_INFO(" - alpha: %.2f", task->alpha);
558 XBT_INFO(" - Dependencies to satisfy: %d", task->unsatisfied_dependencies);
559 if (!xbt_dynar_is_empty(task->tasks_before)) {
560 XBT_INFO(" - pre-dependencies:");
561 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
562 XBT_INFO(" %s", SD_task_get_name(dependency->src));
565 if (!xbt_dynar_is_empty(task->tasks_after)) {
566 XBT_INFO(" - post-dependencies:");
567 xbt_dynar_foreach(task->tasks_after, counter, dependency) {
568 XBT_INFO(" %s", SD_task_get_name(dependency->dst));
573 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
574 void SD_task_dotty(SD_task_t task, void *out)
576 unsigned int counter;
577 SD_dependency_t dependency;
578 FILE *fout = (FILE*)out;
579 fprintf(fout, " T%p [label=\"%.20s\"", task, task->name);
580 switch (task->kind) {
581 case SD_TASK_COMM_E2E:
582 case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
583 fprintf(fout, ", shape=box");
585 case SD_TASK_COMP_SEQ:
586 case SD_TASK_COMP_PAR_AMDAHL:
587 fprintf(fout, ", shape=circle");
590 xbt_die("Unknown task type!");
592 fprintf(fout, "];\n");
593 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
594 fprintf(fout, " T%p -> T%p;\n", dependency->src, dependency->dst);
598 /* Destroys a dependency between two tasks.
600 static void __SD_task_dependency_destroy(void *dependency)
602 xbt_free(((SD_dependency_t)dependency)->name);
603 xbt_free(dependency);
607 * \brief Adds a dependency between two tasks
609 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
610 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
612 * \param name the name of the new dependency (can be \c NULL)
613 * \param data the user data you want to associate with this dependency (can be \c NULL)
614 * \param src the task which must be executed first
615 * \param dst the task you want to make depend on \a src
616 * \see SD_task_dependency_remove()
618 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
622 unsigned long length;
625 SD_dependency_t dependency;
626 e_SD_task_state_t state;
628 dynar = src->tasks_after;
629 length = xbt_dynar_length(dynar);
633 "Cannot add a dependency between task '%s' and itself",
634 SD_task_get_name(src));
636 state = SD_task_get_state(src);
637 if (state != SD_NOT_SCHEDULED && state != SD_SCHEDULABLE &&
638 state != SD_RUNNING && !__SD_task_is_scheduled_or_runnable(src))
640 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED,"
641 " SD_RUNNABLE or SD_RUNNING", SD_task_get_name(src));
643 state = SD_task_get_state(dst);
644 if (state != SD_NOT_SCHEDULED && state != SD_SCHEDULABLE &&
645 !__SD_task_is_scheduled_or_runnable(dst))
647 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED,"
648 "or SD_RUNNABLE", SD_task_get_name(dst));
650 XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s",
651 SD_task_get_name(src), SD_task_get_name(dst));
652 for (i = 0; i < length && !found; i++) {
653 xbt_dynar_get_cpy(dynar, i, &dependency);
654 found = (dependency->dst == dst);
655 XBT_DEBUG("Dependency %lu: dependency->dst = %s", i,
656 SD_task_get_name(dependency->dst));
661 "A dependency already exists between task '%s' and task '%s'",
662 SD_task_get_name(src), SD_task_get_name(dst));
664 dependency = xbt_new(s_SD_dependency_t, 1);
666 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
667 dependency->data = data;
668 dependency->src = src;
669 dependency->dst = dst;
671 /* src must be executed before dst */
672 xbt_dynar_push(src->tasks_after, &dependency);
673 xbt_dynar_push(dst->tasks_before, &dependency);
675 dst->unsatisfied_dependencies++;
678 /* if the task was runnable, then dst->tasks_before is not empty anymore,
679 so we must go back to state SD_SCHEDULED */
680 if (SD_task_get_state(dst) == SD_RUNNABLE) {
682 ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
683 SD_task_get_name(dst));
684 SD_task_set_state(dst, SD_SCHEDULED);
688 * \brief Returns the name given as input when dependency has been created..
691 * \param dst a task depending on \a src
694 const char *SD_task_dependency_get_name(SD_task_t src, SD_task_t dst){
696 SD_dependency_t dependency;
698 xbt_dynar_foreach(src->tasks_after, i, dependency){
699 if (dependency->dst == dst)
700 return dependency->name;
706 * \brief Indicates whether there is a dependency between two tasks.
709 * \param dst a task depending on \a src
711 * If src is NULL, checks whether dst has any pre-dependency.
712 * If dst is NULL, checks whether src has any post-dependency.
714 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
716 unsigned int counter;
717 SD_dependency_t dependency;
719 xbt_assert(src != NULL
721 "Invalid parameter: both src and dst are NULL");
725 xbt_dynar_foreach(src->tasks_after, counter, dependency) {
726 if (dependency->dst == dst)
730 return xbt_dynar_length(src->tasks_after);
733 return xbt_dynar_length(dst->tasks_before);
739 * \brief Remove a dependency between two tasks
742 * \param dst a task depending on \a src
743 * \see SD_task_dependency_add()
745 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
749 unsigned long length;
752 SD_dependency_t dependency;
754 /* remove the dependency from src->tasks_after */
755 dynar = src->tasks_after;
756 length = xbt_dynar_length(dynar);
758 for (i = 0; i < length && !found; i++) {
759 xbt_dynar_get_cpy(dynar, i, &dependency);
760 if (dependency->dst == dst) {
761 xbt_dynar_remove_at(dynar, i, NULL);
767 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
768 SD_task_get_name(src), SD_task_get_name(dst),
769 SD_task_get_name(dst), SD_task_get_name(src));
771 /* remove the dependency from dst->tasks_before */
772 dynar = dst->tasks_before;
773 length = xbt_dynar_length(dynar);
776 for (i = 0; i < length && !found; i++) {
777 xbt_dynar_get_cpy(dynar, i, &dependency);
778 if (dependency->src == src) {
779 xbt_dynar_remove_at(dynar, i, NULL);
780 __SD_task_dependency_destroy(dependency);
781 dst->unsatisfied_dependencies--;
786 /* should never happen... */
788 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
789 SD_task_get_name(dst), SD_task_get_name(src),
790 SD_task_get_name(src), SD_task_get_name(dst));
792 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
794 if (dst->unsatisfied_dependencies == 0) {
795 if (SD_task_get_state(dst) == SD_SCHEDULED)
796 SD_task_set_state(dst, SD_RUNNABLE);
798 SD_task_set_state(dst, SD_SCHEDULABLE);
801 if (dst->is_not_ready == 0)
802 SD_task_set_state(dst, SD_SCHEDULABLE);
804 /* __SD_print_dependencies(src);
805 __SD_print_dependencies(dst); */
809 * \brief Returns the user data associated with a dependency between two tasks
812 * \param dst a task depending on \a src
813 * \return the user data associated with this dependency (can be \c NULL)
814 * \see SD_task_dependency_add()
816 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
820 unsigned long length;
823 SD_dependency_t dependency;
825 dynar = src->tasks_after;
826 length = xbt_dynar_length(dynar);
828 for (i = 0; i < length && !found; i++) {
829 xbt_dynar_get_cpy(dynar, i, &dependency);
830 found = (dependency->dst == dst);
833 THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'",
834 SD_task_get_name(src), SD_task_get_name(dst));
835 return dependency->data;
839 * \brief Adds a watch point to a task
841 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
842 * task becomes the one given in argument. The
843 * watch point is then automatically removed.
846 * \param state the \ref e_SD_task_state_t "state" you want to watch
847 * (cannot be #SD_NOT_SCHEDULED)
848 * \see SD_task_unwatch()
850 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
852 if (state & SD_NOT_SCHEDULED)
854 "Cannot add a watch point for state SD_NOT_SCHEDULED");
856 task->watch_points = task->watch_points | state;
860 * \brief Removes a watch point from a task
863 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
864 * \see SD_task_watch()
866 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
868 xbt_assert(state != SD_NOT_SCHEDULED,
869 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
871 task->watch_points = task->watch_points & ~state;
875 * \brief Returns an approximative estimation of the execution time of a task.
877 * The estimation is very approximative because the value returned is the time
878 * the task would take if it was executed now and if it was the only task.
880 * \param task the task to evaluate
881 * \param workstation_nb number of workstations on which the task would be executed
882 * \param workstation_list the workstations on which the task would be executed
883 * \param flops_amount computation amount for each workstation
884 * \param bytes_amount communication amount between each pair of workstations
887 double SD_task_get_execution_time(SD_task_t task,
889 const SD_workstation_t *
891 const double *flops_amount,
892 const double *bytes_amount)
894 double time, max_time = 0.0;
896 xbt_assert(workstation_nb > 0, "Invalid parameter");
898 /* the task execution time is the maximum execution time of the parallel tasks */
900 for (i = 0; i < workstation_nb; i++) {
902 if (flops_amount != NULL)
904 SD_workstation_get_computation_time(workstation_list[i],
907 if (bytes_amount != NULL)
908 for (j = 0; j < workstation_nb; j++) {
910 SD_route_get_communication_time(workstation_list[i],
917 if (time > max_time) {
924 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
926 if (SD_task_get_state(task) > SD_SCHEDULABLE)
927 THROWF(arg_error, 0, "Task '%s' has already been scheduled",
928 SD_task_get_name(task));
930 /* update the task state */
931 if (task->unsatisfied_dependencies == 0)
932 SD_task_set_state(task, SD_RUNNABLE);
934 SD_task_set_state(task, SD_SCHEDULED);
938 * \brief Schedules a task
940 * The task state must be #SD_NOT_SCHEDULED.
941 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
942 * i.e. when its dependencies are satisfied.
944 * \param task the task you want to schedule
945 * \param workstation_count number of workstations on which the task will be executed
946 * \param workstation_list the workstations on which the task will be executed
947 * \param flops_amount computation amount for each workstation
948 * \param bytes_amount communication amount between each pair of workstations
949 * \param rate task execution speed rate
950 * \see SD_task_unschedule()
952 void SD_task_schedule(SD_task_t task, int workstation_count,
953 const SD_workstation_t * workstation_list,
954 const double *flops_amount,
955 const double *bytes_amount, double rate)
957 xbt_assert(workstation_count > 0, "workstation_nb must be positive");
959 task->workstation_nb = workstation_count;
963 task->flops_amount = (double*)xbt_realloc(task->flops_amount,
964 sizeof(double) * workstation_count);
965 memcpy(task->flops_amount, flops_amount,
966 sizeof(double) * workstation_count);
968 xbt_free(task->flops_amount);
969 task->flops_amount = NULL;
972 int communication_nb = workstation_count * workstation_count;
974 task->bytes_amount = (double*)xbt_realloc(task->bytes_amount,
975 sizeof(double) * communication_nb);
976 memcpy(task->bytes_amount, bytes_amount,
977 sizeof(double) * communication_nb);
979 xbt_free(task->bytes_amount);
980 task->bytes_amount = NULL;
983 task->workstation_list = (SD_workstation_t*)
984 xbt_realloc(task->workstation_list,
985 sizeof(SD_workstation_t) * workstation_count);
986 memcpy(task->workstation_list, workstation_list,
987 sizeof(SD_workstation_t) * workstation_count);
989 SD_task_do_schedule(task);
993 * \brief Unschedules a task
995 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
996 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
997 * Call SD_task_schedule() to schedule it again.
999 * \param task the task you want to unschedule
1000 * \see SD_task_schedule()
1002 void SD_task_unschedule(SD_task_t task)
1004 if (task->state != SD_SCHEDULED &&
1005 task->state != SD_RUNNABLE &&
1006 task->state != SD_RUNNING &&
1007 task->state != SD_FAILED)
1008 THROWF(arg_error, 0,
1009 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
1010 SD_task_get_name(task));
1012 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
1013 && ((task->kind == SD_TASK_COMP_PAR_AMDAHL) ||
1014 (task->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK))) { /* Don't free scheduling data for typed tasks */
1015 __SD_task_destroy_scheduling_data(task);
1016 xbt_free(task->workstation_list);
1017 task->workstation_list=NULL;
1018 task->workstation_nb = 0;
1021 if (SD_task_get_state(task) == SD_RUNNING)
1022 /* the task should become SD_FAILED */
1023 task->surf_action->cancel();
1025 if (task->unsatisfied_dependencies == 0)
1026 SD_task_set_state(task, SD_SCHEDULABLE);
1028 SD_task_set_state(task, SD_NOT_SCHEDULED);
1030 task->remains = task->amount;
1031 task->start_time = -1.0;
1034 /* Destroys the data memorized by SD_task_schedule.
1035 * Task state must be SD_SCHEDULED or SD_RUNNABLE.
1037 static void __SD_task_destroy_scheduling_data(SD_task_t task)
1039 if (!__SD_task_is_scheduled_or_runnable(task))
1040 THROWF(arg_error, 0,
1041 "Task '%s' must be SD_SCHEDULED or SD_RUNNABLE",
1042 SD_task_get_name(task));
1044 xbt_free(task->flops_amount);
1045 xbt_free(task->bytes_amount);
1046 task->flops_amount = task->bytes_amount = NULL;
1049 /* Runs a task. This function is directly called by __SD_task_try_to_run if
1050 * the task doesn't have to wait in FIFOs. Otherwise, it is called by
1051 * __SD_task_just_done when the task gets out of its FIFOs.
1053 void SD_task_run(SD_task_t task)
1059 xbt_assert(SD_task_get_state(task) == SD_RUNNABLE,
1060 "Task '%s' is not runnable! Task state: %d",
1061 SD_task_get_name(task), (int)SD_task_get_state(task));
1062 xbt_assert(task->workstation_list != NULL,
1063 "Task '%s': workstation_list is NULL!",
1064 SD_task_get_name(task));
1066 XBT_DEBUG("Running task '%s'", SD_task_get_name(task));
1068 /* Copy the elements of the task into the action */
1069 int host_nb = task->workstation_nb;
1070 hosts = xbt_new(sg_host_t, host_nb);
1072 for (i = 0; i < host_nb; i++)
1073 hosts[i] = task->workstation_list[i];
1075 double *flops_amount = xbt_new0(double, host_nb);
1076 double *bytes_amount = xbt_new0(double, host_nb * host_nb);
1078 if(task->flops_amount)
1079 memcpy(flops_amount, task->flops_amount, sizeof(double) * host_nb);
1080 if(task->bytes_amount)
1081 memcpy(bytes_amount, task->bytes_amount,
1082 sizeof(double) * host_nb * host_nb);
1084 task->surf_action = surf_host_model->executeParallelTask(
1085 host_nb, hosts, flops_amount, bytes_amount, task->rate);
1087 task->surf_action->setData(task);
1089 XBT_DEBUG("surf_action = %p", task->surf_action);
1092 TRACE_surf_action(task->surf_action, task->category);
1094 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
1095 SD_task_set_state(task, SD_RUNNING);
1096 xbt_assert(SD_task_get_state(task) == SD_RUNNING,
1097 "Bad state of task '%s': %d",
1098 SD_task_get_name(task), (int)SD_task_get_state(task));
1103 * Remove all dependencies associated with a task. This function is called
1104 * when the task is destroyed.
1106 static void __SD_task_remove_dependencies(SD_task_t task)
1108 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1109 because each one is stored twice */
1110 SD_dependency_t dependency;
1111 while (!xbt_dynar_is_empty(task->tasks_before)) {
1112 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1113 SD_task_dependency_remove(dependency->src, dependency->dst);
1116 while (!xbt_dynar_is_empty(task->tasks_after)) {
1117 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1118 SD_task_dependency_remove(dependency->src, dependency->dst);
1123 * \brief Returns the start time of a task
1125 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1127 * \param task: a task
1128 * \return the start time of this task
1130 double SD_task_get_start_time(SD_task_t task)
1132 if (task->surf_action)
1133 return task->surf_action->getStartTime();
1135 return task->start_time;
1139 * \brief Returns the finish time of a task
1141 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1142 * If the state is not completed yet, the returned value is an
1143 * estimation of the task finish time. This value can fluctuate
1144 * until the task is completed.
1146 * \param task: a task
1147 * \return the start time of this task
1149 double SD_task_get_finish_time(SD_task_t task)
1151 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1152 return task->surf_action->getFinishTime();
1154 return task->finish_time;
1159 void SD_task_distribute_comp_amdahl(SD_task_t task, int ws_count)
1162 xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1163 "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1164 "Cannot use this function.",
1165 SD_task_get_name(task));
1166 task->flops_amount = xbt_new0(double, ws_count);
1167 task->bytes_amount = xbt_new0(double, ws_count * ws_count);
1168 xbt_free(task->workstation_list);
1169 task->workstation_nb = ws_count;
1170 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1172 for(i=0;i<ws_count;i++){
1173 task->flops_amount[i] =
1174 (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1179 /** @brief Auto-schedules a task.
1181 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1182 * allows to specify the task costs at creation, and decouple them from the
1183 * scheduling process where you just specify which resource should deliver the
1186 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e()
1187 * or SD_task_create_comp_seq(). Check their definitions for the exact semantic
1191 * We should create tasks kind for the following categories:
1192 * - Point to point communication (done)
1193 * - Sequential computation (done)
1194 * - group communication (redistribution, several kinds)
1195 * - parallel tasks with no internal communication (one kind per speedup
1196 * model such as Amdahl)
1197 * - idem+ internal communication. Task type not enough since we cannot store
1198 * comm cost alongside to comp one)
1200 void SD_task_schedulev(SD_task_t task, int count,
1201 const SD_workstation_t * list)
1204 SD_dependency_t dep;
1206 xbt_assert(task->kind != 0,
1207 "Task %s is not typed. Cannot automatically schedule it.",
1208 SD_task_get_name(task));
1209 switch (task->kind) {
1210 case SD_TASK_COMP_PAR_AMDAHL:
1211 SD_task_distribute_comp_amdahl(task, count);
1212 case SD_TASK_COMM_E2E:
1213 case SD_TASK_COMP_SEQ:
1214 xbt_assert(task->workstation_nb == count,
1215 "Got %d locations, but were expecting %d locations",
1216 count,task->workstation_nb);
1217 for (i = 0; i < count; i++)
1218 task->workstation_list[i] = list[i];
1219 if (SD_task_get_kind(task)== SD_TASK_COMP_SEQ && !task->flops_amount){
1220 /*This task has failed and is rescheduled. Reset the flops_amount*/
1221 task->flops_amount = xbt_new0(double, 1);
1222 task->flops_amount[0] = task->remains;
1224 SD_task_do_schedule(task);
1227 xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1228 SD_task_get_name(task));
1230 if (task->kind == SD_TASK_COMM_E2E) {
1231 XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1232 SD_task_get_name(task),
1233 sg_host_get_name(task->workstation_list[0]),
1234 sg_host_get_name(task->workstation_list[1]),
1235 task->bytes_amount[2]);
1239 /* Iterate over all children and parents being COMM_E2E to say where I am
1240 * located (and start them if runnable) */
1241 if (task->kind == SD_TASK_COMP_SEQ) {
1242 XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1243 SD_task_get_name(task),
1244 sg_host_get_name(task->workstation_list[0]),
1245 task->flops_amount[0]);
1247 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1248 SD_task_t before = dep->src;
1249 if (before->kind == SD_TASK_COMM_E2E) {
1250 before->workstation_list[1] = task->workstation_list[0];
1252 if (before->workstation_list[0] &&
1253 (SD_task_get_state(before)< SD_SCHEDULED)) {
1254 SD_task_do_schedule(before);
1256 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1257 SD_task_get_name(before),
1258 sg_host_get_name(before->workstation_list[0]),
1259 sg_host_get_name(before->workstation_list[1]),
1260 before->bytes_amount[2]);
1264 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1265 SD_task_t after = dep->dst;
1266 if (after->kind == SD_TASK_COMM_E2E) {
1267 after->workstation_list[0] = task->workstation_list[0];
1268 if (after->workstation_list[1]
1269 && (SD_task_get_state(after)< SD_SCHEDULED)) {
1270 SD_task_do_schedule(after);
1272 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1273 SD_task_get_name(after),
1274 sg_host_get_name(after->workstation_list[0]),
1275 sg_host_get_name(after->workstation_list[1]),
1276 after->bytes_amount[2]);
1282 /* Iterate over all children and parents being MXN_1D_BLOCK to say where I am
1283 * located (and start them if runnable) */
1284 if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1285 XBT_VERB("Schedule computation task %s on %d workstations. %.f flops"
1286 " will be distributed following Amdahl's Law",
1287 SD_task_get_name(task), task->workstation_nb,
1288 task->flops_amount[0]);
1289 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1290 SD_task_t before = dep->src;
1291 if (before->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1292 if (!before->workstation_list){
1293 XBT_VERB("Sender side of Task %s is not scheduled yet",
1294 SD_task_get_name(before));
1295 before->workstation_list = xbt_new0(SD_workstation_t, count);
1296 before->workstation_nb = count;
1297 XBT_VERB("Fill the workstation list with list of Task '%s'",
1298 SD_task_get_name(task));
1299 for (i=0;i<count;i++)
1300 before->workstation_list[i] = task->workstation_list[i];
1302 XBT_VERB("Build communication matrix for task '%s'",
1303 SD_task_get_name(before));
1305 double src_start, src_end, dst_start, dst_end;
1306 src_nb = before->workstation_nb;
1308 before->workstation_list = (SD_workstation_t*) xbt_realloc(
1309 before->workstation_list,
1310 (before->workstation_nb+count)*sizeof(s_SD_workstation_t));
1311 for(i=0; i<count; i++)
1312 before->workstation_list[before->workstation_nb+i] =
1313 task->workstation_list[i];
1315 before->workstation_nb += count;
1316 xbt_free(before->flops_amount);
1317 xbt_free(before->bytes_amount);
1318 before->flops_amount = xbt_new0(double,
1319 before->workstation_nb);
1320 before->bytes_amount = xbt_new0(double,
1321 before->workstation_nb*
1322 before->workstation_nb);
1324 for(i=0;i<src_nb;i++){
1325 src_start = i*before->amount/src_nb;
1326 src_end = src_start + before->amount/src_nb;
1327 for(j=0; j<dst_nb; j++){
1328 dst_start = j*before->amount/dst_nb;
1329 dst_end = dst_start + before->amount/dst_nb;
1330 XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)",
1331 sg_host_get_name(before->workstation_list[i]),
1332 sg_host_get_name(before->workstation_list[src_nb+j]),
1333 src_start, src_end, dst_start, dst_end);
1334 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1335 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1337 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1338 MIN(src_end, dst_end) - MAX(src_start, dst_start);
1340 XBT_VERB("==> %.2f",
1341 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1345 if (SD_task_get_state(before)< SD_SCHEDULED) {
1346 SD_task_do_schedule(before);
1348 ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1349 SD_task_get_name(before),before->amount, src_nb, dst_nb);
1354 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1355 SD_task_t after = dep->dst;
1356 if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1357 if (!after->workstation_list){
1358 XBT_VERB("Receiver side of Task '%s' is not scheduled yet",
1359 SD_task_get_name(after));
1360 after->workstation_list = xbt_new0(SD_workstation_t, count);
1361 after->workstation_nb = count;
1362 XBT_VERB("Fill the workstation list with list of Task '%s'",
1363 SD_task_get_name(task));
1364 for (i=0;i<count;i++)
1365 after->workstation_list[i] = task->workstation_list[i];
1368 double src_start, src_end, dst_start, dst_end;
1370 dst_nb = after->workstation_nb;
1371 after->workstation_list = (SD_workstation_t*) xbt_realloc(
1372 after->workstation_list,
1373 (after->workstation_nb+count)*sizeof(s_SD_workstation_t));
1374 for(i=after->workstation_nb - 1; i>=0; i--)
1375 after->workstation_list[count+i] = after->workstation_list[i];
1376 for(i=0; i<count; i++)
1377 after->workstation_list[i] = task->workstation_list[i];
1379 after->workstation_nb += count;
1381 xbt_free(after->flops_amount);
1382 xbt_free(after->bytes_amount);
1384 after->flops_amount = xbt_new0(double, after->workstation_nb);
1385 after->bytes_amount = xbt_new0(double,
1386 after->workstation_nb*
1387 after->workstation_nb);
1389 for(i=0;i<src_nb;i++){
1390 src_start = i*after->amount/src_nb;
1391 src_end = src_start + after->amount/src_nb;
1392 for(j=0; j<dst_nb; j++){
1393 dst_start = j*after->amount/dst_nb;
1394 dst_end = dst_start + after->amount/dst_nb;
1395 XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)",
1396 i, j, src_start, src_end, dst_start, dst_end);
1397 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1398 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1400 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1401 MIN(src_end, dst_end)- MAX(src_start, dst_start);
1403 XBT_VERB("==> %.2f",
1404 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1408 if (SD_task_get_state(after)< SD_SCHEDULED) {
1409 SD_task_do_schedule(after);
1411 ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1412 SD_task_get_name(after),after->amount, src_nb, dst_nb);
1420 /** @brief autoschedule a task on a list of workstations
1422 * This function is very similar to SD_task_schedulev(),
1423 * but takes the list of workstations to schedule onto as separate parameters.
1424 * It builds a proper vector of workstations and then call SD_task_schedulev()
1426 void SD_task_schedulel(SD_task_t task, int count, ...)
1429 SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1431 va_start(ap, count);
1432 for (i = 0; i < count; i++) {
1433 list[i] = va_arg(ap, SD_workstation_t);
1436 SD_task_schedulev(task, count, list);