1 /* Copyright (c) 2006, 2007, 2008, 2009, 2010. 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"
12 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
13 "Logging specific to SimDag (task)");
15 static void __SD_task_remove_dependencies(SD_task_t task);
16 static void __SD_task_destroy_scheduling_data(SD_task_t task);
19 * \brief Creates a new task.
21 * \param name the name of the task (can be \c NULL)
22 * \param data the user data you want to associate with the task (can be \c NULL)
23 * \param amount amount of the task
24 * \return the new task
25 * \see SD_task_destroy()
27 SD_task_t SD_task_create(const char *name, void *data, double amount)
33 task = xbt_new(s_SD_task_t, 1);
35 /* general information */
36 task->data = data; /* user data */
37 task->name = xbt_strdup(name);
38 task->kind = SD_TASK_NOT_TYPED;
39 task->state_hookup.prev = NULL;
40 task->state_hookup.next = NULL;
41 task->state_set = sd_global->not_scheduled_task_set;
42 task->state = SD_NOT_SCHEDULED;
43 xbt_swag_insert(task, task->state_set);
45 task->amount = amount;
46 task->remains = amount;
47 task->start_time = -1.0;
48 task->finish_time = -1.0;
49 task->surf_action = NULL;
50 task->watch_points = 0;
53 task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
54 task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
55 task->unsatisfied_dependencies=0;
58 /* scheduling parameters */
59 task->workstation_nb = 0;
60 task->workstation_list = NULL;
61 task->computation_amount = NULL;
62 task->communication_amount = NULL;
65 sd_global->task_number++;
71 * \brief Returns the user data of a task
74 * \return the user data associated with this task (can be \c NULL)
75 * \see SD_task_set_data()
77 void *SD_task_get_data(SD_task_t task)
80 xbt_assert0(task != NULL, "Invalid parameter");
85 * \brief Sets the user data of a task
87 * The new data can be \c NULL. The old data should have been freed first
88 * if it was not \c NULL.
91 * \param data the new data you want to associate with this task
92 * \see SD_task_get_data()
94 void SD_task_set_data(SD_task_t task, void *data)
97 xbt_assert0(task != NULL, "Invalid parameter");
102 * \brief Returns the state of a task
105 * \return the current \ref e_SD_task_state_t "state" of this task:
106 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
107 * \see e_SD_task_state_t
109 e_SD_task_state_t SD_task_get_state(SD_task_t task)
111 SD_CHECK_INIT_DONE();
112 xbt_assert0(task != NULL, "Invalid parameter");
116 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
118 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
120 xbt_swag_remove(task, task->state_set);
122 case SD_NOT_SCHEDULED:
123 task->state_set = sd_global->not_scheduled_task_set;
126 task->state_set = sd_global->schedulable_task_set;
129 task->state_set = sd_global->scheduled_task_set;
132 task->state_set = sd_global->runnable_task_set;
135 task->state_set = sd_global->in_fifo_task_set;
138 task->state_set = sd_global->running_task_set;
140 surf_workstation_model->action_get_start_time(task->surf_action);
143 task->state_set = sd_global->done_task_set;
145 surf_workstation_model->action_get_finish_time(task->surf_action);
149 task->state_set = sd_global->failed_task_set;
152 xbt_assert0(0, "Invalid state");
154 xbt_swag_insert(task, task->state_set);
155 task->state = new_state;
157 if (task->watch_points & new_state) {
158 VERB1("Watch point reached with task '%s'!", SD_task_get_name(task));
159 sd_global->watch_point_reached = 1;
160 SD_task_unwatch(task, new_state); /* remove the watch point */
165 * \brief Returns the name of a task
168 * \return the name of this task (can be \c NULL)
170 const char *SD_task_get_name(SD_task_t task)
172 SD_CHECK_INIT_DONE();
173 xbt_assert0(task != NULL, "Invalid parameter");
177 /** @brief Allows to change the name of a task */
178 void SD_task_set_name(SD_task_t task, const char *name) {
179 xbt_free(task->name);
180 task->name = xbt_strdup(name);
183 /** @brief Returns the dynar of the parents of a task
186 * \return a newly allocated dynar comprising the parents of this task
189 xbt_dynar_t SD_task_get_parents(SD_task_t task)
194 SD_CHECK_INIT_DONE();
195 xbt_assert0(task != NULL, "Invalid parameter");
197 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
198 xbt_dynar_foreach(task->tasks_before, i, dep){
199 xbt_dynar_push(parents, &(dep->src));
204 /** @brief Returns the dynar of the parents of a task
207 * \return a newly allocated dynar comprising the parents of this task
209 xbt_dynar_t SD_task_get_children(SD_task_t task)
212 xbt_dynar_t children;
214 SD_CHECK_INIT_DONE();
215 xbt_assert0(task != NULL, "Invalid parameter");
217 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
218 xbt_dynar_foreach(task->tasks_after, i, dep){
219 xbt_dynar_push(children, &(dep->dst));
225 * \brief Returns the amount of workstations involved in a task
227 * Only call this on already scheduled tasks!
230 int SD_task_get_workstation_count(SD_task_t task)
232 SD_CHECK_INIT_DONE();
233 xbt_assert0(task != NULL, "Invalid parameter");
234 // xbt_assert1( task->state_set != sd_global->scheduled_task_set,
235 // "Unscheduled task %s", task->name);
236 return task->workstation_nb;
240 * \brief Returns the list of workstations involved in a task
242 * Only call this on already scheduled tasks!
245 SD_workstation_t* SD_task_get_workstation_list(SD_task_t task)
247 SD_CHECK_INIT_DONE();
248 xbt_assert0(task != NULL, "Invalid parameter");
249 //xbt_assert1( task->state_set != sd_global->scheduled_task_set,
250 // "Unscheduled task %s", task->name);
251 return task->workstation_list;
255 * \brief Returns the total amount of work contained in a task
258 * \return the total amount of work (computation or data transfer) for this task
259 * \see SD_task_get_remaining_amount()
261 double SD_task_get_amount(SD_task_t task)
263 SD_CHECK_INIT_DONE();
264 xbt_assert0(task != NULL, "Invalid parameter");
269 * \brief Returns the remaining amount work to do till the completion of a task
272 * \return the remaining amount of work (computation or data transfer) of this task
273 * \see SD_task_get_amount()
275 double SD_task_get_remaining_amount(SD_task_t task)
277 SD_CHECK_INIT_DONE();
278 xbt_assert0(task != NULL, "Invalid parameter");
280 if (task->surf_action)
281 return surf_workstation_model->get_remains(task->surf_action);
283 return task->remains;
286 int SD_task_get_kind(SD_task_t task) {
290 /** @brief Displays debugging informations about a task */
291 void SD_task_dump(SD_task_t task)
293 unsigned int counter;
294 SD_dependency_t dependency;
297 INFO1("Displaying task %s",SD_task_get_name(task));
298 statename=bprintf("%s %s %s %s %s %s %s %s",
299 (task->state&SD_NOT_SCHEDULED?"not scheduled":""),
300 (task->state&SD_SCHEDULABLE?"schedulable":""),
301 (task->state&SD_SCHEDULED?"scheduled":""),
302 (task->state&SD_RUNNABLE?"runnable":"not runnable"),
303 (task->state&SD_IN_FIFO?"in fifo":""),
304 (task->state&SD_RUNNING?"running":""),
305 (task->state&SD_DONE?"done":""),
306 (task->state&SD_FAILED?"failed":""));
307 INFO1(" - state: %s",statename);
312 case SD_TASK_COMM_E2E:
313 INFO0(" - kind: end-to-end communication");
315 case SD_TASK_COMP_SEQ:
316 INFO0(" - kind: sequential computation");
319 INFO1(" - (unknown kind %d)",task->kind);
322 INFO1(" - amount: %.0f",SD_task_get_amount(task));
323 INFO1(" - Dependencies to satisfy: %d", task->unsatisfied_dependencies);
324 if (xbt_dynar_length(task->tasks_before)) {
325 INFO0(" - pre-dependencies:");
326 xbt_dynar_foreach(task->tasks_before,counter,dependency) {
327 INFO1(" %s",SD_task_get_name(dependency->src));
330 if (xbt_dynar_length(task->tasks_after)) {
331 INFO0(" - post-dependencies:");
332 xbt_dynar_foreach(task->tasks_after,counter,dependency) {
333 INFO1(" %s",SD_task_get_name(dependency->dst));
337 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
338 void SD_task_dotty(SD_task_t task,void* out) {
339 unsigned int counter;
340 SD_dependency_t dependency;
341 fprintf(out, " T%p [label=\"%.20s\"",task, task->name);
343 case SD_TASK_COMM_E2E:
344 fprintf(out,", shape=box");
346 case SD_TASK_COMP_SEQ:
347 fprintf(out,", shape=circle");
350 xbt_die("Unknown task type!");
353 xbt_dynar_foreach(task->tasks_before,counter,dependency) {
354 fprintf(out," T%p -> T%p;\n",dependency->src, dependency->dst);
358 /* Destroys a dependency between two tasks.
360 static void __SD_task_dependency_destroy(void *dependency)
362 if (((SD_dependency_t) dependency)->name != NULL)
363 xbt_free(((SD_dependency_t) dependency)->name);
364 xbt_free(dependency);
368 * \brief Adds a dependency between two tasks
370 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
371 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
373 * \param name the name of the new dependency (can be \c NULL)
374 * \param data the user data you want to associate with this dependency (can be \c NULL)
375 * \param src the task which must be executed first
376 * \param dst the task you want to make depend on \a src
377 * \see SD_task_dependency_remove()
379 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
386 SD_dependency_t dependency;
388 SD_CHECK_INIT_DONE();
389 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
391 dynar = src->tasks_after;
392 length = xbt_dynar_length(dynar);
396 "Cannot add a dependency between task '%s' and itself",
397 SD_task_get_name(src));
399 if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_schedulable(src)
400 && !__SD_task_is_scheduled_or_runnable(src))
402 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
403 SD_task_get_name(src));
405 if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_schedulable(dst)
406 && !__SD_task_is_scheduled_or_runnable(dst))
408 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
409 SD_task_get_name(dst));
411 DEBUG2("SD_task_dependency_add: src = %s, dst = %s", SD_task_get_name(src),
412 SD_task_get_name(dst));
413 for (i = 0; i < length && !found; i++) {
414 xbt_dynar_get_cpy(dynar, i, &dependency);
415 found = (dependency->dst == dst);
416 DEBUG2("Dependency %d: dependency->dst = %s", i,
417 SD_task_get_name(dependency->dst));
422 "A dependency already exists between task '%s' and task '%s'",
423 SD_task_get_name(src), SD_task_get_name(dst));
425 dependency = xbt_new(s_SD_dependency_t, 1);
427 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
428 dependency->data = data;
429 dependency->src = src;
430 dependency->dst = dst;
432 /* src must be executed before dst */
433 xbt_dynar_push(src->tasks_after, &dependency);
434 xbt_dynar_push(dst->tasks_before, &dependency);
436 dst->unsatisfied_dependencies++;
439 /* if the task was runnable, then dst->tasks_before is not empty anymore,
440 so we must go back to state SD_SCHEDULED */
441 if (__SD_task_is_runnable(dst)) {
442 DEBUG1("SD_task_dependency_add: %s was runnable and becomes scheduled!",
443 SD_task_get_name(dst));
444 __SD_task_set_state(dst, SD_SCHEDULED);
447 /* __SD_print_dependencies(src);
448 __SD_print_dependencies(dst); */
452 * \brief Indacates whether there is a dependency between two tasks.
455 * \param dst a task depending on \a src
457 * If src is NULL, checks whether dst has any pre-dependency.
458 * If dst is NULL, checks whether src has any post-dependency.
460 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
462 unsigned int counter;
463 SD_dependency_t dependency;
465 SD_CHECK_INIT_DONE();
466 xbt_assert0(src != NULL || dst != NULL, "Invalid parameter: both src and dst are NULL");
470 xbt_dynar_foreach(src->tasks_after,counter,dependency) {
471 if (dependency->dst == dst)
475 return xbt_dynar_length(src->tasks_after);
478 return xbt_dynar_length(dst->tasks_before);
484 * \brief Remove a dependency between two tasks
487 * \param dst a task depending on \a src
488 * \see SD_task_dependency_add()
490 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
497 SD_dependency_t dependency;
499 SD_CHECK_INIT_DONE();
500 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
502 /* remove the dependency from src->tasks_after */
503 dynar = src->tasks_after;
504 length = xbt_dynar_length(dynar);
506 for (i = 0; i < length && !found; i++) {
507 xbt_dynar_get_cpy(dynar, i, &dependency);
508 if (dependency->dst == dst) {
509 xbt_dynar_remove_at(dynar, i, NULL);
515 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
516 SD_task_get_name(src), SD_task_get_name(dst),
517 SD_task_get_name(dst), SD_task_get_name(src));
519 /* remove the dependency from dst->tasks_before */
520 dynar = dst->tasks_before;
521 length = xbt_dynar_length(dynar);
524 for (i = 0; i < length && !found; i++) {
525 xbt_dynar_get_cpy(dynar, i, &dependency);
526 if (dependency->src == src) {
527 xbt_dynar_remove_at(dynar, i, NULL);
528 __SD_task_dependency_destroy(dependency);
529 dst->unsatisfied_dependencies--;
534 /* should never happen... */
536 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
537 SD_task_get_name(dst), SD_task_get_name(src),
538 SD_task_get_name(src), SD_task_get_name(dst));
540 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
542 if (dst->unsatisfied_dependencies == 0){
543 if (__SD_task_is_scheduled(dst))
544 __SD_task_set_state(dst, SD_RUNNABLE);
546 __SD_task_set_state(dst, SD_SCHEDULABLE);
549 if (dst->is_not_ready == 0)
550 __SD_task_set_state(dst, SD_SCHEDULABLE);
552 /* __SD_print_dependencies(src);
553 __SD_print_dependencies(dst); */
557 * \brief Returns the user data associated with a dependency between two tasks
560 * \param dst a task depending on \a src
561 * \return the user data associated with this dependency (can be \c NULL)
562 * \see SD_task_dependency_add()
564 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
571 SD_dependency_t dependency;
574 SD_CHECK_INIT_DONE();
575 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
577 dynar = src->tasks_after;
578 length = xbt_dynar_length(dynar);
580 for (i = 0; i < length && !found; i++) {
581 xbt_dynar_get_cpy(dynar, i, &dependency);
582 found = (dependency->dst == dst);
585 THROW2(arg_error, 0, "No dependency found between task '%s' and '%s'",
586 SD_task_get_name(src), SD_task_get_name(dst));
587 return dependency->data;
590 /* temporary function for debugging */
591 static void __SD_print_watch_points(SD_task_t task)
593 static const int state_masks[] =
594 { SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE, SD_FAILED };
595 static const char *state_names[] =
596 { "schedulable", "scheduled", "running", "runnable", "done", "failed" };
599 INFO2("Task '%s' watch points (%x): ", SD_task_get_name(task),
603 for (i = 0; i < 5; i++) {
604 if (task->watch_points & state_masks[i])
605 INFO1("%s ", state_names[i]);
610 * \brief Adds a watch point to a task
612 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
613 * task becomes the one given in argument. The
614 * watch point is then automatically removed.
617 * \param state the \ref e_SD_task_state_t "state" you want to watch
618 * (cannot be #SD_NOT_SCHEDULED)
619 * \see SD_task_unwatch()
621 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
623 SD_CHECK_INIT_DONE();
624 xbt_assert0(task != NULL, "Invalid parameter");
626 if (state & SD_NOT_SCHEDULED)
628 "Cannot add a watch point for state SD_NOT_SCHEDULED");
630 task->watch_points = task->watch_points | state;
631 /* __SD_print_watch_points(task); */
635 * \brief Removes a watch point from a task
638 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
639 * \see SD_task_watch()
641 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
643 SD_CHECK_INIT_DONE();
644 xbt_assert0(task != NULL, "Invalid parameter");
645 xbt_assert0(state != SD_NOT_SCHEDULED,
646 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
648 task->watch_points = task->watch_points & ~state;
649 /* __SD_print_watch_points(task); */
653 * \brief Returns an approximative estimation of the execution time of a task.
655 * The estimation is very approximative because the value returned is the time
656 * the task would take if it was executed now and if it was the only task.
658 * \param task the task to evaluate
659 * \param workstation_nb number of workstations on which the task would be executed
660 * \param workstation_list the workstations on which the task would be executed
661 * \param computation_amount computation amount for each workstation
662 * \param communication_amount communication amount between each pair of workstations
665 double SD_task_get_execution_time(SD_task_t task,
667 const SD_workstation_t * workstation_list,
668 const double *computation_amount,
669 const double *communication_amount)
671 double time, max_time = 0.0;
673 SD_CHECK_INIT_DONE();
674 xbt_assert0(task != NULL && workstation_nb > 0 && workstation_list != NULL,
675 "Invalid parameter");
677 /* the task execution time is the maximum execution time of the parallel tasks */
679 for (i = 0; i < workstation_nb; i++) {
681 if (computation_amount != NULL)
683 SD_workstation_get_computation_time(workstation_list[i],
684 computation_amount[i]);
686 if (communication_amount != NULL)
687 for (j = 0; j < workstation_nb; j++) {
689 SD_route_get_communication_time(workstation_list[i],
691 communication_amount[i *
696 if (time > max_time) {
702 static XBT_INLINE void SD_task_do_schedule(SD_task_t task) {
703 SD_CHECK_INIT_DONE();
705 if (!__SD_task_is_not_scheduled(task) && !__SD_task_is_schedulable(task) )
706 THROW1(arg_error, 0, "Task '%s' has already been scheduled",
707 SD_task_get_name(task));
709 /* update the task state */
710 if (task->unsatisfied_dependencies == 0)
711 __SD_task_set_state(task, SD_RUNNABLE);
713 __SD_task_set_state(task, SD_SCHEDULED);
717 * \brief Schedules a task
719 * The task state must be #SD_NOT_SCHEDULED.
720 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
721 * i.e. when its dependencies are satisfied.
723 * \param task the task you want to schedule
724 * \param workstation_nb number of workstations on which the task will be executed
725 * \param workstation_list the workstations on which the task will be executed
726 * \param computation_amount computation amount for each workstation
727 * \param communication_amount communication amount between each pair of workstations
728 * \param rate task execution speed rate
729 * \see SD_task_unschedule()
731 void SD_task_schedule(SD_task_t task, int workstation_count,
732 const SD_workstation_t * workstation_list,
733 const double *computation_amount,
734 const double *communication_amount, double rate)
736 int communication_nb;
737 task->workstation_nb = 0;
739 xbt_assert0(workstation_count > 0, "workstation_nb must be positive");
741 task->workstation_nb = workstation_count;
744 if (computation_amount) {
745 task->computation_amount = xbt_new(double, workstation_count);
746 memcpy(task->computation_amount, computation_amount,
747 sizeof(double) * workstation_count);
749 task->computation_amount = NULL;
752 communication_nb = workstation_count * workstation_count;
753 if (communication_amount) {
754 task->communication_amount = xbt_new(double, communication_nb);
755 memcpy(task->communication_amount, communication_amount,
756 sizeof(double) * communication_nb);
758 task->communication_amount = NULL;
761 task->workstation_list = xbt_new(SD_workstation_t, workstation_count);
762 memcpy(task->workstation_list, workstation_list,
763 sizeof(SD_workstation_t) * workstation_count);
765 SD_task_do_schedule(task);
768 * \brief Unschedules a task
770 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
771 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
772 * Call SD_task_schedule() to schedule it again.
774 * \param task the task you want to unschedule
775 * \see SD_task_schedule()
777 void SD_task_unschedule(SD_task_t task)
779 SD_CHECK_INIT_DONE();
780 xbt_assert0(task != NULL, "Invalid parameter");
782 if (task->state_set != sd_global->scheduled_task_set &&
783 task->state_set != sd_global->runnable_task_set &&
784 task->state_set != sd_global->running_task_set &&
785 task->state_set != sd_global->failed_task_set)
787 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
788 SD_task_get_name(task));
790 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
791 && task->kind == SD_TASK_NOT_TYPED) /* Don't free scheduling data for typed tasks */
792 __SD_task_destroy_scheduling_data(task);
794 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
795 surf_workstation_model->action_cancel(task->surf_action);
797 if (task->unsatisfied_dependencies == 0)
798 __SD_task_set_state(task, SD_SCHEDULABLE);
800 __SD_task_set_state(task, SD_NOT_SCHEDULED);
802 task->remains = task->amount;
803 task->start_time = -1.0;
806 /* Destroys the data memorized by SD_task_schedule. Task state must be SD_SCHEDULED or SD_RUNNABLE.
808 static void __SD_task_destroy_scheduling_data(SD_task_t task)
810 SD_CHECK_INIT_DONE();
811 if (!__SD_task_is_scheduled_or_runnable(task) && !__SD_task_is_in_fifo(task))
813 "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
814 SD_task_get_name(task));
816 xbt_free(task->computation_amount);
817 xbt_free(task->communication_amount);
818 task->computation_amount = task->communication_amount = NULL;
821 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
822 * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
823 * the task gets out of its fifos.
825 void __SD_task_really_run(SD_task_t task)
829 void **surf_workstations;
831 SD_CHECK_INIT_DONE();
832 xbt_assert0(task != NULL, "Invalid parameter");
833 xbt_assert2(__SD_task_is_runnable_or_in_fifo(task),
834 "Task '%s' is not runnable or in a fifo! Task state: %d",
835 SD_task_get_name(task), SD_task_get_state(task));
836 xbt_assert1(task->workstation_list != NULL,
837 "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
841 DEBUG1("Really running task '%s'", SD_task_get_name(task));
843 /* set this task as current task for the workstations in sequential mode */
844 for (i = 0; i < task->workstation_nb; i++) {
845 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
846 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
847 task->workstation_list[i]->current_task = task;
848 xbt_assert0(__SD_workstation_is_busy(task->workstation_list[i]),
849 "The workstation should be busy now");
853 DEBUG1("Task '%s' set as current task for its workstations",
854 SD_task_get_name(task));
858 /* we have to create a Surf workstation array instead of the SimDag workstation array */
859 surf_workstations = xbt_new(void *, task->workstation_nb);
861 for (i = 0; i < task->workstation_nb; i++)
862 surf_workstations[i] = task->workstation_list[i]->surf_workstation;
864 /* 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 */
865 #define cost_or_zero(array,pos) ((array)?(array)[pos]:0.0)
867 task->surf_action = NULL;
868 if ((task->workstation_nb == 1) && (cost_or_zero(task->communication_amount,0) == 0.0)) {
870 surf_workstation_model->extension.
871 workstation.execute(surf_workstations[0], cost_or_zero(task->computation_amount,0));
872 } else if ((task->workstation_nb == 1)
873 && (cost_or_zero(task->computation_amount,0) == 0.0)) {
876 surf_workstation_model->extension.
877 workstation.communicate(surf_workstations[0], surf_workstations[0],
878 cost_or_zero(task->communication_amount,0), task->rate);
879 } else if ((task->workstation_nb == 2)
880 && (cost_or_zero(task->computation_amount,0) == 0.0)
881 && (cost_or_zero(task->computation_amount,1) == 0.0)) {
885 for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
886 if (cost_or_zero(task->communication_amount,i) > 0.0) {
888 value = cost_or_zero(task->communication_amount,i);
893 surf_workstation_model->extension.
894 workstation.communicate(surf_workstations[0], surf_workstations[1],
900 if (!task->surf_action) {
901 double *computation_amount = xbt_new(double, task->workstation_nb);
902 double *communication_amount = xbt_new(double, task->workstation_nb *
903 task->workstation_nb);
905 memcpy(computation_amount, task->computation_amount, sizeof(double) *
906 task->workstation_nb);
907 memcpy(communication_amount, task->communication_amount,
908 sizeof(double) * task->workstation_nb * task->workstation_nb);
911 surf_workstation_model->extension.
912 workstation.execute_parallel_task(task->workstation_nb,
913 surf_workstations, computation_amount,
914 communication_amount, task->amount,
917 xbt_free(surf_workstations);
920 surf_workstation_model->action_data_set(task->surf_action, task);
922 DEBUG1("surf_action = %p", task->surf_action);
924 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
925 __SD_task_set_state(task, SD_RUNNING);
926 xbt_assert2(__SD_task_is_running(task), "Bad state of task '%s': %d",
927 SD_task_get_name(task), SD_task_get_state(task));
931 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_RUNNABLE
932 * (ie when its dependencies are satisfied).
933 * If one of the workstations where the task is scheduled on is busy (in sequential mode),
934 * the task doesn't start.
935 * Returns whether the task has started.
937 int __SD_task_try_to_run(SD_task_t task)
942 SD_workstation_t workstation;
944 SD_CHECK_INIT_DONE();
945 xbt_assert0(task != NULL, "Invalid parameter");
946 xbt_assert2(__SD_task_is_runnable(task),
947 "Task '%s' is not runnable! Task state: %d",
948 SD_task_get_name(task), SD_task_get_state(task));
951 for (i = 0; i < task->workstation_nb; i++) {
952 can_start = can_start &&
953 !__SD_workstation_is_busy(task->workstation_list[i]);
956 DEBUG2("Task '%s' can start: %d", SD_task_get_name(task), can_start);
958 if (!can_start) { /* if the task cannot start and is not in the fifos yet */
959 for (i = 0; i < task->workstation_nb; i++) {
960 workstation = task->workstation_list[i];
961 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
962 DEBUG2("Pushing task '%s' in the fifo of workstation '%s'",
963 SD_task_get_name(task), SD_workstation_get_name(workstation));
964 xbt_fifo_push(workstation->task_fifo, task);
967 __SD_task_set_state(task, SD_IN_FIFO);
968 xbt_assert2(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
969 SD_task_get_name(task), SD_task_get_state(task));
970 DEBUG1("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
972 __SD_task_really_run(task);
978 /* This function is called by SD_simulate when a task is done.
979 * It updates task->state and task->action and executes if necessary the tasks
980 * which were waiting in fifos for the end of `task'
982 void __SD_task_just_done(SD_task_t task)
985 SD_workstation_t workstation;
988 int candidate_nb = 0;
989 int candidate_capacity = 8;
990 SD_task_t *candidates;
993 SD_CHECK_INIT_DONE();
994 xbt_assert0(task != NULL, "Invalid parameter");
995 xbt_assert1(__SD_task_is_running(task),
996 "The task must be running! Task state: %d",
997 SD_task_get_state(task));
998 xbt_assert1(task->workstation_list != NULL,
999 "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
1002 candidates = xbt_new(SD_task_t, 8);
1004 __SD_task_set_state(task, SD_DONE);
1005 surf_workstation_model->action_unref(task->surf_action);
1006 task->surf_action = NULL;
1008 DEBUG0("Looking for candidates");
1010 /* if the task was executed on sequential workstations,
1011 maybe we can execute the next task of the fifo for each workstation */
1012 for (i = 0; i < task->workstation_nb; i++) {
1013 workstation = task->workstation_list[i];
1014 DEBUG2("Workstation '%s': access_mode = %d",
1015 SD_workstation_get_name(workstation), workstation->access_mode);
1016 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1017 xbt_assert1(workstation->task_fifo != NULL,
1018 "Workstation '%s' has sequential access but no fifo!",
1019 SD_workstation_get_name(workstation));
1020 xbt_assert2(workstation->current_task =
1021 task, "Workstation '%s': current task should be '%s'",
1022 SD_workstation_get_name(workstation),
1023 SD_task_get_name(task));
1025 /* the task is over so we can release the workstation */
1026 workstation->current_task = NULL;
1028 DEBUG0("Getting candidate in fifo");
1030 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1031 (workstation->task_fifo));
1033 if (candidate != NULL) {
1034 DEBUG1("Candidate: '%s'", SD_task_get_name(candidate));
1035 xbt_assert2(__SD_task_is_in_fifo(candidate),
1036 "Bad state of candidate '%s': %d",
1037 SD_task_get_name(candidate),
1038 SD_task_get_state(candidate));
1041 DEBUG1("Candidate in fifo: %p", candidate);
1043 /* if there was a task waiting for my place */
1044 if (candidate != NULL) {
1045 /* Unfortunately, we are not sure yet that we can execute the task now,
1046 because the task can be waiting more deeply in some other workstation's fifos...
1047 So we memorize all candidate tasks, and then we will check for each candidate
1048 whether or not all its workstations are available. */
1050 /* realloc if necessary */
1051 if (candidate_nb == candidate_capacity) {
1052 candidate_capacity *= 2;
1054 xbt_realloc(candidates, sizeof(SD_task_t) * candidate_capacity);
1057 /* register the candidate */
1058 candidates[candidate_nb++] = candidate;
1059 candidate->fifo_checked = 0;
1064 DEBUG1("Candidates found: %d", candidate_nb);
1066 /* now we check every candidate task */
1067 for (i = 0; i < candidate_nb; i++) {
1068 candidate = candidates[i];
1070 if (candidate->fifo_checked) {
1071 continue; /* we have already evaluated that task */
1074 xbt_assert2(__SD_task_is_in_fifo(candidate),
1075 "Bad state of candidate '%s': %d",
1076 SD_task_get_name(candidate), SD_task_get_state(candidate));
1078 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1079 workstation = candidate->workstation_list[j];
1081 /* I can start on this workstation if the workstation is shared
1082 or if I am the first task in the fifo */
1083 can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS ||
1085 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1086 (workstation->task_fifo));
1089 DEBUG2("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1092 /* now we are sure that I can start! */
1094 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1095 workstation = candidate->workstation_list[j];
1097 /* update the fifo */
1098 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1099 candidate = xbt_fifo_shift(workstation->task_fifo); /* the return value is stored just for debugging */
1100 DEBUG1("Head of the fifo: '%s'",
1101 (candidate != NULL) ? SD_task_get_name(candidate) : "NULL");
1102 xbt_assert0(candidate == candidates[i],
1103 "Error in __SD_task_just_done: bad first task in the fifo");
1105 } /* for each workstation */
1107 /* finally execute the task */
1108 DEBUG2("Task '%s' state: %d", SD_task_get_name(candidate),
1109 SD_task_get_state(candidate));
1110 __SD_task_really_run(candidate);
1113 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1114 SD_task_get_name(candidate), candidate->state_set,
1115 sd_global->running_task_set, __SD_task_is_running(candidate));
1116 xbt_assert2(__SD_task_is_running(candidate),
1117 "Bad state of task '%s': %d", SD_task_get_name(candidate),
1118 SD_task_get_state(candidate));
1119 DEBUG0("Okay, the task is running.");
1122 candidate->fifo_checked = 1;
1123 } /* for each candidate */
1125 xbt_free(candidates);
1128 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1130 static void __SD_task_remove_dependencies(SD_task_t task)
1132 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1133 because each one is stored twice */
1134 SD_dependency_t dependency;
1135 while (xbt_dynar_length(task->tasks_before) > 0) {
1136 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1137 SD_task_dependency_remove(dependency->src, dependency->dst);
1140 while (xbt_dynar_length(task->tasks_after) > 0) {
1141 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1142 SD_task_dependency_remove(dependency->src, dependency->dst);
1147 * \brief Returns the start time of a task
1149 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1151 * \param task: a task
1152 * \return the start time of this task
1154 double SD_task_get_start_time(SD_task_t task)
1156 SD_CHECK_INIT_DONE();
1157 xbt_assert0(task != NULL, "Invalid parameter");
1158 if (task->surf_action)
1159 return surf_workstation_model->action_get_start_time(task->surf_action);
1161 return task->start_time;
1165 * \brief Returns the finish time of a task
1167 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1168 * If the state is not completed yet, the returned value is an
1169 * estimation of the task finish time. This value can fluctuate
1170 * until the task is completed.
1172 * \param task: a task
1173 * \return the start time of this task
1175 double SD_task_get_finish_time(SD_task_t task)
1177 SD_CHECK_INIT_DONE();
1178 xbt_assert0(task != NULL, "Invalid parameter");
1180 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1181 return surf_workstation_model->action_get_finish_time(task->surf_action);
1183 return task->finish_time;
1187 * \brief Destroys a task.
1189 * The user data (if any) should have been destroyed first.
1191 * \param task the task you want to destroy
1192 * \see SD_task_create()
1194 void SD_task_destroy(SD_task_t task)
1196 SD_CHECK_INIT_DONE();
1197 xbt_assert0(task != NULL, "Invalid parameter");
1199 DEBUG1("Destroying task %s...", SD_task_get_name(task));
1201 __SD_task_remove_dependencies(task);
1202 /* if the task was scheduled or runnable we have to free the scheduling parameters */
1203 if (__SD_task_is_scheduled_or_runnable(task))
1204 __SD_task_destroy_scheduling_data(task);
1205 xbt_swag_remove(task,task->state_set);
1207 if (task->name != NULL)
1208 xbt_free(task->name);
1210 if (task->surf_action != NULL)
1211 surf_workstation_model->action_unref(task->surf_action);
1213 if (task->workstation_list != NULL)
1214 xbt_free(task->workstation_list);
1216 if (task->communication_amount)
1217 xbt_free(task->communication_amount);
1219 if (task->computation_amount)
1220 xbt_free(task->computation_amount);
1222 xbt_dynar_free(&task->tasks_before);
1223 xbt_dynar_free(&task->tasks_after);
1226 sd_global->task_number--;
1228 DEBUG0("Task destroyed.");
1232 static XBT_INLINE SD_task_t SD_task_create_sized(const char*name,void*data,double amount,int ws_count) {
1233 SD_task_t task = SD_task_create(name,data,amount);
1234 task->communication_amount = xbt_new0(double,ws_count*ws_count);
1235 task->computation_amount = xbt_new0(double,ws_count);
1236 task->workstation_nb = ws_count;
1237 task->workstation_list = xbt_new0(SD_workstation_t,ws_count);
1240 /** @brief create a end-to-end communication task that can then be auto-scheduled
1242 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1243 * allows to specify the task costs at creation, and decorelate them from the
1244 * scheduling process where you just specify which resource should deliver the
1247 * A end-to-end communication must be scheduled on 2 hosts, and the amount
1248 * specified at creation is sent from hosts[0] to hosts[1].
1250 SD_task_t SD_task_create_comm_e2e(const char*name, void *data, double amount) {
1251 SD_task_t res = SD_task_create_sized(name,data,amount,2);
1252 res->communication_amount[2] = amount;
1253 res->kind=SD_TASK_COMM_E2E;
1256 /** @brief create a sequential computation task that can then be auto-scheduled
1258 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1259 * allows to specify the task costs at creation, and decorelate them from the
1260 * scheduling process where you just specify which resource should deliver the
1263 * A sequential computation must be scheduled on 1 host, and the amount
1264 * specified at creation to be run on hosts[0].
1266 SD_task_t SD_task_create_comp_seq(const char*name, void *data, double amount) {
1267 SD_task_t res = SD_task_create_sized(name,data,amount,1);
1268 res->computation_amount[0]=amount;
1269 res->kind=SD_TASK_COMP_SEQ;
1273 /** @brief Auto-schedules a task.
1275 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1276 * allows to specify the task costs at creation, and decorelate them from the
1277 * scheduling process where you just specify which resource should deliver the
1280 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1281 * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1285 * We should create tasks kind for the following categories:
1286 * - Point to point communication (done)
1287 * - Sequential computation (done)
1288 * - group communication (redistribution, several kinds)
1289 * - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1290 * - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1292 void SD_task_schedulev(SD_task_t task, int count, const SD_workstation_t*list) {
1294 SD_dependency_t dep;
1296 xbt_assert1(task->kind != 0,"Task %s is not typed. Cannot automatically schedule it.",SD_task_get_name(task));
1297 switch(task->kind) {
1298 case SD_TASK_COMM_E2E:
1299 case SD_TASK_COMP_SEQ:
1300 xbt_assert(task->workstation_nb==count);
1301 for (i=0;i<count;i++)
1302 task->workstation_list[i]=list[i];
1303 SD_task_do_schedule(task);
1306 xbt_die(bprintf("Kind of task %s not supported by SD_task_schedulev()",
1307 SD_task_get_name(task)));
1309 if (task->kind == SD_TASK_COMM_E2E) {
1310 VERB4("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1311 SD_task_get_name(task),
1312 SD_workstation_get_name(task->workstation_list[0]),SD_workstation_get_name(task->workstation_list[1]),
1313 task->communication_amount[2]);
1316 /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if runnable) */
1317 if (task->kind == SD_TASK_COMP_SEQ) {
1318 VERB3("Schedule computation task %s on %s. It costs %.f flops",
1319 SD_task_get_name(task),SD_workstation_get_name(task->workstation_list[0]),
1320 task->computation_amount[0]);
1322 xbt_dynar_foreach(task->tasks_before,cpt,dep) {
1323 SD_task_t before = dep->src;
1324 if (before->kind == SD_TASK_COMM_E2E) {
1325 before->workstation_list[1] = task->workstation_list[0];
1327 if (before->workstation_list[0] &&
1328 (__SD_task_is_schedulable(before) || __SD_task_is_not_scheduled(before))) {
1329 SD_task_do_schedule(before);
1330 VERB4("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1331 SD_task_get_name(before),
1332 SD_workstation_get_name(before->workstation_list[0]),SD_workstation_get_name(before->workstation_list[1]),
1333 before->communication_amount[2]);
1337 xbt_dynar_foreach(task->tasks_after,cpt,dep) {
1338 SD_task_t after = dep->dst;
1339 if (after->kind == SD_TASK_COMM_E2E) {
1340 after->workstation_list[0] = task->workstation_list[0];
1341 // if (after->workstation_list[1] && (__SD_task_is_not_scheduled(after) ||
1342 // __SD_task_is_schedulable(after))) {
1343 // SD_task_do_schedule(after);
1344 // VERB4("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1345 // SD_task_get_name(after),
1346 // SD_workstation_get_name(after->workstation_list[0]),SD_workstation_get_name(after->workstation_list[1]),
1347 // after->communication_amount[2]);
1354 /** @brief autoschedule a task on a list of workstations
1356 * This function is very similar to SD_task_schedulev(),
1357 * but takes the list of workstations to schedule onto as separate parameters.
1358 * It builds a proper vector of workstations and then call SD_task_schedulev()
1360 void SD_task_schedulel(SD_task_t task, int count, ...) {
1362 SD_workstation_t *list=xbt_new(SD_workstation_t,count);
1365 for (i=0;i<count;i++) {
1366 list[i] = va_arg(ap,SD_workstation_t);
1369 SD_task_schedulev(task,count,list);