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 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 Returns the state of a task
256 * \return the current \ref e_SD_task_state_t "state" of this task:
257 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
258 * \see e_SD_task_state_t
260 e_SD_task_state_t SD_task_get_state(SD_task_t task)
265 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
267 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
269 xbt_swag_remove(task, task->state_set);
271 case SD_NOT_SCHEDULED:
272 task->state_set = sd_global->not_scheduled_task_set;
275 task->state_set = sd_global->schedulable_task_set;
278 task->state_set = sd_global->scheduled_task_set;
281 task->state_set = sd_global->runnable_task_set;
284 task->state_set = sd_global->in_fifo_task_set;
287 task->state_set = sd_global->running_task_set;
289 surf_workstation_model->action_get_start_time(task->surf_action);
292 task->state_set = sd_global->done_task_set;
294 surf_workstation_model->action_get_finish_time(task->surf_action);
297 jedule_log_sd_event(task);
301 task->state_set = sd_global->failed_task_set;
304 xbt_die( "Invalid state");
306 xbt_swag_insert(task, task->state_set);
307 task->state = new_state;
309 if (task->watch_points & new_state) {
310 XBT_VERB("Watch point reached with task '%s'!", SD_task_get_name(task));
311 sd_global->watch_point_reached = 1;
312 SD_task_unwatch(task, new_state); /* remove the watch point */
317 * \brief Returns the name of a task
320 * \return the name of this task (can be \c NULL)
322 const char *SD_task_get_name(SD_task_t task)
327 /** @brief Allows to change the name of a task */
328 void SD_task_set_name(SD_task_t task, const char *name)
330 xbt_free(task->name);
331 task->name = xbt_strdup(name);
334 /** @brief Returns the dynar of the parents of a task
337 * \return a newly allocated dynar comprising the parents of this task
340 xbt_dynar_t SD_task_get_parents(SD_task_t task)
346 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
347 xbt_dynar_foreach(task->tasks_before, i, dep) {
348 xbt_dynar_push(parents, &(dep->src));
353 /** @brief Returns the dynar of the parents of a task
356 * \return a newly allocated dynar comprising the parents of this task
358 xbt_dynar_t SD_task_get_children(SD_task_t task)
361 xbt_dynar_t children;
364 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
365 xbt_dynar_foreach(task->tasks_after, i, dep) {
366 xbt_dynar_push(children, &(dep->dst));
372 * \brief Returns the amount of workstations involved in a task
374 * Only call this on already scheduled tasks!
377 int SD_task_get_workstation_count(SD_task_t task)
379 return task->workstation_nb;
383 * \brief Returns the list of workstations involved in a task
385 * Only call this on already scheduled tasks!
388 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
390 return task->workstation_list;
394 * \brief Returns the total amount of work contained in a task
397 * \return the total amount of work (computation or data transfer) for this task
398 * \see SD_task_get_remaining_amount()
400 double SD_task_get_amount(SD_task_t task)
406 * \brief Returns the remaining amount work to do till the completion of a task
409 * \return the remaining amount of work (computation or data transfer) of this task
410 * \see SD_task_get_amount()
412 double SD_task_get_remaining_amount(SD_task_t task)
414 if (task->surf_action)
415 return surf_workstation_model->get_remains(task->surf_action);
417 return task->remains;
420 int SD_task_get_kind(SD_task_t task)
425 /** @brief Displays debugging informations about a task */
426 void SD_task_dump(SD_task_t task)
428 unsigned int counter;
429 SD_dependency_t dependency;
432 XBT_INFO("Displaying task %s", SD_task_get_name(task));
433 statename = bprintf("%s %s %s %s %s %s %s %s",
434 (task->state & SD_NOT_SCHEDULED ? "not scheduled" :
436 (task->state & SD_SCHEDULABLE ? "schedulable" : ""),
437 (task->state & SD_SCHEDULED ? "scheduled" : ""),
438 (task->state & SD_RUNNABLE ? "runnable" :
440 (task->state & SD_IN_FIFO ? "in fifo" : ""),
441 (task->state & SD_RUNNING ? "running" : ""),
442 (task->state & SD_DONE ? "done" : ""),
443 (task->state & SD_FAILED ? "failed" : ""));
444 XBT_INFO(" - state: %s", statename);
447 if (task->kind != 0) {
448 switch (task->kind) {
449 case SD_TASK_COMM_E2E:
450 XBT_INFO(" - kind: end-to-end communication");
452 case SD_TASK_COMP_SEQ:
453 XBT_INFO(" - kind: sequential computation");
455 case SD_TASK_COMP_PAR_AMDAHL:
456 XBT_INFO(" - kind: parallel computation following Amdahl's law");
459 XBT_INFO(" - (unknown kind %d)", task->kind);
462 XBT_INFO(" - amount: %.0f", SD_task_get_amount(task));
463 XBT_INFO(" - Dependencies to satisfy: %u", task->unsatisfied_dependencies);
464 if (!xbt_dynar_is_empty(task->tasks_before)) {
465 XBT_INFO(" - pre-dependencies:");
466 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
467 XBT_INFO(" %s", SD_task_get_name(dependency->src));
470 if (!xbt_dynar_is_empty(task->tasks_after)) {
471 XBT_INFO(" - post-dependencies:");
472 xbt_dynar_foreach(task->tasks_after, counter, dependency) {
473 XBT_INFO(" %s", SD_task_get_name(dependency->dst));
478 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
479 void SD_task_dotty(SD_task_t task, void *out)
481 unsigned int counter;
482 SD_dependency_t dependency;
483 fprintf(out, " T%p [label=\"%.20s\"", task, task->name);
484 switch (task->kind) {
485 case SD_TASK_COMM_E2E:
486 fprintf(out, ", shape=box");
488 case SD_TASK_COMP_SEQ:
489 fprintf(out, ", shape=circle");
492 xbt_die("Unknown task type!");
494 fprintf(out, "];\n");
495 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
496 fprintf(out, " T%p -> T%p;\n", dependency->src, dependency->dst);
500 /* Destroys a dependency between two tasks.
502 static void __SD_task_dependency_destroy(void *dependency)
504 xbt_free(((SD_dependency_t)dependency)->name);
505 xbt_free(dependency);
509 * \brief Adds a dependency between two tasks
511 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
512 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
514 * \param name the name of the new dependency (can be \c NULL)
515 * \param data the user data you want to associate with this dependency (can be \c NULL)
516 * \param src the task which must be executed first
517 * \param dst the task you want to make depend on \a src
518 * \see SD_task_dependency_remove()
520 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
527 SD_dependency_t dependency;
529 dynar = src->tasks_after;
530 length = xbt_dynar_length(dynar);
534 "Cannot add a dependency between task '%s' and itself",
535 SD_task_get_name(src));
537 if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_schedulable(src)
538 && !__SD_task_is_scheduled_or_runnable(src) && !__SD_task_is_running(src))
540 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE"
542 SD_task_get_name(src));
544 if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_schedulable(dst)
545 && !__SD_task_is_scheduled_or_runnable(dst))
547 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
548 SD_task_get_name(dst));
550 XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s",
551 SD_task_get_name(src), SD_task_get_name(dst));
552 for (i = 0; i < length && !found; i++) {
553 xbt_dynar_get_cpy(dynar, i, &dependency);
554 found = (dependency->dst == dst);
555 XBT_DEBUG("Dependency %d: dependency->dst = %s", i,
556 SD_task_get_name(dependency->dst));
561 "A dependency already exists between task '%s' and task '%s'",
562 SD_task_get_name(src), SD_task_get_name(dst));
564 dependency = xbt_new(s_SD_dependency_t, 1);
566 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
567 dependency->data = data;
568 dependency->src = src;
569 dependency->dst = dst;
571 /* src must be executed before dst */
572 xbt_dynar_push(src->tasks_after, &dependency);
573 xbt_dynar_push(dst->tasks_before, &dependency);
575 dst->unsatisfied_dependencies++;
578 /* if the task was runnable, then dst->tasks_before is not empty anymore,
579 so we must go back to state SD_SCHEDULED */
580 if (__SD_task_is_runnable(dst)) {
582 ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
583 SD_task_get_name(dst));
584 __SD_task_set_state(dst, SD_SCHEDULED);
587 /* __SD_print_dependencies(src);
588 __SD_print_dependencies(dst); */
592 * \brief Indicates whether there is a dependency between two tasks.
595 * \param dst a task depending on \a src
597 * If src is NULL, checks whether dst has any pre-dependency.
598 * If dst is NULL, checks whether src has any post-dependency.
600 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
602 unsigned int counter;
603 SD_dependency_t dependency;
605 xbt_assert(src != NULL
607 "Invalid parameter: both src and dst are NULL");
611 xbt_dynar_foreach(src->tasks_after, counter, dependency) {
612 if (dependency->dst == dst)
616 return xbt_dynar_length(src->tasks_after);
619 return xbt_dynar_length(dst->tasks_before);
625 * \brief Remove a dependency between two tasks
628 * \param dst a task depending on \a src
629 * \see SD_task_dependency_add()
631 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
638 SD_dependency_t dependency;
640 /* remove the dependency from src->tasks_after */
641 dynar = src->tasks_after;
642 length = xbt_dynar_length(dynar);
644 for (i = 0; i < length && !found; i++) {
645 xbt_dynar_get_cpy(dynar, i, &dependency);
646 if (dependency->dst == dst) {
647 xbt_dynar_remove_at(dynar, i, NULL);
653 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
654 SD_task_get_name(src), SD_task_get_name(dst),
655 SD_task_get_name(dst), SD_task_get_name(src));
657 /* remove the dependency from dst->tasks_before */
658 dynar = dst->tasks_before;
659 length = xbt_dynar_length(dynar);
662 for (i = 0; i < length && !found; i++) {
663 xbt_dynar_get_cpy(dynar, i, &dependency);
664 if (dependency->src == src) {
665 xbt_dynar_remove_at(dynar, i, NULL);
666 __SD_task_dependency_destroy(dependency);
667 dst->unsatisfied_dependencies--;
672 /* should never happen... */
674 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
675 SD_task_get_name(dst), SD_task_get_name(src),
676 SD_task_get_name(src), SD_task_get_name(dst));
678 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
680 if (dst->unsatisfied_dependencies == 0) {
681 if (__SD_task_is_scheduled(dst))
682 __SD_task_set_state(dst, SD_RUNNABLE);
684 __SD_task_set_state(dst, SD_SCHEDULABLE);
687 if (dst->is_not_ready == 0)
688 __SD_task_set_state(dst, SD_SCHEDULABLE);
690 /* __SD_print_dependencies(src);
691 __SD_print_dependencies(dst); */
695 * \brief Returns the user data associated with a dependency between two tasks
698 * \param dst a task depending on \a src
699 * \return the user data associated with this dependency (can be \c NULL)
700 * \see SD_task_dependency_add()
702 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
709 SD_dependency_t dependency;
711 dynar = src->tasks_after;
712 length = xbt_dynar_length(dynar);
714 for (i = 0; i < length && !found; i++) {
715 xbt_dynar_get_cpy(dynar, i, &dependency);
716 found = (dependency->dst == dst);
719 THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'",
720 SD_task_get_name(src), SD_task_get_name(dst));
721 return dependency->data;
724 /* temporary function for debugging */
725 static void __SD_print_watch_points(SD_task_t task)
727 static const int state_masks[] =
728 { SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE,
731 static const char *state_names[] =
732 { "schedulable", "scheduled", "running", "runnable", "done",
737 XBT_INFO("Task '%s' watch points (%x): ", SD_task_get_name(task),
741 for (i = 0; i < 5; i++) {
742 if (task->watch_points & state_masks[i])
743 XBT_INFO("%s ", state_names[i]);
748 * \brief Adds a watch point to a task
750 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
751 * task becomes the one given in argument. The
752 * watch point is then automatically removed.
755 * \param state the \ref e_SD_task_state_t "state" you want to watch
756 * (cannot be #SD_NOT_SCHEDULED)
757 * \see SD_task_unwatch()
759 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
761 if (state & SD_NOT_SCHEDULED)
763 "Cannot add a watch point for state SD_NOT_SCHEDULED");
765 task->watch_points = task->watch_points | state;
766 /* __SD_print_watch_points(task); */
770 * \brief Removes a watch point from a task
773 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
774 * \see SD_task_watch()
776 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
778 xbt_assert(state != SD_NOT_SCHEDULED,
779 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
781 task->watch_points = task->watch_points & ~state;
782 /* __SD_print_watch_points(task); */
786 * \brief Returns an approximative estimation of the execution time of a task.
788 * The estimation is very approximative because the value returned is the time
789 * the task would take if it was executed now and if it was the only task.
791 * \param task the task to evaluate
792 * \param workstation_nb number of workstations on which the task would be executed
793 * \param workstation_list the workstations on which the task would be executed
794 * \param computation_amount computation amount for each workstation
795 * \param communication_amount communication amount between each pair of workstations
798 double SD_task_get_execution_time(SD_task_t task,
800 const SD_workstation_t *
802 const double *computation_amount,
803 const double *communication_amount)
805 double time, max_time = 0.0;
807 xbt_assert(workstation_nb > 0, "Invalid parameter");
809 /* the task execution time is the maximum execution time of the parallel tasks */
811 for (i = 0; i < workstation_nb; i++) {
813 if (computation_amount != NULL)
815 SD_workstation_get_computation_time(workstation_list[i],
816 computation_amount[i]);
818 if (communication_amount != NULL)
819 for (j = 0; j < workstation_nb; j++) {
821 SD_route_get_communication_time(workstation_list[i],
823 communication_amount[i *
828 if (time > max_time) {
835 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
837 if (!__SD_task_is_not_scheduled(task) && !__SD_task_is_schedulable(task))
838 THROWF(arg_error, 0, "Task '%s' has already been scheduled",
839 SD_task_get_name(task));
841 /* update the task state */
842 if (task->unsatisfied_dependencies == 0)
843 __SD_task_set_state(task, SD_RUNNABLE);
845 __SD_task_set_state(task, SD_SCHEDULED);
849 * \brief Schedules a task
851 * The task state must be #SD_NOT_SCHEDULED.
852 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
853 * i.e. when its dependencies are satisfied.
855 * \param task the task you want to schedule
856 * \param workstation_count number of workstations on which the task will be executed
857 * \param workstation_list the workstations on which the task will be executed
858 * \param computation_amount computation amount for each workstation
859 * \param communication_amount communication amount between each pair of workstations
860 * \param rate task execution speed rate
861 * \see SD_task_unschedule()
863 void SD_task_schedule(SD_task_t task, int workstation_count,
864 const SD_workstation_t * workstation_list,
865 const double *computation_amount,
866 const double *communication_amount, double rate)
868 int communication_nb;
869 task->workstation_nb = 0;
871 xbt_assert(workstation_count > 0, "workstation_nb must be positive");
873 task->workstation_nb = workstation_count;
876 if (computation_amount) {
877 task->computation_amount = xbt_realloc(task->computation_amount,
878 sizeof(double) * workstation_count);
879 memcpy(task->computation_amount, computation_amount,
880 sizeof(double) * workstation_count);
882 xbt_free(task->computation_amount);
883 task->computation_amount = NULL;
886 communication_nb = workstation_count * workstation_count;
887 if (communication_amount) {
888 task->communication_amount = xbt_realloc(task->communication_amount,
889 sizeof(double) * communication_nb);
890 memcpy(task->communication_amount, communication_amount,
891 sizeof(double) * communication_nb);
893 xbt_free(task->communication_amount);
894 task->communication_amount = NULL;
897 task->workstation_list =
898 xbt_realloc(task->workstation_list,
899 sizeof(SD_workstation_t) * workstation_count);
900 memcpy(task->workstation_list, workstation_list,
901 sizeof(SD_workstation_t) * workstation_count);
903 SD_task_do_schedule(task);
907 * \brief Unschedules a task
909 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
910 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
911 * Call SD_task_schedule() to schedule it again.
913 * \param task the task you want to unschedule
914 * \see SD_task_schedule()
916 void SD_task_unschedule(SD_task_t task)
918 if (task->state_set != sd_global->scheduled_task_set &&
919 task->state_set != sd_global->runnable_task_set &&
920 task->state_set != sd_global->running_task_set &&
921 task->state_set != sd_global->failed_task_set)
923 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
924 SD_task_get_name(task));
926 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
927 &&task->kind == SD_TASK_NOT_TYPED) /* Don't free scheduling data for typed tasks */
928 __SD_task_destroy_scheduling_data(task);
930 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
931 surf_workstation_model->action_cancel(task->surf_action);
933 if (task->unsatisfied_dependencies == 0)
934 __SD_task_set_state(task, SD_SCHEDULABLE);
936 __SD_task_set_state(task, SD_NOT_SCHEDULED);
938 task->remains = task->amount;
939 task->start_time = -1.0;
942 /* Destroys the data memorized by SD_task_schedule. Task state must be SD_SCHEDULED or SD_RUNNABLE.
944 static void __SD_task_destroy_scheduling_data(SD_task_t task)
946 if (!__SD_task_is_scheduled_or_runnable(task)
947 && !__SD_task_is_in_fifo(task))
949 "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
950 SD_task_get_name(task));
952 xbt_free(task->computation_amount);
953 xbt_free(task->communication_amount);
954 task->computation_amount = task->communication_amount = NULL;
957 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
958 * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
959 * the task gets out of its fifos.
961 void __SD_task_really_run(SD_task_t task)
965 void **surf_workstations;
967 xbt_assert(__SD_task_is_runnable_or_in_fifo(task),
968 "Task '%s' is not runnable or in a fifo! Task state: %d",
969 SD_task_get_name(task), (int)SD_task_get_state(task));
970 xbt_assert(task->workstation_list != NULL,
971 "Task '%s': workstation_list is NULL!",
972 SD_task_get_name(task));
976 XBT_DEBUG("Really running task '%s'", SD_task_get_name(task));
978 /* set this task as current task for the workstations in sequential mode */
979 for (i = 0; i < task->workstation_nb; i++) {
980 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
981 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
982 task->workstation_list[i]->current_task = task;
983 xbt_assert(__SD_workstation_is_busy(task->workstation_list[i]),
984 "The workstation should be busy now");
988 XBT_DEBUG("Task '%s' set as current task for its workstations",
989 SD_task_get_name(task));
993 /* we have to create a Surf workstation array instead of the SimDag workstation array */
994 surf_workstations = xbt_new(void *, task->workstation_nb);
996 for (i = 0; i < task->workstation_nb; i++)
997 surf_workstations[i] = task->workstation_list[i]->surf_workstation;
999 /* 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 */
1000 #define cost_or_zero(array,pos) ((array)?(array)[pos]:0.0)
1002 task->surf_action = NULL;
1003 if ((task->workstation_nb == 1)
1004 && (cost_or_zero(task->communication_amount, 0) == 0.0)) {
1006 surf_workstation_model->extension.
1007 workstation.execute(surf_workstations[0],
1008 cost_or_zero(task->computation_amount, 0));
1009 } else if ((task->workstation_nb == 1)
1010 && (cost_or_zero(task->computation_amount, 0) == 0.0)) {
1013 surf_workstation_model->extension.
1014 workstation.communicate(surf_workstations[0], surf_workstations[0],
1015 cost_or_zero(task->communication_amount,
1017 } else if ((task->workstation_nb == 2)
1018 && (cost_or_zero(task->computation_amount, 0) == 0.0)
1019 && (cost_or_zero(task->computation_amount, 1) == 0.0)) {
1023 for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
1024 if (cost_or_zero(task->communication_amount, i) > 0.0) {
1026 value = cost_or_zero(task->communication_amount, i);
1031 surf_workstation_model->extension.
1032 workstation.communicate(surf_workstations[0],
1033 surf_workstations[1], value, task->rate);
1038 if (!task->surf_action) {
1039 double *computation_amount = xbt_new(double, task->workstation_nb);
1040 double *communication_amount = xbt_new(double, task->workstation_nb *
1041 task->workstation_nb);
1043 memcpy(computation_amount, task->computation_amount, sizeof(double) *
1044 task->workstation_nb);
1045 memcpy(communication_amount, task->communication_amount,
1046 sizeof(double) * task->workstation_nb * task->workstation_nb);
1049 surf_workstation_model->extension.
1050 workstation.execute_parallel_task(task->workstation_nb,
1053 communication_amount,
1056 xbt_free(surf_workstations);
1059 surf_workstation_model->action_data_set(task->surf_action, task);
1061 XBT_DEBUG("surf_action = %p", task->surf_action);
1065 TRACE_surf_action(task->surf_action, task->category);
1068 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
1069 __SD_task_set_state(task, SD_RUNNING);
1070 xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
1071 SD_task_get_name(task), (int)SD_task_get_state(task));
1075 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_RUNNABLE
1076 * (ie when its dependencies are satisfied).
1077 * If one of the workstations where the task is scheduled on is busy (in sequential mode),
1078 * the task doesn't start.
1079 * Returns whether the task has started.
1081 int __SD_task_try_to_run(SD_task_t task)
1086 SD_workstation_t workstation;
1088 xbt_assert(__SD_task_is_runnable(task),
1089 "Task '%s' is not runnable! Task state: %d",
1090 SD_task_get_name(task), (int)SD_task_get_state(task));
1093 for (i = 0; i < task->workstation_nb; i++) {
1094 can_start = can_start &&
1095 !__SD_workstation_is_busy(task->workstation_list[i]);
1098 XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1100 if (!can_start) { /* if the task cannot start and is not in the fifos yet */
1101 for (i = 0; i < task->workstation_nb; i++) {
1102 workstation = task->workstation_list[i];
1103 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1104 XBT_DEBUG("Pushing task '%s' in the fifo of workstation '%s'",
1105 SD_task_get_name(task),
1106 SD_workstation_get_name(workstation));
1107 xbt_fifo_push(workstation->task_fifo, task);
1110 __SD_task_set_state(task, SD_IN_FIFO);
1111 xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1112 SD_task_get_name(task), (int)SD_task_get_state(task));
1113 XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1115 __SD_task_really_run(task);
1121 /* This function is called by SD_simulate when a task is done.
1122 * It updates task->state and task->action and executes if necessary the tasks
1123 * which were waiting in fifos for the end of `task'
1125 void __SD_task_just_done(SD_task_t task)
1128 SD_workstation_t workstation;
1130 SD_task_t candidate;
1131 int candidate_nb = 0;
1132 int candidate_capacity = 8;
1133 SD_task_t *candidates;
1136 xbt_assert(__SD_task_is_running(task),
1137 "The task must be running! Task state: %d",
1138 (int)SD_task_get_state(task));
1139 xbt_assert(task->workstation_list != NULL,
1140 "Task '%s': workstation_list is NULL!",
1141 SD_task_get_name(task));
1144 candidates = xbt_new(SD_task_t, 8);
1146 __SD_task_set_state(task, SD_DONE);
1147 surf_workstation_model->action_unref(task->surf_action);
1148 task->surf_action = NULL;
1150 XBT_DEBUG("Looking for candidates");
1152 /* if the task was executed on sequential workstations,
1153 maybe we can execute the next task of the fifo for each workstation */
1154 for (i = 0; i < task->workstation_nb; i++) {
1155 workstation = task->workstation_list[i];
1156 XBT_DEBUG("Workstation '%s': access_mode = %d",
1157 SD_workstation_get_name(workstation), (int)workstation->access_mode);
1158 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1159 xbt_assert(workstation->task_fifo != NULL,
1160 "Workstation '%s' has sequential access but no fifo!",
1161 SD_workstation_get_name(workstation));
1162 xbt_assert(workstation->current_task =
1163 task, "Workstation '%s': current task should be '%s'",
1164 SD_workstation_get_name(workstation),
1165 SD_task_get_name(task));
1167 /* the task is over so we can release the workstation */
1168 workstation->current_task = NULL;
1170 XBT_DEBUG("Getting candidate in fifo");
1172 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1173 (workstation->task_fifo));
1175 if (candidate != NULL) {
1176 XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1177 xbt_assert(__SD_task_is_in_fifo(candidate),
1178 "Bad state of candidate '%s': %d",
1179 SD_task_get_name(candidate),
1180 (int)SD_task_get_state(candidate));
1183 XBT_DEBUG("Candidate in fifo: %p", candidate);
1185 /* if there was a task waiting for my place */
1186 if (candidate != NULL) {
1187 /* Unfortunately, we are not sure yet that we can execute the task now,
1188 because the task can be waiting more deeply in some other workstation's fifos...
1189 So we memorize all candidate tasks, and then we will check for each candidate
1190 whether or not all its workstations are available. */
1192 /* realloc if necessary */
1193 if (candidate_nb == candidate_capacity) {
1194 candidate_capacity *= 2;
1196 xbt_realloc(candidates,
1197 sizeof(SD_task_t) * candidate_capacity);
1200 /* register the candidate */
1201 candidates[candidate_nb++] = candidate;
1202 candidate->fifo_checked = 0;
1207 XBT_DEBUG("Candidates found: %d", candidate_nb);
1209 /* now we check every candidate task */
1210 for (i = 0; i < candidate_nb; i++) {
1211 candidate = candidates[i];
1213 if (candidate->fifo_checked) {
1214 continue; /* we have already evaluated that task */
1217 xbt_assert(__SD_task_is_in_fifo(candidate),
1218 "Bad state of candidate '%s': %d",
1219 SD_task_get_name(candidate), (int)SD_task_get_state(candidate));
1221 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1222 workstation = candidate->workstation_list[j];
1224 /* I can start on this workstation if the workstation is shared
1225 or if I am the first task in the fifo */
1226 can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS
1228 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1229 (workstation->task_fifo));
1232 XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1235 /* now we are sure that I can start! */
1237 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1238 workstation = candidate->workstation_list[j];
1240 /* update the fifo */
1241 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1242 candidate = xbt_fifo_shift(workstation->task_fifo); /* the return value is stored just for debugging */
1243 XBT_DEBUG("Head of the fifo: '%s'",
1245 NULL) ? SD_task_get_name(candidate) : "NULL");
1246 xbt_assert(candidate == candidates[i],
1247 "Error in __SD_task_just_done: bad first task in the fifo");
1249 } /* for each workstation */
1251 /* finally execute the task */
1252 XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1253 (int)SD_task_get_state(candidate));
1254 __SD_task_really_run(candidate);
1257 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1258 SD_task_get_name(candidate), candidate->state_set,
1259 sd_global->running_task_set, __SD_task_is_running(candidate));
1260 xbt_assert(__SD_task_is_running(candidate),
1261 "Bad state of task '%s': %d",
1262 SD_task_get_name(candidate),
1263 (int)SD_task_get_state(candidate));
1264 XBT_DEBUG("Okay, the task is running.");
1267 candidate->fifo_checked = 1;
1268 } /* for each candidate */
1270 xbt_free(candidates);
1273 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1275 static void __SD_task_remove_dependencies(SD_task_t task)
1277 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1278 because each one is stored twice */
1279 SD_dependency_t dependency;
1280 while (!xbt_dynar_is_empty(task->tasks_before)) {
1281 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1282 SD_task_dependency_remove(dependency->src, dependency->dst);
1285 while (!xbt_dynar_is_empty(task->tasks_after)) {
1286 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1287 SD_task_dependency_remove(dependency->src, dependency->dst);
1292 * \brief Returns the start time of a task
1294 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1296 * \param task: a task
1297 * \return the start time of this task
1299 double SD_task_get_start_time(SD_task_t task)
1301 if (task->surf_action)
1302 return surf_workstation_model->
1303 action_get_start_time(task->surf_action);
1305 return task->start_time;
1309 * \brief Returns the finish time of a task
1311 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1312 * If the state is not completed yet, the returned value is an
1313 * estimation of the task finish time. This value can fluctuate
1314 * until the task is completed.
1316 * \param task: a task
1317 * \return the start time of this task
1319 double SD_task_get_finish_time(SD_task_t task)
1321 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1322 return surf_workstation_model->
1323 action_get_finish_time(task->surf_action);
1325 return task->finish_time;
1330 void SD_task_distribute_comp_amdhal(SD_task_t task, int ws_count)
1333 xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1334 "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1335 "Cannot use this function.",
1336 SD_task_get_name(task));
1338 task->computation_amount = xbt_new0(double, ws_count);
1339 task->communication_amount = xbt_new0(double, ws_count * ws_count);
1340 task->workstation_nb = ws_count;
1341 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1343 for(i=0;i<ws_count;i++){
1344 task->computation_amount[i] =
1345 (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1349 /** @brief Auto-schedules a task.
1351 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1352 * allows to specify the task costs at creation, and decorelate them from the
1353 * scheduling process where you just specify which resource should deliver the
1356 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1357 * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1361 * We should create tasks kind for the following categories:
1362 * - Point to point communication (done)
1363 * - Sequential computation (done)
1364 * - group communication (redistribution, several kinds)
1365 * - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1366 * - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1368 void SD_task_schedulev(SD_task_t task, int count,
1369 const SD_workstation_t * list)
1372 SD_dependency_t dep;
1374 xbt_assert(task->kind != 0,
1375 "Task %s is not typed. Cannot automatically schedule it.",
1376 SD_task_get_name(task));
1377 switch (task->kind) {
1378 case SD_TASK_COMM_E2E:
1379 case SD_TASK_COMP_PAR_AMDAHL:
1380 xbt_assert(task->computation_amount, "SD_task_distribute_comp_amdhal should be called first.");
1381 case SD_TASK_COMP_SEQ:
1382 xbt_assert(task->workstation_nb == count,"Got %d locations, but were expecting %d locations",count,task->workstation_nb);
1383 for (i = 0; i < count; i++)
1384 task->workstation_list[i] = list[i];
1385 SD_task_do_schedule(task);
1388 xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1389 SD_task_get_name(task));
1391 if (task->kind == SD_TASK_COMM_E2E) {
1392 XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1393 SD_task_get_name(task),
1394 SD_workstation_get_name(task->workstation_list[0]),
1395 SD_workstation_get_name(task->workstation_list[1]),
1396 task->communication_amount[2]);
1399 if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1400 XBT_VERB("Schedule computation task %s on %d hosts. It costs %.f flops on each host",
1401 SD_task_get_name(task),
1402 task->workstation_nb,
1403 task->computation_amount[0]);
1406 /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if runnable) */
1407 if (task->kind == SD_TASK_COMP_SEQ) {
1408 XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1409 SD_task_get_name(task),
1410 SD_workstation_get_name(task->workstation_list[0]),
1411 task->computation_amount[0]);
1413 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1414 SD_task_t before = dep->src;
1415 if (before->kind == SD_TASK_COMM_E2E) {
1416 before->workstation_list[1] = task->workstation_list[0];
1418 if (before->workstation_list[0] &&
1419 (__SD_task_is_schedulable(before)
1420 || __SD_task_is_not_scheduled(before))) {
1421 SD_task_do_schedule(before);
1423 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1424 SD_task_get_name(before),
1425 SD_workstation_get_name(before->workstation_list[0]),
1426 SD_workstation_get_name(before->workstation_list[1]),
1427 before->communication_amount[2]);
1431 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1432 SD_task_t after = dep->dst;
1433 if (after->kind == SD_TASK_COMM_E2E) {
1434 after->workstation_list[0] = task->workstation_list[0];
1435 //J-N : Why did you comment on these line (this comment add a bug I think)?
1436 if (after->workstation_list[1]
1437 && (__SD_task_is_not_scheduled(after)
1438 || __SD_task_is_schedulable(after))) {
1439 SD_task_do_schedule(after);
1441 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1442 SD_task_get_name(after),
1443 SD_workstation_get_name(after->workstation_list[0]),
1444 SD_workstation_get_name(after->workstation_list[1]),
1445 after->communication_amount[2]);
1453 /** @brief autoschedule a task on a list of workstations
1455 * This function is very similar to SD_task_schedulev(),
1456 * but takes the list of workstations to schedule onto as separate parameters.
1457 * It builds a proper vector of workstations and then call SD_task_schedulev()
1459 void SD_task_schedulel(SD_task_t task, int count, ...)
1462 SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1464 va_start(ap, count);
1465 for (i = 0; i < count; i++) {
1466 list[i] = va_arg(ap, SD_workstation_t);
1469 SD_task_schedulev(task, count, list);
1474 * \brief Sets the tracing category of a task.
1476 * This function should be called after the creation of a
1477 * SimDAG task, to define the category of that task. The first
1478 * parameter must contain a task that was created with the
1479 * function #SD_task_create. The second parameter must contain
1480 * a category that was previously declared with the function
1483 * \param task The task to be considered
1484 * \param category the name of the category to be associated to the task
1486 * \see SD_task_get_category, TRACE_category, TRACE_category_with_color
1488 void SD_task_set_category (SD_task_t task, const char *category)
1491 if (!TRACE_is_enabled()) return;
1492 if (task == NULL) return;
1493 if (category == NULL){
1494 if (task->category) xbt_free (task->category);
1495 task->category = NULL;
1497 task->category = xbt_strdup (category);
1503 * \brief Gets the current tracing category of a task.
1505 * \param task The task to be considered
1507 * \see SD_task_set_category
1509 * \return Returns the name of the tracing category of the given task, NULL otherwise
1511 const char *SD_task_get_category (SD_task_t task)
1514 return task->category;