1 /* Copyright (c) 2007-2009 Da SimGrid Team. All rights reserved. */
3 /* This program is free software; you can redistribute it and/or modify it
4 * under the terms of the license (GNU LGPL) which comes with this package. */
7 #include "simdag/simdag.h"
8 #include "xbt/sysdep.h"
11 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
12 "Logging specific to SimDag (task)");
14 static void __SD_task_remove_dependencies(SD_task_t task);
15 static void __SD_task_destroy_scheduling_data(SD_task_t task);
18 * \brief Creates a new task.
20 * \param name the name of the task (can be \c NULL)
21 * \param data the user data you want to associate with the task (can be \c NULL)
22 * \param amount amount of the task
23 * \return the new task
24 * \see SD_task_destroy()
26 SD_task_t SD_task_create(const char *name, void *data, double amount)
32 task = xbt_new(s_SD_task_t, 1);
34 /* general information */
35 task->data = data; /* user data */
36 task->name = xbt_strdup(name);
37 task->kind = SD_TASK_NOT_TYPED;
38 task->state_hookup.prev = NULL;
39 task->state_hookup.next = NULL;
40 task->state_set = sd_global->not_scheduled_task_set;
41 task->state = SD_NOT_SCHEDULED;
42 xbt_swag_insert(task, task->state_set);
44 task->amount = amount;
45 task->remains = amount;
46 task->start_time = -1.0;
47 task->finish_time = -1.0;
48 task->surf_action = NULL;
49 task->watch_points = 0;
52 task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
53 task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
55 /* scheduling parameters */
56 task->workstation_nb = 0;
57 task->workstation_list = NULL;
58 task->computation_amount = NULL;
59 task->communication_amount = NULL;
62 sd_global->task_number++;
68 * \brief Returns the user data of a task
71 * \return the user data associated with this task (can be \c NULL)
72 * \see SD_task_set_data()
74 void *SD_task_get_data(SD_task_t task)
77 xbt_assert0(task != NULL, "Invalid parameter");
82 * \brief Sets the user data of a task
84 * The new data can be \c NULL. The old data should have been freed first
85 * if it was not \c NULL.
88 * \param data the new data you want to associate with this task
89 * \see SD_task_get_data()
91 void SD_task_set_data(SD_task_t task, void *data)
94 xbt_assert0(task != NULL, "Invalid parameter");
99 * \brief Returns the state of a task
102 * \return the current \ref e_SD_task_state_t "state" of this task:
103 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_READY, #SD_RUNNING, #SD_DONE or #SD_FAILED
104 * \see e_SD_task_state_t
106 e_SD_task_state_t SD_task_get_state(SD_task_t task)
108 SD_CHECK_INIT_DONE();
109 xbt_assert0(task != NULL, "Invalid parameter");
113 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
115 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
117 xbt_swag_remove(task, task->state_set);
119 case SD_NOT_SCHEDULED:
120 task->state_set = sd_global->not_scheduled_task_set;
123 task->state_set = sd_global->scheduled_task_set;
126 task->state_set = sd_global->ready_task_set;
129 task->state_set = sd_global->in_fifo_task_set;
132 task->state_set = sd_global->running_task_set;
134 surf_workstation_model->action_get_start_time(task->surf_action);
137 task->state_set = sd_global->done_task_set;
139 surf_workstation_model->action_get_finish_time(task->surf_action);
143 task->state_set = sd_global->failed_task_set;
146 xbt_assert0(0, "Invalid state");
148 xbt_swag_insert(task, task->state_set);
149 task->state = new_state;
151 if (task->watch_points & new_state) {
152 INFO1("Watch point reached with task '%s'!", SD_task_get_name(task));
153 sd_global->watch_point_reached = 1;
154 SD_task_unwatch(task, new_state); /* remove the watch point */
159 * \brief Returns the name of a task
162 * \return the name of this task (can be \c NULL)
164 const char *SD_task_get_name(SD_task_t task)
166 SD_CHECK_INIT_DONE();
167 xbt_assert0(task != NULL, "Invalid parameter");
171 /** @brief Returns the dynar of the parents of a task
174 * \return a newly allocated dynar comprising the parents of this task
177 xbt_dynar_t SD_task_get_parents(SD_task_t task)
182 SD_CHECK_INIT_DONE();
183 xbt_assert0(task != NULL, "Invalid parameter");
185 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
186 xbt_dynar_foreach(task->tasks_before, i, dep){
187 xbt_dynar_push(parents, &(dep->src));
192 /** @brief Returns the dynar of the parents of a task
195 * \return a newly allocated dynar comprising the parents of this task
197 xbt_dynar_t SD_task_get_children(SD_task_t task)
200 xbt_dynar_t children;
202 SD_CHECK_INIT_DONE();
203 xbt_assert0(task != NULL, "Invalid parameter");
205 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
206 xbt_dynar_foreach(task->tasks_after, i, dep){
207 xbt_dynar_push(children, &(dep->dst));
213 * \brief Returns the amount of workstations involved in a task
215 * Only call this on already scheduled tasks!
218 int SD_task_get_workstation_count(SD_task_t task)
220 SD_CHECK_INIT_DONE();
221 xbt_assert0(task != NULL, "Invalid parameter");
222 // xbt_assert1( task->state_set != sd_global->scheduled_task_set,
223 // "Unscheduled task %s", task->name);
224 return task->workstation_nb;
228 * \brief Returns the list of workstations involved in a task
230 * Only call this on already scheduled tasks!
233 SD_workstation_t* SD_task_get_workstation_list(SD_task_t task)
235 SD_CHECK_INIT_DONE();
236 xbt_assert0(task != NULL, "Invalid parameter");
237 //xbt_assert1( task->state_set != sd_global->scheduled_task_set,
238 // "Unscheduled task %s", task->name);
239 return task->workstation_list;
243 * \brief Returns the total amount of work contained in a task
246 * \return the total amount of work (computation or data transfer) for this task
247 * \see SD_task_get_remaining_amount()
249 double SD_task_get_amount(SD_task_t task)
251 SD_CHECK_INIT_DONE();
252 xbt_assert0(task != NULL, "Invalid parameter");
257 * \brief Returns the remaining amount work to do till the completion of a task
260 * \return the remaining amount of work (computation or data transfer) of this task
261 * \see SD_task_get_amount()
263 double SD_task_get_remaining_amount(SD_task_t task)
265 SD_CHECK_INIT_DONE();
266 xbt_assert0(task != NULL, "Invalid parameter");
268 if (task->surf_action)
269 return surf_workstation_model->get_remains(task->surf_action);
271 return task->remains;
274 int SD_task_get_kind(SD_task_t task) {
278 /** @brief Displays debugging informations about a task */
279 void SD_task_dump(SD_task_t task)
281 unsigned int counter;
282 SD_dependency_t dependency;
285 INFO1("Displaying task %s",SD_task_get_name(task));
286 statename=bprintf("%s %s %s %s %s %s %s",
287 (task->state&SD_NOT_SCHEDULED?"not scheduled":""),
288 (task->state&SD_SCHEDULED?"scheduled":""),
289 (task->state&SD_READY?"ready":"not ready"),
290 (task->state&SD_IN_FIFO?"in fifo":""),
291 (task->state&SD_RUNNING?"running":""),
292 (task->state&SD_DONE?"done":""),
293 (task->state&SD_FAILED?"failed":""));
294 INFO1(" - state: %s",statename);
299 case SD_TASK_COMM_E2E:
300 INFO0(" - kind: end-to-end communication");
302 case SD_TASK_COMP_SEQ:
303 INFO0(" - kind: sequential computation");
306 INFO1(" - (unknown kind %d)",task->kind);
309 INFO1(" - amount: %.0f",SD_task_get_amount(task));
310 if (xbt_dynar_length(task->tasks_before)) {
311 INFO0(" - pre-dependencies:");
312 xbt_dynar_foreach(task->tasks_before,counter,dependency) {
313 INFO1(" %s",SD_task_get_name(dependency->src));
316 if (xbt_dynar_length(task->tasks_after)) {
317 INFO0(" - post-dependencies:");
318 xbt_dynar_foreach(task->tasks_after,counter,dependency) {
319 INFO1(" %s",SD_task_get_name(dependency->dst));
323 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
324 void SD_task_dotty(SD_task_t task,void* out) {
325 unsigned int counter;
326 SD_dependency_t dependency;
327 fprintf(out, " T%p [label=\"%.20s\"",task, task->name);
329 case SD_TASK_COMM_E2E:
330 fprintf(out,", shape=box");
332 case SD_TASK_COMP_SEQ:
333 fprintf(out,", shape=circle");
336 xbt_die("Unknown task type!");
339 xbt_dynar_foreach(task->tasks_before,counter,dependency) {
340 fprintf(out," T%p -> T%p;\n",dependency->src, dependency->dst);
344 /* Destroys a dependency between two tasks.
346 static void __SD_task_dependency_destroy(void *dependency)
348 if (((SD_dependency_t) dependency)->name != NULL)
349 xbt_free(((SD_dependency_t) dependency)->name);
350 xbt_free(dependency);
354 * \brief Adds a dependency between two tasks
356 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
357 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_READY.
359 * \param name the name of the new dependency (can be \c NULL)
360 * \param data the user data you want to associate with this dependency (can be \c NULL)
361 * \param src the task which must be executed first
362 * \param dst the task you want to make depend on \a src
363 * \see SD_task_dependency_remove()
365 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
372 SD_dependency_t dependency;
374 SD_CHECK_INIT_DONE();
375 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
377 dynar = src->tasks_after;
378 length = xbt_dynar_length(dynar);
382 "Cannot add a dependency between task '%s' and itself",
383 SD_task_get_name(src));
385 if (!__SD_task_is_not_scheduled(src)
386 && !__SD_task_is_scheduled_or_ready(src))
388 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
389 SD_task_get_name(src));
391 if (!__SD_task_is_not_scheduled(dst)
392 && !__SD_task_is_scheduled_or_ready(dst))
394 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
395 SD_task_get_name(dst));
397 DEBUG2("SD_task_dependency_add: src = %s, dst = %s", SD_task_get_name(src),
398 SD_task_get_name(dst));
399 for (i = 0; i < length && !found; i++) {
400 xbt_dynar_get_cpy(dynar, i, &dependency);
401 found = (dependency->dst == dst);
402 DEBUG2("Dependency %d: dependency->dst = %s", i,
403 SD_task_get_name(dependency->dst));
408 "A dependency already exists between task '%s' and task '%s'",
409 SD_task_get_name(src), SD_task_get_name(dst));
411 dependency = xbt_new(s_SD_dependency_t, 1);
413 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
414 dependency->data = data;
415 dependency->src = src;
416 dependency->dst = dst;
418 /* src must be executed before dst */
419 xbt_dynar_push(src->tasks_after, &dependency);
420 xbt_dynar_push(dst->tasks_before, &dependency);
422 /* if the task was ready, then dst->tasks_before is not empty anymore,
423 so we must go back to state SD_SCHEDULED */
424 if (__SD_task_is_ready(dst)) {
425 DEBUG1("SD_task_dependency_add: %s was ready and becomes scheduled!",
426 SD_task_get_name(dst));
427 __SD_task_set_state(dst, SD_SCHEDULED);
430 /* __SD_print_dependencies(src);
431 __SD_print_dependencies(dst); */
435 * \brief Indacates whether there is a dependency between two tasks.
438 * \param dst a task depending on \a src
440 * If src is NULL, checks whether dst has any pre-dependency.
441 * If dst is NULL, checks whether src has any post-dependency.
443 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
445 unsigned int counter;
446 SD_dependency_t dependency;
448 SD_CHECK_INIT_DONE();
449 xbt_assert0(src != NULL || dst != NULL, "Invalid parameter: both src and dst are NULL");
453 xbt_dynar_foreach(src->tasks_after,counter,dependency) {
454 if (dependency->dst == dst)
458 return xbt_dynar_length(src->tasks_after);
461 return xbt_dynar_length(dst->tasks_before);
467 * \brief Remove a dependency between two tasks
470 * \param dst a task depending on \a src
471 * \see SD_task_dependency_add()
473 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
480 SD_dependency_t dependency;
482 SD_CHECK_INIT_DONE();
483 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
485 /* remove the dependency from src->tasks_after */
486 dynar = src->tasks_after;
487 length = xbt_dynar_length(dynar);
489 for (i = 0; i < length && !found; i++) {
490 xbt_dynar_get_cpy(dynar, i, &dependency);
491 if (dependency->dst == dst) {
492 xbt_dynar_remove_at(dynar, i, NULL);
498 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
499 SD_task_get_name(src), SD_task_get_name(dst),
500 SD_task_get_name(dst), SD_task_get_name(src));
502 /* remove the dependency from dst->tasks_before */
503 dynar = dst->tasks_before;
504 length = xbt_dynar_length(dynar);
507 for (i = 0; i < length && !found; i++) {
508 xbt_dynar_get_cpy(dynar, i, &dependency);
509 if (dependency->src == src) {
510 xbt_dynar_remove_at(dynar, i, NULL);
511 __SD_task_dependency_destroy(dependency);
515 /* should never happen... */
517 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
518 SD_task_get_name(dst), SD_task_get_name(src),
519 SD_task_get_name(src), SD_task_get_name(dst));
521 /* if the task was scheduled and dst->tasks_before is empty now, we can make it ready */
522 if (xbt_dynar_length(dst->tasks_before) == 0 && __SD_task_is_scheduled(dst))
523 __SD_task_set_state(dst, SD_READY);
525 /* __SD_print_dependencies(src);
526 __SD_print_dependencies(dst); */
530 * \brief Returns the user data associated with a dependency between two tasks
533 * \param dst a task depending on \a src
534 * \return the user data associated with this dependency (can be \c NULL)
535 * \see SD_task_dependency_add()
537 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
544 SD_dependency_t dependency;
547 SD_CHECK_INIT_DONE();
548 xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
550 dynar = src->tasks_after;
551 length = xbt_dynar_length(dynar);
553 for (i = 0; i < length && !found; i++) {
554 xbt_dynar_get_cpy(dynar, i, &dependency);
555 found = (dependency->dst == dst);
558 THROW2(arg_error, 0, "No dependency found between task '%s' and '%s'",
559 SD_task_get_name(src), SD_task_get_name(dst));
560 return dependency->data;
563 /* temporary function for debugging */
564 static void __SD_print_watch_points(SD_task_t task)
566 static const int state_masks[] =
567 { SD_SCHEDULED, SD_RUNNING, SD_READY, SD_DONE, SD_FAILED };
568 static const char *state_names[] =
569 { "scheduled", "running", "ready", "done", "failed" };
572 INFO2("Task '%s' watch points (%x): ", SD_task_get_name(task),
576 for (i = 0; i < 5; i++) {
577 if (task->watch_points & state_masks[i])
578 INFO1("%s ", state_names[i]);
583 * \brief Adds a watch point to a task
585 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
586 * task becomes the one given in argument. The
587 * watch point is then automatically removed.
590 * \param state the \ref e_SD_task_state_t "state" you want to watch
591 * (cannot be #SD_NOT_SCHEDULED)
592 * \see SD_task_unwatch()
594 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
596 SD_CHECK_INIT_DONE();
597 xbt_assert0(task != NULL, "Invalid parameter");
599 if (state & SD_NOT_SCHEDULED)
601 "Cannot add a watch point for state SD_NOT_SCHEDULED");
603 task->watch_points = task->watch_points | state;
604 /* __SD_print_watch_points(task); */
608 * \brief Removes a watch point from a task
611 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
612 * \see SD_task_watch()
614 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
616 SD_CHECK_INIT_DONE();
617 xbt_assert0(task != NULL, "Invalid parameter");
618 xbt_assert0(state != SD_NOT_SCHEDULED,
619 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
621 task->watch_points = task->watch_points & ~state;
622 /* __SD_print_watch_points(task); */
626 * \brief Returns an approximative estimation of the execution time of a task.
628 * The estimation is very approximative because the value returned is the time
629 * the task would take if it was executed now and if it was the only task.
631 * \param task the task to evaluate
632 * \param workstation_nb number of workstations on which the task would be executed
633 * \param workstation_list the workstations on which the task would be executed
634 * \param computation_amount computation amount for each workstation
635 * \param communication_amount communication amount between each pair of workstations
638 double SD_task_get_execution_time(SD_task_t task,
640 const SD_workstation_t * workstation_list,
641 const double *computation_amount,
642 const double *communication_amount)
644 double time, max_time = 0.0;
646 SD_CHECK_INIT_DONE();
647 xbt_assert0(task != NULL && workstation_nb > 0 && workstation_list != NULL,
648 "Invalid parameter");
650 /* the task execution time is the maximum execution time of the parallel tasks */
652 for (i = 0; i < workstation_nb; i++) {
654 if (computation_amount != NULL)
656 SD_workstation_get_computation_time(workstation_list[i],
657 computation_amount[i]);
659 if (communication_amount != NULL)
660 for (j = 0; j < workstation_nb; j++) {
662 SD_route_get_communication_time(workstation_list[i],
664 communication_amount[i *
669 if (time > max_time) {
675 static inline void SD_task_do_schedule(SD_task_t task) {
676 SD_CHECK_INIT_DONE();
678 if (!__SD_task_is_not_scheduled(task))
679 THROW1(arg_error, 0, "Task '%s' has already been scheduled",
680 SD_task_get_name(task));
682 /* update the task state */
683 if (xbt_dynar_length(task->tasks_before) == 0)
684 __SD_task_set_state(task, SD_READY);
686 __SD_task_set_state(task, SD_SCHEDULED);
690 * \brief Schedules a task
692 * The task state must be #SD_NOT_SCHEDULED.
693 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
694 * i.e. when its dependencies are satisfied.
696 * \param task the task you want to schedule
697 * \param workstation_nb number of workstations on which the task will be executed
698 * \param workstation_list the workstations on which the task will be executed
699 * \param computation_amount computation amount for each workstation
700 * \param communication_amount communication amount between each pair of workstations
701 * \param rate task execution speed rate
702 * \see SD_task_unschedule()
704 void SD_task_schedule(SD_task_t task, int workstation_count,
705 const SD_workstation_t * workstation_list,
706 const double *computation_amount,
707 const double *communication_amount, double rate)
709 xbt_assert0(workstation_count > 0, "workstation_nb must be positive");
711 int communication_nb;
713 task->workstation_nb = workstation_count;
716 if (computation_amount) {
717 task->computation_amount = xbt_new(double, workstation_count);
718 memcpy(task->computation_amount, computation_amount,
719 sizeof(double) * workstation_count);
721 task->computation_amount = NULL;
724 communication_nb = workstation_count * workstation_count;
725 if (communication_amount) {
726 task->communication_amount = xbt_new(double, communication_nb);
727 memcpy(task->communication_amount, communication_amount,
728 sizeof(double) * communication_nb);
730 task->communication_amount = NULL;
733 task->workstation_list = xbt_new(SD_workstation_t, workstation_count);
734 memcpy(task->workstation_list, workstation_list,
735 sizeof(SD_workstation_t) * workstation_count);
737 SD_task_do_schedule(task);
740 * \brief Unschedules a task
742 * The task state must be #SD_SCHEDULED, #SD_READY, #SD_RUNNING or #SD_FAILED.
743 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
744 * Call SD_task_schedule() to schedule it again.
746 * \param task the task you want to unschedule
747 * \see SD_task_schedule()
749 void SD_task_unschedule(SD_task_t task)
751 SD_CHECK_INIT_DONE();
752 xbt_assert0(task != NULL, "Invalid parameter");
754 if (task->state_set != sd_global->scheduled_task_set &&
755 task->state_set != sd_global->ready_task_set &&
756 task->state_set != sd_global->running_task_set &&
757 task->state_set != sd_global->failed_task_set)
759 "Task %s: the state must be SD_SCHEDULED, SD_READY, SD_RUNNING or SD_FAILED",
760 SD_task_get_name(task));
762 if (__SD_task_is_scheduled_or_ready(task) /* if the task is scheduled or ready */
763 && task->kind == SD_TASK_NOT_TYPED) /* Don't free scheduling data for typed tasks */
764 __SD_task_destroy_scheduling_data(task);
766 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
767 surf_workstation_model->action_cancel(task->surf_action);
769 __SD_task_set_state(task, SD_NOT_SCHEDULED);
770 task->remains = task->amount;
771 task->start_time = -1.0;
774 /* Destroys the data memorised by SD_task_schedule. Task state must be SD_SCHEDULED or SD_READY.
776 static void __SD_task_destroy_scheduling_data(SD_task_t task)
778 SD_CHECK_INIT_DONE();
779 if (!__SD_task_is_scheduled_or_ready(task) && !__SD_task_is_in_fifo(task))
781 "Task '%s' must be SD_SCHEDULED, SD_READY or SD_IN_FIFO",
782 SD_task_get_name(task));
784 xbt_free(task->computation_amount);
785 xbt_free(task->communication_amount);
786 task->computation_amount = task->communication_amount = NULL;
789 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
790 * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
791 * the task gets out of its fifos.
793 void __SD_task_really_run(SD_task_t task)
797 void **surf_workstations;
799 SD_CHECK_INIT_DONE();
800 xbt_assert0(task != NULL, "Invalid parameter");
801 xbt_assert2(__SD_task_is_ready_or_in_fifo(task),
802 "Task '%s' is not ready or in a fifo! Task state: %d",
803 SD_task_get_name(task), SD_task_get_state(task));
804 xbt_assert1(task->workstation_list != NULL,
805 "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
809 DEBUG1("Really running task '%s'", SD_task_get_name(task));
811 /* set this task as current task for the workstations in sequential mode */
812 for (i = 0; i < task->workstation_nb; i++) {
813 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
814 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
815 task->workstation_list[i]->current_task = task;
816 xbt_assert0(__SD_workstation_is_busy(task->workstation_list[i]),
817 "The workstation should be busy now");
821 DEBUG1("Task '%s' set as current task for its workstations",
822 SD_task_get_name(task));
826 /* we have to create a Surf workstation array instead of the SimDag workstation array */
827 surf_workstations = xbt_new(void *, task->workstation_nb);
829 for (i = 0; i < task->workstation_nb; i++)
830 surf_workstations[i] = task->workstation_list[i]->surf_workstation;
832 /* 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 */
833 #define cost_or_zero(array,pos) ((array)?(array)[pos]:0.0)
835 task->surf_action = NULL;
836 if ((task->workstation_nb == 1) && (cost_or_zero(task->communication_amount,0) == 0.0)) {
838 surf_workstation_model->extension.
839 workstation.execute(surf_workstations[0], cost_or_zero(task->computation_amount,0));
840 } else if ((task->workstation_nb == 1)
841 && (cost_or_zero(task->computation_amount,0) == 0.0)) {
844 surf_workstation_model->extension.
845 workstation.communicate(surf_workstations[0], surf_workstations[0],
846 cost_or_zero(task->communication_amount,0), task->rate);
847 } else if ((task->workstation_nb == 2)
848 && (cost_or_zero(task->computation_amount,0) == 0.0)
849 && (cost_or_zero(task->computation_amount,1) == 0.0)) {
853 for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
854 if (cost_or_zero(task->communication_amount,i) > 0.0) {
856 value = cost_or_zero(task->communication_amount,i);
861 surf_workstation_model->extension.
862 workstation.communicate(surf_workstations[0], surf_workstations[1],
868 if (!task->surf_action) {
869 double *computation_amount = xbt_new(double, task->workstation_nb);
870 double *communication_amount = xbt_new(double, task->workstation_nb *
871 task->workstation_nb);
873 memcpy(computation_amount, task->computation_amount, sizeof(double) *
874 task->workstation_nb);
875 memcpy(communication_amount, task->communication_amount,
876 sizeof(double) * task->workstation_nb * task->workstation_nb);
879 surf_workstation_model->extension.
880 workstation.execute_parallel_task(task->workstation_nb,
881 surf_workstations, computation_amount,
882 communication_amount, task->amount,
885 xbt_free(surf_workstations);
888 surf_workstation_model->action_data_set(task->surf_action, task);
890 DEBUG1("surf_action = %p", task->surf_action);
892 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
893 __SD_task_set_state(task, SD_RUNNING);
894 xbt_assert2(__SD_task_is_running(task), "Bad state of task '%s': %d",
895 SD_task_get_name(task), SD_task_get_state(task));
899 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_READY
900 * (ie when its dependencies are satisfied).
901 * If one of the workstations where the task is scheduled on is busy (in sequential mode),
902 * the task doesn't start.
903 * Returns whether the task has started.
905 int __SD_task_try_to_run(SD_task_t task)
910 SD_workstation_t workstation;
912 SD_CHECK_INIT_DONE();
913 xbt_assert0(task != NULL, "Invalid parameter");
914 xbt_assert2(__SD_task_is_ready(task),
915 "Task '%s' is not ready! Task state: %d",
916 SD_task_get_name(task), SD_task_get_state(task));
919 for (i = 0; i < task->workstation_nb; i++) {
920 can_start = !__SD_workstation_is_busy(task->workstation_list[i]);
923 DEBUG2("Task '%s' can start: %d", SD_task_get_name(task), can_start);
925 if (!can_start) { /* if the task cannot start and is not in the fifos yet */
926 for (i = 0; i < task->workstation_nb; i++) {
927 workstation = task->workstation_list[i];
928 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
929 DEBUG2("Pushing task '%s' in the fifo of workstation '%s'",
930 SD_task_get_name(task), SD_workstation_get_name(workstation));
931 xbt_fifo_push(workstation->task_fifo, task);
934 __SD_task_set_state(task, SD_IN_FIFO);
935 xbt_assert2(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
936 SD_task_get_name(task), SD_task_get_state(task));
937 DEBUG1("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
939 __SD_task_really_run(task);
945 /* This function is called by SD_simulate when a task is done.
946 * It updates task->state and task->action and executes if necessary the tasks
947 * which were waiting in fifos for the end of `task'
949 void __SD_task_just_done(SD_task_t task)
952 SD_workstation_t workstation;
955 int candidate_nb = 0;
956 int candidate_capacity = 8;
957 SD_task_t *candidates;
960 SD_CHECK_INIT_DONE();
961 xbt_assert0(task != NULL, "Invalid parameter");
962 xbt_assert1(__SD_task_is_running(task),
963 "The task must be running! Task state: %d",
964 SD_task_get_state(task));
965 xbt_assert1(task->workstation_list != NULL,
966 "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
969 candidates = xbt_new(SD_task_t, 8);
971 __SD_task_set_state(task, SD_DONE);
972 surf_workstation_model->action_unref(task->surf_action);
973 task->surf_action = NULL;
975 DEBUG0("Looking for candidates");
977 /* if the task was executed on sequential workstations,
978 maybe we can execute the next task of the fifo for each workstation */
979 for (i = 0; i < task->workstation_nb; i++) {
980 workstation = task->workstation_list[i];
981 DEBUG2("Workstation '%s': access_mode = %d",
982 SD_workstation_get_name(workstation), workstation->access_mode);
983 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
984 xbt_assert1(workstation->task_fifo != NULL,
985 "Workstation '%s' has sequential access but no fifo!",
986 SD_workstation_get_name(workstation));
987 xbt_assert2(workstation->current_task =
988 task, "Workstation '%s': current task should be '%s'",
989 SD_workstation_get_name(workstation),
990 SD_task_get_name(task));
992 /* the task is over so we can release the workstation */
993 workstation->current_task = NULL;
995 DEBUG0("Getting candidate in fifo");
997 xbt_fifo_get_item_content(xbt_fifo_get_first_item
998 (workstation->task_fifo));
1000 if (candidate != NULL) {
1001 DEBUG1("Candidate: '%s'", SD_task_get_name(candidate));
1002 xbt_assert2(__SD_task_is_in_fifo(candidate),
1003 "Bad state of candidate '%s': %d",
1004 SD_task_get_name(candidate),
1005 SD_task_get_state(candidate));
1008 DEBUG1("Candidate in fifo: %p", candidate);
1010 /* if there was a task waiting for my place */
1011 if (candidate != NULL) {
1012 /* Unfortunately, we are not sure yet that we can execute the task now,
1013 because the task can be waiting more deeply in some other workstation's fifos...
1014 So we memorize all candidate tasks, and then we will check for each candidate
1015 whether or not all its workstations are available. */
1017 /* realloc if necessary */
1018 if (candidate_nb == candidate_capacity) {
1019 candidate_capacity *= 2;
1021 xbt_realloc(candidates, sizeof(SD_task_t) * candidate_capacity);
1024 /* register the candidate */
1025 candidates[candidate_nb++] = candidate;
1026 candidate->fifo_checked = 0;
1031 DEBUG1("Candidates found: %d", candidate_nb);
1033 /* now we check every candidate task */
1034 for (i = 0; i < candidate_nb; i++) {
1035 candidate = candidates[i];
1037 if (candidate->fifo_checked) {
1038 continue; /* we have already evaluated that task */
1041 xbt_assert2(__SD_task_is_in_fifo(candidate),
1042 "Bad state of candidate '%s': %d",
1043 SD_task_get_name(candidate), SD_task_get_state(candidate));
1045 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1046 workstation = candidate->workstation_list[j];
1048 /* I can start on this workstation if the workstation is shared
1049 or if I am the first task in the fifo */
1050 can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS ||
1052 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1053 (workstation->task_fifo));
1056 DEBUG2("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1059 /* now we are sure that I can start! */
1061 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1062 workstation = candidate->workstation_list[j];
1064 /* update the fifo */
1065 if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1066 candidate = xbt_fifo_shift(workstation->task_fifo); /* the return value is stored just for debugging */
1067 DEBUG1("Head of the fifo: '%s'",
1068 (candidate != NULL) ? SD_task_get_name(candidate) : "NULL");
1069 xbt_assert0(candidate == candidates[i],
1070 "Error in __SD_task_just_done: bad first task in the fifo");
1072 } /* for each workstation */
1074 /* finally execute the task */
1075 DEBUG2("Task '%s' state: %d", SD_task_get_name(candidate),
1076 SD_task_get_state(candidate));
1077 __SD_task_really_run(candidate);
1080 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1081 SD_task_get_name(candidate), candidate->state_set,
1082 sd_global->running_task_set, __SD_task_is_running(candidate));
1083 xbt_assert2(__SD_task_is_running(candidate),
1084 "Bad state of task '%s': %d", SD_task_get_name(candidate),
1085 SD_task_get_state(candidate));
1086 DEBUG0("Okay, the task is running.");
1089 candidate->fifo_checked = 1;
1090 } /* for each candidate */
1092 xbt_free(candidates);
1095 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1097 static void __SD_task_remove_dependencies(SD_task_t task)
1099 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1100 because each one is stored twice */
1101 SD_dependency_t dependency;
1102 while (xbt_dynar_length(task->tasks_before) > 0) {
1103 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1104 SD_task_dependency_remove(dependency->src, dependency->dst);
1107 while (xbt_dynar_length(task->tasks_after) > 0) {
1108 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1109 SD_task_dependency_remove(dependency->src, dependency->dst);
1114 * \brief Returns the start time of a task
1116 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1118 * \param task: a task
1119 * \return the start time of this task
1121 double SD_task_get_start_time(SD_task_t task)
1123 SD_CHECK_INIT_DONE();
1124 xbt_assert0(task != NULL, "Invalid parameter");
1125 if (task->surf_action)
1126 return surf_workstation_model->action_get_start_time(task->surf_action);
1128 return task->start_time;
1132 * \brief Returns the finish time of a task
1134 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1135 * If the state is not completed yet, the returned value is an
1136 * estimation of the task finish time. This value can fluctuate
1137 * until the task is completed.
1139 * \param task: a task
1140 * \return the start time of this task
1142 double SD_task_get_finish_time(SD_task_t task)
1144 SD_CHECK_INIT_DONE();
1145 xbt_assert0(task != NULL, "Invalid parameter");
1147 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1148 return surf_workstation_model->action_get_finish_time(task->surf_action);
1150 return task->finish_time;
1154 * \brief Destroys a task.
1156 * The user data (if any) should have been destroyed first.
1158 * \param task the task you want to destroy
1159 * \see SD_task_create()
1161 void SD_task_destroy(SD_task_t task)
1163 SD_CHECK_INIT_DONE();
1164 xbt_assert0(task != NULL, "Invalid parameter");
1166 DEBUG1("Destroying task %s...", SD_task_get_name(task));
1168 __SD_task_remove_dependencies(task);
1169 /* if the task was scheduled or ready we have to free the scheduling parameters */
1170 if (__SD_task_is_scheduled_or_ready(task))
1171 __SD_task_destroy_scheduling_data(task);
1172 xbt_swag_remove(task,task->state_set);
1174 if (task->name != NULL)
1175 xbt_free(task->name);
1177 if (task->surf_action != NULL)
1178 surf_workstation_model->action_unref(task->surf_action);
1180 if (task->workstation_list != NULL)
1181 xbt_free(task->workstation_list);
1183 if (task->communication_amount)
1184 xbt_free(task->communication_amount);
1186 if (task->computation_amount)
1187 xbt_free(task->computation_amount);
1189 xbt_dynar_free(&task->tasks_before);
1190 xbt_dynar_free(&task->tasks_after);
1193 sd_global->task_number--;
1195 DEBUG0("Task destroyed.");
1199 static inline SD_task_t SD_task_create_sized(const char*name,void*data,double amount,int ws_count) {
1200 SD_task_t task = SD_task_create(name,data,amount);
1201 task->communication_amount = xbt_new0(double,ws_count*ws_count);
1202 task->computation_amount = xbt_new0(double,ws_count);
1203 task->workstation_nb = ws_count;
1204 task->workstation_list = xbt_new0(SD_workstation_t,ws_count);
1207 /** @brief create a end-to-end communication task that can then be auto-scheduled
1209 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1210 * allows to specify the task costs at creation, and decorelate them from the
1211 * scheduling process where you just specify which resource should deliver the
1214 * A end-to-end communication must be scheduled on 2 hosts, and the amount
1215 * specified at creation is sent from hosts[0] to hosts[1].
1217 SD_task_t SD_task_create_comm_e2e(const char*name, void *data, double amount) {
1218 SD_task_t res = SD_task_create_sized(name,data,amount,2);
1219 res->communication_amount[2] = amount;
1220 res->kind=SD_TASK_COMM_E2E;
1223 /** @brief create a sequential computation task that can then be auto-scheduled
1225 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1226 * allows to specify the task costs at creation, and decorelate them from the
1227 * scheduling process where you just specify which resource should deliver the
1230 * A sequential computation must be scheduled on 1 host, and the amount
1231 * specified at creation to be run on hosts[0].
1233 SD_task_t SD_task_create_comp_seq(const char*name, void *data, double amount) {
1234 SD_task_t res = SD_task_create_sized(name,data,amount,1);
1235 res->computation_amount[0]=amount;
1236 res->kind=SD_TASK_COMP_SEQ;
1240 /** @brief Auto-schedules a task.
1242 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1243 * allows to specify the task costs at creation, and decorelate them from the
1244 * scheduling process where you just specify which resource should deliver the
1247 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1248 * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1252 * We should create tasks kind for the following categories:
1253 * - Point to point communication (done)
1254 * - Sequential computation (done)
1255 * - group communication (redistribution, several kinds)
1256 * - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1257 * - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1259 void SD_task_schedulev(SD_task_t task, int count, const SD_workstation_t*list) {
1261 xbt_assert1(task->kind != 0,"Task %s is not typed. Cannot automatically schedule it.",SD_task_get_name(task));
1262 switch(task->kind) {
1263 case SD_TASK_COMM_E2E:
1264 case SD_TASK_COMP_SEQ:
1265 xbt_assert(task->workstation_nb==count);
1266 for (i=0;i<count;i++)
1267 task->workstation_list[i]=list[i];
1268 SD_task_do_schedule(task);
1271 xbt_die(bprintf("Kind of task %s not supported by SD_task_schedulev()",
1272 SD_task_get_name(task)));
1274 if (task->kind == SD_TASK_COMM_E2E) {
1275 VERB4("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1276 SD_task_get_name(task),
1277 SD_workstation_get_name(task->workstation_list[0]),SD_workstation_get_name(task->workstation_list[1]),
1278 task->communication_amount[2]);
1281 /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if ready) */
1282 if (task->kind == SD_TASK_COMP_SEQ) {
1283 VERB3("Schedule computation task %s on %s. It costs %.f flops",
1284 SD_task_get_name(task),SD_workstation_get_name(task->workstation_list[0]),
1285 task->computation_amount[0]);
1286 SD_dependency_t dep;
1288 xbt_dynar_foreach(task->tasks_before,cpt,dep) {
1289 SD_task_t before = dep->src;
1290 if (before->kind == SD_TASK_COMM_E2E) {
1291 before->workstation_list[1] = task->workstation_list[0];
1292 if (before->workstation_list[0] && __SD_task_is_not_scheduled(before)) {
1293 SD_task_do_schedule(before);
1294 VERB4("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1295 SD_task_get_name(before),
1296 SD_workstation_get_name(before->workstation_list[0]),SD_workstation_get_name(before->workstation_list[1]),
1297 before->communication_amount[2]);
1301 xbt_dynar_foreach(task->tasks_after,cpt,dep) {
1302 SD_task_t after = dep->dst;
1303 if (after->kind == SD_TASK_COMM_E2E) {
1304 after->workstation_list[0] = task->workstation_list[0];
1305 if (after->workstation_list[1] && __SD_task_is_not_scheduled(after)) {
1306 SD_task_do_schedule(after);
1307 VERB4("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1308 SD_task_get_name(after),
1309 SD_workstation_get_name(after->workstation_list[0]),SD_workstation_get_name(after->workstation_list[1]),
1310 after->communication_amount[2]);
1317 /** @brief autoschedule a task on a list of workstations
1319 * This function is very similar to SD_task_schedulev(),
1320 * but takes the list of workstations to schedule onto as separate parameters.
1321 * It builds a proper vector of workstations and then call SD_task_schedulev()
1323 void SD_task_schedulel(SD_task_t task, int count, ...) {
1325 SD_workstation_t *list=xbt_new(SD_workstation_t,count);
1328 for (i=0;i<count;i++) {
1329 list[i] = va_arg(ap,SD_workstation_t);
1332 SD_task_schedulev(task,count,list);