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++;
90 TRACE_sd_task_create(task);
95 static XBT_INLINE SD_task_t SD_task_create_sized(const char *name,
96 void *data, double amount,
99 SD_task_t task = SD_task_create(name, data, amount);
100 task->bytes_amount = xbt_new0(double, ws_count * ws_count);
101 task->flops_amount = xbt_new0(double, ws_count);
102 task->workstation_nb = ws_count;
103 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
107 /** @brief create a end-to-end communication task that can then be auto-scheduled
109 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
110 * allows to specify the task costs at creation, and decouple them from the
111 * scheduling process where you just specify which resource should deliver the
114 * A end-to-end communication must be scheduled on 2 hosts, and the amount
115 * specified at creation is sent from hosts[0] to hosts[1].
117 SD_task_t SD_task_create_comm_e2e(const char *name, void *data,
120 SD_task_t res = SD_task_create_sized(name, data, amount, 2);
121 res->bytes_amount[2] = amount;
122 res->kind = SD_TASK_COMM_E2E;
124 TRACE_category("COMM_E2E");
125 TRACE_sd_set_task_category(res, "COMM_E2E");
130 /** @brief create a sequential computation task that can then be auto-scheduled
132 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
133 * allows to specify the task costs at creation, and decouple them from the
134 * scheduling process where you just specify which resource should deliver the
137 * A sequential computation must be scheduled on 1 host, and the amount
138 * specified at creation to be run on hosts[0].
140 * \param name the name of the task (can be \c NULL)
141 * \param data the user data you want to associate with the task (can be \c NULL)
142 * \param flops_amount amount of compute work to be done by the task
143 * \return the new SD_TASK_COMP_SEQ typed task
145 SD_task_t SD_task_create_comp_seq(const char *name, void *data,
148 SD_task_t res = SD_task_create_sized(name, data, flops_amount, 1);
149 res->flops_amount[0] = flops_amount;
150 res->kind = SD_TASK_COMP_SEQ;
152 TRACE_category("COMP_SEQ");
153 TRACE_sd_set_task_category(res, "COMP_SEQ");
158 /** @brief create a parallel computation task that can then be auto-scheduled
160 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
161 * allows to specify the task costs at creation, and decouple them from the
162 * scheduling process where you just specify which resource should deliver the
165 * A parallel computation can be scheduled on any number of host.
166 * The underlying speedup model is Amdahl's law.
167 * To be auto-scheduled, \see SD_task_distribute_comp_amdahl has to be called
169 * \param name the name of the task (can be \c NULL)
170 * \param data the user data you want to associate with the task (can be \c NULL)
171 * \param flops_amount amount of compute work to be done by the task
172 * \param alpha purely serial fraction of the work to be done (in [0.;1.[)
173 * \return the new task
175 SD_task_t SD_task_create_comp_par_amdahl(const char *name, void *data,
176 double flops_amount, double alpha)
178 xbt_assert(alpha < 1. && alpha >= 0.,
179 "Invalid parameter: alpha must be in [0.;1.[");
181 SD_task_t res = SD_task_create(name, data, flops_amount);
183 res->kind = SD_TASK_COMP_PAR_AMDAHL;
185 TRACE_category("COMP_PAR_AMDAHL");
186 TRACE_sd_set_task_category(res, "COMP_PAR_AMDAHL");
191 /** @brief create a complex data redistribution task that can then be
194 * Auto-scheduling mean that the task can be used with SD_task_schedulev().
195 * This allows to specify the task costs at creation, and decouple them from
196 * the scheduling process where you just specify which resource should
199 * A data redistribution can be scheduled on any number of host.
200 * The assumed distribution is a 1D block distribution. Each host owns the same
201 * share of the \see amount.
202 * To be auto-scheduled, \see SD_task_distribute_comm_mxn_1d_block has to be
204 * \param name the name of the task (can be \c NULL)
205 * \param data the user data you want to associate with the task (can be
207 * \param amount amount of data to redistribute by the task
208 * \return the new task
210 SD_task_t SD_task_create_comm_par_mxn_1d_block(const char *name, void *data,
213 SD_task_t res = SD_task_create(name, data, amount);
214 res->workstation_list=NULL;
215 res->kind = SD_TASK_COMM_PAR_MXN_1D_BLOCK;
217 TRACE_category("COMM_PAR_MXN_1D_BLOCK");
218 TRACE_sd_set_task_category(res, "COMM_PAR_MXN_1D_BLOCK");
224 * \brief Destroys a task.
226 * The user data (if any) should have been destroyed first.
228 * \param task the task you want to destroy
229 * \see SD_task_create()
231 void SD_task_destroy(SD_task_t task)
234 XBT_DEBUG("Destroying task %s...", SD_task_get_name(task));
236 __SD_task_remove_dependencies(task);
237 /* if the task was scheduled or runnable we have to free the scheduling parameters */
238 if (__SD_task_is_scheduled_or_runnable(task))
239 __SD_task_destroy_scheduling_data(task);
241 idx = xbt_dynar_search_or_negative(sd_global->return_set, &task);
243 xbt_dynar_remove_at(sd_global->return_set, idx, NULL);
246 xbt_free(task->name);
248 if (task->surf_action != NULL)
249 task->surf_action->unref();
251 xbt_free(task->workstation_list);
252 xbt_free(task->bytes_amount);
253 xbt_free(task->flops_amount);
255 TRACE_sd_task_destroy(task);
257 xbt_mallocator_release(sd_global->task_mallocator,task);
258 sd_global->task_number--;
260 XBT_DEBUG("Task destroyed.");
264 * \brief Returns the user data of a task
267 * \return the user data associated with this task (can be \c NULL)
268 * \see SD_task_set_data()
270 void *SD_task_get_data(SD_task_t task)
276 * \brief Sets the user data of a task
278 * The new data can be \c NULL. The old data should have been freed first
279 * if it was not \c NULL.
282 * \param data the new data you want to associate with this task
283 * \see SD_task_get_data()
285 void SD_task_set_data(SD_task_t task, void *data)
291 * \brief Sets the rate of a task
293 * This will change the network bandwidth a task can use. This rate
294 * cannot be dynamically changed. Once the task has started, this call
295 * is ineffective. This rate depends on both the nominal bandwidth on
296 * the route onto which the task is scheduled (\see
297 * SD_task_get_current_bandwidth) and the amount of data to transfer.
299 * To divide the nominal bandwidth by 2, the rate then has to be :
300 * rate = bandwidth/(2*amount)
302 * \param task a \see SD_TASK_COMM_E2E task (end-to-end communication)
303 * \param rate the new rate you want to associate with this task.
305 void SD_task_set_rate(SD_task_t task, double rate)
307 xbt_assert(task->kind == SD_TASK_COMM_E2E,
308 "The rate can be modified for end-to-end communications only.");
309 if(task->start_time<0) {
312 XBT_WARN("Task %p has started. Changing rate is ineffective.", task);
317 * \brief Returns the state of a task
320 * \return the current \ref e_SD_task_state_t "state" of this task:
321 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
322 * \see e_SD_task_state_t
324 e_SD_task_state_t SD_task_get_state(SD_task_t task)
329 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
331 void SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
335 case SD_NOT_SCHEDULED:
337 if (SD_task_get_state(task) == SD_FAILED){
338 xbt_dynar_remove_at(sd_global->completed_task_set,
339 xbt_dynar_search(sd_global->completed_task_set, &task), NULL);
340 xbt_dynar_push(sd_global->initial_task_set,&task);
344 if (SD_task_get_state(task) == SD_RUNNABLE){
345 xbt_dynar_remove_at(sd_global->executable_task_set,
346 xbt_dynar_search(sd_global->executable_task_set, &task), NULL);
347 xbt_dynar_push(sd_global->initial_task_set,&task);
351 idx = xbt_dynar_search_or_negative(sd_global->initial_task_set, &task);
353 xbt_dynar_remove_at(sd_global->initial_task_set, idx, NULL);
354 xbt_dynar_push(sd_global->executable_task_set,&task);
358 xbt_dynar_remove_at(sd_global->executable_task_set,
359 xbt_dynar_search(sd_global->executable_task_set, &task), NULL);
362 xbt_dynar_push(sd_global->completed_task_set,&task);
363 task->finish_time = task->surf_action->getFinishTime();
366 jedule_log_sd_event(task);
370 xbt_dynar_push(sd_global->completed_task_set,&task);
373 xbt_die( "Invalid state");
376 task->state = new_state;
378 if (task->watch_points & new_state) {
379 XBT_VERB("Watch point reached with task '%s'!", SD_task_get_name(task));
380 sd_global->watch_point_reached = 1;
381 SD_task_unwatch(task, new_state); /* remove the watch point */
386 * \brief Returns the name of a task
389 * \return the name of this task (can be \c NULL)
391 const char *SD_task_get_name(SD_task_t task)
396 /** @brief Allows to change the name of a task */
397 void SD_task_set_name(SD_task_t task, const char *name)
399 xbt_free(task->name);
400 task->name = xbt_strdup(name);
403 /** @brief Returns the dynar of the parents of a task
406 * \return a newly allocated dynar comprising the parents of this task
409 xbt_dynar_t SD_task_get_parents(SD_task_t task)
415 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
416 xbt_dynar_foreach(task->tasks_before, i, dep) {
417 xbt_dynar_push(parents, &(dep->src));
422 /** @brief Returns the dynar of the parents of a task
425 * \return a newly allocated dynar comprising the parents of this task
427 xbt_dynar_t SD_task_get_children(SD_task_t task)
430 xbt_dynar_t children;
433 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
434 xbt_dynar_foreach(task->tasks_after, i, dep) {
435 xbt_dynar_push(children, &(dep->dst));
441 * \brief Returns the amount of workstations involved in a task
443 * Only call this on already scheduled tasks!
446 int SD_task_get_workstation_count(SD_task_t task)
448 return task->workstation_nb;
452 * \brief Returns the list of workstations involved in a task
454 * Only call this on already scheduled tasks!
457 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
459 return task->workstation_list;
463 * \brief Returns the total amount of work contained in a task
466 * \return the total amount of work (computation or data transfer) for this task
467 * \see SD_task_get_remaining_amount()
469 double SD_task_get_amount(SD_task_t task)
475 * \brief Sets the total amount of work of a task
476 * For sequential typed tasks (COMP_SEQ and COMM_E2E), it also sets the
477 * appropriate values in the flops_amount and bytes_amount arrays
478 * respectively. Nothing more than modifying task->amount is done for paralle
479 * typed tasks (COMP_PAR_AMDAHL and COMM_PAR_MXN_1D_BLOCK) as the distribution
480 * of the amount of work is done at scheduling time.
483 * \param amount the new amount of work to execute
485 void SD_task_set_amount(SD_task_t task, double amount)
487 task->amount = amount;
488 if (task->kind == SD_TASK_COMP_SEQ)
489 task->flops_amount[0] = amount;
490 if (task->kind == SD_TASK_COMM_E2E)
491 task->bytes_amount[2] = amount;
495 * \brief Returns the alpha parameter of a SD_TASK_COMP_PAR_AMDAHL task
497 * \param task a parallel task assuming Amdahl's law as speedup model
498 * \return the alpha parameter (serial part of a task in percent) for this task
500 double SD_task_get_alpha(SD_task_t task)
502 xbt_assert(SD_task_get_kind(task) == SD_TASK_COMP_PAR_AMDAHL,
503 "Alpha parameter is not defined for this kink of task");
509 * \brief Returns the remaining amount work to do till the completion of a task
512 * \return the remaining amount of work (computation or data transfer) of this task
513 * \see SD_task_get_amount()
515 double SD_task_get_remaining_amount(SD_task_t task)
517 if (task->surf_action)
518 return surf_action_get_remains(task->surf_action);
520 return task->remains;
523 e_SD_task_kind_t SD_task_get_kind(SD_task_t task)
528 /** @brief Displays debugging informations about a task */
529 void SD_task_dump(SD_task_t task)
531 unsigned int counter;
532 SD_dependency_t dependency;
535 XBT_INFO("Displaying task %s", SD_task_get_name(task));
536 statename = bprintf("%s%s%s%s%s%s%s",
537 (task->state == SD_NOT_SCHEDULED ? " not scheduled" :
539 (task->state == SD_SCHEDULABLE ? " schedulable" : ""),
540 (task->state == SD_SCHEDULED ? " scheduled" : ""),
541 (task->state == SD_RUNNABLE ? " runnable" :
543 (task->state == SD_RUNNING ? " running" : ""),
544 (task->state == SD_DONE ? " done" : ""),
545 (task->state == SD_FAILED ? " failed" : ""));
546 XBT_INFO(" - state:%s", statename);
549 if (task->kind != 0) {
550 switch (task->kind) {
551 case SD_TASK_COMM_E2E:
552 XBT_INFO(" - kind: end-to-end communication");
554 case SD_TASK_COMP_SEQ:
555 XBT_INFO(" - kind: sequential computation");
557 case SD_TASK_COMP_PAR_AMDAHL:
558 XBT_INFO(" - kind: parallel computation following Amdahl's law");
560 case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
561 XBT_INFO(" - kind: MxN data redistribution assuming 1D block distribution");
564 XBT_INFO(" - (unknown kind %d)", task->kind);
569 XBT_INFO(" - tracing category: %s", task->category);
571 XBT_INFO(" - amount: %.0f", SD_task_get_amount(task));
572 if (task->kind == SD_TASK_COMP_PAR_AMDAHL)
573 XBT_INFO(" - alpha: %.2f", task->alpha);
574 XBT_INFO(" - Dependencies to satisfy: %d", task->unsatisfied_dependencies);
575 if (!xbt_dynar_is_empty(task->tasks_before)) {
576 XBT_INFO(" - pre-dependencies:");
577 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
578 XBT_INFO(" %s", SD_task_get_name(dependency->src));
581 if (!xbt_dynar_is_empty(task->tasks_after)) {
582 XBT_INFO(" - post-dependencies:");
583 xbt_dynar_foreach(task->tasks_after, counter, dependency) {
584 XBT_INFO(" %s", SD_task_get_name(dependency->dst));
589 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
590 void SD_task_dotty(SD_task_t task, void *out)
592 unsigned int counter;
593 SD_dependency_t dependency;
594 FILE *fout = (FILE*)out;
595 fprintf(fout, " T%p [label=\"%.20s\"", task, task->name);
596 switch (task->kind) {
597 case SD_TASK_COMM_E2E:
598 case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
599 fprintf(fout, ", shape=box");
601 case SD_TASK_COMP_SEQ:
602 case SD_TASK_COMP_PAR_AMDAHL:
603 fprintf(fout, ", shape=circle");
606 xbt_die("Unknown task type!");
608 fprintf(fout, "];\n");
609 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
610 fprintf(fout, " T%p -> T%p;\n", dependency->src, dependency->dst);
614 /* Destroys a dependency between two tasks.
616 static void __SD_task_dependency_destroy(void *dependency)
618 xbt_free(((SD_dependency_t)dependency)->name);
619 xbt_free(dependency);
623 * \brief Adds a dependency between two tasks
625 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
626 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
628 * \param name the name of the new dependency (can be \c NULL)
629 * \param data the user data you want to associate with this dependency (can be \c NULL)
630 * \param src the task which must be executed first
631 * \param dst the task you want to make depend on \a src
632 * \see SD_task_dependency_remove()
634 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
638 unsigned long length;
641 SD_dependency_t dependency;
642 e_SD_task_state_t state;
644 dynar = src->tasks_after;
645 length = xbt_dynar_length(dynar);
649 "Cannot add a dependency between task '%s' and itself",
650 SD_task_get_name(src));
652 state = SD_task_get_state(src);
653 if (state != SD_NOT_SCHEDULED && state != SD_SCHEDULABLE &&
654 state != SD_RUNNING && !__SD_task_is_scheduled_or_runnable(src))
656 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED,"
657 " SD_RUNNABLE or SD_RUNNING", SD_task_get_name(src));
659 state = SD_task_get_state(dst);
660 if (state != SD_NOT_SCHEDULED && state != SD_SCHEDULABLE &&
661 !__SD_task_is_scheduled_or_runnable(dst))
663 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED,"
664 "or SD_RUNNABLE", SD_task_get_name(dst));
666 XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s",
667 SD_task_get_name(src), SD_task_get_name(dst));
668 for (i = 0; i < length && !found; i++) {
669 xbt_dynar_get_cpy(dynar, i, &dependency);
670 found = (dependency->dst == dst);
671 XBT_DEBUG("Dependency %lu: dependency->dst = %s", i,
672 SD_task_get_name(dependency->dst));
677 "A dependency already exists between task '%s' and task '%s'",
678 SD_task_get_name(src), SD_task_get_name(dst));
680 dependency = xbt_new(s_SD_dependency_t, 1);
682 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
683 dependency->data = data;
684 dependency->src = src;
685 dependency->dst = dst;
687 /* src must be executed before dst */
688 xbt_dynar_push(src->tasks_after, &dependency);
689 xbt_dynar_push(dst->tasks_before, &dependency);
691 dst->unsatisfied_dependencies++;
694 /* if the task was runnable, then dst->tasks_before is not empty anymore,
695 so we must go back to state SD_SCHEDULED */
696 if (SD_task_get_state(dst) == SD_RUNNABLE) {
698 ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
699 SD_task_get_name(dst));
700 SD_task_set_state(dst, SD_SCHEDULED);
704 * \brief Returns the name given as input when dependency has been created..
707 * \param dst a task depending on \a src
710 const char *SD_task_dependency_get_name(SD_task_t src, SD_task_t dst){
712 SD_dependency_t dependency;
714 xbt_dynar_foreach(src->tasks_after, i, dependency){
715 if (dependency->dst == dst)
716 return dependency->name;
722 * \brief Indicates whether there is a dependency between two tasks.
725 * \param dst a task depending on \a src
727 * If src is NULL, checks whether dst has any pre-dependency.
728 * If dst is NULL, checks whether src has any post-dependency.
730 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
732 unsigned int counter;
733 SD_dependency_t dependency;
735 xbt_assert(src != NULL
737 "Invalid parameter: both src and dst are NULL");
741 xbt_dynar_foreach(src->tasks_after, counter, dependency) {
742 if (dependency->dst == dst)
746 return xbt_dynar_length(src->tasks_after);
749 return xbt_dynar_length(dst->tasks_before);
755 * \brief Remove a dependency between two tasks
758 * \param dst a task depending on \a src
759 * \see SD_task_dependency_add()
761 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
765 unsigned long length;
768 SD_dependency_t dependency;
770 /* remove the dependency from src->tasks_after */
771 dynar = src->tasks_after;
772 length = xbt_dynar_length(dynar);
774 for (i = 0; i < length && !found; i++) {
775 xbt_dynar_get_cpy(dynar, i, &dependency);
776 if (dependency->dst == dst) {
777 xbt_dynar_remove_at(dynar, i, NULL);
783 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
784 SD_task_get_name(src), SD_task_get_name(dst),
785 SD_task_get_name(dst), SD_task_get_name(src));
787 /* remove the dependency from dst->tasks_before */
788 dynar = dst->tasks_before;
789 length = xbt_dynar_length(dynar);
792 for (i = 0; i < length && !found; i++) {
793 xbt_dynar_get_cpy(dynar, i, &dependency);
794 if (dependency->src == src) {
795 xbt_dynar_remove_at(dynar, i, NULL);
796 __SD_task_dependency_destroy(dependency);
797 dst->unsatisfied_dependencies--;
802 /* should never happen... */
804 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
805 SD_task_get_name(dst), SD_task_get_name(src),
806 SD_task_get_name(src), SD_task_get_name(dst));
808 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
810 if (dst->unsatisfied_dependencies == 0) {
811 if (SD_task_get_state(dst) == SD_SCHEDULED)
812 SD_task_set_state(dst, SD_RUNNABLE);
814 SD_task_set_state(dst, SD_SCHEDULABLE);
817 if (dst->is_not_ready == 0)
818 SD_task_set_state(dst, SD_SCHEDULABLE);
820 /* __SD_print_dependencies(src);
821 __SD_print_dependencies(dst); */
825 * \brief Returns the user data associated with a dependency between two tasks
828 * \param dst a task depending on \a src
829 * \return the user data associated with this dependency (can be \c NULL)
830 * \see SD_task_dependency_add()
832 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
836 unsigned long length;
839 SD_dependency_t dependency;
841 dynar = src->tasks_after;
842 length = xbt_dynar_length(dynar);
844 for (i = 0; i < length && !found; i++) {
845 xbt_dynar_get_cpy(dynar, i, &dependency);
846 found = (dependency->dst == dst);
849 THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'",
850 SD_task_get_name(src), SD_task_get_name(dst));
851 return dependency->data;
855 * \brief Adds a watch point to a task
857 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
858 * task becomes the one given in argument. The
859 * watch point is then automatically removed.
862 * \param state the \ref e_SD_task_state_t "state" you want to watch
863 * (cannot be #SD_NOT_SCHEDULED)
864 * \see SD_task_unwatch()
866 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
868 if (state & SD_NOT_SCHEDULED)
870 "Cannot add a watch point for state SD_NOT_SCHEDULED");
872 task->watch_points = task->watch_points | state;
876 * \brief Removes a watch point from a task
879 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
880 * \see SD_task_watch()
882 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
884 xbt_assert(state != SD_NOT_SCHEDULED,
885 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
887 task->watch_points = task->watch_points & ~state;
891 * \brief Returns an approximative estimation of the execution time of a task.
893 * The estimation is very approximative because the value returned is the time
894 * the task would take if it was executed now and if it was the only task.
896 * \param task the task to evaluate
897 * \param workstation_nb number of workstations on which the task would be executed
898 * \param workstation_list the workstations on which the task would be executed
899 * \param flops_amount computation amount for each workstation
900 * \param bytes_amount communication amount between each pair of workstations
903 double SD_task_get_execution_time(SD_task_t task,
905 const SD_workstation_t *
907 const double *flops_amount,
908 const double *bytes_amount)
910 double time, max_time = 0.0;
912 xbt_assert(workstation_nb > 0, "Invalid parameter");
914 /* the task execution time is the maximum execution time of the parallel tasks */
916 for (i = 0; i < workstation_nb; i++) {
918 if (flops_amount != NULL)
920 SD_workstation_get_computation_time(workstation_list[i],
923 if (bytes_amount != NULL)
924 for (j = 0; j < workstation_nb; j++) {
926 SD_route_get_communication_time(workstation_list[i],
933 if (time > max_time) {
940 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
942 if (SD_task_get_state(task) > SD_SCHEDULABLE)
943 THROWF(arg_error, 0, "Task '%s' has already been scheduled",
944 SD_task_get_name(task));
946 /* update the task state */
947 if (task->unsatisfied_dependencies == 0)
948 SD_task_set_state(task, SD_RUNNABLE);
950 SD_task_set_state(task, SD_SCHEDULED);
954 * \brief Schedules a task
956 * The task state must be #SD_NOT_SCHEDULED.
957 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
958 * i.e. when its dependencies are satisfied.
960 * \param task the task you want to schedule
961 * \param workstation_count number of workstations on which the task will be executed
962 * \param workstation_list the workstations on which the task will be executed
963 * \param flops_amount computation amount for each workstation
964 * \param bytes_amount communication amount between each pair of workstations
965 * \param rate task execution speed rate
966 * \see SD_task_unschedule()
968 void SD_task_schedule(SD_task_t task, int workstation_count,
969 const SD_workstation_t * workstation_list,
970 const double *flops_amount,
971 const double *bytes_amount, double rate)
973 xbt_assert(workstation_count > 0, "workstation_nb must be positive");
975 task->workstation_nb = workstation_count;
979 task->flops_amount = (double*)xbt_realloc(task->flops_amount,
980 sizeof(double) * workstation_count);
981 memcpy(task->flops_amount, flops_amount,
982 sizeof(double) * workstation_count);
984 xbt_free(task->flops_amount);
985 task->flops_amount = NULL;
988 int communication_nb = workstation_count * workstation_count;
990 task->bytes_amount = (double*)xbt_realloc(task->bytes_amount,
991 sizeof(double) * communication_nb);
992 memcpy(task->bytes_amount, bytes_amount,
993 sizeof(double) * communication_nb);
995 xbt_free(task->bytes_amount);
996 task->bytes_amount = NULL;
999 task->workstation_list = (SD_workstation_t*)
1000 xbt_realloc(task->workstation_list,
1001 sizeof(SD_workstation_t) * workstation_count);
1002 memcpy(task->workstation_list, workstation_list,
1003 sizeof(SD_workstation_t) * workstation_count);
1005 SD_task_do_schedule(task);
1009 * \brief Unschedules a task
1011 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
1012 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
1013 * Call SD_task_schedule() to schedule it again.
1015 * \param task the task you want to unschedule
1016 * \see SD_task_schedule()
1018 void SD_task_unschedule(SD_task_t task)
1020 if (task->state != SD_SCHEDULED &&
1021 task->state != SD_RUNNABLE &&
1022 task->state != SD_RUNNING &&
1023 task->state != SD_FAILED)
1024 THROWF(arg_error, 0,
1025 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
1026 SD_task_get_name(task));
1028 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
1029 && ((task->kind == SD_TASK_COMP_PAR_AMDAHL) ||
1030 (task->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK))) { /* Don't free scheduling data for typed tasks */
1031 __SD_task_destroy_scheduling_data(task);
1032 xbt_free(task->workstation_list);
1033 task->workstation_list=NULL;
1034 task->workstation_nb = 0;
1037 if (SD_task_get_state(task) == SD_RUNNING)
1038 /* the task should become SD_FAILED */
1039 task->surf_action->cancel();
1041 if (task->unsatisfied_dependencies == 0)
1042 SD_task_set_state(task, SD_SCHEDULABLE);
1044 SD_task_set_state(task, SD_NOT_SCHEDULED);
1046 task->remains = task->amount;
1047 task->start_time = -1.0;
1050 /* Destroys the data memorized by SD_task_schedule.
1051 * Task state must be SD_SCHEDULED or SD_RUNNABLE.
1053 static void __SD_task_destroy_scheduling_data(SD_task_t task)
1055 if (!__SD_task_is_scheduled_or_runnable(task))
1056 THROWF(arg_error, 0,
1057 "Task '%s' must be SD_SCHEDULED or SD_RUNNABLE",
1058 SD_task_get_name(task));
1060 xbt_free(task->flops_amount);
1061 xbt_free(task->bytes_amount);
1062 task->flops_amount = task->bytes_amount = NULL;
1065 /* Runs a task. This function is directly called by __SD_task_try_to_run if
1066 * the task doesn't have to wait in FIFOs. Otherwise, it is called by
1067 * __SD_task_just_done when the task gets out of its FIFOs.
1069 void SD_task_run(SD_task_t task)
1075 xbt_assert(SD_task_get_state(task) == SD_RUNNABLE,
1076 "Task '%s' is not runnable! Task state: %d",
1077 SD_task_get_name(task), (int)SD_task_get_state(task));
1078 xbt_assert(task->workstation_list != NULL,
1079 "Task '%s': workstation_list is NULL!",
1080 SD_task_get_name(task));
1082 XBT_DEBUG("Running task '%s'", SD_task_get_name(task));
1084 /* Copy the elements of the task into the action */
1085 int host_nb = task->workstation_nb;
1086 hosts = xbt_new(sg_host_t, host_nb);
1088 for (i = 0; i < host_nb; i++)
1089 hosts[i] = task->workstation_list[i];
1091 double *flops_amount = xbt_new0(double, host_nb);
1092 double *bytes_amount = xbt_new0(double, host_nb * host_nb);
1094 if(task->flops_amount)
1095 memcpy(flops_amount, task->flops_amount, sizeof(double) * host_nb);
1096 if(task->bytes_amount)
1097 memcpy(bytes_amount, task->bytes_amount,
1098 sizeof(double) * host_nb * host_nb);
1100 task->surf_action = surf_host_model->executeParallelTask(
1101 host_nb, hosts, flops_amount, bytes_amount, task->rate);
1103 task->surf_action->setData(task);
1105 XBT_DEBUG("surf_action = %p", task->surf_action);
1108 TRACE_surf_action(task->surf_action, task->category);
1110 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
1111 SD_task_set_state(task, SD_RUNNING);
1112 xbt_assert(SD_task_get_state(task) == SD_RUNNING,
1113 "Bad state of task '%s': %d",
1114 SD_task_get_name(task), (int)SD_task_get_state(task));
1119 * Remove all dependencies associated with a task. This function is called
1120 * when the task is destroyed.
1122 static void __SD_task_remove_dependencies(SD_task_t task)
1124 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1125 because each one is stored twice */
1126 SD_dependency_t dependency;
1127 while (!xbt_dynar_is_empty(task->tasks_before)) {
1128 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1129 SD_task_dependency_remove(dependency->src, dependency->dst);
1132 while (!xbt_dynar_is_empty(task->tasks_after)) {
1133 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1134 SD_task_dependency_remove(dependency->src, dependency->dst);
1139 * \brief Returns the start time of a task
1141 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1143 * \param task: a task
1144 * \return the start time of this task
1146 double SD_task_get_start_time(SD_task_t task)
1148 if (task->surf_action)
1149 return task->surf_action->getStartTime();
1151 return task->start_time;
1155 * \brief Returns the finish time of a task
1157 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1158 * If the state is not completed yet, the returned value is an
1159 * estimation of the task finish time. This value can fluctuate
1160 * until the task is completed.
1162 * \param task: a task
1163 * \return the start time of this task
1165 double SD_task_get_finish_time(SD_task_t task)
1167 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1168 return task->surf_action->getFinishTime();
1170 return task->finish_time;
1175 void SD_task_distribute_comp_amdahl(SD_task_t task, int ws_count)
1178 xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1179 "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1180 "Cannot use this function.",
1181 SD_task_get_name(task));
1182 task->flops_amount = xbt_new0(double, ws_count);
1183 task->bytes_amount = xbt_new0(double, ws_count * ws_count);
1184 xbt_free(task->workstation_list);
1185 task->workstation_nb = ws_count;
1186 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1188 for(i=0;i<ws_count;i++){
1189 task->flops_amount[i] =
1190 (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1195 /** @brief Auto-schedules a task.
1197 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1198 * allows to specify the task costs at creation, and decouple them from the
1199 * scheduling process where you just specify which resource should deliver the
1202 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e()
1203 * or SD_task_create_comp_seq(). Check their definitions for the exact semantic
1207 * We should create tasks kind for the following categories:
1208 * - Point to point communication (done)
1209 * - Sequential computation (done)
1210 * - group communication (redistribution, several kinds)
1211 * - parallel tasks with no internal communication (one kind per speedup
1212 * model such as Amdahl)
1213 * - idem+ internal communication. Task type not enough since we cannot store
1214 * comm cost alongside to comp one)
1216 void SD_task_schedulev(SD_task_t task, int count,
1217 const SD_workstation_t * list)
1220 SD_dependency_t dep;
1222 xbt_assert(task->kind != 0,
1223 "Task %s is not typed. Cannot automatically schedule it.",
1224 SD_task_get_name(task));
1225 switch (task->kind) {
1226 case SD_TASK_COMP_PAR_AMDAHL:
1227 SD_task_distribute_comp_amdahl(task, count);
1228 case SD_TASK_COMM_E2E:
1229 case SD_TASK_COMP_SEQ:
1230 xbt_assert(task->workstation_nb == count,
1231 "Got %d locations, but were expecting %d locations",
1232 count,task->workstation_nb);
1233 for (i = 0; i < count; i++)
1234 task->workstation_list[i] = list[i];
1235 if (SD_task_get_kind(task)== SD_TASK_COMP_SEQ && !task->flops_amount){
1236 /*This task has failed and is rescheduled. Reset the flops_amount*/
1237 task->flops_amount = xbt_new0(double, 1);
1238 task->flops_amount[0] = task->remains;
1240 SD_task_do_schedule(task);
1243 xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1244 SD_task_get_name(task));
1246 if (task->kind == SD_TASK_COMM_E2E) {
1247 XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1248 SD_task_get_name(task),
1249 SD_workstation_get_name(task->workstation_list[0]),
1250 SD_workstation_get_name(task->workstation_list[1]),
1251 task->bytes_amount[2]);
1255 /* Iterate over all children and parents being COMM_E2E to say where I am
1256 * located (and start them if runnable) */
1257 if (task->kind == SD_TASK_COMP_SEQ) {
1258 XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1259 SD_task_get_name(task),
1260 SD_workstation_get_name(task->workstation_list[0]),
1261 task->flops_amount[0]);
1263 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1264 SD_task_t before = dep->src;
1265 if (before->kind == SD_TASK_COMM_E2E) {
1266 before->workstation_list[1] = task->workstation_list[0];
1268 if (before->workstation_list[0] &&
1269 (SD_task_get_state(before)< SD_SCHEDULED)) {
1270 SD_task_do_schedule(before);
1272 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1273 SD_task_get_name(before),
1274 SD_workstation_get_name(before->workstation_list[0]),
1275 SD_workstation_get_name(before->workstation_list[1]),
1276 before->bytes_amount[2]);
1280 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1281 SD_task_t after = dep->dst;
1282 if (after->kind == SD_TASK_COMM_E2E) {
1283 after->workstation_list[0] = task->workstation_list[0];
1284 if (after->workstation_list[1]
1285 && (SD_task_get_state(after)< SD_SCHEDULED)) {
1286 SD_task_do_schedule(after);
1288 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1289 SD_task_get_name(after),
1290 SD_workstation_get_name(after->workstation_list[0]),
1291 SD_workstation_get_name(after->workstation_list[1]),
1292 after->bytes_amount[2]);
1298 /* Iterate over all children and parents being MXN_1D_BLOCK to say where I am
1299 * located (and start them if runnable) */
1300 if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1301 XBT_VERB("Schedule computation task %s on %d workstations. %.f flops"
1302 " will be distributed following Amdahl's Law",
1303 SD_task_get_name(task), task->workstation_nb,
1304 task->flops_amount[0]);
1305 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1306 SD_task_t before = dep->src;
1307 if (before->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1308 if (!before->workstation_list){
1309 XBT_VERB("Sender side of Task %s is not scheduled yet",
1310 SD_task_get_name(before));
1311 before->workstation_list = xbt_new0(SD_workstation_t, count);
1312 before->workstation_nb = count;
1313 XBT_VERB("Fill the workstation list with list of Task '%s'",
1314 SD_task_get_name(task));
1315 for (i=0;i<count;i++)
1316 before->workstation_list[i] = task->workstation_list[i];
1318 XBT_VERB("Build communication matrix for task '%s'",
1319 SD_task_get_name(before));
1321 double src_start, src_end, dst_start, dst_end;
1322 src_nb = before->workstation_nb;
1324 before->workstation_list = (SD_workstation_t*) xbt_realloc(
1325 before->workstation_list,
1326 (before->workstation_nb+count)*sizeof(s_SD_workstation_t));
1327 for(i=0; i<count; i++)
1328 before->workstation_list[before->workstation_nb+i] =
1329 task->workstation_list[i];
1331 before->workstation_nb += count;
1332 xbt_free(before->flops_amount);
1333 xbt_free(before->bytes_amount);
1334 before->flops_amount = xbt_new0(double,
1335 before->workstation_nb);
1336 before->bytes_amount = xbt_new0(double,
1337 before->workstation_nb*
1338 before->workstation_nb);
1340 for(i=0;i<src_nb;i++){
1341 src_start = i*before->amount/src_nb;
1342 src_end = src_start + before->amount/src_nb;
1343 for(j=0; j<dst_nb; j++){
1344 dst_start = j*before->amount/dst_nb;
1345 dst_end = dst_start + before->amount/dst_nb;
1346 XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)",
1347 SD_workstation_get_name(before->workstation_list[i]),
1348 SD_workstation_get_name(before->workstation_list[src_nb+j]),
1349 src_start, src_end, dst_start, dst_end);
1350 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1351 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1353 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1354 MIN(src_end, dst_end) - MAX(src_start, dst_start);
1356 XBT_VERB("==> %.2f",
1357 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1361 if (SD_task_get_state(before)< SD_SCHEDULED) {
1362 SD_task_do_schedule(before);
1364 ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1365 SD_task_get_name(before),before->amount, src_nb, dst_nb);
1370 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1371 SD_task_t after = dep->dst;
1372 if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1373 if (!after->workstation_list){
1374 XBT_VERB("Receiver side of Task '%s' is not scheduled yet",
1375 SD_task_get_name(after));
1376 after->workstation_list = xbt_new0(SD_workstation_t, count);
1377 after->workstation_nb = count;
1378 XBT_VERB("Fill the workstation list with list of Task '%s'",
1379 SD_task_get_name(task));
1380 for (i=0;i<count;i++)
1381 after->workstation_list[i] = task->workstation_list[i];
1384 double src_start, src_end, dst_start, dst_end;
1386 dst_nb = after->workstation_nb;
1387 after->workstation_list = (SD_workstation_t*) xbt_realloc(
1388 after->workstation_list,
1389 (after->workstation_nb+count)*sizeof(s_SD_workstation_t));
1390 for(i=after->workstation_nb - 1; i>=0; i--)
1391 after->workstation_list[count+i] = after->workstation_list[i];
1392 for(i=0; i<count; i++)
1393 after->workstation_list[i] = task->workstation_list[i];
1395 after->workstation_nb += count;
1397 xbt_free(after->flops_amount);
1398 xbt_free(after->bytes_amount);
1400 after->flops_amount = xbt_new0(double, after->workstation_nb);
1401 after->bytes_amount = xbt_new0(double,
1402 after->workstation_nb*
1403 after->workstation_nb);
1405 for(i=0;i<src_nb;i++){
1406 src_start = i*after->amount/src_nb;
1407 src_end = src_start + after->amount/src_nb;
1408 for(j=0; j<dst_nb; j++){
1409 dst_start = j*after->amount/dst_nb;
1410 dst_end = dst_start + after->amount/dst_nb;
1411 XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)",
1412 i, j, src_start, src_end, dst_start, dst_end);
1413 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1414 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1416 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1417 MIN(src_end, dst_end)- MAX(src_start, dst_start);
1419 XBT_VERB("==> %.2f",
1420 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1424 if (SD_task_get_state(after)< SD_SCHEDULED) {
1425 SD_task_do_schedule(after);
1427 ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1428 SD_task_get_name(after),after->amount, src_nb, dst_nb);
1436 /** @brief autoschedule a task on a list of workstations
1438 * This function is very similar to SD_task_schedulev(),
1439 * but takes the list of workstations to schedule onto as separate parameters.
1440 * It builds a proper vector of workstations and then call SD_task_schedulev()
1442 void SD_task_schedulel(SD_task_t task, int count, ...)
1445 SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1447 va_start(ap, count);
1448 for (i = 0; i < count; i++) {
1449 list[i] = va_arg(ap, SD_workstation_t);
1452 SD_task_schedulev(task, count, list);