1 /* Copyright (c) 2006, 2007, 2008, 2009, 2010, 2011. 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. */
8 #include "simdag/simdag.h"
9 #include "xbt/sysdep.h"
10 #include "xbt/dynar.h"
11 #include "instr/instr_private.h"
13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
14 "Logging specific to SimDag (task)");
16 static void __SD_task_remove_dependencies(SD_task_t task);
17 static void __SD_task_destroy_scheduling_data(SD_task_t task);
19 void* SD_task_new_f(void)
21 SD_task_t task = xbt_new0(s_SD_task_t, 1);
22 task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
23 task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
28 void SD_task_recycle_f(void *t)
30 SD_task_t task = (SD_task_t) t;
32 /* Reset the content */
33 task->kind = SD_TASK_NOT_TYPED;
34 task->state_hookup.prev = NULL;
35 task->state_hookup.next = NULL;
36 task->state_set = sd_global->not_scheduled_task_set;
37 xbt_swag_insert(task, task->state_set);
38 task->state = SD_NOT_SCHEDULED;
39 task->return_hookup.prev = NULL;
40 task->return_hookup.next = NULL;
44 task->start_time = -1.0;
45 task->finish_time = -1.0;
46 task->surf_action = NULL;
47 task->watch_points = 0;
50 xbt_dynar_reset(task->tasks_before);
51 xbt_dynar_reset(task->tasks_after);
52 task->unsatisfied_dependencies = 0;
53 task->is_not_ready = 0;
55 /* scheduling parameters */
56 task->workstation_nb = 0;
57 task->workstation_list = NULL;
58 task->computation_amount = NULL;
59 task->communication_amount = NULL;
63 void SD_task_free_f(void *t)
65 SD_task_t task = (SD_task_t)t;
67 xbt_dynar_free(&task->tasks_before);
68 xbt_dynar_free(&task->tasks_after);
73 * \brief Creates a new task.
75 * \param name the name of the task (can be \c NULL)
76 * \param data the user data you want to associate with the task (can be \c NULL)
77 * \param amount amount of the task
78 * \return the new task
79 * \see SD_task_destroy()
81 SD_task_t SD_task_create(const char *name, void *data, double amount)
83 SD_task_t task = xbt_mallocator_get(sd_global->task_mallocator);
85 /* general information */
86 task->data = data; /* user data */
87 task->name = xbt_strdup(name);
88 task->amount = amount;
89 task->remains = amount;
91 sd_global->task_number++;
94 task->category = NULL;
100 static XBT_INLINE SD_task_t SD_task_create_sized(const char *name,
101 void *data, double amount,
104 SD_task_t task = SD_task_create(name, data, amount);
105 task->communication_amount = xbt_new0(double, ws_count * ws_count);
106 task->computation_amount = xbt_new0(double, ws_count);
107 task->workstation_nb = ws_count;
108 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
112 /** @brief create a end-to-end communication task that can then be auto-scheduled
114 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
115 * allows to specify the task costs at creation, and decouple them from the
116 * scheduling process where you just specify which resource should deliver the
119 * A end-to-end communication must be scheduled on 2 hosts, and the amount
120 * specified at creation is sent from hosts[0] to hosts[1].
122 SD_task_t SD_task_create_comm_e2e(const char *name, void *data,
125 SD_task_t res = SD_task_create_sized(name, data, amount, 2);
126 res->communication_amount[2] = amount;
127 res->kind = SD_TASK_COMM_E2E;
131 /** @brief create a sequential computation task that can then be auto-scheduled
133 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
134 * allows to specify the task costs at creation, and decouple them from the
135 * scheduling process where you just specify which resource should deliver the
138 * A sequential computation must be scheduled on 1 host, and the amount
139 * specified at creation to be run on hosts[0].
141 * \param name the name of the task (can be \c NULL)
142 * \param data the user data you want to associate with the task (can be \c NULL)
143 * \param amount amount of compute work to be done by the task
144 * \return the new SD_TASK_COMP_SEQ typed task
146 SD_task_t SD_task_create_comp_seq(const char *name, void *data,
149 SD_task_t res = SD_task_create_sized(name, data, amount, 1);
150 res->computation_amount[0] = amount;
151 res->kind = SD_TASK_COMP_SEQ;
155 /** @brief create a parallel computation task that can then be auto-scheduled
157 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
158 * allows to specify the task costs at creation, and decouple them from the
159 * scheduling process where you just specify which resource should deliver the
162 * A parallel computation can be scheduled on any number of host.
163 * The underlying speedup model is Amdahl's law.
164 * To be auto-scheduled, \see SD_task_distribute_comp_amdhal has to be called
166 * \param name the name of the task (can be \c NULL)
167 * \param data the user data you want to associate with the task (can be \c NULL)
168 * \param amount amount of compute work to be done by the task
169 * \param alpha purely serial fraction of the work to be done (in [0.;1.[)
170 * \return the new task
172 SD_task_t SD_task_create_comp_par_amdahl(const char *name, void *data,
173 double amount, double alpha)
175 xbt_assert(alpha < 1. && alpha >= 0.,
176 "Invalid parameter: alpha must be in [0.;1.[");
178 SD_task_t res = SD_task_create(name, data, amount);
180 res->kind = SD_TASK_COMP_PAR_AMDAHL;
186 * \brief Destroys a task.
188 * The user data (if any) should have been destroyed first.
190 * \param task the task you want to destroy
191 * \see SD_task_create()
193 void SD_task_destroy(SD_task_t task)
195 XBT_DEBUG("Destroying task %s...", SD_task_get_name(task));
197 __SD_task_remove_dependencies(task);
198 /* if the task was scheduled or runnable we have to free the scheduling parameters */
199 if (__SD_task_is_scheduled_or_runnable(task))
200 __SD_task_destroy_scheduling_data(task);
201 if (task->state_set != NULL) /* would be null if just created */
202 xbt_swag_remove(task, task->state_set);
204 xbt_swag_remove(task, sd_global->return_set);
206 xbt_free(task->name);
208 if (task->surf_action != NULL)
209 surf_workstation_model->action_unref(task->surf_action);
211 xbt_free(task->workstation_list);
212 xbt_free(task->communication_amount);
213 xbt_free(task->computation_amount);
215 xbt_mallocator_release(sd_global->task_mallocator,task);
216 sd_global->task_number--;
219 if (task->category) xbt_free(task->category);
222 XBT_DEBUG("Task destroyed.");
226 * \brief Returns the user data of a task
229 * \return the user data associated with this task (can be \c NULL)
230 * \see SD_task_set_data()
232 void *SD_task_get_data(SD_task_t task)
238 * \brief Sets the user data of a task
240 * The new data can be \c NULL. The old data should have been freed first
241 * if it was not \c NULL.
244 * \param data the new data you want to associate with this task
245 * \see SD_task_get_data()
247 void SD_task_set_data(SD_task_t task, void *data)
253 * \brief Sets the rate of a task
255 * This will change the percentage of the available power or network bandwidth
259 * \param rate the new rate you want to associate with this task
261 void SD_task_set_rate(SD_task_t task, double rate)
267 * \brief Returns the state of a task
270 * \return the current \ref e_SD_task_state_t "state" of this task:
271 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
272 * \see e_SD_task_state_t
274 e_SD_task_state_t SD_task_get_state(SD_task_t task)
279 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
281 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
283 xbt_swag_remove(task, task->state_set);
285 case SD_NOT_SCHEDULED:
286 task->state_set = sd_global->not_scheduled_task_set;
289 task->state_set = sd_global->schedulable_task_set;
292 task->state_set = sd_global->scheduled_task_set;
295 task->state_set = sd_global->runnable_task_set;
298 task->state_set = sd_global->in_fifo_task_set;
301 task->state_set = sd_global->running_task_set;
303 surf_workstation_model->action_get_start_time(task->surf_action);
306 task->state_set = sd_global->done_task_set;
308 surf_workstation_model->action_get_finish_time(task->surf_action);
311 jedule_log_sd_event(task);
315 task->state_set = sd_global->failed_task_set;
318 xbt_die( "Invalid state");
320 xbt_swag_insert(task, task->state_set);
321 task->state = new_state;
323 if (task->watch_points & new_state) {
324 XBT_VERB("Watch point reached with task '%s'!", SD_task_get_name(task));
325 sd_global->watch_point_reached = 1;
326 SD_task_unwatch(task, new_state); /* remove the watch point */
331 * \brief Returns the name of a task
334 * \return the name of this task (can be \c NULL)
336 const char *SD_task_get_name(SD_task_t task)
341 /** @brief Allows to change the name of a task */
342 void SD_task_set_name(SD_task_t task, const char *name)
344 xbt_free(task->name);
345 task->name = xbt_strdup(name);
348 /** @brief Returns the dynar of the parents of a task
351 * \return a newly allocated dynar comprising the parents of this task
354 xbt_dynar_t SD_task_get_parents(SD_task_t task)
360 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
361 xbt_dynar_foreach(task->tasks_before, i, dep) {
362 xbt_dynar_push(parents, &(dep->src));
367 /** @brief Returns the dynar of the parents of a task
370 * \return a newly allocated dynar comprising the parents of this task
372 xbt_dynar_t SD_task_get_children(SD_task_t task)
375 xbt_dynar_t children;
378 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
379 xbt_dynar_foreach(task->tasks_after, i, dep) {
380 xbt_dynar_push(children, &(dep->dst));
386 * \brief Returns the amount of workstations involved in a task
388 * Only call this on already scheduled tasks!
391 int SD_task_get_workstation_count(SD_task_t task)
393 return task->workstation_nb;
397 * \brief Returns the list of workstations involved in a task
399 * Only call this on already scheduled tasks!
402 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
404 return task->workstation_list;
408 * \brief Returns the total amount of work contained in a task
411 * \return the total amount of work (computation or data transfer) for this task
412 * \see SD_task_get_remaining_amount()
414 double SD_task_get_amount(SD_task_t task)
420 * \brief Returns the remaining amount work to do till the completion of a task
423 * \return the remaining amount of work (computation or data transfer) of this task
424 * \see SD_task_get_amount()
426 double SD_task_get_remaining_amount(SD_task_t task)
428 if (task->surf_action)
429 return surf_workstation_model->get_remains(task->surf_action);
431 return task->remains;
434 int SD_task_get_kind(SD_task_t task)
439 /** @brief Displays debugging informations about a task */
440 void SD_task_dump(SD_task_t task)
442 unsigned int counter;
443 SD_dependency_t dependency;
446 XBT_INFO("Displaying task %s", SD_task_get_name(task));
447 statename = bprintf("%s %s %s %s %s %s %s %s",
448 (task->state & SD_NOT_SCHEDULED ? "not scheduled" :
450 (task->state & SD_SCHEDULABLE ? "schedulable" : ""),
451 (task->state & SD_SCHEDULED ? "scheduled" : ""),
452 (task->state & SD_RUNNABLE ? "runnable" :
454 (task->state & SD_IN_FIFO ? "in fifo" : ""),
455 (task->state & SD_RUNNING ? "running" : ""),
456 (task->state & SD_DONE ? "done" : ""),
457 (task->state & SD_FAILED ? "failed" : ""));
458 XBT_INFO(" - state: %s", statename);
461 if (task->kind != 0) {
462 switch (task->kind) {
463 case SD_TASK_COMM_E2E:
464 XBT_INFO(" - kind: end-to-end communication");
466 case SD_TASK_COMP_SEQ:
467 XBT_INFO(" - kind: sequential computation");
469 case SD_TASK_COMP_PAR_AMDAHL:
470 XBT_INFO(" - kind: parallel computation following Amdahl's law");
473 XBT_INFO(" - (unknown kind %d)", task->kind);
476 XBT_INFO(" - amount: %.0f", SD_task_get_amount(task));
477 XBT_INFO(" - Dependencies to satisfy: %u", task->unsatisfied_dependencies);
478 if (!xbt_dynar_is_empty(task->tasks_before)) {
479 XBT_INFO(" - pre-dependencies:");
480 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
481 XBT_INFO(" %s", SD_task_get_name(dependency->src));
484 if (!xbt_dynar_is_empty(task->tasks_after)) {
485 XBT_INFO(" - post-dependencies:");
486 xbt_dynar_foreach(task->tasks_after, counter, dependency) {
487 XBT_INFO(" %s", SD_task_get_name(dependency->dst));
492 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
493 void SD_task_dotty(SD_task_t task, void *out)
495 unsigned int counter;
496 SD_dependency_t dependency;
497 fprintf(out, " T%p [label=\"%.20s\"", task, task->name);
498 switch (task->kind) {
499 case SD_TASK_COMM_E2E:
500 fprintf(out, ", shape=box");
502 case SD_TASK_COMP_SEQ:
503 fprintf(out, ", shape=circle");
506 xbt_die("Unknown task type!");
508 fprintf(out, "];\n");
509 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
510 fprintf(out, " T%p -> T%p;\n", dependency->src, dependency->dst);
514 /* Destroys a dependency between two tasks.
516 static void __SD_task_dependency_destroy(void *dependency)
518 xbt_free(((SD_dependency_t)dependency)->name);
519 xbt_free(dependency);
523 * \brief Adds a dependency between two tasks
525 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
526 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
528 * \param name the name of the new dependency (can be \c NULL)
529 * \param data the user data you want to associate with this dependency (can be \c NULL)
530 * \param src the task which must be executed first
531 * \param dst the task you want to make depend on \a src
532 * \see SD_task_dependency_remove()
534 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
541 SD_dependency_t dependency;
543 dynar = src->tasks_after;
544 length = xbt_dynar_length(dynar);
548 "Cannot add a dependency between task '%s' and itself",
549 SD_task_get_name(src));
551 if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_schedulable(src)
552 && !__SD_task_is_scheduled_or_runnable(src) && !__SD_task_is_running(src))
554 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE"
556 SD_task_get_name(src));
558 if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_schedulable(dst)
559 && !__SD_task_is_scheduled_or_runnable(dst))
561 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
562 SD_task_get_name(dst));
564 XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s",
565 SD_task_get_name(src), SD_task_get_name(dst));
566 for (i = 0; i < length && !found; i++) {
567 xbt_dynar_get_cpy(dynar, i, &dependency);
568 found = (dependency->dst == dst);
569 XBT_DEBUG("Dependency %d: dependency->dst = %s", i,
570 SD_task_get_name(dependency->dst));
575 "A dependency already exists between task '%s' and task '%s'",
576 SD_task_get_name(src), SD_task_get_name(dst));
578 dependency = xbt_new(s_SD_dependency_t, 1);
580 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
581 dependency->data = data;
582 dependency->src = src;
583 dependency->dst = dst;
585 /* src must be executed before dst */
586 xbt_dynar_push(src->tasks_after, &dependency);
587 xbt_dynar_push(dst->tasks_before, &dependency);
589 dst->unsatisfied_dependencies++;
592 /* if the task was runnable, then dst->tasks_before is not empty anymore,
593 so we must go back to state SD_SCHEDULED */
594 if (__SD_task_is_runnable(dst)) {
596 ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
597 SD_task_get_name(dst));
598 __SD_task_set_state(dst, SD_SCHEDULED);
601 /* __SD_print_dependencies(src);
602 __SD_print_dependencies(dst); */
606 * \brief Indicates whether there is a dependency between two tasks.
609 * \param dst a task depending on \a src
611 * If src is NULL, checks whether dst has any pre-dependency.
612 * If dst is NULL, checks whether src has any post-dependency.
614 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
616 unsigned int counter;
617 SD_dependency_t dependency;
619 xbt_assert(src != NULL
621 "Invalid parameter: both src and dst are NULL");
625 xbt_dynar_foreach(src->tasks_after, counter, dependency) {
626 if (dependency->dst == dst)
630 return xbt_dynar_length(src->tasks_after);
633 return xbt_dynar_length(dst->tasks_before);
639 * \brief Remove a dependency between two tasks
642 * \param dst a task depending on \a src
643 * \see SD_task_dependency_add()
645 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
652 SD_dependency_t dependency;
654 /* remove the dependency from src->tasks_after */
655 dynar = src->tasks_after;
656 length = xbt_dynar_length(dynar);
658 for (i = 0; i < length && !found; i++) {
659 xbt_dynar_get_cpy(dynar, i, &dependency);
660 if (dependency->dst == dst) {
661 xbt_dynar_remove_at(dynar, i, NULL);
667 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
668 SD_task_get_name(src), SD_task_get_name(dst),
669 SD_task_get_name(dst), SD_task_get_name(src));
671 /* remove the dependency from dst->tasks_before */
672 dynar = dst->tasks_before;
673 length = xbt_dynar_length(dynar);
676 for (i = 0; i < length && !found; i++) {
677 xbt_dynar_get_cpy(dynar, i, &dependency);
678 if (dependency->src == src) {
679 xbt_dynar_remove_at(dynar, i, NULL);
680 __SD_task_dependency_destroy(dependency);
681 dst->unsatisfied_dependencies--;
686 /* should never happen... */
688 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
689 SD_task_get_name(dst), SD_task_get_name(src),
690 SD_task_get_name(src), SD_task_get_name(dst));
692 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
694 if (dst->unsatisfied_dependencies == 0) {
695 if (__SD_task_is_scheduled(dst))
696 __SD_task_set_state(dst, SD_RUNNABLE);
698 __SD_task_set_state(dst, SD_SCHEDULABLE);
701 if (dst->is_not_ready == 0)
702 __SD_task_set_state(dst, SD_SCHEDULABLE);
704 /* __SD_print_dependencies(src);
705 __SD_print_dependencies(dst); */
709 * \brief Returns the user data associated with a dependency between two tasks
712 * \param dst a task depending on \a src
713 * \return the user data associated with this dependency (can be \c NULL)
714 * \see SD_task_dependency_add()
716 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
723 SD_dependency_t dependency;
725 dynar = src->tasks_after;
726 length = xbt_dynar_length(dynar);
728 for (i = 0; i < length && !found; i++) {
729 xbt_dynar_get_cpy(dynar, i, &dependency);
730 found = (dependency->dst == dst);
733 THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'",
734 SD_task_get_name(src), SD_task_get_name(dst));
735 return dependency->data;
738 /* temporary function for debugging */
739 static void __SD_print_watch_points(SD_task_t task)
741 static const int state_masks[] =
742 { SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE,
745 static const char *state_names[] =
746 { "schedulable", "scheduled", "running", "runnable", "done",
751 XBT_INFO("Task '%s' watch points (%x): ", SD_task_get_name(task),
755 for (i = 0; i < 5; i++) {
756 if (task->watch_points & state_masks[i])
757 XBT_INFO("%s ", state_names[i]);
762 * \brief Adds a watch point to a task
764 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
765 * task becomes the one given in argument. The
766 * watch point is then automatically removed.
769 * \param state the \ref e_SD_task_state_t "state" you want to watch
770 * (cannot be #SD_NOT_SCHEDULED)
771 * \see SD_task_unwatch()
773 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
775 if (state & SD_NOT_SCHEDULED)
777 "Cannot add a watch point for state SD_NOT_SCHEDULED");
779 task->watch_points = task->watch_points | state;
780 /* __SD_print_watch_points(task); */
784 * \brief Removes a watch point from a task
787 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
788 * \see SD_task_watch()
790 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
792 xbt_assert(state != SD_NOT_SCHEDULED,
793 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
795 task->watch_points = task->watch_points & ~state;
796 /* __SD_print_watch_points(task); */
800 * \brief Returns an approximative estimation of the execution time of a task.
802 * The estimation is very approximative because the value returned is the time
803 * the task would take if it was executed now and if it was the only task.
805 * \param task the task to evaluate
806 * \param workstation_nb number of workstations on which the task would be executed
807 * \param workstation_list the workstations on which the task would be executed
808 * \param computation_amount computation amount for each workstation
809 * \param communication_amount communication amount between each pair of workstations
812 double SD_task_get_execution_time(SD_task_t task,
814 const SD_workstation_t *
816 const double *computation_amount,
817 const double *communication_amount)
819 double time, max_time = 0.0;
821 xbt_assert(workstation_nb > 0, "Invalid parameter");
823 /* the task execution time is the maximum execution time of the parallel tasks */
825 for (i = 0; i < workstation_nb; i++) {
827 if (computation_amount != NULL)
829 SD_workstation_get_computation_time(workstation_list[i],
830 computation_amount[i]);
832 if (communication_amount != NULL)
833 for (j = 0; j < workstation_nb; j++) {
835 SD_route_get_communication_time(workstation_list[i],
837 communication_amount[i *
842 if (time > max_time) {
849 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
851 if (!__SD_task_is_not_scheduled(task) && !__SD_task_is_schedulable(task))
852 THROWF(arg_error, 0, "Task '%s' has already been scheduled",
853 SD_task_get_name(task));
855 /* update the task state */
856 if (task->unsatisfied_dependencies == 0)
857 __SD_task_set_state(task, SD_RUNNABLE);
859 __SD_task_set_state(task, SD_SCHEDULED);
863 * \brief Schedules a task
865 * The task state must be #SD_NOT_SCHEDULED.
866 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
867 * i.e. when its dependencies are satisfied.
869 * \param task the task you want to schedule
870 * \param workstation_count number of workstations on which the task will be executed
871 * \param workstation_list the workstations on which the task will be executed
872 * \param computation_amount computation amount for each workstation
873 * \param communication_amount communication amount between each pair of workstations
874 * \param rate task execution speed rate
875 * \see SD_task_unschedule()
877 void SD_task_schedule(SD_task_t task, int workstation_count,
878 const SD_workstation_t * workstation_list,
879 const double *computation_amount,
880 const double *communication_amount, double rate)
882 int communication_nb;
883 task->workstation_nb = 0;
885 xbt_assert(workstation_count > 0, "workstation_nb must be positive");
887 task->workstation_nb = workstation_count;
890 if (computation_amount) {
891 task->computation_amount = xbt_realloc(task->computation_amount,
892 sizeof(double) * workstation_count);
893 memcpy(task->computation_amount, computation_amount,
894 sizeof(double) * workstation_count);
896 xbt_free(task->computation_amount);
897 task->computation_amount = NULL;
900 communication_nb = workstation_count * workstation_count;
901 if (communication_amount) {
902 task->communication_amount = xbt_realloc(task->communication_amount,
903 sizeof(double) * communication_nb);
904 memcpy(task->communication_amount, communication_amount,
905 sizeof(double) * communication_nb);
907 xbt_free(task->communication_amount);
908 task->communication_amount = NULL;
911 task->workstation_list =
912 xbt_realloc(task->workstation_list,
913 sizeof(SD_workstation_t) * workstation_count);
914 memcpy(task->workstation_list, workstation_list,
915 sizeof(SD_workstation_t) * workstation_count);
917 SD_task_do_schedule(task);
921 * \brief Unschedules a task
923 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
924 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
925 * Call SD_task_schedule() to schedule it again.
927 * \param task the task you want to unschedule
928 * \see SD_task_schedule()
930 void SD_task_unschedule(SD_task_t task)
932 if (task->state_set != sd_global->scheduled_task_set &&
933 task->state_set != sd_global->runnable_task_set &&
934 task->state_set != sd_global->running_task_set &&
935 task->state_set != sd_global->failed_task_set)
937 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
938 SD_task_get_name(task));
940 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
941 &&task->kind == SD_TASK_NOT_TYPED) /* Don't free scheduling data for typed tasks */
942 __SD_task_destroy_scheduling_data(task);
944 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
945 surf_workstation_model->action_cancel(task->surf_action);
947 if (task->unsatisfied_dependencies == 0)
948 __SD_task_set_state(task, SD_SCHEDULABLE);
950 __SD_task_set_state(task, SD_NOT_SCHEDULED);
952 task->remains = task->amount;
953 task->start_time = -1.0;
956 /* Destroys the data memorized by SD_task_schedule. Task state must be SD_SCHEDULED or SD_RUNNABLE.
958 static void __SD_task_destroy_scheduling_data(SD_task_t task)
960 if (!__SD_task_is_scheduled_or_runnable(task)
961 && !__SD_task_is_in_fifo(task))
963 "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
964 SD_task_get_name(task));
966 xbt_free(task->computation_amount);
967 xbt_free(task->communication_amount);
968 task->computation_amount = task->communication_amount = NULL;
971 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
972 * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
973 * the task gets out of its fifos.
975 void __SD_task_really_run(SD_task_t task)
979 void **surf_workstations;
981 xbt_assert(__SD_task_is_runnable_or_in_fifo(task),
982 "Task '%s' is not runnable or in a fifo! Task state: %d",
983 SD_task_get_name(task), (int)SD_task_get_state(task));
984 xbt_assert(task->workstation_list != NULL,
985 "Task '%s': workstation_list is NULL!",
986 SD_task_get_name(task));
990 XBT_DEBUG("Really running task '%s'", SD_task_get_name(task));
992 /* set this task as current task for the workstations in sequential mode */
993 for (i = 0; i < task->workstation_nb; i++) {
994 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
995 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
996 task->workstation_list[i]->current_task = task;
997 xbt_assert(__SD_workstation_is_busy(task->workstation_list[i]),
998 "The workstation should be busy now");
1002 XBT_DEBUG("Task '%s' set as current task for its workstations",
1003 SD_task_get_name(task));
1005 /* start the task */
1007 /* we have to create a Surf workstation array instead of the SimDag workstation array */
1008 surf_workstations = xbt_new(void *, task->workstation_nb);
1010 for (i = 0; i < task->workstation_nb; i++)
1011 surf_workstations[i] = task->workstation_list[i]->surf_workstation;
1013 /* It's allowed to pass a NULL vector as cost to mean vector of 0.0 (easing user's life). Let's deal with it */
1014 #define cost_or_zero(array,pos) ((array)?(array)[pos]:0.0)
1016 task->surf_action = NULL;
1017 if ((task->workstation_nb == 1)
1018 && (cost_or_zero(task->communication_amount, 0) == 0.0)) {
1020 surf_workstation_model->extension.
1021 workstation.execute(surf_workstations[0],
1022 cost_or_zero(task->computation_amount, 0));
1023 } else if ((task->workstation_nb == 1)
1024 && (cost_or_zero(task->computation_amount, 0) == 0.0)) {
1027 surf_workstation_model->extension.
1028 workstation.communicate(surf_workstations[0], surf_workstations[0],
1029 cost_or_zero(task->communication_amount,
1031 } else if ((task->workstation_nb == 2)
1032 && (cost_or_zero(task->computation_amount, 0) == 0.0)
1033 && (cost_or_zero(task->computation_amount, 1) == 0.0)) {
1037 for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
1038 if (cost_or_zero(task->communication_amount, i) > 0.0) {
1040 value = cost_or_zero(task->communication_amount, i);
1045 surf_workstation_model->extension.
1046 workstation.communicate(surf_workstations[0],
1047 surf_workstations[1], value, task->rate);
1052 if (!task->surf_action) {
1053 double *computation_amount = xbt_new(double, task->workstation_nb);
1054 double *communication_amount = xbt_new(double, task->workstation_nb *
1055 task->workstation_nb);
1057 memcpy(computation_amount, task->computation_amount, sizeof(double) *
1058 task->workstation_nb);
1059 memcpy(communication_amount, task->communication_amount,
1060 sizeof(double) * task->workstation_nb * task->workstation_nb);
1063 surf_workstation_model->extension.
1064 workstation.execute_parallel_task(task->workstation_nb,
1067 communication_amount,
1070 xbt_free(surf_workstations);
1073 surf_workstation_model->action_data_set(task->surf_action, task);
1075 XBT_DEBUG("surf_action = %p", task->surf_action);
1079 TRACE_surf_action(task->surf_action, task->category);
1082 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
1083 __SD_task_set_state(task, SD_RUNNING);
1084 xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
1085 SD_task_get_name(task), (int)SD_task_get_state(task));
1089 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_RUNNABLE
1090 * (ie when its dependencies are satisfied).
1091 * If one of the workstations where the task is scheduled on is busy (in sequential mode),
1092 * the task doesn't start.
1093 * Returns whether the task has started.
1095 int __SD_task_try_to_run(SD_task_t task)
1100 SD_workstation_t workstation;
1102 xbt_assert(__SD_task_is_runnable(task),
1103 "Task '%s' is not runnable! Task state: %d",
1104 SD_task_get_name(task), (int)SD_task_get_state(task));
1107 for (i = 0; i < task->workstation_nb; i++) {
1108 can_start = can_start &&
1109 !__SD_workstation_is_busy(task->workstation_list[i]);
1112 XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1114 if (!can_start) { /* if the task cannot start and is not in the fifos yet */
1115 for (i = 0; i < task->workstation_nb; i++) {
1116 workstation = task->workstation_list[i];
1117 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1118 XBT_DEBUG("Pushing task '%s' in the fifo of workstation '%s'",
1119 SD_task_get_name(task),
1120 SD_workstation_get_name(workstation));
1121 xbt_fifo_push(workstation->task_fifo, task);
1124 __SD_task_set_state(task, SD_IN_FIFO);
1125 xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1126 SD_task_get_name(task), (int)SD_task_get_state(task));
1127 XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1129 __SD_task_really_run(task);
1135 /* This function is called by SD_simulate when a task is done.
1136 * It updates task->state and task->action and executes if necessary the tasks
1137 * which were waiting in fifos for the end of `task'
1139 void __SD_task_just_done(SD_task_t task)
1142 SD_workstation_t workstation;
1144 SD_task_t candidate;
1145 int candidate_nb = 0;
1146 int candidate_capacity = 8;
1147 SD_task_t *candidates;
1150 xbt_assert(__SD_task_is_running(task),
1151 "The task must be running! Task state: %d",
1152 (int)SD_task_get_state(task));
1153 xbt_assert(task->workstation_list != NULL,
1154 "Task '%s': workstation_list is NULL!",
1155 SD_task_get_name(task));
1158 candidates = xbt_new(SD_task_t, 8);
1160 __SD_task_set_state(task, SD_DONE);
1161 surf_workstation_model->action_unref(task->surf_action);
1162 task->surf_action = NULL;
1164 XBT_DEBUG("Looking for candidates");
1166 /* if the task was executed on sequential workstations,
1167 maybe we can execute the next task of the fifo for each workstation */
1168 for (i = 0; i < task->workstation_nb; i++) {
1169 workstation = task->workstation_list[i];
1170 XBT_DEBUG("Workstation '%s': access_mode = %d",
1171 SD_workstation_get_name(workstation), (int)workstation->access_mode);
1172 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1173 xbt_assert(workstation->task_fifo != NULL,
1174 "Workstation '%s' has sequential access but no fifo!",
1175 SD_workstation_get_name(workstation));
1176 xbt_assert(workstation->current_task =
1177 task, "Workstation '%s': current task should be '%s'",
1178 SD_workstation_get_name(workstation),
1179 SD_task_get_name(task));
1181 /* the task is over so we can release the workstation */
1182 workstation->current_task = NULL;
1184 XBT_DEBUG("Getting candidate in fifo");
1186 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1187 (workstation->task_fifo));
1189 if (candidate != NULL) {
1190 XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1191 xbt_assert(__SD_task_is_in_fifo(candidate),
1192 "Bad state of candidate '%s': %d",
1193 SD_task_get_name(candidate),
1194 (int)SD_task_get_state(candidate));
1197 XBT_DEBUG("Candidate in fifo: %p", candidate);
1199 /* if there was a task waiting for my place */
1200 if (candidate != NULL) {
1201 /* Unfortunately, we are not sure yet that we can execute the task now,
1202 because the task can be waiting more deeply in some other workstation's fifos...
1203 So we memorize all candidate tasks, and then we will check for each candidate
1204 whether or not all its workstations are available. */
1206 /* realloc if necessary */
1207 if (candidate_nb == candidate_capacity) {
1208 candidate_capacity *= 2;
1210 xbt_realloc(candidates,
1211 sizeof(SD_task_t) * candidate_capacity);
1214 /* register the candidate */
1215 candidates[candidate_nb++] = candidate;
1216 candidate->fifo_checked = 0;
1221 XBT_DEBUG("Candidates found: %d", candidate_nb);
1223 /* now we check every candidate task */
1224 for (i = 0; i < candidate_nb; i++) {
1225 candidate = candidates[i];
1227 if (candidate->fifo_checked) {
1228 continue; /* we have already evaluated that task */
1231 xbt_assert(__SD_task_is_in_fifo(candidate),
1232 "Bad state of candidate '%s': %d",
1233 SD_task_get_name(candidate), (int)SD_task_get_state(candidate));
1235 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1236 workstation = candidate->workstation_list[j];
1238 /* I can start on this workstation if the workstation is shared
1239 or if I am the first task in the fifo */
1240 can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS
1242 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1243 (workstation->task_fifo));
1246 XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1249 /* now we are sure that I can start! */
1251 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1252 workstation = candidate->workstation_list[j];
1254 /* update the fifo */
1255 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1256 candidate = xbt_fifo_shift(workstation->task_fifo); /* the return value is stored just for debugging */
1257 XBT_DEBUG("Head of the fifo: '%s'",
1259 NULL) ? SD_task_get_name(candidate) : "NULL");
1260 xbt_assert(candidate == candidates[i],
1261 "Error in __SD_task_just_done: bad first task in the fifo");
1263 } /* for each workstation */
1265 /* finally execute the task */
1266 XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1267 (int)SD_task_get_state(candidate));
1268 __SD_task_really_run(candidate);
1271 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1272 SD_task_get_name(candidate), candidate->state_set,
1273 sd_global->running_task_set, __SD_task_is_running(candidate));
1274 xbt_assert(__SD_task_is_running(candidate),
1275 "Bad state of task '%s': %d",
1276 SD_task_get_name(candidate),
1277 (int)SD_task_get_state(candidate));
1278 XBT_DEBUG("Okay, the task is running.");
1281 candidate->fifo_checked = 1;
1282 } /* for each candidate */
1284 xbt_free(candidates);
1287 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1289 static void __SD_task_remove_dependencies(SD_task_t task)
1291 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1292 because each one is stored twice */
1293 SD_dependency_t dependency;
1294 while (!xbt_dynar_is_empty(task->tasks_before)) {
1295 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1296 SD_task_dependency_remove(dependency->src, dependency->dst);
1299 while (!xbt_dynar_is_empty(task->tasks_after)) {
1300 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1301 SD_task_dependency_remove(dependency->src, dependency->dst);
1306 * \brief Returns the start time of a task
1308 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1310 * \param task: a task
1311 * \return the start time of this task
1313 double SD_task_get_start_time(SD_task_t task)
1315 if (task->surf_action)
1316 return surf_workstation_model->
1317 action_get_start_time(task->surf_action);
1319 return task->start_time;
1323 * \brief Returns the finish time of a task
1325 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1326 * If the state is not completed yet, the returned value is an
1327 * estimation of the task finish time. This value can fluctuate
1328 * until the task is completed.
1330 * \param task: a task
1331 * \return the start time of this task
1333 double SD_task_get_finish_time(SD_task_t task)
1335 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1336 return surf_workstation_model->
1337 action_get_finish_time(task->surf_action);
1339 return task->finish_time;
1344 void SD_task_distribute_comp_amdhal(SD_task_t task, int ws_count)
1347 xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1348 "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1349 "Cannot use this function.",
1350 SD_task_get_name(task));
1352 task->computation_amount = xbt_new0(double, ws_count);
1353 task->communication_amount = xbt_new0(double, ws_count * ws_count);
1354 task->workstation_nb = ws_count;
1355 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1357 for(i=0;i<ws_count;i++){
1358 task->computation_amount[i] =
1359 (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1363 /** @brief Auto-schedules a task.
1365 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1366 * allows to specify the task costs at creation, and decorelate them from the
1367 * scheduling process where you just specify which resource should deliver the
1370 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1371 * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1375 * We should create tasks kind for the following categories:
1376 * - Point to point communication (done)
1377 * - Sequential computation (done)
1378 * - group communication (redistribution, several kinds)
1379 * - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1380 * - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1382 void SD_task_schedulev(SD_task_t task, int count,
1383 const SD_workstation_t * list)
1386 SD_dependency_t dep;
1388 xbt_assert(task->kind != 0,
1389 "Task %s is not typed. Cannot automatically schedule it.",
1390 SD_task_get_name(task));
1391 switch (task->kind) {
1392 case SD_TASK_COMM_E2E:
1393 case SD_TASK_COMP_PAR_AMDAHL:
1394 xbt_assert(task->computation_amount, "SD_task_distribute_comp_amdhal should be called first.");
1395 case SD_TASK_COMP_SEQ:
1396 xbt_assert(task->workstation_nb == count,"Got %d locations, but were expecting %d locations",count,task->workstation_nb);
1397 for (i = 0; i < count; i++)
1398 task->workstation_list[i] = list[i];
1399 SD_task_do_schedule(task);
1402 xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1403 SD_task_get_name(task));
1405 if (task->kind == SD_TASK_COMM_E2E) {
1406 XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1407 SD_task_get_name(task),
1408 SD_workstation_get_name(task->workstation_list[0]),
1409 SD_workstation_get_name(task->workstation_list[1]),
1410 task->communication_amount[2]);
1413 if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1414 XBT_VERB("Schedule computation task %s on %d hosts. It costs %.f flops on each host",
1415 SD_task_get_name(task),
1416 task->workstation_nb,
1417 task->computation_amount[0]);
1420 /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if runnable) */
1421 if (task->kind == SD_TASK_COMP_SEQ) {
1422 XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1423 SD_task_get_name(task),
1424 SD_workstation_get_name(task->workstation_list[0]),
1425 task->computation_amount[0]);
1427 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1428 SD_task_t before = dep->src;
1429 if (before->kind == SD_TASK_COMM_E2E) {
1430 before->workstation_list[1] = task->workstation_list[0];
1432 if (before->workstation_list[0] &&
1433 (__SD_task_is_schedulable(before)
1434 || __SD_task_is_not_scheduled(before))) {
1435 SD_task_do_schedule(before);
1437 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1438 SD_task_get_name(before),
1439 SD_workstation_get_name(before->workstation_list[0]),
1440 SD_workstation_get_name(before->workstation_list[1]),
1441 before->communication_amount[2]);
1445 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1446 SD_task_t after = dep->dst;
1447 if (after->kind == SD_TASK_COMM_E2E) {
1448 after->workstation_list[0] = task->workstation_list[0];
1449 //J-N : Why did you comment on these line (this comment add a bug I think)?
1450 if (after->workstation_list[1]
1451 && (__SD_task_is_not_scheduled(after)
1452 || __SD_task_is_schedulable(after))) {
1453 SD_task_do_schedule(after);
1455 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1456 SD_task_get_name(after),
1457 SD_workstation_get_name(after->workstation_list[0]),
1458 SD_workstation_get_name(after->workstation_list[1]),
1459 after->communication_amount[2]);
1467 /** @brief autoschedule a task on a list of workstations
1469 * This function is very similar to SD_task_schedulev(),
1470 * but takes the list of workstations to schedule onto as separate parameters.
1471 * It builds a proper vector of workstations and then call SD_task_schedulev()
1473 void SD_task_schedulel(SD_task_t task, int count, ...)
1476 SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1478 va_start(ap, count);
1479 for (i = 0; i < count; i++) {
1480 list[i] = va_arg(ap, SD_workstation_t);
1483 SD_task_schedulev(task, count, list);
1488 * \brief Sets the tracing category of a task.
1490 * This function should be called after the creation of a
1491 * SimDAG task, to define the category of that task. The first
1492 * parameter must contain a task that was created with the
1493 * function #SD_task_create. The second parameter must contain
1494 * a category that was previously declared with the function
1497 * \param task The task to be considered
1498 * \param category the name of the category to be associated to the task
1500 * \see SD_task_get_category, TRACE_category, TRACE_category_with_color
1502 void SD_task_set_category (SD_task_t task, const char *category)
1505 if (!TRACE_is_enabled()) return;
1506 if (task == NULL) return;
1507 if (category == NULL){
1508 if (task->category) xbt_free (task->category);
1509 task->category = NULL;
1511 task->category = xbt_strdup (category);
1517 * \brief Gets the current tracing category of a task.
1519 * \param task The task to be considered
1521 * \see SD_task_set_category
1523 * \return Returns the name of the tracing category of the given task, NULL otherwise
1525 const char *SD_task_get_category (SD_task_t task)
1528 return task->category;