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;
56 /* scheduling parameters */
57 task->workstation_nb = 0;
58 task->workstation_list = NULL;
59 task->computation_amount = NULL;
60 task->communication_amount = NULL;
63 sd_global->task_number++;
69 * \brief Returns the user data of a task
72 * \return the user data associated with this task (can be \c NULL)
73 * \see SD_task_set_data()
75 void *SD_task_get_data(SD_task_t task)
78 xbt_assert0(task != NULL, "Invalid parameter");
83 * \brief Sets the user data of a task
85 * The new data can be \c NULL. The old data should have been freed first
86 * if it was not \c NULL.
89 * \param data the new data you want to associate with this task
90 * \see SD_task_get_data()
92 void SD_task_set_data(SD_task_t task, void *data)
95 xbt_assert0(task != NULL, "Invalid parameter");
100 * \brief Returns the state of a task
103 * \return the current \ref e_SD_task_state_t "state" of this task:
104 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
105 * \see e_SD_task_state_t
107 e_SD_task_state_t SD_task_get_state(SD_task_t task)
109 SD_CHECK_INIT_DONE();
110 xbt_assert0(task != NULL, "Invalid parameter");
114 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
116 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
118 xbt_swag_remove(task, task->state_set);
120 case SD_NOT_SCHEDULED:
121 task->state_set = sd_global->not_scheduled_task_set;
124 task->state_set = sd_global->ready_task_set;
127 task->state_set = sd_global->scheduled_task_set;
130 task->state_set = sd_global->runnable_task_set;
133 task->state_set = sd_global->in_fifo_task_set;
136 task->state_set = sd_global->running_task_set;
138 surf_workstation_model->action_get_start_time(task->surf_action);
141 task->state_set = sd_global->done_task_set;
143 surf_workstation_model->action_get_finish_time(task->surf_action);
147 task->state_set = sd_global->failed_task_set;
150 xbt_assert0(0, "Invalid state");
152 xbt_swag_insert(task, task->state_set);
153 task->state = new_state;
155 if (task->watch_points & new_state) {
156 VERB1("Watch point reached with task '%s'!", SD_task_get_name(task));
157 sd_global->watch_point_reached = 1;
158 SD_task_unwatch(task, new_state); /* remove the watch point */
163 * \brief Returns the name of a task
166 * \return the name of this task (can be \c NULL)
168 const char *SD_task_get_name(SD_task_t task)
170 SD_CHECK_INIT_DONE();
171 xbt_assert0(task != NULL, "Invalid parameter");
175 /** @brief Allows to change the name of a task */
176 void SD_task_set_name(SD_task_t task, const char *name) {
177 xbt_free(task->name);
178 task->name = xbt_strdup(name);
181 /** @brief Returns the dynar of the parents of a task
184 * \return a newly allocated dynar comprising the parents of this task
187 xbt_dynar_t SD_task_get_parents(SD_task_t task)
192 SD_CHECK_INIT_DONE();
193 xbt_assert0(task != NULL, "Invalid parameter");
195 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
196 xbt_dynar_foreach(task->tasks_before, i, dep){
197 xbt_dynar_push(parents, &(dep->src));
202 /** @brief Returns the dynar of the parents of a task
205 * \return a newly allocated dynar comprising the parents of this task
207 xbt_dynar_t SD_task_get_children(SD_task_t task)
210 xbt_dynar_t children;
212 SD_CHECK_INIT_DONE();
213 xbt_assert0(task != NULL, "Invalid parameter");
215 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
216 xbt_dynar_foreach(task->tasks_after, i, dep){
217 xbt_dynar_push(children, &(dep->dst));
223 * \brief Returns the amount of workstations involved in a task
225 * Only call this on already scheduled tasks!
228 int SD_task_get_workstation_count(SD_task_t task)
230 SD_CHECK_INIT_DONE();
231 xbt_assert0(task != NULL, "Invalid parameter");
232 // xbt_assert1( task->state_set != sd_global->scheduled_task_set,
233 // "Unscheduled task %s", task->name);
234 return task->workstation_nb;
238 * \brief Returns the list of workstations involved in a task
240 * Only call this on already scheduled tasks!
243 SD_workstation_t* SD_task_get_workstation_list(SD_task_t task)
245 SD_CHECK_INIT_DONE();
246 xbt_assert0(task != NULL, "Invalid parameter");
247 //xbt_assert1( task->state_set != sd_global->scheduled_task_set,
248 // "Unscheduled task %s", task->name);
249 return task->workstation_list;
253 * \brief Returns the total amount of work contained in a task
256 * \return the total amount of work (computation or data transfer) for this task
257 * \see SD_task_get_remaining_amount()
259 double SD_task_get_amount(SD_task_t task)
261 SD_CHECK_INIT_DONE();
262 xbt_assert0(task != NULL, "Invalid parameter");
267 * \brief Returns the remaining amount work to do till the completion of a task
270 * \return the remaining amount of work (computation or data transfer) of this task
271 * \see SD_task_get_amount()
273 double SD_task_get_remaining_amount(SD_task_t task)
275 SD_CHECK_INIT_DONE();
276 xbt_assert0(task != NULL, "Invalid parameter");
278 if (task->surf_action)
279 return surf_workstation_model->get_remains(task->surf_action);
281 return task->remains;
284 int SD_task_get_kind(SD_task_t task) {
288 /** @brief Displays debugging informations about a task */
289 void SD_task_dump(SD_task_t task)
291 unsigned int counter;
292 SD_dependency_t dependency;
295 INFO1("Displaying task %s",SD_task_get_name(task));
296 statename=bprintf("%s %s %s %s %s %s %s",
297 (task->state&SD_NOT_SCHEDULED?"not scheduled":""),
298 (task->state&SD_READY?"ready":""),
299 (task->state&SD_SCHEDULED?"scheduled":""),
300 (task->state&SD_RUNNABLE?"runnable":"not runnable"),
301 (task->state&SD_IN_FIFO?"in fifo":""),
302 (task->state&SD_RUNNING?"running":""),
303 (task->state&SD_DONE?"done":""),
304 (task->state&SD_FAILED?"failed":""));
305 INFO1(" - state: %s",statename);
310 case SD_TASK_COMM_E2E:
311 INFO0(" - kind: end-to-end communication");
313 case SD_TASK_COMP_SEQ:
314 INFO0(" - kind: sequential computation");
317 INFO1(" - (unknown kind %d)",task->kind);
320 INFO1(" - amount: %.0f",SD_task_get_amount(task));
321 INFO1(" - Dependencies to satisfy: %d", task->unsatisfied_dependencies);
322 if (xbt_dynar_length(task->tasks_before)) {
323 INFO0(" - pre-dependencies:");
324 xbt_dynar_foreach(task->tasks_before,counter,dependency) {
325 INFO1(" %s",SD_task_get_name(dependency->src));
328 if (xbt_dynar_length(task->tasks_after)) {
329 INFO0(" - post-dependencies:");
330 xbt_dynar_foreach(task->tasks_after,counter,dependency) {
331 INFO1(" %s",SD_task_get_name(dependency->dst));
335 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
336 void SD_task_dotty(SD_task_t task,void* out) {
337 unsigned int counter;
338 SD_dependency_t dependency;
339 fprintf(out, " T%p [label=\"%.20s\"",task, task->name);
341 case SD_TASK_COMM_E2E:
342 fprintf(out,", shape=box");
344 case SD_TASK_COMP_SEQ:
345 fprintf(out,", shape=circle");
348 xbt_die("Unknown task type!");
351 xbt_dynar_foreach(task->tasks_before,counter,dependency) {
352 fprintf(out," T%p -> T%p;\n",dependency->src, dependency->dst);
356 /* Destroys a dependency between two tasks.
358 static void __SD_task_dependency_destroy(void *dependency)
360 if (((SD_dependency_t) dependency)->name != NULL)
361 xbt_free(((SD_dependency_t) dependency)->name);
362 xbt_free(dependency);
366 * \brief Adds a dependency between two tasks
368 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
369 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
371 * \param name the name of the new dependency (can be \c NULL)
372 * \param data the user data you want to associate with this dependency (can be \c NULL)
373 * \param src the task which must be executed first
374 * \param dst the task you want to make depend on \a src
375 * \see SD_task_dependency_remove()
377 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
384 SD_dependency_t dependency;
386 SD_CHECK_INIT_DONE();
387 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
389 dynar = src->tasks_after;
390 length = xbt_dynar_length(dynar);
394 "Cannot add a dependency between task '%s' and itself",
395 SD_task_get_name(src));
397 if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_ready(src)
398 && !__SD_task_is_scheduled_or_runnable(src))
400 "Task '%s' must be SD_NOT_SCHEDULED, SD_READY, SD_SCHEDULED or SD_RUNNABLE",
401 SD_task_get_name(src));
403 if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_ready(dst)
404 && !__SD_task_is_scheduled_or_runnable(dst))
406 "Task '%s' must be SD_NOT_SCHEDULED, SD_READY, SD_SCHEDULED or SD_RUNNABLE",
407 SD_task_get_name(dst));
409 DEBUG2("SD_task_dependency_add: src = %s, dst = %s", SD_task_get_name(src),
410 SD_task_get_name(dst));
411 for (i = 0; i < length && !found; i++) {
412 xbt_dynar_get_cpy(dynar, i, &dependency);
413 found = (dependency->dst == dst);
414 DEBUG2("Dependency %d: dependency->dst = %s", i,
415 SD_task_get_name(dependency->dst));
420 "A dependency already exists between task '%s' and task '%s'",
421 SD_task_get_name(src), SD_task_get_name(dst));
423 dependency = xbt_new(s_SD_dependency_t, 1);
425 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
426 dependency->data = data;
427 dependency->src = src;
428 dependency->dst = dst;
430 /* src must be executed before dst */
431 xbt_dynar_push(src->tasks_after, &dependency);
432 xbt_dynar_push(dst->tasks_before, &dependency);
434 dst->unsatisfied_dependencies++;
436 /* if the task was runnable, then dst->tasks_before is not empty anymore,
437 so we must go back to state SD_SCHEDULED */
438 if (__SD_task_is_runnable(dst)) {
439 DEBUG1("SD_task_dependency_add: %s was runnable and becomes scheduled!",
440 SD_task_get_name(dst));
441 __SD_task_set_state(dst, SD_SCHEDULED);
444 /* __SD_print_dependencies(src);
445 __SD_print_dependencies(dst); */
449 * \brief Indacates whether there is a dependency between two tasks.
452 * \param dst a task depending on \a src
454 * If src is NULL, checks whether dst has any pre-dependency.
455 * If dst is NULL, checks whether src has any post-dependency.
457 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
459 unsigned int counter;
460 SD_dependency_t dependency;
462 SD_CHECK_INIT_DONE();
463 xbt_assert0(src != NULL || dst != NULL, "Invalid parameter: both src and dst are NULL");
467 xbt_dynar_foreach(src->tasks_after,counter,dependency) {
468 if (dependency->dst == dst)
472 return xbt_dynar_length(src->tasks_after);
475 return xbt_dynar_length(dst->tasks_before);
481 * \brief Remove a dependency between two tasks
484 * \param dst a task depending on \a src
485 * \see SD_task_dependency_add()
487 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
494 SD_dependency_t dependency;
496 SD_CHECK_INIT_DONE();
497 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
499 /* remove the dependency from src->tasks_after */
500 dynar = src->tasks_after;
501 length = xbt_dynar_length(dynar);
503 for (i = 0; i < length && !found; i++) {
504 xbt_dynar_get_cpy(dynar, i, &dependency);
505 if (dependency->dst == dst) {
506 xbt_dynar_remove_at(dynar, i, NULL);
512 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
513 SD_task_get_name(src), SD_task_get_name(dst),
514 SD_task_get_name(dst), SD_task_get_name(src));
516 /* remove the dependency from dst->tasks_before */
517 dynar = dst->tasks_before;
518 length = xbt_dynar_length(dynar);
521 for (i = 0; i < length && !found; i++) {
522 xbt_dynar_get_cpy(dynar, i, &dependency);
523 if (dependency->src == src) {
524 xbt_dynar_remove_at(dynar, i, NULL);
525 __SD_task_dependency_destroy(dependency);
526 dst->unsatisfied_dependencies--;
530 /* should never happen... */
532 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
533 SD_task_get_name(dst), SD_task_get_name(src),
534 SD_task_get_name(src), SD_task_get_name(dst));
536 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
538 if (dst->unsatisfied_dependencies == 0){
539 if (__SD_task_is_scheduled(dst))
540 __SD_task_set_state(dst, SD_RUNNABLE);
542 __SD_task_set_state(dst, SD_READY);
544 /* __SD_print_dependencies(src);
545 __SD_print_dependencies(dst); */
549 * \brief Returns the user data associated with a dependency between two tasks
552 * \param dst a task depending on \a src
553 * \return the user data associated with this dependency (can be \c NULL)
554 * \see SD_task_dependency_add()
556 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
563 SD_dependency_t dependency;
566 SD_CHECK_INIT_DONE();
567 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
569 dynar = src->tasks_after;
570 length = xbt_dynar_length(dynar);
572 for (i = 0; i < length && !found; i++) {
573 xbt_dynar_get_cpy(dynar, i, &dependency);
574 found = (dependency->dst == dst);
577 THROW2(arg_error, 0, "No dependency found between task '%s' and '%s'",
578 SD_task_get_name(src), SD_task_get_name(dst));
579 return dependency->data;
582 /* temporary function for debugging */
583 static void __SD_print_watch_points(SD_task_t task)
585 static const int state_masks[] =
586 { SD_READY, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE, SD_FAILED };
587 static const char *state_names[] =
588 { "ready", "scheduled", "running", "runnable", "done", "failed" };
591 INFO2("Task '%s' watch points (%x): ", SD_task_get_name(task),
595 for (i = 0; i < 5; i++) {
596 if (task->watch_points & state_masks[i])
597 INFO1("%s ", state_names[i]);
602 * \brief Adds a watch point to a task
604 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
605 * task becomes the one given in argument. The
606 * watch point is then automatically removed.
609 * \param state the \ref e_SD_task_state_t "state" you want to watch
610 * (cannot be #SD_NOT_SCHEDULED)
611 * \see SD_task_unwatch()
613 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
615 SD_CHECK_INIT_DONE();
616 xbt_assert0(task != NULL, "Invalid parameter");
618 if (state & SD_NOT_SCHEDULED)
620 "Cannot add a watch point for state SD_NOT_SCHEDULED");
622 task->watch_points = task->watch_points | state;
623 /* __SD_print_watch_points(task); */
627 * \brief Removes a watch point from a task
630 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
631 * \see SD_task_watch()
633 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
635 SD_CHECK_INIT_DONE();
636 xbt_assert0(task != NULL, "Invalid parameter");
637 xbt_assert0(state != SD_NOT_SCHEDULED,
638 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
640 task->watch_points = task->watch_points & ~state;
641 /* __SD_print_watch_points(task); */
645 * \brief Returns an approximative estimation of the execution time of a task.
647 * The estimation is very approximative because the value returned is the time
648 * the task would take if it was executed now and if it was the only task.
650 * \param task the task to evaluate
651 * \param workstation_nb number of workstations on which the task would be executed
652 * \param workstation_list the workstations on which the task would be executed
653 * \param computation_amount computation amount for each workstation
654 * \param communication_amount communication amount between each pair of workstations
657 double SD_task_get_execution_time(SD_task_t task,
659 const SD_workstation_t * workstation_list,
660 const double *computation_amount,
661 const double *communication_amount)
663 double time, max_time = 0.0;
665 SD_CHECK_INIT_DONE();
666 xbt_assert0(task != NULL && workstation_nb > 0 && workstation_list != NULL,
667 "Invalid parameter");
669 /* the task execution time is the maximum execution time of the parallel tasks */
671 for (i = 0; i < workstation_nb; i++) {
673 if (computation_amount != NULL)
675 SD_workstation_get_computation_time(workstation_list[i],
676 computation_amount[i]);
678 if (communication_amount != NULL)
679 for (j = 0; j < workstation_nb; j++) {
681 SD_route_get_communication_time(workstation_list[i],
683 communication_amount[i *
688 if (time > max_time) {
694 static XBT_INLINE void SD_task_do_schedule(SD_task_t task) {
695 SD_CHECK_INIT_DONE();
697 if (!__SD_task_is_not_scheduled(task))
698 THROW1(arg_error, 0, "Task '%s' has already been scheduled",
699 SD_task_get_name(task));
701 /* update the task state */
702 if (task->unsatisfied_dependencies == 0)
703 __SD_task_set_state(task, SD_RUNNABLE);
705 __SD_task_set_state(task, SD_SCHEDULED);
709 * \brief Schedules a task
711 * The task state must be #SD_NOT_SCHEDULED.
712 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
713 * i.e. when its dependencies are satisfied.
715 * \param task the task you want to schedule
716 * \param workstation_nb number of workstations on which the task will be executed
717 * \param workstation_list the workstations on which the task will be executed
718 * \param computation_amount computation amount for each workstation
719 * \param communication_amount communication amount between each pair of workstations
720 * \param rate task execution speed rate
721 * \see SD_task_unschedule()
723 void SD_task_schedule(SD_task_t task, int workstation_count,
724 const SD_workstation_t * workstation_list,
725 const double *computation_amount,
726 const double *communication_amount, double rate)
728 int communication_nb;
729 task->workstation_nb = 0;
731 xbt_assert0(workstation_count > 0, "workstation_nb must be positive");
733 task->workstation_nb = workstation_count;
736 if (computation_amount) {
737 task->computation_amount = xbt_new(double, workstation_count);
738 memcpy(task->computation_amount, computation_amount,
739 sizeof(double) * workstation_count);
741 task->computation_amount = NULL;
744 communication_nb = workstation_count * workstation_count;
745 if (communication_amount) {
746 task->communication_amount = xbt_new(double, communication_nb);
747 memcpy(task->communication_amount, communication_amount,
748 sizeof(double) * communication_nb);
750 task->communication_amount = NULL;
753 task->workstation_list = xbt_new(SD_workstation_t, workstation_count);
754 memcpy(task->workstation_list, workstation_list,
755 sizeof(SD_workstation_t) * workstation_count);
757 SD_task_do_schedule(task);
760 * \brief Unschedules a task
762 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
763 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
764 * Call SD_task_schedule() to schedule it again.
766 * \param task the task you want to unschedule
767 * \see SD_task_schedule()
769 void SD_task_unschedule(SD_task_t task)
771 SD_CHECK_INIT_DONE();
772 xbt_assert0(task != NULL, "Invalid parameter");
774 if (task->state_set != sd_global->scheduled_task_set &&
775 task->state_set != sd_global->runnable_task_set &&
776 task->state_set != sd_global->running_task_set &&
777 task->state_set != sd_global->failed_task_set)
779 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
780 SD_task_get_name(task));
782 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
783 && task->kind == SD_TASK_NOT_TYPED) /* Don't free scheduling data for typed tasks */
784 __SD_task_destroy_scheduling_data(task);
786 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
787 surf_workstation_model->action_cancel(task->surf_action);
789 if (task->unsatisfied_dependencies == 0)
790 __SD_task_set_state(task, SD_READY);
792 __SD_task_set_state(task, SD_NOT_SCHEDULED);
794 task->remains = task->amount;
795 task->start_time = -1.0;
798 /* Destroys the data memorised by SD_task_schedule. Task state must be SD_SCHEDULED or SD_RUNNABLE.
800 static void __SD_task_destroy_scheduling_data(SD_task_t task)
802 SD_CHECK_INIT_DONE();
803 if (!__SD_task_is_scheduled_or_runnable(task) && !__SD_task_is_in_fifo(task))
805 "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
806 SD_task_get_name(task));
808 xbt_free(task->computation_amount);
809 xbt_free(task->communication_amount);
810 task->computation_amount = task->communication_amount = NULL;
813 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
814 * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
815 * the task gets out of its fifos.
817 void __SD_task_really_run(SD_task_t task)
821 void **surf_workstations;
823 SD_CHECK_INIT_DONE();
824 xbt_assert0(task != NULL, "Invalid parameter");
825 xbt_assert2(__SD_task_is_runnable_or_in_fifo(task),
826 "Task '%s' is not runnable or in a fifo! Task state: %d",
827 SD_task_get_name(task), SD_task_get_state(task));
828 xbt_assert1(task->workstation_list != NULL,
829 "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
833 DEBUG1("Really running task '%s'", SD_task_get_name(task));
835 /* set this task as current task for the workstations in sequential mode */
836 for (i = 0; i < task->workstation_nb; i++) {
837 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
838 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
839 task->workstation_list[i]->current_task = task;
840 xbt_assert0(__SD_workstation_is_busy(task->workstation_list[i]),
841 "The workstation should be busy now");
845 DEBUG1("Task '%s' set as current task for its workstations",
846 SD_task_get_name(task));
850 /* we have to create a Surf workstation array instead of the SimDag workstation array */
851 surf_workstations = xbt_new(void *, task->workstation_nb);
853 for (i = 0; i < task->workstation_nb; i++)
854 surf_workstations[i] = task->workstation_list[i]->surf_workstation;
856 /* 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 */
857 #define cost_or_zero(array,pos) ((array)?(array)[pos]:0.0)
859 task->surf_action = NULL;
860 if ((task->workstation_nb == 1) && (cost_or_zero(task->communication_amount,0) == 0.0)) {
862 surf_workstation_model->extension.
863 workstation.execute(surf_workstations[0], cost_or_zero(task->computation_amount,0));
864 } else if ((task->workstation_nb == 1)
865 && (cost_or_zero(task->computation_amount,0) == 0.0)) {
868 surf_workstation_model->extension.
869 workstation.communicate(surf_workstations[0], surf_workstations[0],
870 cost_or_zero(task->communication_amount,0), task->rate);
871 } else if ((task->workstation_nb == 2)
872 && (cost_or_zero(task->computation_amount,0) == 0.0)
873 && (cost_or_zero(task->computation_amount,1) == 0.0)) {
877 for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
878 if (cost_or_zero(task->communication_amount,i) > 0.0) {
880 value = cost_or_zero(task->communication_amount,i);
885 surf_workstation_model->extension.
886 workstation.communicate(surf_workstations[0], surf_workstations[1],
892 if (!task->surf_action) {
893 double *computation_amount = xbt_new(double, task->workstation_nb);
894 double *communication_amount = xbt_new(double, task->workstation_nb *
895 task->workstation_nb);
897 memcpy(computation_amount, task->computation_amount, sizeof(double) *
898 task->workstation_nb);
899 memcpy(communication_amount, task->communication_amount,
900 sizeof(double) * task->workstation_nb * task->workstation_nb);
903 surf_workstation_model->extension.
904 workstation.execute_parallel_task(task->workstation_nb,
905 surf_workstations, computation_amount,
906 communication_amount, task->amount,
909 xbt_free(surf_workstations);
912 surf_workstation_model->action_data_set(task->surf_action, task);
914 DEBUG1("surf_action = %p", task->surf_action);
916 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
917 __SD_task_set_state(task, SD_RUNNING);
918 xbt_assert2(__SD_task_is_running(task), "Bad state of task '%s': %d",
919 SD_task_get_name(task), SD_task_get_state(task));
923 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_RUNNABLE
924 * (ie when its dependencies are satisfied).
925 * If one of the workstations where the task is scheduled on is busy (in sequential mode),
926 * the task doesn't start.
927 * Returns whether the task has started.
929 int __SD_task_try_to_run(SD_task_t task)
934 SD_workstation_t workstation;
936 SD_CHECK_INIT_DONE();
937 xbt_assert0(task != NULL, "Invalid parameter");
938 xbt_assert2(__SD_task_is_runnable(task),
939 "Task '%s' is not runnable! Task state: %d",
940 SD_task_get_name(task), SD_task_get_state(task));
943 for (i = 0; i < task->workstation_nb; i++) {
944 can_start = can_start &&
945 !__SD_workstation_is_busy(task->workstation_list[i]);
948 DEBUG2("Task '%s' can start: %d", SD_task_get_name(task), can_start);
950 if (!can_start) { /* if the task cannot start and is not in the fifos yet */
951 for (i = 0; i < task->workstation_nb; i++) {
952 workstation = task->workstation_list[i];
953 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
954 DEBUG2("Pushing task '%s' in the fifo of workstation '%s'",
955 SD_task_get_name(task), SD_workstation_get_name(workstation));
956 xbt_fifo_push(workstation->task_fifo, task);
959 __SD_task_set_state(task, SD_IN_FIFO);
960 xbt_assert2(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
961 SD_task_get_name(task), SD_task_get_state(task));
962 DEBUG1("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
964 __SD_task_really_run(task);
970 /* This function is called by SD_simulate when a task is done.
971 * It updates task->state and task->action and executes if necessary the tasks
972 * which were waiting in fifos for the end of `task'
974 void __SD_task_just_done(SD_task_t task)
977 SD_workstation_t workstation;
980 int candidate_nb = 0;
981 int candidate_capacity = 8;
982 SD_task_t *candidates;
985 SD_CHECK_INIT_DONE();
986 xbt_assert0(task != NULL, "Invalid parameter");
987 xbt_assert1(__SD_task_is_running(task),
988 "The task must be running! Task state: %d",
989 SD_task_get_state(task));
990 xbt_assert1(task->workstation_list != NULL,
991 "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
994 candidates = xbt_new(SD_task_t, 8);
996 __SD_task_set_state(task, SD_DONE);
997 surf_workstation_model->action_unref(task->surf_action);
998 task->surf_action = NULL;
1000 DEBUG0("Looking for candidates");
1002 /* if the task was executed on sequential workstations,
1003 maybe we can execute the next task of the fifo for each workstation */
1004 for (i = 0; i < task->workstation_nb; i++) {
1005 workstation = task->workstation_list[i];
1006 DEBUG2("Workstation '%s': access_mode = %d",
1007 SD_workstation_get_name(workstation), workstation->access_mode);
1008 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1009 xbt_assert1(workstation->task_fifo != NULL,
1010 "Workstation '%s' has sequential access but no fifo!",
1011 SD_workstation_get_name(workstation));
1012 xbt_assert2(workstation->current_task =
1013 task, "Workstation '%s': current task should be '%s'",
1014 SD_workstation_get_name(workstation),
1015 SD_task_get_name(task));
1017 /* the task is over so we can release the workstation */
1018 workstation->current_task = NULL;
1020 DEBUG0("Getting candidate in fifo");
1022 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1023 (workstation->task_fifo));
1025 if (candidate != NULL) {
1026 DEBUG1("Candidate: '%s'", SD_task_get_name(candidate));
1027 xbt_assert2(__SD_task_is_in_fifo(candidate),
1028 "Bad state of candidate '%s': %d",
1029 SD_task_get_name(candidate),
1030 SD_task_get_state(candidate));
1033 DEBUG1("Candidate in fifo: %p", candidate);
1035 /* if there was a task waiting for my place */
1036 if (candidate != NULL) {
1037 /* Unfortunately, we are not sure yet that we can execute the task now,
1038 because the task can be waiting more deeply in some other workstation's fifos...
1039 So we memorize all candidate tasks, and then we will check for each candidate
1040 whether or not all its workstations are available. */
1042 /* realloc if necessary */
1043 if (candidate_nb == candidate_capacity) {
1044 candidate_capacity *= 2;
1046 xbt_realloc(candidates, sizeof(SD_task_t) * candidate_capacity);
1049 /* register the candidate */
1050 candidates[candidate_nb++] = candidate;
1051 candidate->fifo_checked = 0;
1056 DEBUG1("Candidates found: %d", candidate_nb);
1058 /* now we check every candidate task */
1059 for (i = 0; i < candidate_nb; i++) {
1060 candidate = candidates[i];
1062 if (candidate->fifo_checked) {
1063 continue; /* we have already evaluated that task */
1066 xbt_assert2(__SD_task_is_in_fifo(candidate),
1067 "Bad state of candidate '%s': %d",
1068 SD_task_get_name(candidate), SD_task_get_state(candidate));
1070 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1071 workstation = candidate->workstation_list[j];
1073 /* I can start on this workstation if the workstation is shared
1074 or if I am the first task in the fifo */
1075 can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS ||
1077 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1078 (workstation->task_fifo));
1081 DEBUG2("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1084 /* now we are sure that I can start! */
1086 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1087 workstation = candidate->workstation_list[j];
1089 /* update the fifo */
1090 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1091 candidate = xbt_fifo_shift(workstation->task_fifo); /* the return value is stored just for debugging */
1092 DEBUG1("Head of the fifo: '%s'",
1093 (candidate != NULL) ? SD_task_get_name(candidate) : "NULL");
1094 xbt_assert0(candidate == candidates[i],
1095 "Error in __SD_task_just_done: bad first task in the fifo");
1097 } /* for each workstation */
1099 /* finally execute the task */
1100 DEBUG2("Task '%s' state: %d", SD_task_get_name(candidate),
1101 SD_task_get_state(candidate));
1102 __SD_task_really_run(candidate);
1105 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1106 SD_task_get_name(candidate), candidate->state_set,
1107 sd_global->running_task_set, __SD_task_is_running(candidate));
1108 xbt_assert2(__SD_task_is_running(candidate),
1109 "Bad state of task '%s': %d", SD_task_get_name(candidate),
1110 SD_task_get_state(candidate));
1111 DEBUG0("Okay, the task is running.");
1114 candidate->fifo_checked = 1;
1115 } /* for each candidate */
1117 xbt_free(candidates);
1120 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1122 static void __SD_task_remove_dependencies(SD_task_t task)
1124 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1125 because each one is stored twice */
1126 SD_dependency_t dependency;
1127 while (xbt_dynar_length(task->tasks_before) > 0) {
1128 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1129 SD_task_dependency_remove(dependency->src, dependency->dst);
1132 while (xbt_dynar_length(task->tasks_after) > 0) {
1133 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1134 SD_task_dependency_remove(dependency->src, dependency->dst);
1139 * \brief Returns the start time of a task
1141 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1143 * \param task: a task
1144 * \return the start time of this task
1146 double SD_task_get_start_time(SD_task_t task)
1148 SD_CHECK_INIT_DONE();
1149 xbt_assert0(task != NULL, "Invalid parameter");
1150 if (task->surf_action)
1151 return surf_workstation_model->action_get_start_time(task->surf_action);
1153 return task->start_time;
1157 * \brief Returns the finish time of a task
1159 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1160 * If the state is not completed yet, the returned value is an
1161 * estimation of the task finish time. This value can fluctuate
1162 * until the task is completed.
1164 * \param task: a task
1165 * \return the start time of this task
1167 double SD_task_get_finish_time(SD_task_t task)
1169 SD_CHECK_INIT_DONE();
1170 xbt_assert0(task != NULL, "Invalid parameter");
1172 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1173 return surf_workstation_model->action_get_finish_time(task->surf_action);
1175 return task->finish_time;
1179 * \brief Destroys a task.
1181 * The user data (if any) should have been destroyed first.
1183 * \param task the task you want to destroy
1184 * \see SD_task_create()
1186 void SD_task_destroy(SD_task_t task)
1188 SD_CHECK_INIT_DONE();
1189 xbt_assert0(task != NULL, "Invalid parameter");
1191 DEBUG1("Destroying task %s...", SD_task_get_name(task));
1193 __SD_task_remove_dependencies(task);
1194 /* if the task was scheduled or runnable we have to free the scheduling parameters */
1195 if (__SD_task_is_scheduled_or_runnable(task))
1196 __SD_task_destroy_scheduling_data(task);
1197 xbt_swag_remove(task,task->state_set);
1199 if (task->name != NULL)
1200 xbt_free(task->name);
1202 if (task->surf_action != NULL)
1203 surf_workstation_model->action_unref(task->surf_action);
1205 if (task->workstation_list != NULL)
1206 xbt_free(task->workstation_list);
1208 if (task->communication_amount)
1209 xbt_free(task->communication_amount);
1211 if (task->computation_amount)
1212 xbt_free(task->computation_amount);
1214 xbt_dynar_free(&task->tasks_before);
1215 xbt_dynar_free(&task->tasks_after);
1218 sd_global->task_number--;
1220 DEBUG0("Task destroyed.");
1224 static XBT_INLINE SD_task_t SD_task_create_sized(const char*name,void*data,double amount,int ws_count) {
1225 SD_task_t task = SD_task_create(name,data,amount);
1226 task->communication_amount = xbt_new0(double,ws_count*ws_count);
1227 task->computation_amount = xbt_new0(double,ws_count);
1228 task->workstation_nb = ws_count;
1229 task->workstation_list = xbt_new0(SD_workstation_t,ws_count);
1232 /** @brief create a end-to-end communication task that can then be auto-scheduled
1234 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1235 * allows to specify the task costs at creation, and decorelate them from the
1236 * scheduling process where you just specify which resource should deliver the
1239 * A end-to-end communication must be scheduled on 2 hosts, and the amount
1240 * specified at creation is sent from hosts[0] to hosts[1].
1242 SD_task_t SD_task_create_comm_e2e(const char*name, void *data, double amount) {
1243 SD_task_t res = SD_task_create_sized(name,data,amount,2);
1244 res->communication_amount[2] = amount;
1245 res->kind=SD_TASK_COMM_E2E;
1248 /** @brief create a sequential computation task that can then be auto-scheduled
1250 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1251 * allows to specify the task costs at creation, and decorelate them from the
1252 * scheduling process where you just specify which resource should deliver the
1255 * A sequential computation must be scheduled on 1 host, and the amount
1256 * specified at creation to be run on hosts[0].
1258 SD_task_t SD_task_create_comp_seq(const char*name, void *data, double amount) {
1259 SD_task_t res = SD_task_create_sized(name,data,amount,1);
1260 res->computation_amount[0]=amount;
1261 res->kind=SD_TASK_COMP_SEQ;
1265 /** @brief Auto-schedules a task.
1267 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1268 * allows to specify the task costs at creation, and decorelate them from the
1269 * scheduling process where you just specify which resource should deliver the
1272 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1273 * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1277 * We should create tasks kind for the following categories:
1278 * - Point to point communication (done)
1279 * - Sequential computation (done)
1280 * - group communication (redistribution, several kinds)
1281 * - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1282 * - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1284 void SD_task_schedulev(SD_task_t task, int count, const SD_workstation_t*list) {
1286 SD_dependency_t dep;
1288 xbt_assert1(task->kind != 0,"Task %s is not typed. Cannot automatically schedule it.",SD_task_get_name(task));
1289 switch(task->kind) {
1290 case SD_TASK_COMM_E2E:
1291 case SD_TASK_COMP_SEQ:
1292 xbt_assert(task->workstation_nb==count);
1293 for (i=0;i<count;i++)
1294 task->workstation_list[i]=list[i];
1295 SD_task_do_schedule(task);
1298 xbt_die(bprintf("Kind of task %s not supported by SD_task_schedulev()",
1299 SD_task_get_name(task)));
1301 if (task->kind == SD_TASK_COMM_E2E) {
1302 VERB4("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1303 SD_task_get_name(task),
1304 SD_workstation_get_name(task->workstation_list[0]),SD_workstation_get_name(task->workstation_list[1]),
1305 task->communication_amount[2]);
1308 /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if runnable) */
1309 if (task->kind == SD_TASK_COMP_SEQ) {
1310 VERB3("Schedule computation task %s on %s. It costs %.f flops",
1311 SD_task_get_name(task),SD_workstation_get_name(task->workstation_list[0]),
1312 task->computation_amount[0]);
1314 xbt_dynar_foreach(task->tasks_before,cpt,dep) {
1315 SD_task_t before = dep->src;
1316 if (before->kind == SD_TASK_COMM_E2E) {
1317 before->workstation_list[1] = task->workstation_list[0];
1318 if (before->workstation_list[0] && __SD_task_is_not_scheduled(before)) {
1319 SD_task_do_schedule(before);
1320 VERB4("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1321 SD_task_get_name(before),
1322 SD_workstation_get_name(before->workstation_list[0]),SD_workstation_get_name(before->workstation_list[1]),
1323 before->communication_amount[2]);
1327 xbt_dynar_foreach(task->tasks_after,cpt,dep) {
1328 SD_task_t after = dep->dst;
1329 if (after->kind == SD_TASK_COMM_E2E) {
1330 after->workstation_list[0] = task->workstation_list[0];
1331 if (after->workstation_list[1] && __SD_task_is_not_scheduled(after)) {
1332 SD_task_do_schedule(after);
1333 VERB4("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1334 SD_task_get_name(after),
1335 SD_workstation_get_name(after->workstation_list[0]),SD_workstation_get_name(after->workstation_list[1]),
1336 after->communication_amount[2]);
1343 /** @brief autoschedule a task on a list of workstations
1345 * This function is very similar to SD_task_schedulev(),
1346 * but takes the list of workstations to schedule onto as separate parameters.
1347 * It builds a proper vector of workstations and then call SD_task_schedulev()
1349 void SD_task_schedulel(SD_task_t task, int count, ...) {
1351 SD_workstation_t *list=xbt_new(SD_workstation_t,count);
1354 for (i=0;i<count;i++) {
1355 list[i] = va_arg(ap,SD_workstation_t);
1358 SD_task_schedulev(task,count,list);