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"
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);
20 * \brief Creates a new task.
22 * \param name the name of the task (can be \c NULL)
23 * \param data the user data you want to associate with the task (can be \c NULL)
24 * \param amount amount of the task
25 * \return the new task
26 * \see SD_task_destroy()
28 SD_task_t SD_task_create(const char *name, void *data, double amount)
34 task = xbt_new(s_SD_task_t, 1);
36 /* general information */
37 task->data = data; /* user data */
38 task->name = xbt_strdup(name);
39 task->kind = SD_TASK_NOT_TYPED;
40 task->state_hookup.prev = NULL;
41 task->state_hookup.next = NULL;
42 task->state_set = sd_global->not_scheduled_task_set;
43 task->state = SD_NOT_SCHEDULED;
45 xbt_swag_insert(task, task->state_set);
47 task->amount = amount;
48 task->remains = amount;
49 task->start_time = -1.0;
50 task->finish_time = -1.0;
51 task->surf_action = NULL;
52 task->watch_points = 0;
55 task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
56 task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
57 task->unsatisfied_dependencies = 0;
58 task->is_not_ready = 0;
60 /* scheduling parameters */
61 task->workstation_nb = 0;
62 task->workstation_list = NULL;
63 task->computation_amount = NULL;
64 task->communication_amount = NULL;
67 sd_global->task_number++;
70 TRACE_sd_task_create(task);
77 * \brief Returns the user data of a task
80 * \return the user data associated with this task (can be \c NULL)
81 * \see SD_task_set_data()
83 void *SD_task_get_data(SD_task_t task)
86 xbt_assert0(task != NULL, "Invalid parameter");
91 * \brief Sets the user data of a task
93 * The new data can be \c NULL. The old data should have been freed first
94 * if it was not \c NULL.
97 * \param data the new data you want to associate with this task
98 * \see SD_task_get_data()
100 void SD_task_set_data(SD_task_t task, void *data)
102 SD_CHECK_INIT_DONE();
103 xbt_assert0(task != NULL, "Invalid parameter");
108 * \brief Returns the state of a task
111 * \return the current \ref e_SD_task_state_t "state" of this task:
112 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
113 * \see e_SD_task_state_t
115 e_SD_task_state_t SD_task_get_state(SD_task_t task)
117 SD_CHECK_INIT_DONE();
118 xbt_assert0(task != NULL, "Invalid parameter");
122 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
124 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
126 xbt_swag_remove(task, task->state_set);
128 case SD_NOT_SCHEDULED:
129 task->state_set = sd_global->not_scheduled_task_set;
132 task->state_set = sd_global->schedulable_task_set;
135 task->state_set = sd_global->scheduled_task_set;
138 task->state_set = sd_global->runnable_task_set;
141 task->state_set = sd_global->in_fifo_task_set;
144 task->state_set = sd_global->running_task_set;
146 surf_workstation_model->action_get_start_time(task->surf_action);
149 task->state_set = sd_global->done_task_set;
151 surf_workstation_model->action_get_finish_time(task->surf_action);
155 task->state_set = sd_global->failed_task_set;
158 xbt_assert0(0, "Invalid state");
160 xbt_swag_insert(task, task->state_set);
161 task->state = new_state;
163 if (task->watch_points & new_state) {
164 VERB1("Watch point reached with task '%s'!", SD_task_get_name(task));
165 sd_global->watch_point_reached = 1;
166 SD_task_unwatch(task, new_state); /* remove the watch point */
171 * \brief Returns the name of a task
174 * \return the name of this task (can be \c NULL)
176 const char *SD_task_get_name(SD_task_t task)
178 SD_CHECK_INIT_DONE();
179 xbt_assert0(task != NULL, "Invalid parameter");
183 /** @brief Allows to change the name of a task */
184 void SD_task_set_name(SD_task_t task, const char *name)
186 xbt_free(task->name);
187 task->name = xbt_strdup(name);
190 /** @brief Returns the dynar of the parents of a task
193 * \return a newly allocated dynar comprising the parents of this task
196 xbt_dynar_t SD_task_get_parents(SD_task_t task)
201 SD_CHECK_INIT_DONE();
202 xbt_assert0(task != NULL, "Invalid parameter");
204 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
205 xbt_dynar_foreach(task->tasks_before, i, dep) {
206 xbt_dynar_push(parents, &(dep->src));
211 /** @brief Returns the dynar of the parents of a task
214 * \return a newly allocated dynar comprising the parents of this task
216 xbt_dynar_t SD_task_get_children(SD_task_t task)
219 xbt_dynar_t children;
221 SD_CHECK_INIT_DONE();
222 xbt_assert0(task != NULL, "Invalid parameter");
224 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
225 xbt_dynar_foreach(task->tasks_after, i, dep) {
226 xbt_dynar_push(children, &(dep->dst));
232 * \brief Returns the amount of workstations involved in a task
234 * Only call this on already scheduled tasks!
237 int SD_task_get_workstation_count(SD_task_t task)
239 SD_CHECK_INIT_DONE();
240 xbt_assert0(task != NULL, "Invalid parameter");
241 // xbt_assert1( task->state_set != sd_global->scheduled_task_set,
242 // "Unscheduled task %s", task->name);
243 return task->workstation_nb;
247 * \brief Returns the list of workstations involved in a task
249 * Only call this on already scheduled tasks!
252 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
254 SD_CHECK_INIT_DONE();
255 xbt_assert0(task != NULL, "Invalid parameter");
256 //xbt_assert1( task->state_set != sd_global->scheduled_task_set,
257 // "Unscheduled task %s", task->name);
258 return task->workstation_list;
262 * \brief Returns the total amount of work contained in a task
265 * \return the total amount of work (computation or data transfer) for this task
266 * \see SD_task_get_remaining_amount()
268 double SD_task_get_amount(SD_task_t task)
270 SD_CHECK_INIT_DONE();
271 xbt_assert0(task != NULL, "Invalid parameter");
276 * \brief Returns the remaining amount work to do till the completion of a task
279 * \return the remaining amount of work (computation or data transfer) of this task
280 * \see SD_task_get_amount()
282 double SD_task_get_remaining_amount(SD_task_t task)
284 SD_CHECK_INIT_DONE();
285 xbt_assert0(task != NULL, "Invalid parameter");
287 if (task->surf_action)
288 return surf_workstation_model->get_remains(task->surf_action);
290 return task->remains;
293 int SD_task_get_kind(SD_task_t task)
298 /** @brief Displays debugging informations about a task */
299 void SD_task_dump(SD_task_t task)
301 unsigned int counter;
302 SD_dependency_t dependency;
305 INFO1("Displaying task %s", SD_task_get_name(task));
306 statename = bprintf("%s %s %s %s %s %s %s %s",
307 (task->state & SD_NOT_SCHEDULED ? "not scheduled" :
309 (task->state & SD_SCHEDULABLE ? "schedulable" : ""),
310 (task->state & SD_SCHEDULED ? "scheduled" : ""),
311 (task->state & SD_RUNNABLE ? "runnable" :
313 (task->state & SD_IN_FIFO ? "in fifo" : ""),
314 (task->state & SD_RUNNING ? "running" : ""),
315 (task->state & SD_DONE ? "done" : ""),
316 (task->state & SD_FAILED ? "failed" : ""));
317 INFO1(" - state: %s", statename);
320 if (task->kind != 0) {
321 switch (task->kind) {
322 case SD_TASK_COMM_E2E:
323 INFO0(" - kind: end-to-end communication");
325 case SD_TASK_COMP_SEQ:
326 INFO0(" - kind: sequential computation");
329 INFO1(" - (unknown kind %d)", task->kind);
332 INFO1(" - amount: %.0f", SD_task_get_amount(task));
333 INFO1(" - Dependencies to satisfy: %d", task->unsatisfied_dependencies);
334 if (xbt_dynar_length(task->tasks_before)) {
335 INFO0(" - pre-dependencies:");
336 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
337 INFO1(" %s", SD_task_get_name(dependency->src));
340 if (xbt_dynar_length(task->tasks_after)) {
341 INFO0(" - post-dependencies:");
342 xbt_dynar_foreach(task->tasks_after, counter, dependency) {
343 INFO1(" %s", SD_task_get_name(dependency->dst));
348 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
349 void SD_task_dotty(SD_task_t task, void *out)
351 unsigned int counter;
352 SD_dependency_t dependency;
353 fprintf(out, " T%p [label=\"%.20s\"", task, task->name);
354 switch (task->kind) {
355 case SD_TASK_COMM_E2E:
356 fprintf(out, ", shape=box");
358 case SD_TASK_COMP_SEQ:
359 fprintf(out, ", shape=circle");
362 xbt_die("Unknown task type!");
364 fprintf(out, "];\n");
365 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
366 fprintf(out, " T%p -> T%p;\n", dependency->src, dependency->dst);
370 /* Destroys a dependency between two tasks.
372 static void __SD_task_dependency_destroy(void *dependency)
374 if (((SD_dependency_t) dependency)->name != NULL)
375 xbt_free(((SD_dependency_t) dependency)->name);
376 xbt_free(dependency);
380 * \brief Adds a dependency between two tasks
382 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
383 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
385 * \param name the name of the new dependency (can be \c NULL)
386 * \param data the user data you want to associate with this dependency (can be \c NULL)
387 * \param src the task which must be executed first
388 * \param dst the task you want to make depend on \a src
389 * \see SD_task_dependency_remove()
391 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
398 SD_dependency_t dependency;
400 SD_CHECK_INIT_DONE();
401 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
403 dynar = src->tasks_after;
404 length = xbt_dynar_length(dynar);
408 "Cannot add a dependency between task '%s' and itself",
409 SD_task_get_name(src));
411 if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_schedulable(src)
412 && !__SD_task_is_scheduled_or_runnable(src))
414 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
415 SD_task_get_name(src));
417 if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_schedulable(dst)
418 && !__SD_task_is_scheduled_or_runnable(dst))
420 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
421 SD_task_get_name(dst));
423 DEBUG2("SD_task_dependency_add: src = %s, dst = %s",
424 SD_task_get_name(src), SD_task_get_name(dst));
425 for (i = 0; i < length && !found; i++) {
426 xbt_dynar_get_cpy(dynar, i, &dependency);
427 found = (dependency->dst == dst);
428 DEBUG2("Dependency %d: dependency->dst = %s", i,
429 SD_task_get_name(dependency->dst));
434 "A dependency already exists between task '%s' and task '%s'",
435 SD_task_get_name(src), SD_task_get_name(dst));
437 dependency = xbt_new(s_SD_dependency_t, 1);
439 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
440 dependency->data = data;
441 dependency->src = src;
442 dependency->dst = dst;
444 /* src must be executed before dst */
445 xbt_dynar_push(src->tasks_after, &dependency);
446 xbt_dynar_push(dst->tasks_before, &dependency);
448 dst->unsatisfied_dependencies++;
451 /* if the task was runnable, then dst->tasks_before is not empty anymore,
452 so we must go back to state SD_SCHEDULED */
453 if (__SD_task_is_runnable(dst)) {
455 ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
456 SD_task_get_name(dst));
457 __SD_task_set_state(dst, SD_SCHEDULED);
460 /* __SD_print_dependencies(src);
461 __SD_print_dependencies(dst); */
465 * \brief Indacates whether there is a dependency between two tasks.
468 * \param dst a task depending on \a src
470 * If src is NULL, checks whether dst has any pre-dependency.
471 * If dst is NULL, checks whether src has any post-dependency.
473 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
475 unsigned int counter;
476 SD_dependency_t dependency;
478 SD_CHECK_INIT_DONE();
479 xbt_assert0(src != NULL
481 "Invalid parameter: both src and dst are NULL");
485 xbt_dynar_foreach(src->tasks_after, counter, dependency) {
486 if (dependency->dst == dst)
490 return xbt_dynar_length(src->tasks_after);
493 return xbt_dynar_length(dst->tasks_before);
499 * \brief Remove a dependency between two tasks
502 * \param dst a task depending on \a src
503 * \see SD_task_dependency_add()
505 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
512 SD_dependency_t dependency;
514 SD_CHECK_INIT_DONE();
515 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
517 /* remove the dependency from src->tasks_after */
518 dynar = src->tasks_after;
519 length = xbt_dynar_length(dynar);
521 for (i = 0; i < length && !found; i++) {
522 xbt_dynar_get_cpy(dynar, i, &dependency);
523 if (dependency->dst == dst) {
524 xbt_dynar_remove_at(dynar, i, NULL);
530 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
531 SD_task_get_name(src), SD_task_get_name(dst),
532 SD_task_get_name(dst), SD_task_get_name(src));
534 /* remove the dependency from dst->tasks_before */
535 dynar = dst->tasks_before;
536 length = xbt_dynar_length(dynar);
539 for (i = 0; i < length && !found; i++) {
540 xbt_dynar_get_cpy(dynar, i, &dependency);
541 if (dependency->src == src) {
542 xbt_dynar_remove_at(dynar, i, NULL);
543 __SD_task_dependency_destroy(dependency);
544 dst->unsatisfied_dependencies--;
549 /* should never happen... */
551 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
552 SD_task_get_name(dst), SD_task_get_name(src),
553 SD_task_get_name(src), SD_task_get_name(dst));
555 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
557 if (dst->unsatisfied_dependencies == 0) {
558 if (__SD_task_is_scheduled(dst))
559 __SD_task_set_state(dst, SD_RUNNABLE);
561 __SD_task_set_state(dst, SD_SCHEDULABLE);
564 if (dst->is_not_ready == 0)
565 __SD_task_set_state(dst, SD_SCHEDULABLE);
567 /* __SD_print_dependencies(src);
568 __SD_print_dependencies(dst); */
572 * \brief Returns the user data associated with a dependency between two tasks
575 * \param dst a task depending on \a src
576 * \return the user data associated with this dependency (can be \c NULL)
577 * \see SD_task_dependency_add()
579 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
586 SD_dependency_t dependency;
589 SD_CHECK_INIT_DONE();
590 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
592 dynar = src->tasks_after;
593 length = xbt_dynar_length(dynar);
595 for (i = 0; i < length && !found; i++) {
596 xbt_dynar_get_cpy(dynar, i, &dependency);
597 found = (dependency->dst == dst);
600 THROW2(arg_error, 0, "No dependency found between task '%s' and '%s'",
601 SD_task_get_name(src), SD_task_get_name(dst));
602 return dependency->data;
605 /* temporary function for debugging */
606 static void __SD_print_watch_points(SD_task_t task)
608 static const int state_masks[] =
609 { SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE,
612 static const char *state_names[] =
613 { "schedulable", "scheduled", "running", "runnable", "done",
618 INFO2("Task '%s' watch points (%x): ", SD_task_get_name(task),
622 for (i = 0; i < 5; i++) {
623 if (task->watch_points & state_masks[i])
624 INFO1("%s ", state_names[i]);
629 * \brief Adds a watch point to a task
631 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
632 * task becomes the one given in argument. The
633 * watch point is then automatically removed.
636 * \param state the \ref e_SD_task_state_t "state" you want to watch
637 * (cannot be #SD_NOT_SCHEDULED)
638 * \see SD_task_unwatch()
640 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
642 SD_CHECK_INIT_DONE();
643 xbt_assert0(task != NULL, "Invalid parameter");
645 if (state & SD_NOT_SCHEDULED)
647 "Cannot add a watch point for state SD_NOT_SCHEDULED");
649 task->watch_points = task->watch_points | state;
650 /* __SD_print_watch_points(task); */
654 * \brief Removes a watch point from a task
657 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
658 * \see SD_task_watch()
660 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
662 SD_CHECK_INIT_DONE();
663 xbt_assert0(task != NULL, "Invalid parameter");
664 xbt_assert0(state != SD_NOT_SCHEDULED,
665 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
667 task->watch_points = task->watch_points & ~state;
668 /* __SD_print_watch_points(task); */
672 * \brief Returns an approximative estimation of the execution time of a task.
674 * The estimation is very approximative because the value returned is the time
675 * the task would take if it was executed now and if it was the only task.
677 * \param task the task to evaluate
678 * \param workstation_nb number of workstations on which the task would be executed
679 * \param workstation_list the workstations on which the task would be executed
680 * \param computation_amount computation amount for each workstation
681 * \param communication_amount communication amount between each pair of workstations
684 double SD_task_get_execution_time(SD_task_t task,
686 const SD_workstation_t *
688 const double *computation_amount,
689 const double *communication_amount)
691 double time, max_time = 0.0;
693 SD_CHECK_INIT_DONE();
694 xbt_assert0(task != NULL && workstation_nb > 0
695 && workstation_list != NULL, "Invalid parameter");
697 /* the task execution time is the maximum execution time of the parallel tasks */
699 for (i = 0; i < workstation_nb; i++) {
701 if (computation_amount != NULL)
703 SD_workstation_get_computation_time(workstation_list[i],
704 computation_amount[i]);
706 if (communication_amount != NULL)
707 for (j = 0; j < workstation_nb; j++) {
709 SD_route_get_communication_time(workstation_list[i],
711 communication_amount[i *
716 if (time > max_time) {
723 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
725 SD_CHECK_INIT_DONE();
727 if (!__SD_task_is_not_scheduled(task) && !__SD_task_is_schedulable(task))
728 THROW1(arg_error, 0, "Task '%s' has already been scheduled",
729 SD_task_get_name(task));
731 /* update the task state */
732 if (task->unsatisfied_dependencies == 0)
733 __SD_task_set_state(task, SD_RUNNABLE);
735 __SD_task_set_state(task, SD_SCHEDULED);
739 * \brief Schedules a task
741 * The task state must be #SD_NOT_SCHEDULED.
742 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
743 * i.e. when its dependencies are satisfied.
745 * \param task the task you want to schedule
746 * \param workstation_nb number of workstations on which the task will be executed
747 * \param workstation_list the workstations on which the task will be executed
748 * \param computation_amount computation amount for each workstation
749 * \param communication_amount communication amount between each pair of workstations
750 * \param rate task execution speed rate
751 * \see SD_task_unschedule()
753 void SD_task_schedule(SD_task_t task, int workstation_count,
754 const SD_workstation_t * workstation_list,
755 const double *computation_amount,
756 const double *communication_amount, double rate)
758 int communication_nb;
759 task->workstation_nb = 0;
761 xbt_assert0(workstation_count > 0, "workstation_nb must be positive");
763 task->workstation_nb = workstation_count;
766 if (computation_amount) {
767 task->computation_amount = xbt_realloc(task->computation_amount,
768 sizeof(double) * workstation_count);
769 memcpy(task->computation_amount, computation_amount,
770 sizeof(double) * workstation_count);
772 xbt_free(task->computation_amount);
773 task->computation_amount = NULL;
776 communication_nb = workstation_count * workstation_count;
777 if (communication_amount) {
778 task->communication_amount = xbt_realloc(task->communication_amount,
779 sizeof(double) * communication_nb);
780 memcpy(task->communication_amount, communication_amount,
781 sizeof(double) * communication_nb);
783 xbt_free(task->communication_amount);
784 task->communication_amount = NULL;
787 task->workstation_list =
788 xbt_realloc(task->workstation_list,
789 sizeof(SD_workstation_t) * workstation_count);
790 memcpy(task->workstation_list, workstation_list,
791 sizeof(SD_workstation_t) * workstation_count);
793 SD_task_do_schedule(task);
797 * \brief Unschedules a task
799 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
800 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
801 * Call SD_task_schedule() to schedule it again.
803 * \param task the task you want to unschedule
804 * \see SD_task_schedule()
806 void SD_task_unschedule(SD_task_t task)
808 SD_CHECK_INIT_DONE();
809 xbt_assert0(task != NULL, "Invalid parameter");
811 if (task->state_set != sd_global->scheduled_task_set &&
812 task->state_set != sd_global->runnable_task_set &&
813 task->state_set != sd_global->running_task_set &&
814 task->state_set != sd_global->failed_task_set)
816 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
817 SD_task_get_name(task));
819 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
820 &&task->kind == SD_TASK_NOT_TYPED) /* Don't free scheduling data for typed tasks */
821 __SD_task_destroy_scheduling_data(task);
823 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
824 surf_workstation_model->action_cancel(task->surf_action);
826 if (task->unsatisfied_dependencies == 0)
827 __SD_task_set_state(task, SD_SCHEDULABLE);
829 __SD_task_set_state(task, SD_NOT_SCHEDULED);
831 task->remains = task->amount;
832 task->start_time = -1.0;
835 /* Destroys the data memorized by SD_task_schedule. Task state must be SD_SCHEDULED or SD_RUNNABLE.
837 static void __SD_task_destroy_scheduling_data(SD_task_t task)
839 SD_CHECK_INIT_DONE();
840 if (!__SD_task_is_scheduled_or_runnable(task)
841 && !__SD_task_is_in_fifo(task))
843 "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
844 SD_task_get_name(task));
846 xbt_free(task->computation_amount);
847 xbt_free(task->communication_amount);
848 task->computation_amount = task->communication_amount = NULL;
851 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
852 * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
853 * the task gets out of its fifos.
855 void __SD_task_really_run(SD_task_t task)
859 void **surf_workstations;
861 SD_CHECK_INIT_DONE();
862 xbt_assert0(task != NULL, "Invalid parameter");
863 xbt_assert2(__SD_task_is_runnable_or_in_fifo(task),
864 "Task '%s' is not runnable or in a fifo! Task state: %d",
865 SD_task_get_name(task), SD_task_get_state(task));
866 xbt_assert1(task->workstation_list != NULL,
867 "Task '%s': workstation_list is NULL!",
868 SD_task_get_name(task));
872 DEBUG1("Really running task '%s'", SD_task_get_name(task));
874 /* set this task as current task for the workstations in sequential mode */
875 for (i = 0; i < task->workstation_nb; i++) {
876 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
877 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
878 task->workstation_list[i]->current_task = task;
879 xbt_assert0(__SD_workstation_is_busy(task->workstation_list[i]),
880 "The workstation should be busy now");
884 DEBUG1("Task '%s' set as current task for its workstations",
885 SD_task_get_name(task));
889 /* we have to create a Surf workstation array instead of the SimDag workstation array */
890 surf_workstations = xbt_new(void *, task->workstation_nb);
892 for (i = 0; i < task->workstation_nb; i++)
893 surf_workstations[i] = task->workstation_list[i]->surf_workstation;
895 /* 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 */
896 #define cost_or_zero(array,pos) ((array)?(array)[pos]:0.0)
898 task->surf_action = NULL;
899 if ((task->workstation_nb == 1)
900 && (cost_or_zero(task->communication_amount, 0) == 0.0)) {
902 surf_workstation_model->extension.
903 workstation.execute(surf_workstations[0],
904 cost_or_zero(task->computation_amount, 0));
905 } else if ((task->workstation_nb == 1)
906 && (cost_or_zero(task->computation_amount, 0) == 0.0)) {
909 surf_workstation_model->extension.
910 workstation.communicate(surf_workstations[0], surf_workstations[0],
911 cost_or_zero(task->communication_amount,
913 } else if ((task->workstation_nb == 2)
914 && (cost_or_zero(task->computation_amount, 0) == 0.0)
915 && (cost_or_zero(task->computation_amount, 1) == 0.0)) {
919 for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
920 if (cost_or_zero(task->communication_amount, i) > 0.0) {
922 value = cost_or_zero(task->communication_amount, i);
927 surf_workstation_model->extension.
928 workstation.communicate(surf_workstations[0],
929 surf_workstations[1], value, task->rate);
934 if (!task->surf_action) {
935 double *computation_amount = xbt_new(double, task->workstation_nb);
936 double *communication_amount = xbt_new(double, task->workstation_nb *
937 task->workstation_nb);
939 memcpy(computation_amount, task->computation_amount, sizeof(double) *
940 task->workstation_nb);
941 memcpy(communication_amount, task->communication_amount,
942 sizeof(double) * task->workstation_nb * task->workstation_nb);
945 surf_workstation_model->extension.
946 workstation.execute_parallel_task(task->workstation_nb,
949 communication_amount,
950 task->amount, task->rate);
952 xbt_free(surf_workstations);
955 surf_workstation_model->action_data_set(task->surf_action, task);
957 DEBUG1("surf_action = %p", task->surf_action);
961 TRACE_surf_action(task->surf_action, task->category);
965 jedule_log_sd_event(task);
968 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
969 __SD_task_set_state(task, SD_RUNNING);
970 xbt_assert2(__SD_task_is_running(task), "Bad state of task '%s': %d",
971 SD_task_get_name(task), SD_task_get_state(task));
975 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_RUNNABLE
976 * (ie when its dependencies are satisfied).
977 * If one of the workstations where the task is scheduled on is busy (in sequential mode),
978 * the task doesn't start.
979 * Returns whether the task has started.
981 int __SD_task_try_to_run(SD_task_t task)
986 SD_workstation_t workstation;
988 SD_CHECK_INIT_DONE();
989 xbt_assert0(task != NULL, "Invalid parameter");
990 xbt_assert2(__SD_task_is_runnable(task),
991 "Task '%s' is not runnable! Task state: %d",
992 SD_task_get_name(task), SD_task_get_state(task));
995 for (i = 0; i < task->workstation_nb; i++) {
996 can_start = can_start &&
997 !__SD_workstation_is_busy(task->workstation_list[i]);
1000 DEBUG2("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1002 if (!can_start) { /* if the task cannot start and is not in the fifos yet */
1003 for (i = 0; i < task->workstation_nb; i++) {
1004 workstation = task->workstation_list[i];
1005 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1006 DEBUG2("Pushing task '%s' in the fifo of workstation '%s'",
1007 SD_task_get_name(task),
1008 SD_workstation_get_name(workstation));
1009 xbt_fifo_push(workstation->task_fifo, task);
1012 __SD_task_set_state(task, SD_IN_FIFO);
1013 xbt_assert2(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1014 SD_task_get_name(task), SD_task_get_state(task));
1015 DEBUG1("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1017 __SD_task_really_run(task);
1023 /* This function is called by SD_simulate when a task is done.
1024 * It updates task->state and task->action and executes if necessary the tasks
1025 * which were waiting in fifos for the end of `task'
1027 void __SD_task_just_done(SD_task_t task)
1030 SD_workstation_t workstation;
1032 SD_task_t candidate;
1033 int candidate_nb = 0;
1034 int candidate_capacity = 8;
1035 SD_task_t *candidates;
1038 SD_CHECK_INIT_DONE();
1039 xbt_assert0(task != NULL, "Invalid parameter");
1040 xbt_assert1(__SD_task_is_running(task),
1041 "The task must be running! Task state: %d",
1042 SD_task_get_state(task));
1043 xbt_assert1(task->workstation_list != NULL,
1044 "Task '%s': workstation_list is NULL!",
1045 SD_task_get_name(task));
1048 candidates = xbt_new(SD_task_t, 8);
1050 __SD_task_set_state(task, SD_DONE);
1051 surf_workstation_model->action_unref(task->surf_action);
1052 task->surf_action = NULL;
1054 DEBUG0("Looking for candidates");
1056 /* if the task was executed on sequential workstations,
1057 maybe we can execute the next task of the fifo for each workstation */
1058 for (i = 0; i < task->workstation_nb; i++) {
1059 workstation = task->workstation_list[i];
1060 DEBUG2("Workstation '%s': access_mode = %d",
1061 SD_workstation_get_name(workstation), workstation->access_mode);
1062 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1063 xbt_assert1(workstation->task_fifo != NULL,
1064 "Workstation '%s' has sequential access but no fifo!",
1065 SD_workstation_get_name(workstation));
1066 xbt_assert2(workstation->current_task =
1067 task, "Workstation '%s': current task should be '%s'",
1068 SD_workstation_get_name(workstation),
1069 SD_task_get_name(task));
1071 /* the task is over so we can release the workstation */
1072 workstation->current_task = NULL;
1074 DEBUG0("Getting candidate in fifo");
1076 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1077 (workstation->task_fifo));
1079 if (candidate != NULL) {
1080 DEBUG1("Candidate: '%s'", SD_task_get_name(candidate));
1081 xbt_assert2(__SD_task_is_in_fifo(candidate),
1082 "Bad state of candidate '%s': %d",
1083 SD_task_get_name(candidate),
1084 SD_task_get_state(candidate));
1087 DEBUG1("Candidate in fifo: %p", candidate);
1089 /* if there was a task waiting for my place */
1090 if (candidate != NULL) {
1091 /* Unfortunately, we are not sure yet that we can execute the task now,
1092 because the task can be waiting more deeply in some other workstation's fifos...
1093 So we memorize all candidate tasks, and then we will check for each candidate
1094 whether or not all its workstations are available. */
1096 /* realloc if necessary */
1097 if (candidate_nb == candidate_capacity) {
1098 candidate_capacity *= 2;
1100 xbt_realloc(candidates,
1101 sizeof(SD_task_t) * candidate_capacity);
1104 /* register the candidate */
1105 candidates[candidate_nb++] = candidate;
1106 candidate->fifo_checked = 0;
1111 DEBUG1("Candidates found: %d", candidate_nb);
1113 /* now we check every candidate task */
1114 for (i = 0; i < candidate_nb; i++) {
1115 candidate = candidates[i];
1117 if (candidate->fifo_checked) {
1118 continue; /* we have already evaluated that task */
1121 xbt_assert2(__SD_task_is_in_fifo(candidate),
1122 "Bad state of candidate '%s': %d",
1123 SD_task_get_name(candidate), SD_task_get_state(candidate));
1125 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1126 workstation = candidate->workstation_list[j];
1128 /* I can start on this workstation if the workstation is shared
1129 or if I am the first task in the fifo */
1130 can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS
1132 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1133 (workstation->task_fifo));
1136 DEBUG2("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1139 /* now we are sure that I can start! */
1141 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1142 workstation = candidate->workstation_list[j];
1144 /* update the fifo */
1145 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1146 candidate = xbt_fifo_shift(workstation->task_fifo); /* the return value is stored just for debugging */
1147 DEBUG1("Head of the fifo: '%s'",
1149 NULL) ? SD_task_get_name(candidate) : "NULL");
1150 xbt_assert0(candidate == candidates[i],
1151 "Error in __SD_task_just_done: bad first task in the fifo");
1153 } /* for each workstation */
1155 /* finally execute the task */
1156 DEBUG2("Task '%s' state: %d", SD_task_get_name(candidate),
1157 SD_task_get_state(candidate));
1158 __SD_task_really_run(candidate);
1161 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1162 SD_task_get_name(candidate), candidate->state_set,
1163 sd_global->running_task_set, __SD_task_is_running(candidate));
1164 xbt_assert2(__SD_task_is_running(candidate),
1165 "Bad state of task '%s': %d",
1166 SD_task_get_name(candidate),
1167 SD_task_get_state(candidate));
1168 DEBUG0("Okay, the task is running.");
1171 candidate->fifo_checked = 1;
1172 } /* for each candidate */
1174 xbt_free(candidates);
1177 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1179 static void __SD_task_remove_dependencies(SD_task_t task)
1181 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1182 because each one is stored twice */
1183 SD_dependency_t dependency;
1184 while (xbt_dynar_length(task->tasks_before) > 0) {
1185 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1186 SD_task_dependency_remove(dependency->src, dependency->dst);
1189 while (xbt_dynar_length(task->tasks_after) > 0) {
1190 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1191 SD_task_dependency_remove(dependency->src, dependency->dst);
1196 * \brief Returns the start time of a task
1198 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1200 * \param task: a task
1201 * \return the start time of this task
1203 double SD_task_get_start_time(SD_task_t task)
1205 SD_CHECK_INIT_DONE();
1206 xbt_assert0(task != NULL, "Invalid parameter");
1207 if (task->surf_action)
1208 return surf_workstation_model->
1209 action_get_start_time(task->surf_action);
1211 return task->start_time;
1215 * \brief Returns the finish time of a task
1217 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1218 * If the state is not completed yet, the returned value is an
1219 * estimation of the task finish time. This value can fluctuate
1220 * until the task is completed.
1222 * \param task: a task
1223 * \return the start time of this task
1225 double SD_task_get_finish_time(SD_task_t task)
1227 SD_CHECK_INIT_DONE();
1228 xbt_assert0(task != NULL, "Invalid parameter");
1230 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1231 return surf_workstation_model->
1232 action_get_finish_time(task->surf_action);
1234 return task->finish_time;
1238 * \brief Destroys a task.
1240 * The user data (if any) should have been destroyed first.
1242 * \param task the task you want to destroy
1243 * \see SD_task_create()
1245 void SD_task_destroy(SD_task_t task)
1247 SD_CHECK_INIT_DONE();
1248 xbt_assert0(task != NULL, "Invalid parameter");
1250 DEBUG1("Destroying task %s...", SD_task_get_name(task));
1252 __SD_task_remove_dependencies(task);
1253 /* if the task was scheduled or runnable we have to free the scheduling parameters */
1254 if (__SD_task_is_scheduled_or_runnable(task))
1255 __SD_task_destroy_scheduling_data(task);
1256 xbt_swag_remove(task, task->state_set);
1258 if (task->name != NULL)
1259 xbt_free(task->name);
1261 if (task->surf_action != NULL)
1262 surf_workstation_model->action_unref(task->surf_action);
1264 if (task->workstation_list != NULL)
1265 xbt_free(task->workstation_list);
1267 if (task->communication_amount)
1268 xbt_free(task->communication_amount);
1270 if (task->computation_amount)
1271 xbt_free(task->computation_amount);
1274 TRACE_sd_task_destroy(task);
1277 xbt_dynar_free(&task->tasks_before);
1278 xbt_dynar_free(&task->tasks_after);
1281 sd_global->task_number--;
1283 DEBUG0("Task destroyed.");
1287 static XBT_INLINE SD_task_t SD_task_create_sized(const char *name,
1288 void *data, double amount,
1291 SD_task_t task = SD_task_create(name, data, amount);
1292 task->communication_amount = xbt_new0(double, ws_count * ws_count);
1293 task->computation_amount = xbt_new0(double, ws_count);
1294 task->workstation_nb = ws_count;
1295 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1299 /** @brief create a end-to-end communication task that can then be auto-scheduled
1301 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1302 * allows to specify the task costs at creation, and decorelate them from the
1303 * scheduling process where you just specify which resource should deliver the
1306 * A end-to-end communication must be scheduled on 2 hosts, and the amount
1307 * specified at creation is sent from hosts[0] to hosts[1].
1309 SD_task_t SD_task_create_comm_e2e(const char *name, void *data,
1312 SD_task_t res = SD_task_create_sized(name, data, amount, 2);
1313 res->communication_amount[2] = amount;
1314 res->kind = SD_TASK_COMM_E2E;
1318 /** @brief create a sequential computation task that can then be auto-scheduled
1320 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1321 * allows to specify the task costs at creation, and decorelate them from the
1322 * scheduling process where you just specify which resource should deliver the
1325 * A sequential computation must be scheduled on 1 host, and the amount
1326 * specified at creation to be run on hosts[0].
1328 SD_task_t SD_task_create_comp_seq(const char *name, void *data,
1331 SD_task_t res = SD_task_create_sized(name, data, amount, 1);
1332 res->computation_amount[0] = amount;
1333 res->kind = SD_TASK_COMP_SEQ;
1337 /** @brief Auto-schedules a task.
1339 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1340 * allows to specify the task costs at creation, and decorelate them from the
1341 * scheduling process where you just specify which resource should deliver the
1344 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1345 * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1349 * We should create tasks kind for the following categories:
1350 * - Point to point communication (done)
1351 * - Sequential computation (done)
1352 * - group communication (redistribution, several kinds)
1353 * - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1354 * - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1356 void SD_task_schedulev(SD_task_t task, int count,
1357 const SD_workstation_t * list)
1360 SD_dependency_t dep;
1362 xbt_assert1(task->kind != 0,
1363 "Task %s is not typed. Cannot automatically schedule it.",
1364 SD_task_get_name(task));
1365 switch (task->kind) {
1366 case SD_TASK_COMM_E2E:
1367 case SD_TASK_COMP_SEQ:
1368 xbt_assert(task->workstation_nb == count);
1369 for (i = 0; i < count; i++)
1370 task->workstation_list[i] = list[i];
1371 SD_task_do_schedule(task);
1374 xbt_die(bprintf("Kind of task %s not supported by SD_task_schedulev()",
1375 SD_task_get_name(task)));
1377 if (task->kind == SD_TASK_COMM_E2E) {
1378 VERB4("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1379 SD_task_get_name(task),
1380 SD_workstation_get_name(task->workstation_list[0]),
1381 SD_workstation_get_name(task->workstation_list[1]),
1382 task->communication_amount[2]);
1385 /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if runnable) */
1386 if (task->kind == SD_TASK_COMP_SEQ) {
1387 VERB3("Schedule computation task %s on %s. It costs %.f flops",
1388 SD_task_get_name(task),
1389 SD_workstation_get_name(task->workstation_list[0]),
1390 task->computation_amount[0]);
1392 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1393 SD_task_t before = dep->src;
1394 if (before->kind == SD_TASK_COMM_E2E) {
1395 before->workstation_list[1] = task->workstation_list[0];
1397 if (before->workstation_list[0] &&
1398 (__SD_task_is_schedulable(before)
1399 || __SD_task_is_not_scheduled(before))) {
1400 SD_task_do_schedule(before);
1402 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1403 SD_task_get_name(before),
1404 SD_workstation_get_name(before->workstation_list[0]),
1405 SD_workstation_get_name(before->workstation_list[1]),
1406 before->communication_amount[2]);
1410 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1411 SD_task_t after = dep->dst;
1412 if (after->kind == SD_TASK_COMM_E2E) {
1413 after->workstation_list[0] = task->workstation_list[0];
1414 //J-N : Why did you comment on these line (this comment add a bug I think)?
1415 if (after->workstation_list[1]
1416 && (__SD_task_is_not_scheduled(after)
1417 || __SD_task_is_schedulable(after))) {
1418 SD_task_do_schedule(after);
1420 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1421 SD_task_get_name(after),
1422 SD_workstation_get_name(after->workstation_list[0]),
1423 SD_workstation_get_name(after->workstation_list[1]),
1424 after->communication_amount[2]);
1432 /** @brief autoschedule a task on a list of workstations
1434 * This function is very similar to SD_task_schedulev(),
1435 * but takes the list of workstations to schedule onto as separate parameters.
1436 * It builds a proper vector of workstations and then call SD_task_schedulev()
1438 void SD_task_schedulel(SD_task_t task, int count, ...)
1441 SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1443 va_start(ap, count);
1444 for (i = 0; i < count; i++) {
1445 list[i] = va_arg(ap, SD_workstation_t);
1448 SD_task_schedulev(task, count, list);