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);
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_READY, #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->scheduled_task_set;
127 task->state_set = sd_global->ready_task_set;
130 task->state_set = sd_global->in_fifo_task_set;
133 task->state_set = sd_global->running_task_set;
135 surf_workstation_model->action_get_start_time(task->surf_action);
138 task->state_set = sd_global->done_task_set;
140 surf_workstation_model->action_get_finish_time(task->surf_action);
144 task->state_set = sd_global->failed_task_set;
147 xbt_assert0(0, "Invalid state");
149 xbt_swag_insert(task, task->state_set);
150 task->state = new_state;
152 if (task->watch_points & new_state) {
153 INFO1("Watch point reached with task '%s'!", SD_task_get_name(task));
154 sd_global->watch_point_reached = 1;
155 SD_task_unwatch(task, new_state); /* remove the watch point */
160 * \brief Returns the name of a task
163 * \return the name of this task (can be \c NULL)
165 const char *SD_task_get_name(SD_task_t task)
167 SD_CHECK_INIT_DONE();
168 xbt_assert0(task != NULL, "Invalid parameter");
172 /** @brief Allows to change the name of a task */
173 void SD_task_set_name(SD_task_t task, const char *name) {
174 xbt_free(task->name);
175 task->name = xbt_strdup(name);
178 /** @brief Returns the dynar of the parents of a task
181 * \return a newly allocated dynar comprising the parents of this task
184 xbt_dynar_t SD_task_get_parents(SD_task_t task)
189 SD_CHECK_INIT_DONE();
190 xbt_assert0(task != NULL, "Invalid parameter");
192 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
193 xbt_dynar_foreach(task->tasks_before, i, dep){
194 xbt_dynar_push(parents, &(dep->src));
199 /** @brief Returns the dynar of the parents of a task
202 * \return a newly allocated dynar comprising the parents of this task
204 xbt_dynar_t SD_task_get_children(SD_task_t task)
207 xbt_dynar_t children;
209 SD_CHECK_INIT_DONE();
210 xbt_assert0(task != NULL, "Invalid parameter");
212 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
213 xbt_dynar_foreach(task->tasks_after, i, dep){
214 xbt_dynar_push(children, &(dep->dst));
220 * \brief Returns the amount of workstations involved in a task
222 * Only call this on already scheduled tasks!
225 int SD_task_get_workstation_count(SD_task_t task)
227 SD_CHECK_INIT_DONE();
228 xbt_assert0(task != NULL, "Invalid parameter");
229 // xbt_assert1( task->state_set != sd_global->scheduled_task_set,
230 // "Unscheduled task %s", task->name);
231 return task->workstation_nb;
235 * \brief Returns the list of workstations involved in a task
237 * Only call this on already scheduled tasks!
240 SD_workstation_t* SD_task_get_workstation_list(SD_task_t task)
242 SD_CHECK_INIT_DONE();
243 xbt_assert0(task != NULL, "Invalid parameter");
244 //xbt_assert1( task->state_set != sd_global->scheduled_task_set,
245 // "Unscheduled task %s", task->name);
246 return task->workstation_list;
250 * \brief Returns the total amount of work contained in a task
253 * \return the total amount of work (computation or data transfer) for this task
254 * \see SD_task_get_remaining_amount()
256 double SD_task_get_amount(SD_task_t task)
258 SD_CHECK_INIT_DONE();
259 xbt_assert0(task != NULL, "Invalid parameter");
264 * \brief Returns the remaining amount work to do till the completion of a task
267 * \return the remaining amount of work (computation or data transfer) of this task
268 * \see SD_task_get_amount()
270 double SD_task_get_remaining_amount(SD_task_t task)
272 SD_CHECK_INIT_DONE();
273 xbt_assert0(task != NULL, "Invalid parameter");
275 if (task->surf_action)
276 return surf_workstation_model->get_remains(task->surf_action);
278 return task->remains;
281 int SD_task_get_kind(SD_task_t task) {
285 /** @brief Displays debugging informations about a task */
286 void SD_task_dump(SD_task_t task)
288 unsigned int counter;
289 SD_dependency_t dependency;
292 INFO1("Displaying task %s",SD_task_get_name(task));
293 statename=bprintf("%s %s %s %s %s %s %s",
294 (task->state&SD_NOT_SCHEDULED?"not scheduled":""),
295 (task->state&SD_SCHEDULED?"scheduled":""),
296 (task->state&SD_READY?"ready":"not ready"),
297 (task->state&SD_IN_FIFO?"in fifo":""),
298 (task->state&SD_RUNNING?"running":""),
299 (task->state&SD_DONE?"done":""),
300 (task->state&SD_FAILED?"failed":""));
301 INFO1(" - state: %s",statename);
306 case SD_TASK_COMM_E2E:
307 INFO0(" - kind: end-to-end communication");
309 case SD_TASK_COMP_SEQ:
310 INFO0(" - kind: sequential computation");
313 INFO1(" - (unknown kind %d)",task->kind);
316 INFO1(" - amount: %.0f",SD_task_get_amount(task));
317 if (xbt_dynar_length(task->tasks_before)) {
318 INFO0(" - pre-dependencies:");
319 xbt_dynar_foreach(task->tasks_before,counter,dependency) {
320 INFO1(" %s",SD_task_get_name(dependency->src));
323 if (xbt_dynar_length(task->tasks_after)) {
324 INFO0(" - post-dependencies:");
325 xbt_dynar_foreach(task->tasks_after,counter,dependency) {
326 INFO1(" %s",SD_task_get_name(dependency->dst));
330 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
331 void SD_task_dotty(SD_task_t task,void* out) {
332 unsigned int counter;
333 SD_dependency_t dependency;
334 fprintf(out, " T%p [label=\"%.20s\"",task, task->name);
336 case SD_TASK_COMM_E2E:
337 fprintf(out,", shape=box");
339 case SD_TASK_COMP_SEQ:
340 fprintf(out,", shape=circle");
343 xbt_die("Unknown task type!");
346 xbt_dynar_foreach(task->tasks_before,counter,dependency) {
347 fprintf(out," T%p -> T%p;\n",dependency->src, dependency->dst);
351 /* Destroys a dependency between two tasks.
353 static void __SD_task_dependency_destroy(void *dependency)
355 if (((SD_dependency_t) dependency)->name != NULL)
356 xbt_free(((SD_dependency_t) dependency)->name);
357 xbt_free(dependency);
361 * \brief Adds a dependency between two tasks
363 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
364 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_READY.
366 * \param name the name of the new dependency (can be \c NULL)
367 * \param data the user data you want to associate with this dependency (can be \c NULL)
368 * \param src the task which must be executed first
369 * \param dst the task you want to make depend on \a src
370 * \see SD_task_dependency_remove()
372 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
379 SD_dependency_t dependency;
381 SD_CHECK_INIT_DONE();
382 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
384 dynar = src->tasks_after;
385 length = xbt_dynar_length(dynar);
389 "Cannot add a dependency between task '%s' and itself",
390 SD_task_get_name(src));
392 if (!__SD_task_is_not_scheduled(src)
393 && !__SD_task_is_scheduled_or_ready(src))
395 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
396 SD_task_get_name(src));
398 if (!__SD_task_is_not_scheduled(dst)
399 && !__SD_task_is_scheduled_or_ready(dst))
401 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
402 SD_task_get_name(dst));
404 DEBUG2("SD_task_dependency_add: src = %s, dst = %s", SD_task_get_name(src),
405 SD_task_get_name(dst));
406 for (i = 0; i < length && !found; i++) {
407 xbt_dynar_get_cpy(dynar, i, &dependency);
408 found = (dependency->dst == dst);
409 DEBUG2("Dependency %d: dependency->dst = %s", i,
410 SD_task_get_name(dependency->dst));
415 "A dependency already exists between task '%s' and task '%s'",
416 SD_task_get_name(src), SD_task_get_name(dst));
418 dependency = xbt_new(s_SD_dependency_t, 1);
420 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
421 dependency->data = data;
422 dependency->src = src;
423 dependency->dst = dst;
425 /* src must be executed before dst */
426 xbt_dynar_push(src->tasks_after, &dependency);
427 xbt_dynar_push(dst->tasks_before, &dependency);
429 /* if the task was ready, then dst->tasks_before is not empty anymore,
430 so we must go back to state SD_SCHEDULED */
431 if (__SD_task_is_ready(dst)) {
432 DEBUG1("SD_task_dependency_add: %s was ready and becomes scheduled!",
433 SD_task_get_name(dst));
434 __SD_task_set_state(dst, SD_SCHEDULED);
437 /* __SD_print_dependencies(src);
438 __SD_print_dependencies(dst); */
442 * \brief Indacates whether there is a dependency between two tasks.
445 * \param dst a task depending on \a src
447 * If src is NULL, checks whether dst has any pre-dependency.
448 * If dst is NULL, checks whether src has any post-dependency.
450 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
452 unsigned int counter;
453 SD_dependency_t dependency;
455 SD_CHECK_INIT_DONE();
456 xbt_assert0(src != NULL || dst != NULL, "Invalid parameter: both src and dst are NULL");
460 xbt_dynar_foreach(src->tasks_after,counter,dependency) {
461 if (dependency->dst == dst)
465 return xbt_dynar_length(src->tasks_after);
468 return xbt_dynar_length(dst->tasks_before);
474 * \brief Remove a dependency between two tasks
477 * \param dst a task depending on \a src
478 * \see SD_task_dependency_add()
480 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
487 SD_dependency_t dependency;
489 SD_CHECK_INIT_DONE();
490 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
492 /* remove the dependency from src->tasks_after */
493 dynar = src->tasks_after;
494 length = xbt_dynar_length(dynar);
496 for (i = 0; i < length && !found; i++) {
497 xbt_dynar_get_cpy(dynar, i, &dependency);
498 if (dependency->dst == dst) {
499 xbt_dynar_remove_at(dynar, i, NULL);
505 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
506 SD_task_get_name(src), SD_task_get_name(dst),
507 SD_task_get_name(dst), SD_task_get_name(src));
509 /* remove the dependency from dst->tasks_before */
510 dynar = dst->tasks_before;
511 length = xbt_dynar_length(dynar);
514 for (i = 0; i < length && !found; i++) {
515 xbt_dynar_get_cpy(dynar, i, &dependency);
516 if (dependency->src == src) {
517 xbt_dynar_remove_at(dynar, i, NULL);
518 __SD_task_dependency_destroy(dependency);
522 /* should never happen... */
524 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
525 SD_task_get_name(dst), SD_task_get_name(src),
526 SD_task_get_name(src), SD_task_get_name(dst));
528 /* if the task was scheduled and dst->tasks_before is empty now, we can make it ready */
529 if (xbt_dynar_length(dst->tasks_before) == 0 && __SD_task_is_scheduled(dst))
530 __SD_task_set_state(dst, SD_READY);
532 /* __SD_print_dependencies(src);
533 __SD_print_dependencies(dst); */
537 * \brief Returns the user data associated with a dependency between two tasks
540 * \param dst a task depending on \a src
541 * \return the user data associated with this dependency (can be \c NULL)
542 * \see SD_task_dependency_add()
544 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
551 SD_dependency_t dependency;
554 SD_CHECK_INIT_DONE();
555 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
557 dynar = src->tasks_after;
558 length = xbt_dynar_length(dynar);
560 for (i = 0; i < length && !found; i++) {
561 xbt_dynar_get_cpy(dynar, i, &dependency);
562 found = (dependency->dst == dst);
565 THROW2(arg_error, 0, "No dependency found between task '%s' and '%s'",
566 SD_task_get_name(src), SD_task_get_name(dst));
567 return dependency->data;
570 /* temporary function for debugging */
571 static void __SD_print_watch_points(SD_task_t task)
573 static const int state_masks[] =
574 { SD_SCHEDULED, SD_RUNNING, SD_READY, SD_DONE, SD_FAILED };
575 static const char *state_names[] =
576 { "scheduled", "running", "ready", "done", "failed" };
579 INFO2("Task '%s' watch points (%x): ", SD_task_get_name(task),
583 for (i = 0; i < 5; i++) {
584 if (task->watch_points & state_masks[i])
585 INFO1("%s ", state_names[i]);
590 * \brief Adds a watch point to a task
592 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
593 * task becomes the one given in argument. The
594 * watch point is then automatically removed.
597 * \param state the \ref e_SD_task_state_t "state" you want to watch
598 * (cannot be #SD_NOT_SCHEDULED)
599 * \see SD_task_unwatch()
601 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
603 SD_CHECK_INIT_DONE();
604 xbt_assert0(task != NULL, "Invalid parameter");
606 if (state & SD_NOT_SCHEDULED)
608 "Cannot add a watch point for state SD_NOT_SCHEDULED");
610 task->watch_points = task->watch_points | state;
611 /* __SD_print_watch_points(task); */
615 * \brief Removes a watch point from a task
618 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
619 * \see SD_task_watch()
621 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
623 SD_CHECK_INIT_DONE();
624 xbt_assert0(task != NULL, "Invalid parameter");
625 xbt_assert0(state != SD_NOT_SCHEDULED,
626 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
628 task->watch_points = task->watch_points & ~state;
629 /* __SD_print_watch_points(task); */
633 * \brief Returns an approximative estimation of the execution time of a task.
635 * The estimation is very approximative because the value returned is the time
636 * the task would take if it was executed now and if it was the only task.
638 * \param task the task to evaluate
639 * \param workstation_nb number of workstations on which the task would be executed
640 * \param workstation_list the workstations on which the task would be executed
641 * \param computation_amount computation amount for each workstation
642 * \param communication_amount communication amount between each pair of workstations
645 double SD_task_get_execution_time(SD_task_t task,
647 const SD_workstation_t * workstation_list,
648 const double *computation_amount,
649 const double *communication_amount)
651 double time, max_time = 0.0;
653 SD_CHECK_INIT_DONE();
654 xbt_assert0(task != NULL && workstation_nb > 0 && workstation_list != NULL,
655 "Invalid parameter");
657 /* the task execution time is the maximum execution time of the parallel tasks */
659 for (i = 0; i < workstation_nb; i++) {
661 if (computation_amount != NULL)
663 SD_workstation_get_computation_time(workstation_list[i],
664 computation_amount[i]);
666 if (communication_amount != NULL)
667 for (j = 0; j < workstation_nb; j++) {
669 SD_route_get_communication_time(workstation_list[i],
671 communication_amount[i *
676 if (time > max_time) {
682 static inline void SD_task_do_schedule(SD_task_t task) {
683 SD_CHECK_INIT_DONE();
685 if (!__SD_task_is_not_scheduled(task))
686 THROW1(arg_error, 0, "Task '%s' has already been scheduled",
687 SD_task_get_name(task));
689 /* update the task state */
690 if (xbt_dynar_length(task->tasks_before) == 0)
691 __SD_task_set_state(task, SD_READY);
693 __SD_task_set_state(task, SD_SCHEDULED);
697 * \brief Schedules a task
699 * The task state must be #SD_NOT_SCHEDULED.
700 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
701 * i.e. when its dependencies are satisfied.
703 * \param task the task you want to schedule
704 * \param workstation_nb number of workstations on which the task will be executed
705 * \param workstation_list the workstations on which the task will be executed
706 * \param computation_amount computation amount for each workstation
707 * \param communication_amount communication amount between each pair of workstations
708 * \param rate task execution speed rate
709 * \see SD_task_unschedule()
711 void SD_task_schedule(SD_task_t task, int workstation_count,
712 const SD_workstation_t * workstation_list,
713 const double *computation_amount,
714 const double *communication_amount, double rate)
716 xbt_assert0(workstation_count > 0, "workstation_nb must be positive");
718 int communication_nb;
720 task->workstation_nb = workstation_count;
723 if (computation_amount) {
724 task->computation_amount = xbt_new(double, workstation_count);
725 memcpy(task->computation_amount, computation_amount,
726 sizeof(double) * workstation_count);
728 task->computation_amount = NULL;
731 communication_nb = workstation_count * workstation_count;
732 if (communication_amount) {
733 task->communication_amount = xbt_new(double, communication_nb);
734 memcpy(task->communication_amount, communication_amount,
735 sizeof(double) * communication_nb);
737 task->communication_amount = NULL;
740 task->workstation_list = xbt_new(SD_workstation_t, workstation_count);
741 memcpy(task->workstation_list, workstation_list,
742 sizeof(SD_workstation_t) * workstation_count);
744 SD_task_do_schedule(task);
747 * \brief Unschedules a task
749 * The task state must be #SD_SCHEDULED, #SD_READY, #SD_RUNNING or #SD_FAILED.
750 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
751 * Call SD_task_schedule() to schedule it again.
753 * \param task the task you want to unschedule
754 * \see SD_task_schedule()
756 void SD_task_unschedule(SD_task_t task)
758 SD_CHECK_INIT_DONE();
759 xbt_assert0(task != NULL, "Invalid parameter");
761 if (task->state_set != sd_global->scheduled_task_set &&
762 task->state_set != sd_global->ready_task_set &&
763 task->state_set != sd_global->running_task_set &&
764 task->state_set != sd_global->failed_task_set)
766 "Task %s: the state must be SD_SCHEDULED, SD_READY, SD_RUNNING or SD_FAILED",
767 SD_task_get_name(task));
769 if (__SD_task_is_scheduled_or_ready(task) /* if the task is scheduled or ready */
770 && task->kind == SD_TASK_NOT_TYPED) /* Don't free scheduling data for typed tasks */
771 __SD_task_destroy_scheduling_data(task);
773 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
774 surf_workstation_model->action_cancel(task->surf_action);
776 __SD_task_set_state(task, SD_NOT_SCHEDULED);
777 task->remains = task->amount;
778 task->start_time = -1.0;
781 /* Destroys the data memorised by SD_task_schedule. Task state must be SD_SCHEDULED or SD_READY.
783 static void __SD_task_destroy_scheduling_data(SD_task_t task)
785 SD_CHECK_INIT_DONE();
786 if (!__SD_task_is_scheduled_or_ready(task) && !__SD_task_is_in_fifo(task))
788 "Task '%s' must be SD_SCHEDULED, SD_READY or SD_IN_FIFO",
789 SD_task_get_name(task));
791 xbt_free(task->computation_amount);
792 xbt_free(task->communication_amount);
793 task->computation_amount = task->communication_amount = NULL;
796 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
797 * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
798 * the task gets out of its fifos.
800 void __SD_task_really_run(SD_task_t task)
804 void **surf_workstations;
806 SD_CHECK_INIT_DONE();
807 xbt_assert0(task != NULL, "Invalid parameter");
808 xbt_assert2(__SD_task_is_ready_or_in_fifo(task),
809 "Task '%s' is not ready or in a fifo! Task state: %d",
810 SD_task_get_name(task), SD_task_get_state(task));
811 xbt_assert1(task->workstation_list != NULL,
812 "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
816 DEBUG1("Really running task '%s'", SD_task_get_name(task));
818 /* set this task as current task for the workstations in sequential mode */
819 for (i = 0; i < task->workstation_nb; i++) {
820 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
821 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
822 task->workstation_list[i]->current_task = task;
823 xbt_assert0(__SD_workstation_is_busy(task->workstation_list[i]),
824 "The workstation should be busy now");
828 DEBUG1("Task '%s' set as current task for its workstations",
829 SD_task_get_name(task));
833 /* we have to create a Surf workstation array instead of the SimDag workstation array */
834 surf_workstations = xbt_new(void *, task->workstation_nb);
836 for (i = 0; i < task->workstation_nb; i++)
837 surf_workstations[i] = task->workstation_list[i]->surf_workstation;
839 /* 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 */
840 #define cost_or_zero(array,pos) ((array)?(array)[pos]:0.0)
842 task->surf_action = NULL;
843 if ((task->workstation_nb == 1) && (cost_or_zero(task->communication_amount,0) == 0.0)) {
845 surf_workstation_model->extension.
846 workstation.execute(surf_workstations[0], cost_or_zero(task->computation_amount,0));
847 } else if ((task->workstation_nb == 1)
848 && (cost_or_zero(task->computation_amount,0) == 0.0)) {
851 surf_workstation_model->extension.
852 workstation.communicate(surf_workstations[0], surf_workstations[0],
853 cost_or_zero(task->communication_amount,0), task->rate);
854 } else if ((task->workstation_nb == 2)
855 && (cost_or_zero(task->computation_amount,0) == 0.0)
856 && (cost_or_zero(task->computation_amount,1) == 0.0)) {
860 for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
861 if (cost_or_zero(task->communication_amount,i) > 0.0) {
863 value = cost_or_zero(task->communication_amount,i);
868 surf_workstation_model->extension.
869 workstation.communicate(surf_workstations[0], surf_workstations[1],
875 if (!task->surf_action) {
876 double *computation_amount = xbt_new(double, task->workstation_nb);
877 double *communication_amount = xbt_new(double, task->workstation_nb *
878 task->workstation_nb);
880 memcpy(computation_amount, task->computation_amount, sizeof(double) *
881 task->workstation_nb);
882 memcpy(communication_amount, task->communication_amount,
883 sizeof(double) * task->workstation_nb * task->workstation_nb);
886 surf_workstation_model->extension.
887 workstation.execute_parallel_task(task->workstation_nb,
888 surf_workstations, computation_amount,
889 communication_amount, task->amount,
892 xbt_free(surf_workstations);
895 surf_workstation_model->action_data_set(task->surf_action, task);
897 DEBUG1("surf_action = %p", task->surf_action);
899 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
900 __SD_task_set_state(task, SD_RUNNING);
901 xbt_assert2(__SD_task_is_running(task), "Bad state of task '%s': %d",
902 SD_task_get_name(task), SD_task_get_state(task));
906 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_READY
907 * (ie when its dependencies are satisfied).
908 * If one of the workstations where the task is scheduled on is busy (in sequential mode),
909 * the task doesn't start.
910 * Returns whether the task has started.
912 int __SD_task_try_to_run(SD_task_t task)
917 SD_workstation_t workstation;
919 SD_CHECK_INIT_DONE();
920 xbt_assert0(task != NULL, "Invalid parameter");
921 xbt_assert2(__SD_task_is_ready(task),
922 "Task '%s' is not ready! Task state: %d",
923 SD_task_get_name(task), SD_task_get_state(task));
926 for (i = 0; i < task->workstation_nb; i++) {
927 can_start = !__SD_workstation_is_busy(task->workstation_list[i]);
930 DEBUG2("Task '%s' can start: %d", SD_task_get_name(task), can_start);
932 if (!can_start) { /* if the task cannot start and is not in the fifos yet */
933 for (i = 0; i < task->workstation_nb; i++) {
934 workstation = task->workstation_list[i];
935 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
936 DEBUG2("Pushing task '%s' in the fifo of workstation '%s'",
937 SD_task_get_name(task), SD_workstation_get_name(workstation));
938 xbt_fifo_push(workstation->task_fifo, task);
941 __SD_task_set_state(task, SD_IN_FIFO);
942 xbt_assert2(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
943 SD_task_get_name(task), SD_task_get_state(task));
944 DEBUG1("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
946 __SD_task_really_run(task);
952 /* This function is called by SD_simulate when a task is done.
953 * It updates task->state and task->action and executes if necessary the tasks
954 * which were waiting in fifos for the end of `task'
956 void __SD_task_just_done(SD_task_t task)
959 SD_workstation_t workstation;
962 int candidate_nb = 0;
963 int candidate_capacity = 8;
964 SD_task_t *candidates;
967 SD_CHECK_INIT_DONE();
968 xbt_assert0(task != NULL, "Invalid parameter");
969 xbt_assert1(__SD_task_is_running(task),
970 "The task must be running! Task state: %d",
971 SD_task_get_state(task));
972 xbt_assert1(task->workstation_list != NULL,
973 "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
976 candidates = xbt_new(SD_task_t, 8);
978 __SD_task_set_state(task, SD_DONE);
979 surf_workstation_model->action_unref(task->surf_action);
980 task->surf_action = NULL;
982 DEBUG0("Looking for candidates");
984 /* if the task was executed on sequential workstations,
985 maybe we can execute the next task of the fifo for each workstation */
986 for (i = 0; i < task->workstation_nb; i++) {
987 workstation = task->workstation_list[i];
988 DEBUG2("Workstation '%s': access_mode = %d",
989 SD_workstation_get_name(workstation), workstation->access_mode);
990 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
991 xbt_assert1(workstation->task_fifo != NULL,
992 "Workstation '%s' has sequential access but no fifo!",
993 SD_workstation_get_name(workstation));
994 xbt_assert2(workstation->current_task =
995 task, "Workstation '%s': current task should be '%s'",
996 SD_workstation_get_name(workstation),
997 SD_task_get_name(task));
999 /* the task is over so we can release the workstation */
1000 workstation->current_task = NULL;
1002 DEBUG0("Getting candidate in fifo");
1004 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1005 (workstation->task_fifo));
1007 if (candidate != NULL) {
1008 DEBUG1("Candidate: '%s'", SD_task_get_name(candidate));
1009 xbt_assert2(__SD_task_is_in_fifo(candidate),
1010 "Bad state of candidate '%s': %d",
1011 SD_task_get_name(candidate),
1012 SD_task_get_state(candidate));
1015 DEBUG1("Candidate in fifo: %p", candidate);
1017 /* if there was a task waiting for my place */
1018 if (candidate != NULL) {
1019 /* Unfortunately, we are not sure yet that we can execute the task now,
1020 because the task can be waiting more deeply in some other workstation's fifos...
1021 So we memorize all candidate tasks, and then we will check for each candidate
1022 whether or not all its workstations are available. */
1024 /* realloc if necessary */
1025 if (candidate_nb == candidate_capacity) {
1026 candidate_capacity *= 2;
1028 xbt_realloc(candidates, sizeof(SD_task_t) * candidate_capacity);
1031 /* register the candidate */
1032 candidates[candidate_nb++] = candidate;
1033 candidate->fifo_checked = 0;
1038 DEBUG1("Candidates found: %d", candidate_nb);
1040 /* now we check every candidate task */
1041 for (i = 0; i < candidate_nb; i++) {
1042 candidate = candidates[i];
1044 if (candidate->fifo_checked) {
1045 continue; /* we have already evaluated that task */
1048 xbt_assert2(__SD_task_is_in_fifo(candidate),
1049 "Bad state of candidate '%s': %d",
1050 SD_task_get_name(candidate), SD_task_get_state(candidate));
1052 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1053 workstation = candidate->workstation_list[j];
1055 /* I can start on this workstation if the workstation is shared
1056 or if I am the first task in the fifo */
1057 can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS ||
1059 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1060 (workstation->task_fifo));
1063 DEBUG2("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1066 /* now we are sure that I can start! */
1068 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1069 workstation = candidate->workstation_list[j];
1071 /* update the fifo */
1072 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1073 candidate = xbt_fifo_shift(workstation->task_fifo); /* the return value is stored just for debugging */
1074 DEBUG1("Head of the fifo: '%s'",
1075 (candidate != NULL) ? SD_task_get_name(candidate) : "NULL");
1076 xbt_assert0(candidate == candidates[i],
1077 "Error in __SD_task_just_done: bad first task in the fifo");
1079 } /* for each workstation */
1081 /* finally execute the task */
1082 DEBUG2("Task '%s' state: %d", SD_task_get_name(candidate),
1083 SD_task_get_state(candidate));
1084 __SD_task_really_run(candidate);
1087 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1088 SD_task_get_name(candidate), candidate->state_set,
1089 sd_global->running_task_set, __SD_task_is_running(candidate));
1090 xbt_assert2(__SD_task_is_running(candidate),
1091 "Bad state of task '%s': %d", SD_task_get_name(candidate),
1092 SD_task_get_state(candidate));
1093 DEBUG0("Okay, the task is running.");
1096 candidate->fifo_checked = 1;
1097 } /* for each candidate */
1099 xbt_free(candidates);
1102 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1104 static void __SD_task_remove_dependencies(SD_task_t task)
1106 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1107 because each one is stored twice */
1108 SD_dependency_t dependency;
1109 while (xbt_dynar_length(task->tasks_before) > 0) {
1110 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1111 SD_task_dependency_remove(dependency->src, dependency->dst);
1114 while (xbt_dynar_length(task->tasks_after) > 0) {
1115 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1116 SD_task_dependency_remove(dependency->src, dependency->dst);
1121 * \brief Returns the start time of a task
1123 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1125 * \param task: a task
1126 * \return the start time of this task
1128 double SD_task_get_start_time(SD_task_t task)
1130 SD_CHECK_INIT_DONE();
1131 xbt_assert0(task != NULL, "Invalid parameter");
1132 if (task->surf_action)
1133 return surf_workstation_model->action_get_start_time(task->surf_action);
1135 return task->start_time;
1139 * \brief Returns the finish time of a task
1141 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1142 * If the state is not completed yet, the returned value is an
1143 * estimation of the task finish time. This value can fluctuate
1144 * until the task is completed.
1146 * \param task: a task
1147 * \return the start time of this task
1149 double SD_task_get_finish_time(SD_task_t task)
1151 SD_CHECK_INIT_DONE();
1152 xbt_assert0(task != NULL, "Invalid parameter");
1154 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1155 return surf_workstation_model->action_get_finish_time(task->surf_action);
1157 return task->finish_time;
1161 * \brief Destroys a task.
1163 * The user data (if any) should have been destroyed first.
1165 * \param task the task you want to destroy
1166 * \see SD_task_create()
1168 void SD_task_destroy(SD_task_t task)
1170 SD_CHECK_INIT_DONE();
1171 xbt_assert0(task != NULL, "Invalid parameter");
1173 DEBUG1("Destroying task %s...", SD_task_get_name(task));
1175 __SD_task_remove_dependencies(task);
1176 /* if the task was scheduled or ready we have to free the scheduling parameters */
1177 if (__SD_task_is_scheduled_or_ready(task))
1178 __SD_task_destroy_scheduling_data(task);
1179 xbt_swag_remove(task,task->state_set);
1181 if (task->name != NULL)
1182 xbt_free(task->name);
1184 if (task->surf_action != NULL)
1185 surf_workstation_model->action_unref(task->surf_action);
1187 if (task->workstation_list != NULL)
1188 xbt_free(task->workstation_list);
1190 if (task->communication_amount)
1191 xbt_free(task->communication_amount);
1193 if (task->computation_amount)
1194 xbt_free(task->computation_amount);
1196 xbt_dynar_free(&task->tasks_before);
1197 xbt_dynar_free(&task->tasks_after);
1200 sd_global->task_number--;
1202 DEBUG0("Task destroyed.");
1206 static inline SD_task_t SD_task_create_sized(const char*name,void*data,double amount,int ws_count) {
1207 SD_task_t task = SD_task_create(name,data,amount);
1208 task->communication_amount = xbt_new0(double,ws_count*ws_count);
1209 task->computation_amount = xbt_new0(double,ws_count);
1210 task->workstation_nb = ws_count;
1211 task->workstation_list = xbt_new0(SD_workstation_t,ws_count);
1214 /** @brief create a end-to-end communication task that can then be auto-scheduled
1216 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1217 * allows to specify the task costs at creation, and decorelate them from the
1218 * scheduling process where you just specify which resource should deliver the
1221 * A end-to-end communication must be scheduled on 2 hosts, and the amount
1222 * specified at creation is sent from hosts[0] to hosts[1].
1224 SD_task_t SD_task_create_comm_e2e(const char*name, void *data, double amount) {
1225 SD_task_t res = SD_task_create_sized(name,data,amount,2);
1226 res->communication_amount[2] = amount;
1227 res->kind=SD_TASK_COMM_E2E;
1230 /** @brief create a sequential computation task that can then be auto-scheduled
1232 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1233 * allows to specify the task costs at creation, and decorelate them from the
1234 * scheduling process where you just specify which resource should deliver the
1237 * A sequential computation must be scheduled on 1 host, and the amount
1238 * specified at creation to be run on hosts[0].
1240 SD_task_t SD_task_create_comp_seq(const char*name, void *data, double amount) {
1241 SD_task_t res = SD_task_create_sized(name,data,amount,1);
1242 res->computation_amount[0]=amount;
1243 res->kind=SD_TASK_COMP_SEQ;
1247 /** @brief Auto-schedules a task.
1249 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1250 * allows to specify the task costs at creation, and decorelate them from the
1251 * scheduling process where you just specify which resource should deliver the
1254 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1255 * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1259 * We should create tasks kind for the following categories:
1260 * - Point to point communication (done)
1261 * - Sequential computation (done)
1262 * - group communication (redistribution, several kinds)
1263 * - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1264 * - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1266 void SD_task_schedulev(SD_task_t task, int count, const SD_workstation_t*list) {
1268 xbt_assert1(task->kind != 0,"Task %s is not typed. Cannot automatically schedule it.",SD_task_get_name(task));
1269 switch(task->kind) {
1270 case SD_TASK_COMM_E2E:
1271 case SD_TASK_COMP_SEQ:
1272 xbt_assert(task->workstation_nb==count);
1273 for (i=0;i<count;i++)
1274 task->workstation_list[i]=list[i];
1275 SD_task_do_schedule(task);
1278 xbt_die(bprintf("Kind of task %s not supported by SD_task_schedulev()",
1279 SD_task_get_name(task)));
1281 if (task->kind == SD_TASK_COMM_E2E) {
1282 VERB4("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1283 SD_task_get_name(task),
1284 SD_workstation_get_name(task->workstation_list[0]),SD_workstation_get_name(task->workstation_list[1]),
1285 task->communication_amount[2]);
1288 /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if ready) */
1289 if (task->kind == SD_TASK_COMP_SEQ) {
1290 VERB3("Schedule computation task %s on %s. It costs %.f flops",
1291 SD_task_get_name(task),SD_workstation_get_name(task->workstation_list[0]),
1292 task->computation_amount[0]);
1293 SD_dependency_t dep;
1295 xbt_dynar_foreach(task->tasks_before,cpt,dep) {
1296 SD_task_t before = dep->src;
1297 if (before->kind == SD_TASK_COMM_E2E) {
1298 before->workstation_list[1] = task->workstation_list[0];
1299 if (before->workstation_list[0] && __SD_task_is_not_scheduled(before)) {
1300 SD_task_do_schedule(before);
1301 VERB4("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1302 SD_task_get_name(before),
1303 SD_workstation_get_name(before->workstation_list[0]),SD_workstation_get_name(before->workstation_list[1]),
1304 before->communication_amount[2]);
1308 xbt_dynar_foreach(task->tasks_after,cpt,dep) {
1309 SD_task_t after = dep->dst;
1310 if (after->kind == SD_TASK_COMM_E2E) {
1311 after->workstation_list[0] = task->workstation_list[0];
1312 if (after->workstation_list[1] && __SD_task_is_not_scheduled(after)) {
1313 SD_task_do_schedule(after);
1314 VERB4("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1315 SD_task_get_name(after),
1316 SD_workstation_get_name(after->workstation_list[0]),SD_workstation_get_name(after->workstation_list[1]),
1317 after->communication_amount[2]);
1324 /** @brief autoschedule a task on a list of workstations
1326 * This function is very similar to SD_task_schedulev(),
1327 * but takes the list of workstations to schedule onto as separate parameters.
1328 * It builds a proper vector of workstations and then call SD_task_schedulev()
1330 void SD_task_schedulel(SD_task_t task, int count, ...) {
1332 SD_workstation_t *list=xbt_new(SD_workstation_t,count);
1335 for (i=0;i<count;i++) {
1336 list[i] = va_arg(ap,SD_workstation_t);
1339 SD_task_schedulev(task,count,list);