1 /* Copyright (c) 2006-2013. The SimGrid Team.
2 * All rights reserved. */
4 /* This program is free software; you can redistribute it and/or modify it
5 * under the terms of the license (GNU LGPL) which comes with this package. */
8 #include "simdag/simdag.h"
9 #include "xbt/sysdep.h"
10 #include "xbt/dynar.h"
11 #include "instr/instr_private.h"
13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
14 "Logging specific to SimDag (task)");
16 static void __SD_task_remove_dependencies(SD_task_t task);
17 static void __SD_task_destroy_scheduling_data(SD_task_t task);
19 void* SD_task_new_f(void)
21 SD_task_t task = xbt_new0(s_SD_task_t, 1);
22 task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
23 task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
28 void SD_task_recycle_f(void *t)
30 SD_task_t task = (SD_task_t) t;
32 /* Reset the content */
33 task->kind = SD_TASK_NOT_TYPED;
34 task->state_hookup.prev = NULL;
35 task->state_hookup.next = NULL;
36 task->state_set = sd_global->not_scheduled_task_set;
37 xbt_swag_insert(task, task->state_set);
38 task->state = SD_NOT_SCHEDULED;
39 task->return_hookup.prev = NULL;
40 task->return_hookup.next = NULL;
44 task->start_time = -1.0;
45 task->finish_time = -1.0;
46 task->surf_action = NULL;
47 task->watch_points = 0;
50 xbt_dynar_reset(task->tasks_before);
51 xbt_dynar_reset(task->tasks_after);
52 task->unsatisfied_dependencies = 0;
53 task->is_not_ready = 0;
55 /* scheduling parameters */
56 task->workstation_nb = 0;
57 task->workstation_list = NULL;
58 task->computation_amount = NULL;
59 task->communication_amount = NULL;
63 void SD_task_free_f(void *t)
65 SD_task_t task = (SD_task_t)t;
67 xbt_dynar_free(&task->tasks_before);
68 xbt_dynar_free(&task->tasks_after);
73 * \brief Creates a new task.
75 * \param name the name of the task (can be \c NULL)
76 * \param data the user data you want to associate with the task (can be \c NULL)
77 * \param amount amount of the task
78 * \return the new task
79 * \see SD_task_destroy()
81 SD_task_t SD_task_create(const char *name, void *data, double amount)
83 SD_task_t task = xbt_mallocator_get(sd_global->task_mallocator);
85 /* general information */
86 task->data = data; /* user data */
87 task->name = xbt_strdup(name);
88 task->amount = amount;
89 task->remains = amount;
91 sd_global->task_number++;
94 TRACE_sd_task_create(task);
100 static XBT_INLINE SD_task_t SD_task_create_sized(const char *name,
101 void *data, double amount,
104 SD_task_t task = SD_task_create(name, data, amount);
105 task->communication_amount = xbt_new0(double, ws_count * ws_count);
106 task->computation_amount = xbt_new0(double, ws_count);
107 task->workstation_nb = ws_count;
108 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
112 /** @brief create a end-to-end communication task that can then be auto-scheduled
114 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
115 * allows to specify the task costs at creation, and decouple them from the
116 * scheduling process where you just specify which resource should deliver the
119 * A end-to-end communication must be scheduled on 2 hosts, and the amount
120 * specified at creation is sent from hosts[0] to hosts[1].
122 SD_task_t SD_task_create_comm_e2e(const char *name, void *data,
125 SD_task_t res = SD_task_create_sized(name, data, amount, 2);
126 res->communication_amount[2] = amount;
127 res->kind = SD_TASK_COMM_E2E;
130 TRACE_category("COMM_E2E");
131 TRACE_sd_set_task_category(res, "COMM_E2E");
137 /** @brief create a sequential computation task that can then be auto-scheduled
139 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
140 * allows to specify the task costs at creation, and decouple them from the
141 * scheduling process where you just specify which resource should deliver the
144 * A sequential computation must be scheduled on 1 host, and the amount
145 * specified at creation to be run on hosts[0].
147 * \param name the name of the task (can be \c NULL)
148 * \param data the user data you want to associate with the task (can be \c NULL)
149 * \param amount amount of compute work to be done by the task
150 * \return the new SD_TASK_COMP_SEQ typed task
152 SD_task_t SD_task_create_comp_seq(const char *name, void *data,
155 SD_task_t res = SD_task_create_sized(name, data, amount, 1);
156 res->computation_amount[0] = amount;
157 res->kind = SD_TASK_COMP_SEQ;
160 TRACE_category("COMP_SEQ");
161 TRACE_sd_set_task_category(res, "COMP_SEQ");
167 /** @brief create a parallel computation task that can then be auto-scheduled
169 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
170 * allows to specify the task costs at creation, and decouple them from the
171 * scheduling process where you just specify which resource should deliver the
174 * A parallel computation can be scheduled on any number of host.
175 * The underlying speedup model is Amdahl's law.
176 * To be auto-scheduled, \see SD_task_distribute_comp_amdahl has to be called
178 * \param name the name of the task (can be \c NULL)
179 * \param data the user data you want to associate with the task (can be \c NULL)
180 * \param amount amount of compute work to be done by the task
181 * \param alpha purely serial fraction of the work to be done (in [0.;1.[)
182 * \return the new task
184 SD_task_t SD_task_create_comp_par_amdahl(const char *name, void *data,
185 double amount, double alpha)
187 xbt_assert(alpha < 1. && alpha >= 0.,
188 "Invalid parameter: alpha must be in [0.;1.[");
190 SD_task_t res = SD_task_create(name, data, amount);
192 res->kind = SD_TASK_COMP_PAR_AMDAHL;
195 TRACE_category("COMP_PAR_AMDAHL");
196 TRACE_sd_set_task_category(res, "COMP_PAR_AMDAHL");
202 /** @brief create a complex data redistribution task that can then be
205 * Auto-scheduling mean that the task can be used with SD_task_schedulev().
206 * This allows to specify the task costs at creation, and decouple them from
207 * the scheduling process where you just specify which resource should
210 * A data redistribution can be scheduled on any number of host.
211 * The assumed distribution is a 1D block distribution. Each host owns the same
212 * share of the \see amount.
213 * To be auto-scheduled, \see SD_task_distribute_comm_mxn_1d_block has to be
215 * \param name the name of the task (can be \c NULL)
216 * \param data the user data you want to associate with the task (can be
218 * \param amount amount of data to redistribute by the task
219 * \return the new task
221 SD_task_t SD_task_create_comm_par_mxn_1d_block(const char *name, void *data,
224 SD_task_t res = SD_task_create(name, data, amount);
225 res->workstation_list=NULL;
226 res->kind = SD_TASK_COMM_PAR_MXN_1D_BLOCK;
229 TRACE_category("COMM_PAR_MXN_1D_BLOCK");
230 TRACE_sd_set_task_category(res, "COMM_PAR_MXN_1D_BLOCK");
237 * \brief Destroys a task.
239 * The user data (if any) should have been destroyed first.
241 * \param task the task you want to destroy
242 * \see SD_task_create()
244 void SD_task_destroy(SD_task_t task)
246 XBT_DEBUG("Destroying task %s...", SD_task_get_name(task));
248 __SD_task_remove_dependencies(task);
249 /* if the task was scheduled or runnable we have to free the scheduling parameters */
250 if (__SD_task_is_scheduled_or_runnable(task))
251 __SD_task_destroy_scheduling_data(task);
252 if (task->state_set != NULL) /* would be null if just created */
253 xbt_swag_remove(task, task->state_set);
255 xbt_swag_remove(task, sd_global->return_set);
257 xbt_free(task->name);
259 if (task->surf_action != NULL)
260 surf_action_unref(task->surf_action);
262 xbt_free(task->workstation_list);
263 xbt_free(task->communication_amount);
264 xbt_free(task->computation_amount);
267 TRACE_sd_task_destroy(task);
270 xbt_mallocator_release(sd_global->task_mallocator,task);
271 sd_global->task_number--;
273 XBT_DEBUG("Task destroyed.");
277 * \brief Returns the user data of a task
280 * \return the user data associated with this task (can be \c NULL)
281 * \see SD_task_set_data()
283 void *SD_task_get_data(SD_task_t task)
289 * \brief Sets the user data of a task
291 * The new data can be \c NULL. The old data should have been freed first
292 * if it was not \c NULL.
295 * \param data the new data you want to associate with this task
296 * \see SD_task_get_data()
298 void SD_task_set_data(SD_task_t task, void *data)
304 * \brief Sets the rate of a task
306 * This will change the network bandwidth a task can use. This rate
307 * depends on both the nominal bandwidth on the route onto which the task is
308 * scheduled (\see SD_task_get_current_bandwidth) and the amount of data to
311 * To divide the nominal bandwidth by 2, the rate then has to be :
312 * rate = bandwidth/(2*amount)
314 * \param task a \see SD_TASK_COMM_E2E task (end-to-end communication)
315 * \param rate the new rate you want to associate with this task.
317 void SD_task_set_rate(SD_task_t task, double rate)
319 xbt_assert(task->kind == SD_TASK_COMM_E2E,
320 "The rate can be modified for end-to-end communications only.");
326 * \brief Returns the state of a task
329 * \return the current \ref e_SD_task_state_t "state" of this task:
330 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
331 * \see e_SD_task_state_t
333 e_SD_task_state_t SD_task_get_state(SD_task_t task)
338 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
340 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
342 xbt_swag_remove(task, task->state_set);
344 case SD_NOT_SCHEDULED:
345 task->state_set = sd_global->not_scheduled_task_set;
348 task->state_set = sd_global->schedulable_task_set;
351 task->state_set = sd_global->scheduled_task_set;
354 task->state_set = sd_global->runnable_task_set;
357 task->state_set = sd_global->in_fifo_task_set;
360 task->state_set = sd_global->running_task_set;
361 task->start_time = surf_action_get_start_time(task->surf_action);
364 task->state_set = sd_global->done_task_set;
365 task->finish_time = surf_action_get_finish_time(task->surf_action);
368 jedule_log_sd_event(task);
372 task->state_set = sd_global->failed_task_set;
375 xbt_die( "Invalid state");
377 xbt_swag_insert(task, task->state_set);
378 task->state = new_state;
380 if (task->watch_points & new_state) {
381 XBT_VERB("Watch point reached with task '%s'!", SD_task_get_name(task));
382 sd_global->watch_point_reached = 1;
383 SD_task_unwatch(task, new_state); /* remove the watch point */
388 * \brief Returns the name of a task
391 * \return the name of this task (can be \c NULL)
393 const char *SD_task_get_name(SD_task_t task)
398 /** @brief Allows to change the name of a task */
399 void SD_task_set_name(SD_task_t task, const char *name)
401 xbt_free(task->name);
402 task->name = xbt_strdup(name);
405 /** @brief Returns the dynar of the parents of a task
408 * \return a newly allocated dynar comprising the parents of this task
411 xbt_dynar_t SD_task_get_parents(SD_task_t task)
417 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
418 xbt_dynar_foreach(task->tasks_before, i, dep) {
419 xbt_dynar_push(parents, &(dep->src));
424 /** @brief Returns the dynar of the parents of a task
427 * \return a newly allocated dynar comprising the parents of this task
429 xbt_dynar_t SD_task_get_children(SD_task_t task)
432 xbt_dynar_t children;
435 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
436 xbt_dynar_foreach(task->tasks_after, i, dep) {
437 xbt_dynar_push(children, &(dep->dst));
443 * \brief Returns the amount of workstations involved in a task
445 * Only call this on already scheduled tasks!
448 int SD_task_get_workstation_count(SD_task_t task)
450 return task->workstation_nb;
454 * \brief Returns the list of workstations involved in a task
456 * Only call this on already scheduled tasks!
459 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
461 return task->workstation_list;
465 * \brief Returns the total amount of work contained in a task
468 * \return the total amount of work (computation or data transfer) for this task
469 * \see SD_task_get_remaining_amount()
471 double SD_task_get_amount(SD_task_t task)
477 * \brief Sets the total amount of work of a task
478 * For sequential typed tasks (COMP_SEQ and COMM_E2E), it also sets the
479 * appropriate values in the computation_amount and communication_amount arrays
480 * respectively. Nothing more than modifying task->amount is done for paralle
481 * typed tasks (COMP_PAR_AMDAHL and COMM_PAR_MXN_1D_BLOCK) as the distribution
482 * of the amount of work is done at scheduling time.
485 * \param amount the new amount of work to execute
487 void SD_task_set_amount(SD_task_t task, double amount)
489 task->amount = amount;
490 if (task->kind == SD_TASK_COMP_SEQ)
491 task->computation_amount[0] = amount;
492 if (task->kind == SD_TASK_COMM_E2E)
493 task->communication_amount[2] = amount;
497 * \brief Returns the alpha parameter of a SD_TASK_COMP_PAR_AMDAHL task
499 * \param task a parallel task assuming Amdahl's law as speedup model
500 * \return the alpha parameter (serial part of a task in percent) for this task
502 double SD_task_get_alpha(SD_task_t task)
504 xbt_assert(SD_task_get_kind(task) == SD_TASK_COMP_PAR_AMDAHL,
505 "Alpha parameter is not defined for this kink of task");
511 * \brief Returns the remaining amount work to do till the completion of a task
514 * \return the remaining amount of work (computation or data transfer) of this task
515 * \see SD_task_get_amount()
517 double SD_task_get_remaining_amount(SD_task_t task)
519 if (task->surf_action)
520 return surf_action_get_remains(task->surf_action);
522 return task->remains;
525 int SD_task_get_kind(SD_task_t task)
530 /** @brief Displays debugging informations about a task */
531 void SD_task_dump(SD_task_t task)
533 unsigned int counter;
534 SD_dependency_t dependency;
537 XBT_INFO("Displaying task %s", SD_task_get_name(task));
538 statename = bprintf("%s %s %s %s %s %s %s %s",
539 (task->state == SD_NOT_SCHEDULED ? "not scheduled" :
541 (task->state == SD_SCHEDULABLE ? "schedulable" : ""),
542 (task->state == SD_SCHEDULED ? "scheduled" : ""),
543 (task->state == SD_RUNNABLE ? "runnable" :
545 (task->state == SD_IN_FIFO ? "in fifo" : ""),
546 (task->state == SD_RUNNING ? "running" : ""),
547 (task->state == SD_DONE ? "done" : ""),
548 (task->state == SD_FAILED ? "failed" : ""));
549 XBT_INFO(" - state: %s", statename);
552 if (task->kind != 0) {
553 switch (task->kind) {
554 case SD_TASK_COMM_E2E:
555 XBT_INFO(" - kind: end-to-end communication");
557 case SD_TASK_COMP_SEQ:
558 XBT_INFO(" - kind: sequential computation");
560 case SD_TASK_COMP_PAR_AMDAHL:
561 XBT_INFO(" - kind: parallel computation following Amdahl's law");
563 case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
564 XBT_INFO(" - kind: MxN data redistribution assuming 1D block distribution");
567 XBT_INFO(" - (unknown kind %d)", task->kind);
573 XBT_INFO(" - tracing category: %s", task->category);
576 XBT_INFO(" - amount: %.0f", SD_task_get_amount(task));
577 if (task->kind == SD_TASK_COMP_PAR_AMDAHL)
578 XBT_INFO(" - alpha: %.2f", task->alpha);
579 XBT_INFO(" - Dependencies to satisfy: %d", task->unsatisfied_dependencies);
580 if (!xbt_dynar_is_empty(task->tasks_before)) {
581 XBT_INFO(" - pre-dependencies:");
582 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
583 XBT_INFO(" %s", SD_task_get_name(dependency->src));
586 if (!xbt_dynar_is_empty(task->tasks_after)) {
587 XBT_INFO(" - post-dependencies:");
588 xbt_dynar_foreach(task->tasks_after, counter, dependency) {
589 XBT_INFO(" %s", SD_task_get_name(dependency->dst));
594 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
595 void SD_task_dotty(SD_task_t task, void *out)
597 unsigned int counter;
598 SD_dependency_t dependency;
599 fprintf(out, " T%p [label=\"%.20s\"", task, task->name);
600 switch (task->kind) {
601 case SD_TASK_COMM_E2E:
602 case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
603 fprintf(out, ", shape=box");
605 case SD_TASK_COMP_SEQ:
606 case SD_TASK_COMP_PAR_AMDAHL:
607 fprintf(out, ", shape=circle");
610 xbt_die("Unknown task type!");
612 fprintf(out, "];\n");
613 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
614 fprintf(out, " T%p -> T%p;\n", dependency->src, dependency->dst);
618 /* Destroys a dependency between two tasks.
620 static void __SD_task_dependency_destroy(void *dependency)
622 xbt_free(((SD_dependency_t)dependency)->name);
623 xbt_free(dependency);
627 * \brief Adds a dependency between two tasks
629 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
630 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
632 * \param name the name of the new dependency (can be \c NULL)
633 * \param data the user data you want to associate with this dependency (can be \c NULL)
634 * \param src the task which must be executed first
635 * \param dst the task you want to make depend on \a src
636 * \see SD_task_dependency_remove()
638 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
642 unsigned long length;
645 SD_dependency_t dependency;
647 dynar = src->tasks_after;
648 length = xbt_dynar_length(dynar);
652 "Cannot add a dependency between task '%s' and itself",
653 SD_task_get_name(src));
655 if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_schedulable(src)
656 && !__SD_task_is_scheduled_or_runnable(src) && !__SD_task_is_running(src))
658 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE"
660 SD_task_get_name(src));
662 if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_schedulable(dst)
663 && !__SD_task_is_scheduled_or_runnable(dst))
665 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
666 SD_task_get_name(dst));
668 XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s",
669 SD_task_get_name(src), SD_task_get_name(dst));
670 for (i = 0; i < length && !found; i++) {
671 xbt_dynar_get_cpy(dynar, i, &dependency);
672 found = (dependency->dst == dst);
673 XBT_DEBUG("Dependency %lu: dependency->dst = %s", i,
674 SD_task_get_name(dependency->dst));
679 "A dependency already exists between task '%s' and task '%s'",
680 SD_task_get_name(src), SD_task_get_name(dst));
682 dependency = xbt_new(s_SD_dependency_t, 1);
684 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
685 dependency->data = data;
686 dependency->src = src;
687 dependency->dst = dst;
689 /* src must be executed before dst */
690 xbt_dynar_push(src->tasks_after, &dependency);
691 xbt_dynar_push(dst->tasks_before, &dependency);
693 dst->unsatisfied_dependencies++;
696 /* if the task was runnable, then dst->tasks_before is not empty anymore,
697 so we must go back to state SD_SCHEDULED */
698 if (__SD_task_is_runnable(dst)) {
700 ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
701 SD_task_get_name(dst));
702 __SD_task_set_state(dst, SD_SCHEDULED);
706 * \brief Returns the name given as input when dependency has been created..
709 * \param dst a task depending on \a src
712 const char *SD_task_dependency_get_name(SD_task_t src, SD_task_t dst){
714 SD_dependency_t dependency;
716 xbt_dynar_foreach(src->tasks_after, i, dependency){
717 if (dependency->dst == dst)
718 return dependency->name;
724 * \brief Indicates whether there is a dependency between two tasks.
727 * \param dst a task depending on \a src
729 * If src is NULL, checks whether dst has any pre-dependency.
730 * If dst is NULL, checks whether src has any post-dependency.
732 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
734 unsigned int counter;
735 SD_dependency_t dependency;
737 xbt_assert(src != NULL
739 "Invalid parameter: both src and dst are NULL");
743 xbt_dynar_foreach(src->tasks_after, counter, dependency) {
744 if (dependency->dst == dst)
748 return xbt_dynar_length(src->tasks_after);
751 return xbt_dynar_length(dst->tasks_before);
757 * \brief Remove a dependency between two tasks
760 * \param dst a task depending on \a src
761 * \see SD_task_dependency_add()
763 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
767 unsigned long length;
770 SD_dependency_t dependency;
772 /* remove the dependency from src->tasks_after */
773 dynar = src->tasks_after;
774 length = xbt_dynar_length(dynar);
776 for (i = 0; i < length && !found; i++) {
777 xbt_dynar_get_cpy(dynar, i, &dependency);
778 if (dependency->dst == dst) {
779 xbt_dynar_remove_at(dynar, i, NULL);
785 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
786 SD_task_get_name(src), SD_task_get_name(dst),
787 SD_task_get_name(dst), SD_task_get_name(src));
789 /* remove the dependency from dst->tasks_before */
790 dynar = dst->tasks_before;
791 length = xbt_dynar_length(dynar);
794 for (i = 0; i < length && !found; i++) {
795 xbt_dynar_get_cpy(dynar, i, &dependency);
796 if (dependency->src == src) {
797 xbt_dynar_remove_at(dynar, i, NULL);
798 __SD_task_dependency_destroy(dependency);
799 dst->unsatisfied_dependencies--;
804 /* should never happen... */
806 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
807 SD_task_get_name(dst), SD_task_get_name(src),
808 SD_task_get_name(src), SD_task_get_name(dst));
810 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
812 if (dst->unsatisfied_dependencies == 0) {
813 if (__SD_task_is_scheduled(dst))
814 __SD_task_set_state(dst, SD_RUNNABLE);
816 __SD_task_set_state(dst, SD_SCHEDULABLE);
819 if (dst->is_not_ready == 0)
820 __SD_task_set_state(dst, SD_SCHEDULABLE);
822 /* __SD_print_dependencies(src);
823 __SD_print_dependencies(dst); */
827 * \brief Returns the user data associated with a dependency between two tasks
830 * \param dst a task depending on \a src
831 * \return the user data associated with this dependency (can be \c NULL)
832 * \see SD_task_dependency_add()
834 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
838 unsigned long length;
841 SD_dependency_t dependency;
843 dynar = src->tasks_after;
844 length = xbt_dynar_length(dynar);
846 for (i = 0; i < length && !found; i++) {
847 xbt_dynar_get_cpy(dynar, i, &dependency);
848 found = (dependency->dst == dst);
851 THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'",
852 SD_task_get_name(src), SD_task_get_name(dst));
853 return dependency->data;
856 /* temporary function for debugging */
857 static void __SD_print_watch_points(SD_task_t task)
859 static const int state_masks[] =
860 { SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE,
863 static const char *state_names[] =
864 { "schedulable", "scheduled", "running", "runnable", "done",
869 XBT_INFO("Task '%s' watch points (%x): ", SD_task_get_name(task),
873 for (i = 0; i < 5; i++) {
874 if (task->watch_points & state_masks[i])
875 XBT_INFO("%s ", state_names[i]);
880 * \brief Adds a watch point to a task
882 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
883 * task becomes the one given in argument. The
884 * watch point is then automatically removed.
887 * \param state the \ref e_SD_task_state_t "state" you want to watch
888 * (cannot be #SD_NOT_SCHEDULED)
889 * \see SD_task_unwatch()
891 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
893 if (state & SD_NOT_SCHEDULED)
895 "Cannot add a watch point for state SD_NOT_SCHEDULED");
897 task->watch_points = task->watch_points | state;
898 /* __SD_print_watch_points(task); */
902 * \brief Removes a watch point from a task
905 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
906 * \see SD_task_watch()
908 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
910 xbt_assert(state != SD_NOT_SCHEDULED,
911 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
913 task->watch_points = task->watch_points & ~state;
914 /* __SD_print_watch_points(task); */
918 * \brief Returns an approximative estimation of the execution time of a task.
920 * The estimation is very approximative because the value returned is the time
921 * the task would take if it was executed now and if it was the only task.
923 * \param task the task to evaluate
924 * \param workstation_nb number of workstations on which the task would be executed
925 * \param workstation_list the workstations on which the task would be executed
926 * \param computation_amount computation amount for each workstation
927 * \param communication_amount communication amount between each pair of workstations
930 double SD_task_get_execution_time(SD_task_t task,
932 const SD_workstation_t *
934 const double *computation_amount,
935 const double *communication_amount)
937 double time, max_time = 0.0;
939 xbt_assert(workstation_nb > 0, "Invalid parameter");
941 /* the task execution time is the maximum execution time of the parallel tasks */
943 for (i = 0; i < workstation_nb; i++) {
945 if (computation_amount != NULL)
947 SD_workstation_get_computation_time(workstation_list[i],
948 computation_amount[i]);
950 if (communication_amount != NULL)
951 for (j = 0; j < workstation_nb; j++) {
953 SD_route_get_communication_time(workstation_list[i],
955 communication_amount[i *
960 if (time > max_time) {
967 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
969 if (!__SD_task_is_not_scheduled(task) && !__SD_task_is_schedulable(task))
970 THROWF(arg_error, 0, "Task '%s' has already been scheduled",
971 SD_task_get_name(task));
973 /* update the task state */
974 if (task->unsatisfied_dependencies == 0)
975 __SD_task_set_state(task, SD_RUNNABLE);
977 __SD_task_set_state(task, SD_SCHEDULED);
981 * \brief Schedules a task
983 * The task state must be #SD_NOT_SCHEDULED.
984 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
985 * i.e. when its dependencies are satisfied.
987 * \param task the task you want to schedule
988 * \param workstation_count number of workstations on which the task will be executed
989 * \param workstation_list the workstations on which the task will be executed
990 * \param computation_amount computation amount for each workstation
991 * \param communication_amount communication amount between each pair of workstations
992 * \param rate task execution speed rate
993 * \see SD_task_unschedule()
995 void SD_task_schedule(SD_task_t task, int workstation_count,
996 const SD_workstation_t * workstation_list,
997 const double *computation_amount,
998 const double *communication_amount, double rate)
1000 int communication_nb;
1001 task->workstation_nb = 0;
1003 xbt_assert(workstation_count > 0, "workstation_nb must be positive");
1005 task->workstation_nb = workstation_count;
1008 if (computation_amount) {
1009 task->computation_amount = xbt_realloc(task->computation_amount,
1010 sizeof(double) * workstation_count);
1011 memcpy(task->computation_amount, computation_amount,
1012 sizeof(double) * workstation_count);
1014 xbt_free(task->computation_amount);
1015 task->computation_amount = NULL;
1018 communication_nb = workstation_count * workstation_count;
1019 if (communication_amount) {
1020 task->communication_amount = xbt_realloc(task->communication_amount,
1021 sizeof(double) * communication_nb);
1022 memcpy(task->communication_amount, communication_amount,
1023 sizeof(double) * communication_nb);
1025 xbt_free(task->communication_amount);
1026 task->communication_amount = NULL;
1029 task->workstation_list =
1030 xbt_realloc(task->workstation_list,
1031 sizeof(SD_workstation_t) * workstation_count);
1032 memcpy(task->workstation_list, workstation_list,
1033 sizeof(SD_workstation_t) * workstation_count);
1035 SD_task_do_schedule(task);
1039 * \brief Unschedules a task
1041 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
1042 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
1043 * Call SD_task_schedule() to schedule it again.
1045 * \param task the task you want to unschedule
1046 * \see SD_task_schedule()
1048 void SD_task_unschedule(SD_task_t task)
1050 if (task->state_set != sd_global->scheduled_task_set &&
1051 task->state_set != sd_global->runnable_task_set &&
1052 task->state_set != sd_global->running_task_set &&
1053 task->state_set != sd_global->failed_task_set)
1054 THROWF(arg_error, 0,
1055 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
1056 SD_task_get_name(task));
1058 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
1059 && ((task->kind == SD_TASK_COMP_PAR_AMDAHL) ||
1060 (task->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK))) { /* Don't free scheduling data for typed tasks */
1061 __SD_task_destroy_scheduling_data(task);
1062 xbt_free(task->workstation_list);
1063 task->workstation_list=NULL;
1064 task->workstation_nb = 0;
1067 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
1068 surf_action_cancel(task->surf_action);
1070 if (task->unsatisfied_dependencies == 0)
1071 __SD_task_set_state(task, SD_SCHEDULABLE);
1073 __SD_task_set_state(task, SD_NOT_SCHEDULED);
1075 task->remains = task->amount;
1076 task->start_time = -1.0;
1079 /* Destroys the data memorized by SD_task_schedule.
1080 * Task state must be SD_SCHEDULED or SD_RUNNABLE.
1082 static void __SD_task_destroy_scheduling_data(SD_task_t task)
1084 if (!__SD_task_is_scheduled_or_runnable(task)
1085 && !__SD_task_is_in_fifo(task))
1086 THROWF(arg_error, 0,
1087 "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
1088 SD_task_get_name(task));
1090 xbt_free(task->computation_amount);
1091 xbt_free(task->communication_amount);
1092 task->computation_amount = task->communication_amount = NULL;
1095 /* Runs a task. This function is directly called by __SD_task_try_to_run if
1096 * the task doesn't have to wait in FIFOs. Otherwise, it is called by
1097 * __SD_task_just_done when the task gets out of its FIFOs.
1099 void __SD_task_really_run(SD_task_t task)
1103 void **surf_workstations;
1105 xbt_assert(__SD_task_is_runnable_or_in_fifo(task),
1106 "Task '%s' is not runnable or in a fifo! Task state: %d",
1107 SD_task_get_name(task), (int)SD_task_get_state(task));
1108 xbt_assert(task->workstation_list != NULL,
1109 "Task '%s': workstation_list is NULL!",
1110 SD_task_get_name(task));
1112 XBT_DEBUG("Really running task '%s'", SD_task_get_name(task));
1113 int workstation_nb = task->workstation_nb;
1115 /* set this task as current task for the workstations in sequential mode */
1116 for (i = 0; i < workstation_nb; i++) {
1117 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
1118 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1119 SD_workstation_priv(task->workstation_list[i])->current_task = task;
1120 xbt_assert(__SD_workstation_is_busy(task->workstation_list[i]),
1121 "The workstation should be busy now");
1125 XBT_DEBUG("Task '%s' set as current task for its workstations",
1126 SD_task_get_name(task));
1128 /* start the task */
1130 /* we have to create a Surf workstation array instead of the SimDag
1131 * workstation array */
1132 surf_workstations = xbt_new(void *, workstation_nb);
1134 for (i = 0; i < workstation_nb; i++)
1135 surf_workstations[i] = surf_workstation_resource_priv(task->workstation_list[i]);
1137 double *computation_amount = xbt_new0(double, workstation_nb);
1138 double *communication_amount = xbt_new0(double, workstation_nb * workstation_nb);
1141 if(task->computation_amount)
1142 memcpy(computation_amount, task->computation_amount, sizeof(double) *
1144 if(task->communication_amount)
1145 memcpy(communication_amount, task->communication_amount,
1146 sizeof(double) * workstation_nb * workstation_nb);
1148 task->surf_action = surf_workstation_model_execute_parallel_task((surf_workstation_model_t)surf_workstation_model,
1152 communication_amount,
1155 surf_action_set_data(task->surf_action, task);
1157 XBT_DEBUG("surf_action = %p", task->surf_action);
1161 TRACE_surf_action(task->surf_action, task->category);
1164 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
1165 __SD_task_set_state(task, SD_RUNNING);
1166 xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
1167 SD_task_get_name(task), (int)SD_task_get_state(task));
1171 /* Tries to run a task. This function is called by SD_simulate() when a
1172 * scheduled task becomes SD_RUNNABLE (i.e., when its dependencies are
1174 * If one of the workstations where the task is scheduled on is busy (in
1175 * sequential mode), the task doesn't start.
1176 * Returns whether the task has started.
1178 int __SD_task_try_to_run(SD_task_t task)
1183 SD_workstation_t workstation;
1185 xbt_assert(__SD_task_is_runnable(task),
1186 "Task '%s' is not runnable! Task state: %d",
1187 SD_task_get_name(task), (int)SD_task_get_state(task));
1190 for (i = 0; i < task->workstation_nb; i++) {
1191 can_start = can_start &&
1192 !__SD_workstation_is_busy(task->workstation_list[i]);
1195 XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1197 if (!can_start) { /* if the task cannot start and is not in the FIFOs yet */
1198 for (i = 0; i < task->workstation_nb; i++) {
1199 workstation = task->workstation_list[i];
1200 if (SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1201 XBT_DEBUG("Pushing task '%s' in the FIFO of workstation '%s'",
1202 SD_task_get_name(task),
1203 SD_workstation_get_name(workstation));
1204 xbt_fifo_push(SD_workstation_priv(workstation)->task_fifo, task);
1207 __SD_task_set_state(task, SD_IN_FIFO);
1208 xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1209 SD_task_get_name(task), (int)SD_task_get_state(task));
1210 XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1212 __SD_task_really_run(task);
1218 /* This function is called by SD_simulate when a task is done.
1219 * It updates task->state and task->action and executes if necessary the tasks
1220 * which were waiting in FIFOs for the end of `task'
1222 void __SD_task_just_done(SD_task_t task)
1225 SD_workstation_t workstation;
1227 SD_task_t candidate;
1228 int candidate_nb = 0;
1229 int candidate_capacity = 8;
1230 SD_task_t *candidates;
1233 xbt_assert(__SD_task_is_running(task),
1234 "The task must be running! Task state: %d",
1235 (int)SD_task_get_state(task));
1236 xbt_assert(task->workstation_list != NULL,
1237 "Task '%s': workstation_list is NULL!",
1238 SD_task_get_name(task));
1241 candidates = xbt_new(SD_task_t, 8);
1243 __SD_task_set_state(task, SD_DONE);
1244 surf_action_unref(task->surf_action);
1245 task->surf_action = NULL;
1247 XBT_DEBUG("Looking for candidates");
1249 /* if the task was executed on sequential workstations,
1250 maybe we can execute the next task of the FIFO for each workstation */
1251 for (i = 0; i < task->workstation_nb; i++) {
1252 workstation = task->workstation_list[i];
1253 XBT_DEBUG("Workstation '%s': access_mode = %d",
1254 SD_workstation_get_name(workstation), (int)SD_workstation_priv(workstation)->access_mode);
1255 if (SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1256 xbt_assert(SD_workstation_priv(workstation)->task_fifo != NULL,
1257 "Workstation '%s' has sequential access but no FIFO!",
1258 SD_workstation_get_name(workstation));
1259 xbt_assert(SD_workstation_priv(workstation)->current_task =
1260 task, "Workstation '%s': current task should be '%s'",
1261 SD_workstation_get_name(workstation),
1262 SD_task_get_name(task));
1264 /* the task is over so we can release the workstation */
1265 SD_workstation_priv(workstation)->current_task = NULL;
1267 XBT_DEBUG("Getting candidate in FIFO");
1269 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1270 (SD_workstation_priv(workstation)->task_fifo));
1272 if (candidate != NULL) {
1273 XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1274 xbt_assert(__SD_task_is_in_fifo(candidate),
1275 "Bad state of candidate '%s': %d",
1276 SD_task_get_name(candidate),
1277 (int)SD_task_get_state(candidate));
1280 XBT_DEBUG("Candidate in fifo: %p", candidate);
1282 /* if there was a task waiting for my place */
1283 if (candidate != NULL) {
1284 /* Unfortunately, we are not sure yet that we can execute the task now,
1285 because the task can be waiting more deeply in some other
1286 workstation's FIFOs ...
1287 So we memorize all candidate tasks, and then we will check for each
1288 candidate whether or not all its workstations are available. */
1290 /* realloc if necessary */
1291 if (candidate_nb == candidate_capacity) {
1292 candidate_capacity *= 2;
1294 xbt_realloc(candidates,
1295 sizeof(SD_task_t) * candidate_capacity);
1298 /* register the candidate */
1299 candidates[candidate_nb++] = candidate;
1300 candidate->fifo_checked = 0;
1305 XBT_DEBUG("Candidates found: %d", candidate_nb);
1307 /* now we check every candidate task */
1308 for (i = 0; i < candidate_nb; i++) {
1309 candidate = candidates[i];
1311 if (candidate->fifo_checked) {
1312 continue; /* we have already evaluated that task */
1315 xbt_assert(__SD_task_is_in_fifo(candidate),
1316 "Bad state of candidate '%s': %d",
1317 SD_task_get_name(candidate), (int)SD_task_get_state(candidate));
1319 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1320 workstation = candidate->workstation_list[j];
1322 /* I can start on this workstation if the workstation is shared
1323 or if I am the first task in the FIFO */
1324 can_start = SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SHARED_ACCESS
1326 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1327 (SD_workstation_priv(workstation)->task_fifo));
1330 XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1333 /* now we are sure that I can start! */
1335 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1336 workstation = candidate->workstation_list[j];
1338 /* update the FIFO */
1339 if (SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1340 candidate = xbt_fifo_shift(SD_workstation_priv(workstation)->task_fifo); /* the return value is stored just for debugging */
1341 XBT_DEBUG("Head of the FIFO: '%s'",
1343 NULL) ? SD_task_get_name(candidate) : "NULL");
1344 xbt_assert(candidate == candidates[i],
1345 "Error in __SD_task_just_done: bad first task in the FIFO");
1347 } /* for each workstation */
1349 /* finally execute the task */
1350 XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1351 (int)SD_task_get_state(candidate));
1352 __SD_task_really_run(candidate);
1355 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1356 SD_task_get_name(candidate), candidate->state_set,
1357 sd_global->running_task_set, __SD_task_is_running(candidate));
1358 xbt_assert(__SD_task_is_running(candidate),
1359 "Bad state of task '%s': %d",
1360 SD_task_get_name(candidate),
1361 (int)SD_task_get_state(candidate));
1362 XBT_DEBUG("Okay, the task is running.");
1365 candidate->fifo_checked = 1;
1366 } /* for each candidate */
1368 xbt_free(candidates);
1372 * Remove all dependencies associated with a task. This function is called
1373 * when the task is destroyed.
1375 static void __SD_task_remove_dependencies(SD_task_t task)
1377 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1378 because each one is stored twice */
1379 SD_dependency_t dependency;
1380 while (!xbt_dynar_is_empty(task->tasks_before)) {
1381 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1382 SD_task_dependency_remove(dependency->src, dependency->dst);
1385 while (!xbt_dynar_is_empty(task->tasks_after)) {
1386 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1387 SD_task_dependency_remove(dependency->src, dependency->dst);
1392 * \brief Returns the start time of a task
1394 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1396 * \param task: a task
1397 * \return the start time of this task
1399 double SD_task_get_start_time(SD_task_t task)
1401 if (task->surf_action)
1402 return surf_action_get_start_time(task->surf_action);
1404 return task->start_time;
1408 * \brief Returns the finish time of a task
1410 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1411 * If the state is not completed yet, the returned value is an
1412 * estimation of the task finish time. This value can fluctuate
1413 * until the task is completed.
1415 * \param task: a task
1416 * \return the start time of this task
1418 double SD_task_get_finish_time(SD_task_t task)
1420 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1421 return surf_action_get_finish_time(task->surf_action);
1423 return task->finish_time;
1428 void SD_task_distribute_comp_amdahl(SD_task_t task, int ws_count)
1431 xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1432 "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1433 "Cannot use this function.",
1434 SD_task_get_name(task));
1435 task->computation_amount = xbt_new0(double, ws_count);
1436 task->communication_amount = xbt_new0(double, ws_count * ws_count);
1437 xbt_free(task->workstation_list);
1438 task->workstation_nb = ws_count;
1439 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1441 for(i=0;i<ws_count;i++){
1442 task->computation_amount[i] =
1443 (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1448 /** @brief Auto-schedules a task.
1450 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1451 * allows to specify the task costs at creation, and decouple them from the
1452 * scheduling process where you just specify which resource should deliver the
1455 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e()
1456 * or SD_task_create_comp_seq(). Check their definitions for the exact semantic
1460 * We should create tasks kind for the following categories:
1461 * - Point to point communication (done)
1462 * - Sequential computation (done)
1463 * - group communication (redistribution, several kinds)
1464 * - parallel tasks with no internal communication (one kind per speedup
1465 * model such as Amdahl)
1466 * - idem+ internal communication. Task type not enough since we cannot store
1467 * comm cost alongside to comp one)
1469 void SD_task_schedulev(SD_task_t task, int count,
1470 const SD_workstation_t * list)
1473 SD_dependency_t dep;
1475 xbt_assert(task->kind != 0,
1476 "Task %s is not typed. Cannot automatically schedule it.",
1477 SD_task_get_name(task));
1478 switch (task->kind) {
1479 case SD_TASK_COMP_PAR_AMDAHL:
1480 SD_task_distribute_comp_amdahl(task, count);
1481 case SD_TASK_COMM_E2E:
1482 case SD_TASK_COMP_SEQ:
1483 xbt_assert(task->workstation_nb == count,
1484 "Got %d locations, but were expecting %d locations",
1485 count,task->workstation_nb);
1486 for (i = 0; i < count; i++)
1487 task->workstation_list[i] = list[i];
1488 if (SD_task_get_kind(task)== SD_TASK_COMP_SEQ && !task->computation_amount){
1489 /*This task has failed and is rescheduled. Reset the computation amount*/
1490 task->computation_amount = xbt_new0(double, 1);
1491 task->computation_amount[0] = task->remains;
1493 SD_task_do_schedule(task);
1496 xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1497 SD_task_get_name(task));
1499 if (task->kind == SD_TASK_COMM_E2E) {
1500 XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1501 SD_task_get_name(task),
1502 SD_workstation_get_name(task->workstation_list[0]),
1503 SD_workstation_get_name(task->workstation_list[1]),
1504 task->communication_amount[2]);
1508 /* Iterate over all children and parents being COMM_E2E to say where I am
1509 * located (and start them if runnable) */
1510 if (task->kind == SD_TASK_COMP_SEQ) {
1511 XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1512 SD_task_get_name(task),
1513 SD_workstation_get_name(task->workstation_list[0]),
1514 task->computation_amount[0]);
1516 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1517 SD_task_t before = dep->src;
1518 if (before->kind == SD_TASK_COMM_E2E) {
1519 before->workstation_list[1] = task->workstation_list[0];
1521 if (before->workstation_list[0] &&
1522 (__SD_task_is_schedulable(before)
1523 || __SD_task_is_not_scheduled(before))) {
1524 SD_task_do_schedule(before);
1526 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1527 SD_task_get_name(before),
1528 SD_workstation_get_name(before->workstation_list[0]),
1529 SD_workstation_get_name(before->workstation_list[1]),
1530 before->communication_amount[2]);
1534 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1535 SD_task_t after = dep->dst;
1536 if (after->kind == SD_TASK_COMM_E2E) {
1537 after->workstation_list[0] = task->workstation_list[0];
1538 if (after->workstation_list[1]
1539 && (__SD_task_is_not_scheduled(after)
1540 || __SD_task_is_schedulable(after))) {
1541 SD_task_do_schedule(after);
1543 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1544 SD_task_get_name(after),
1545 SD_workstation_get_name(after->workstation_list[0]),
1546 SD_workstation_get_name(after->workstation_list[1]),
1547 after->communication_amount[2]);
1553 /* Iterate over all children and parents being MXN_1D_BLOCK to say where I am
1554 * located (and start them if runnable) */
1555 if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1556 XBT_VERB("Schedule computation task %s on %d workstations. %.f flops"
1557 " will be distributed following Amdahl's Law",
1558 SD_task_get_name(task), task->workstation_nb,
1559 task->computation_amount[0]);
1560 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1561 SD_task_t before = dep->src;
1562 if (before->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1563 if (!before->workstation_list){
1564 XBT_VERB("Sender side of Task %s is not scheduled yet",
1565 SD_task_get_name(before));
1566 before->workstation_list = xbt_new0(SD_workstation_t, count);
1567 before->workstation_nb = count;
1568 XBT_VERB("Fill the workstation list with list of Task '%s'",
1569 SD_task_get_name(task));
1570 for (i=0;i<count;i++)
1571 before->workstation_list[i] = task->workstation_list[i];
1573 XBT_VERB("Build communication matrix for task '%s'",
1574 SD_task_get_name(before));
1576 double src_start, src_end, dst_start, dst_end;
1577 src_nb = before->workstation_nb;
1579 before->workstation_list = (SD_workstation_t*) xbt_realloc(
1580 before->workstation_list,
1581 (before->workstation_nb+count)*sizeof(s_SD_workstation_t));
1582 for(i=0; i<count; i++)
1583 before->workstation_list[before->workstation_nb+i] =
1584 task->workstation_list[i];
1586 before->workstation_nb += count;
1587 xbt_free(before->computation_amount);
1588 xbt_free(before->communication_amount);
1589 before->computation_amount = xbt_new0(double,
1590 before->workstation_nb);
1591 before->communication_amount = xbt_new0(double,
1592 before->workstation_nb*
1593 before->workstation_nb);
1595 for(i=0;i<src_nb;i++){
1596 src_start = i*before->amount/src_nb;
1597 src_end = src_start + before->amount/src_nb;
1598 for(j=0; j<dst_nb; j++){
1599 dst_start = j*before->amount/dst_nb;
1600 dst_end = dst_start + before->amount/dst_nb;
1601 XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)",
1602 SD_workstation_get_name(before->workstation_list[i]),
1603 SD_workstation_get_name(before->workstation_list[src_nb+j]),
1604 src_start, src_end, dst_start, dst_end);
1605 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1606 before->communication_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1608 before->communication_amount[i*(src_nb+dst_nb)+src_nb+j] =
1609 MIN(src_end, dst_end) - MAX(src_start, dst_start);
1611 XBT_VERB("==> %.2f",
1612 before->communication_amount[i*(src_nb+dst_nb)+src_nb+j]);
1616 if (__SD_task_is_schedulable(before) ||
1617 __SD_task_is_not_scheduled(before)) {
1618 SD_task_do_schedule(before);
1620 ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1621 SD_task_get_name(before),before->amount, src_nb, dst_nb);
1626 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1627 SD_task_t after = dep->dst;
1628 if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1629 if (!after->workstation_list){
1630 XBT_VERB("Receiver side of Task '%s' is not scheduled yet",
1631 SD_task_get_name(after));
1632 after->workstation_list = xbt_new0(SD_workstation_t, count);
1633 after->workstation_nb = count;
1634 XBT_VERB("Fill the workstation list with list of Task '%s'",
1635 SD_task_get_name(task));
1636 for (i=0;i<count;i++)
1637 after->workstation_list[i] = task->workstation_list[i];
1640 double src_start, src_end, dst_start, dst_end;
1642 dst_nb = after->workstation_nb;
1643 after->workstation_list = (SD_workstation_t*) xbt_realloc(
1644 after->workstation_list,
1645 (after->workstation_nb+count)*sizeof(s_SD_workstation_t));
1646 for(i=after->workstation_nb - 1; i>=0; i--)
1647 after->workstation_list[count+i] = after->workstation_list[i];
1648 for(i=0; i<count; i++)
1649 after->workstation_list[i] = task->workstation_list[i];
1651 after->workstation_nb += count;
1653 xbt_free(after->computation_amount);
1654 xbt_free(after->communication_amount);
1656 after->computation_amount = xbt_new0(double, after->workstation_nb);
1657 after->communication_amount = xbt_new0(double,
1658 after->workstation_nb*
1659 after->workstation_nb);
1661 for(i=0;i<src_nb;i++){
1662 src_start = i*after->amount/src_nb;
1663 src_end = src_start + after->amount/src_nb;
1664 for(j=0; j<dst_nb; j++){
1665 dst_start = j*after->amount/dst_nb;
1666 dst_end = dst_start + after->amount/dst_nb;
1667 XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)",
1668 i, j, src_start, src_end, dst_start, dst_end);
1669 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1670 after->communication_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1672 after->communication_amount[i*(src_nb+dst_nb)+src_nb+j] =
1673 MIN(src_end, dst_end)- MAX(src_start, dst_start);
1675 XBT_VERB("==> %.2f",
1676 after->communication_amount[i*(src_nb+dst_nb)+src_nb+j]);
1680 if (__SD_task_is_schedulable(after) ||
1681 __SD_task_is_not_scheduled(after)) {
1682 SD_task_do_schedule(after);
1684 ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1685 SD_task_get_name(after),after->amount, src_nb, dst_nb);
1693 /** @brief autoschedule a task on a list of workstations
1695 * This function is very similar to SD_task_schedulev(),
1696 * but takes the list of workstations to schedule onto as separate parameters.
1697 * It builds a proper vector of workstations and then call SD_task_schedulev()
1699 void SD_task_schedulel(SD_task_t task, int count, ...)
1702 SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1704 va_start(ap, count);
1705 for (i = 0; i < count; i++) {
1706 list[i] = va_arg(ap, SD_workstation_t);
1709 SD_task_schedulev(task, count, list);