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_workstation_model->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;
362 surf_workstation_model->action_get_start_time(task->surf_action);
365 task->state_set = sd_global->done_task_set;
367 surf_workstation_model->action_get_finish_time(task->surf_action);
370 jedule_log_sd_event(task);
374 task->state_set = sd_global->failed_task_set;
377 xbt_die( "Invalid state");
379 xbt_swag_insert(task, task->state_set);
380 task->state = new_state;
382 if (task->watch_points & new_state) {
383 XBT_VERB("Watch point reached with task '%s'!", SD_task_get_name(task));
384 sd_global->watch_point_reached = 1;
385 SD_task_unwatch(task, new_state); /* remove the watch point */
390 * \brief Returns the name of a task
393 * \return the name of this task (can be \c NULL)
395 const char *SD_task_get_name(SD_task_t task)
400 /** @brief Allows to change the name of a task */
401 void SD_task_set_name(SD_task_t task, const char *name)
403 xbt_free(task->name);
404 task->name = xbt_strdup(name);
407 /** @brief Returns the dynar of the parents of a task
410 * \return a newly allocated dynar comprising the parents of this task
413 xbt_dynar_t SD_task_get_parents(SD_task_t task)
419 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
420 xbt_dynar_foreach(task->tasks_before, i, dep) {
421 xbt_dynar_push(parents, &(dep->src));
426 /** @brief Returns the dynar of the parents of a task
429 * \return a newly allocated dynar comprising the parents of this task
431 xbt_dynar_t SD_task_get_children(SD_task_t task)
434 xbt_dynar_t children;
437 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
438 xbt_dynar_foreach(task->tasks_after, i, dep) {
439 xbt_dynar_push(children, &(dep->dst));
445 * \brief Returns the amount of workstations involved in a task
447 * Only call this on already scheduled tasks!
450 int SD_task_get_workstation_count(SD_task_t task)
452 return task->workstation_nb;
456 * \brief Returns the list of workstations involved in a task
458 * Only call this on already scheduled tasks!
461 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
463 return task->workstation_list;
467 * \brief Returns the total amount of work contained in a task
470 * \return the total amount of work (computation or data transfer) for this task
471 * \see SD_task_get_remaining_amount()
473 double SD_task_get_amount(SD_task_t task)
479 * \brief Sets the total amount of work of a task
480 * For sequential typed tasks (COMP_SEQ and COMM_E2E), it also sets the
481 * appropriate values in the computation_amount and communication_amount arrays
482 * respectively. Nothing more than modifying task->amount is done for paralle
483 * typed tasks (COMP_PAR_AMDAHL and COMM_PAR_MXN_1D_BLOCK) as the distribution
484 * of the amount of work is done at scheduling time.
487 * \param amount the new amount of work to execute
489 void SD_task_set_amount(SD_task_t task, double amount)
491 task->amount = amount;
492 if (task->kind == SD_TASK_COMP_SEQ)
493 task->computation_amount[0] = amount;
494 if (task->kind == SD_TASK_COMM_E2E)
495 task->communication_amount[2] = amount;
499 * \brief Returns the alpha parameter of a SD_TASK_COMP_PAR_AMDAHL task
501 * \param task a parallel task assuming Amdahl's law as speedup model
502 * \return the alpha parameter (serial part of a task in percent) for this task
504 double SD_task_get_alpha(SD_task_t task)
506 xbt_assert(SD_task_get_kind(task) == SD_TASK_COMP_PAR_AMDAHL,
507 "Alpha parameter is not defined for this kink of task");
513 * \brief Returns the remaining amount work to do till the completion of a task
516 * \return the remaining amount of work (computation or data transfer) of this task
517 * \see SD_task_get_amount()
519 double SD_task_get_remaining_amount(SD_task_t task)
521 if (task->surf_action)
522 return surf_workstation_model->get_remains(task->surf_action);
524 return task->remains;
527 int SD_task_get_kind(SD_task_t task)
532 /** @brief Displays debugging informations about a task */
533 void SD_task_dump(SD_task_t task)
535 unsigned int counter;
536 SD_dependency_t dependency;
539 XBT_INFO("Displaying task %s", SD_task_get_name(task));
540 statename = bprintf("%s %s %s %s %s %s %s %s",
541 (task->state == SD_NOT_SCHEDULED ? "not scheduled" :
543 (task->state == SD_SCHEDULABLE ? "schedulable" : ""),
544 (task->state == SD_SCHEDULED ? "scheduled" : ""),
545 (task->state == SD_RUNNABLE ? "runnable" :
547 (task->state == SD_IN_FIFO ? "in fifo" : ""),
548 (task->state == SD_RUNNING ? "running" : ""),
549 (task->state == SD_DONE ? "done" : ""),
550 (task->state == SD_FAILED ? "failed" : ""));
551 XBT_INFO(" - state: %s", statename);
554 if (task->kind != 0) {
555 switch (task->kind) {
556 case SD_TASK_COMM_E2E:
557 XBT_INFO(" - kind: end-to-end communication");
559 case SD_TASK_COMP_SEQ:
560 XBT_INFO(" - kind: sequential computation");
562 case SD_TASK_COMP_PAR_AMDAHL:
563 XBT_INFO(" - kind: parallel computation following Amdahl's law");
565 case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
566 XBT_INFO(" - kind: MxN data redistribution assuming 1D block distribution");
569 XBT_INFO(" - (unknown kind %d)", task->kind);
575 XBT_INFO(" - tracing category: %s", task->category);
578 XBT_INFO(" - amount: %.0f", SD_task_get_amount(task));
579 if (task->kind == SD_TASK_COMP_PAR_AMDAHL)
580 XBT_INFO(" - alpha: %.2f", task->alpha);
581 XBT_INFO(" - Dependencies to satisfy: %d", task->unsatisfied_dependencies);
582 if (!xbt_dynar_is_empty(task->tasks_before)) {
583 XBT_INFO(" - pre-dependencies:");
584 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
585 XBT_INFO(" %s", SD_task_get_name(dependency->src));
588 if (!xbt_dynar_is_empty(task->tasks_after)) {
589 XBT_INFO(" - post-dependencies:");
590 xbt_dynar_foreach(task->tasks_after, counter, dependency) {
591 XBT_INFO(" %s", SD_task_get_name(dependency->dst));
596 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
597 void SD_task_dotty(SD_task_t task, void *out)
599 unsigned int counter;
600 SD_dependency_t dependency;
601 fprintf(out, " T%p [label=\"%.20s\"", task, task->name);
602 switch (task->kind) {
603 case SD_TASK_COMM_E2E:
604 case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
605 fprintf(out, ", shape=box");
607 case SD_TASK_COMP_SEQ:
608 case SD_TASK_COMP_PAR_AMDAHL:
609 fprintf(out, ", shape=circle");
612 xbt_die("Unknown task type!");
614 fprintf(out, "];\n");
615 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
616 fprintf(out, " T%p -> T%p;\n", dependency->src, dependency->dst);
620 /* Destroys a dependency between two tasks.
622 static void __SD_task_dependency_destroy(void *dependency)
624 xbt_free(((SD_dependency_t)dependency)->name);
625 xbt_free(dependency);
629 * \brief Adds a dependency between two tasks
631 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
632 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
634 * \param name the name of the new dependency (can be \c NULL)
635 * \param data the user data you want to associate with this dependency (can be \c NULL)
636 * \param src the task which must be executed first
637 * \param dst the task you want to make depend on \a src
638 * \see SD_task_dependency_remove()
640 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
644 unsigned long length;
647 SD_dependency_t dependency;
649 dynar = src->tasks_after;
650 length = xbt_dynar_length(dynar);
654 "Cannot add a dependency between task '%s' and itself",
655 SD_task_get_name(src));
657 if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_schedulable(src)
658 && !__SD_task_is_scheduled_or_runnable(src) && !__SD_task_is_running(src))
660 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE"
662 SD_task_get_name(src));
664 if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_schedulable(dst)
665 && !__SD_task_is_scheduled_or_runnable(dst))
667 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
668 SD_task_get_name(dst));
670 XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s",
671 SD_task_get_name(src), SD_task_get_name(dst));
672 for (i = 0; i < length && !found; i++) {
673 xbt_dynar_get_cpy(dynar, i, &dependency);
674 found = (dependency->dst == dst);
675 XBT_DEBUG("Dependency %lu: dependency->dst = %s", i,
676 SD_task_get_name(dependency->dst));
681 "A dependency already exists between task '%s' and task '%s'",
682 SD_task_get_name(src), SD_task_get_name(dst));
684 dependency = xbt_new(s_SD_dependency_t, 1);
686 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
687 dependency->data = data;
688 dependency->src = src;
689 dependency->dst = dst;
691 /* src must be executed before dst */
692 xbt_dynar_push(src->tasks_after, &dependency);
693 xbt_dynar_push(dst->tasks_before, &dependency);
695 dst->unsatisfied_dependencies++;
698 /* if the task was runnable, then dst->tasks_before is not empty anymore,
699 so we must go back to state SD_SCHEDULED */
700 if (__SD_task_is_runnable(dst)) {
702 ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
703 SD_task_get_name(dst));
704 __SD_task_set_state(dst, SD_SCHEDULED);
708 * \brief Returns the name given as input when dependency has been created..
711 * \param dst a task depending on \a src
714 const char *SD_task_dependency_get_name(SD_task_t src, SD_task_t dst){
716 SD_dependency_t dependency;
718 xbt_dynar_foreach(src->tasks_after, i, dependency){
719 if (dependency->dst == dst)
720 return dependency->name;
726 * \brief Indicates whether there is a dependency between two tasks.
729 * \param dst a task depending on \a src
731 * If src is NULL, checks whether dst has any pre-dependency.
732 * If dst is NULL, checks whether src has any post-dependency.
734 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
736 unsigned int counter;
737 SD_dependency_t dependency;
739 xbt_assert(src != NULL
741 "Invalid parameter: both src and dst are NULL");
745 xbt_dynar_foreach(src->tasks_after, counter, dependency) {
746 if (dependency->dst == dst)
750 return xbt_dynar_length(src->tasks_after);
753 return xbt_dynar_length(dst->tasks_before);
759 * \brief Remove a dependency between two tasks
762 * \param dst a task depending on \a src
763 * \see SD_task_dependency_add()
765 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
769 unsigned long length;
772 SD_dependency_t dependency;
774 /* remove the dependency from src->tasks_after */
775 dynar = src->tasks_after;
776 length = xbt_dynar_length(dynar);
778 for (i = 0; i < length && !found; i++) {
779 xbt_dynar_get_cpy(dynar, i, &dependency);
780 if (dependency->dst == dst) {
781 xbt_dynar_remove_at(dynar, i, NULL);
787 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
788 SD_task_get_name(src), SD_task_get_name(dst),
789 SD_task_get_name(dst), SD_task_get_name(src));
791 /* remove the dependency from dst->tasks_before */
792 dynar = dst->tasks_before;
793 length = xbt_dynar_length(dynar);
796 for (i = 0; i < length && !found; i++) {
797 xbt_dynar_get_cpy(dynar, i, &dependency);
798 if (dependency->src == src) {
799 xbt_dynar_remove_at(dynar, i, NULL);
800 __SD_task_dependency_destroy(dependency);
801 dst->unsatisfied_dependencies--;
806 /* should never happen... */
808 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
809 SD_task_get_name(dst), SD_task_get_name(src),
810 SD_task_get_name(src), SD_task_get_name(dst));
812 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
814 if (dst->unsatisfied_dependencies == 0) {
815 if (__SD_task_is_scheduled(dst))
816 __SD_task_set_state(dst, SD_RUNNABLE);
818 __SD_task_set_state(dst, SD_SCHEDULABLE);
821 if (dst->is_not_ready == 0)
822 __SD_task_set_state(dst, SD_SCHEDULABLE);
824 /* __SD_print_dependencies(src);
825 __SD_print_dependencies(dst); */
829 * \brief Returns the user data associated with a dependency between two tasks
832 * \param dst a task depending on \a src
833 * \return the user data associated with this dependency (can be \c NULL)
834 * \see SD_task_dependency_add()
836 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
840 unsigned long length;
843 SD_dependency_t dependency;
845 dynar = src->tasks_after;
846 length = xbt_dynar_length(dynar);
848 for (i = 0; i < length && !found; i++) {
849 xbt_dynar_get_cpy(dynar, i, &dependency);
850 found = (dependency->dst == dst);
853 THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'",
854 SD_task_get_name(src), SD_task_get_name(dst));
855 return dependency->data;
858 /* temporary function for debugging */
859 static void __SD_print_watch_points(SD_task_t task)
861 static const int state_masks[] =
862 { SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE,
865 static const char *state_names[] =
866 { "schedulable", "scheduled", "running", "runnable", "done",
871 XBT_INFO("Task '%s' watch points (%x): ", SD_task_get_name(task),
875 for (i = 0; i < 5; i++) {
876 if (task->watch_points & state_masks[i])
877 XBT_INFO("%s ", state_names[i]);
882 * \brief Adds a watch point to a task
884 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
885 * task becomes the one given in argument. The
886 * watch point is then automatically removed.
889 * \param state the \ref e_SD_task_state_t "state" you want to watch
890 * (cannot be #SD_NOT_SCHEDULED)
891 * \see SD_task_unwatch()
893 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
895 if (state & SD_NOT_SCHEDULED)
897 "Cannot add a watch point for state SD_NOT_SCHEDULED");
899 task->watch_points = task->watch_points | state;
900 /* __SD_print_watch_points(task); */
904 * \brief Removes a watch point from a task
907 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
908 * \see SD_task_watch()
910 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
912 xbt_assert(state != SD_NOT_SCHEDULED,
913 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
915 task->watch_points = task->watch_points & ~state;
916 /* __SD_print_watch_points(task); */
920 * \brief Returns an approximative estimation of the execution time of a task.
922 * The estimation is very approximative because the value returned is the time
923 * the task would take if it was executed now and if it was the only task.
925 * \param task the task to evaluate
926 * \param workstation_nb number of workstations on which the task would be executed
927 * \param workstation_list the workstations on which the task would be executed
928 * \param computation_amount computation amount for each workstation
929 * \param communication_amount communication amount between each pair of workstations
932 double SD_task_get_execution_time(SD_task_t task,
934 const SD_workstation_t *
936 const double *computation_amount,
937 const double *communication_amount)
939 double time, max_time = 0.0;
941 xbt_assert(workstation_nb > 0, "Invalid parameter");
943 /* the task execution time is the maximum execution time of the parallel tasks */
945 for (i = 0; i < workstation_nb; i++) {
947 if (computation_amount != NULL)
949 SD_workstation_get_computation_time(workstation_list[i],
950 computation_amount[i]);
952 if (communication_amount != NULL)
953 for (j = 0; j < workstation_nb; j++) {
955 SD_route_get_communication_time(workstation_list[i],
957 communication_amount[i *
962 if (time > max_time) {
969 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
971 if (!__SD_task_is_not_scheduled(task) && !__SD_task_is_schedulable(task))
972 THROWF(arg_error, 0, "Task '%s' has already been scheduled",
973 SD_task_get_name(task));
975 /* update the task state */
976 if (task->unsatisfied_dependencies == 0)
977 __SD_task_set_state(task, SD_RUNNABLE);
979 __SD_task_set_state(task, SD_SCHEDULED);
983 * \brief Schedules a task
985 * The task state must be #SD_NOT_SCHEDULED.
986 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
987 * i.e. when its dependencies are satisfied.
989 * \param task the task you want to schedule
990 * \param workstation_count number of workstations on which the task will be executed
991 * \param workstation_list the workstations on which the task will be executed
992 * \param computation_amount computation amount for each workstation
993 * \param communication_amount communication amount between each pair of workstations
994 * \param rate task execution speed rate
995 * \see SD_task_unschedule()
997 void SD_task_schedule(SD_task_t task, int workstation_count,
998 const SD_workstation_t * workstation_list,
999 const double *computation_amount,
1000 const double *communication_amount, double rate)
1002 int communication_nb;
1003 task->workstation_nb = 0;
1005 xbt_assert(workstation_count > 0, "workstation_nb must be positive");
1007 task->workstation_nb = workstation_count;
1010 if (computation_amount) {
1011 task->computation_amount = xbt_realloc(task->computation_amount,
1012 sizeof(double) * workstation_count);
1013 memcpy(task->computation_amount, computation_amount,
1014 sizeof(double) * workstation_count);
1016 xbt_free(task->computation_amount);
1017 task->computation_amount = NULL;
1020 communication_nb = workstation_count * workstation_count;
1021 if (communication_amount) {
1022 task->communication_amount = xbt_realloc(task->communication_amount,
1023 sizeof(double) * communication_nb);
1024 memcpy(task->communication_amount, communication_amount,
1025 sizeof(double) * communication_nb);
1027 xbt_free(task->communication_amount);
1028 task->communication_amount = NULL;
1031 task->workstation_list =
1032 xbt_realloc(task->workstation_list,
1033 sizeof(SD_workstation_t) * workstation_count);
1034 memcpy(task->workstation_list, workstation_list,
1035 sizeof(SD_workstation_t) * workstation_count);
1037 SD_task_do_schedule(task);
1041 * \brief Unschedules a task
1043 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
1044 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
1045 * Call SD_task_schedule() to schedule it again.
1047 * \param task the task you want to unschedule
1048 * \see SD_task_schedule()
1050 void SD_task_unschedule(SD_task_t task)
1052 if (task->state_set != sd_global->scheduled_task_set &&
1053 task->state_set != sd_global->runnable_task_set &&
1054 task->state_set != sd_global->running_task_set &&
1055 task->state_set != sd_global->failed_task_set)
1056 THROWF(arg_error, 0,
1057 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
1058 SD_task_get_name(task));
1060 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
1061 && ((task->kind == SD_TASK_COMP_PAR_AMDAHL) ||
1062 (task->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK))) { /* Don't free scheduling data for typed tasks */
1063 __SD_task_destroy_scheduling_data(task);
1064 xbt_free(task->workstation_list);
1065 task->workstation_list=NULL;
1066 task->workstation_nb = 0;
1069 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
1070 surf_workstation_model->action_cancel(task->surf_action);
1072 if (task->unsatisfied_dependencies == 0)
1073 __SD_task_set_state(task, SD_SCHEDULABLE);
1075 __SD_task_set_state(task, SD_NOT_SCHEDULED);
1077 task->remains = task->amount;
1078 task->start_time = -1.0;
1081 /* Destroys the data memorized by SD_task_schedule.
1082 * Task state must be SD_SCHEDULED or SD_RUNNABLE.
1084 static void __SD_task_destroy_scheduling_data(SD_task_t task)
1086 if (!__SD_task_is_scheduled_or_runnable(task)
1087 && !__SD_task_is_in_fifo(task))
1088 THROWF(arg_error, 0,
1089 "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
1090 SD_task_get_name(task));
1092 xbt_free(task->computation_amount);
1093 xbt_free(task->communication_amount);
1094 task->computation_amount = task->communication_amount = NULL;
1097 /* Runs a task. This function is directly called by __SD_task_try_to_run if
1098 * the task doesn't have to wait in FIFOs. Otherwise, it is called by
1099 * __SD_task_just_done when the task gets out of its FIFOs.
1101 void __SD_task_really_run(SD_task_t task)
1105 void **surf_workstations;
1107 xbt_assert(__SD_task_is_runnable_or_in_fifo(task),
1108 "Task '%s' is not runnable or in a fifo! Task state: %d",
1109 SD_task_get_name(task), (int)SD_task_get_state(task));
1110 xbt_assert(task->workstation_list != NULL,
1111 "Task '%s': workstation_list is NULL!",
1112 SD_task_get_name(task));
1114 XBT_DEBUG("Really running task '%s'", SD_task_get_name(task));
1115 int workstation_nb = task->workstation_nb;
1117 /* set this task as current task for the workstations in sequential mode */
1118 for (i = 0; i < workstation_nb; i++) {
1119 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
1120 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1121 SD_workstation_priv(task->workstation_list[i])->current_task = task;
1122 xbt_assert(__SD_workstation_is_busy(task->workstation_list[i]),
1123 "The workstation should be busy now");
1127 XBT_DEBUG("Task '%s' set as current task for its workstations",
1128 SD_task_get_name(task));
1130 /* start the task */
1132 /* we have to create a Surf workstation array instead of the SimDag
1133 * workstation array */
1134 surf_workstations = xbt_new(void *, workstation_nb);
1136 for (i = 0; i < workstation_nb; i++)
1137 surf_workstations[i] = task->workstation_list[i];
1139 double *computation_amount = xbt_new0(double, workstation_nb);
1140 double *communication_amount = xbt_new0(double, workstation_nb * workstation_nb);
1143 if(task->computation_amount)
1144 memcpy(computation_amount, task->computation_amount, sizeof(double) *
1146 if(task->communication_amount)
1147 memcpy(communication_amount, task->communication_amount,
1148 sizeof(double) * workstation_nb * workstation_nb);
1151 surf_workstation_model->extension.
1152 workstation.execute_parallel_task(workstation_nb,
1155 communication_amount,
1158 surf_workstation_model->action_data_set(task->surf_action, task);
1160 XBT_DEBUG("surf_action = %p", task->surf_action);
1164 TRACE_surf_action(task->surf_action, task->category);
1167 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
1168 __SD_task_set_state(task, SD_RUNNING);
1169 xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
1170 SD_task_get_name(task), (int)SD_task_get_state(task));
1174 /* Tries to run a task. This function is called by SD_simulate() when a
1175 * scheduled task becomes SD_RUNNABLE (i.e., when its dependencies are
1177 * If one of the workstations where the task is scheduled on is busy (in
1178 * sequential mode), the task doesn't start.
1179 * Returns whether the task has started.
1181 int __SD_task_try_to_run(SD_task_t task)
1186 SD_workstation_t workstation;
1188 xbt_assert(__SD_task_is_runnable(task),
1189 "Task '%s' is not runnable! Task state: %d",
1190 SD_task_get_name(task), (int)SD_task_get_state(task));
1193 for (i = 0; i < task->workstation_nb; i++) {
1194 can_start = can_start &&
1195 !__SD_workstation_is_busy(task->workstation_list[i]);
1198 XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1200 if (!can_start) { /* if the task cannot start and is not in the FIFOs yet */
1201 for (i = 0; i < task->workstation_nb; i++) {
1202 workstation = task->workstation_list[i];
1203 if (SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1204 XBT_DEBUG("Pushing task '%s' in the FIFO of workstation '%s'",
1205 SD_task_get_name(task),
1206 SD_workstation_get_name(workstation));
1207 xbt_fifo_push(SD_workstation_priv(workstation)->task_fifo, task);
1210 __SD_task_set_state(task, SD_IN_FIFO);
1211 xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1212 SD_task_get_name(task), (int)SD_task_get_state(task));
1213 XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1215 __SD_task_really_run(task);
1221 /* This function is called by SD_simulate when a task is done.
1222 * It updates task->state and task->action and executes if necessary the tasks
1223 * which were waiting in FIFOs for the end of `task'
1225 void __SD_task_just_done(SD_task_t task)
1228 SD_workstation_t workstation;
1230 SD_task_t candidate;
1231 int candidate_nb = 0;
1232 int candidate_capacity = 8;
1233 SD_task_t *candidates;
1236 xbt_assert(__SD_task_is_running(task),
1237 "The task must be running! Task state: %d",
1238 (int)SD_task_get_state(task));
1239 xbt_assert(task->workstation_list != NULL,
1240 "Task '%s': workstation_list is NULL!",
1241 SD_task_get_name(task));
1244 candidates = xbt_new(SD_task_t, 8);
1246 __SD_task_set_state(task, SD_DONE);
1247 surf_workstation_model->action_unref(task->surf_action);
1248 task->surf_action = NULL;
1250 XBT_DEBUG("Looking for candidates");
1252 /* if the task was executed on sequential workstations,
1253 maybe we can execute the next task of the FIFO for each workstation */
1254 for (i = 0; i < task->workstation_nb; i++) {
1255 workstation = task->workstation_list[i];
1256 XBT_DEBUG("Workstation '%s': access_mode = %d",
1257 SD_workstation_get_name(workstation), (int)SD_workstation_priv(workstation)->access_mode);
1258 if (SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1259 xbt_assert(SD_workstation_priv(workstation)->task_fifo != NULL,
1260 "Workstation '%s' has sequential access but no FIFO!",
1261 SD_workstation_get_name(workstation));
1262 xbt_assert(SD_workstation_priv(workstation)->current_task =
1263 task, "Workstation '%s': current task should be '%s'",
1264 SD_workstation_get_name(workstation),
1265 SD_task_get_name(task));
1267 /* the task is over so we can release the workstation */
1268 SD_workstation_priv(workstation)->current_task = NULL;
1270 XBT_DEBUG("Getting candidate in FIFO");
1272 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1273 (SD_workstation_priv(workstation)->task_fifo));
1275 if (candidate != NULL) {
1276 XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1277 xbt_assert(__SD_task_is_in_fifo(candidate),
1278 "Bad state of candidate '%s': %d",
1279 SD_task_get_name(candidate),
1280 (int)SD_task_get_state(candidate));
1283 XBT_DEBUG("Candidate in fifo: %p", candidate);
1285 /* if there was a task waiting for my place */
1286 if (candidate != NULL) {
1287 /* Unfortunately, we are not sure yet that we can execute the task now,
1288 because the task can be waiting more deeply in some other
1289 workstation's FIFOs ...
1290 So we memorize all candidate tasks, and then we will check for each
1291 candidate whether or not all its workstations are available. */
1293 /* realloc if necessary */
1294 if (candidate_nb == candidate_capacity) {
1295 candidate_capacity *= 2;
1297 xbt_realloc(candidates,
1298 sizeof(SD_task_t) * candidate_capacity);
1301 /* register the candidate */
1302 candidates[candidate_nb++] = candidate;
1303 candidate->fifo_checked = 0;
1308 XBT_DEBUG("Candidates found: %d", candidate_nb);
1310 /* now we check every candidate task */
1311 for (i = 0; i < candidate_nb; i++) {
1312 candidate = candidates[i];
1314 if (candidate->fifo_checked) {
1315 continue; /* we have already evaluated that task */
1318 xbt_assert(__SD_task_is_in_fifo(candidate),
1319 "Bad state of candidate '%s': %d",
1320 SD_task_get_name(candidate), (int)SD_task_get_state(candidate));
1322 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1323 workstation = candidate->workstation_list[j];
1325 /* I can start on this workstation if the workstation is shared
1326 or if I am the first task in the FIFO */
1327 can_start = SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SHARED_ACCESS
1329 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1330 (SD_workstation_priv(workstation)->task_fifo));
1333 XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1336 /* now we are sure that I can start! */
1338 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1339 workstation = candidate->workstation_list[j];
1341 /* update the FIFO */
1342 if (SD_workstation_priv(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1343 candidate = xbt_fifo_shift(SD_workstation_priv(workstation)->task_fifo); /* the return value is stored just for debugging */
1344 XBT_DEBUG("Head of the FIFO: '%s'",
1346 NULL) ? SD_task_get_name(candidate) : "NULL");
1347 xbt_assert(candidate == candidates[i],
1348 "Error in __SD_task_just_done: bad first task in the FIFO");
1350 } /* for each workstation */
1352 /* finally execute the task */
1353 XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1354 (int)SD_task_get_state(candidate));
1355 __SD_task_really_run(candidate);
1358 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1359 SD_task_get_name(candidate), candidate->state_set,
1360 sd_global->running_task_set, __SD_task_is_running(candidate));
1361 xbt_assert(__SD_task_is_running(candidate),
1362 "Bad state of task '%s': %d",
1363 SD_task_get_name(candidate),
1364 (int)SD_task_get_state(candidate));
1365 XBT_DEBUG("Okay, the task is running.");
1368 candidate->fifo_checked = 1;
1369 } /* for each candidate */
1371 xbt_free(candidates);
1375 * Remove all dependencies associated with a task. This function is called
1376 * when the task is destroyed.
1378 static void __SD_task_remove_dependencies(SD_task_t task)
1380 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1381 because each one is stored twice */
1382 SD_dependency_t dependency;
1383 while (!xbt_dynar_is_empty(task->tasks_before)) {
1384 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1385 SD_task_dependency_remove(dependency->src, dependency->dst);
1388 while (!xbt_dynar_is_empty(task->tasks_after)) {
1389 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1390 SD_task_dependency_remove(dependency->src, dependency->dst);
1395 * \brief Returns the start time of a task
1397 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1399 * \param task: a task
1400 * \return the start time of this task
1402 double SD_task_get_start_time(SD_task_t task)
1404 if (task->surf_action)
1405 return surf_workstation_model->
1406 action_get_start_time(task->surf_action);
1408 return task->start_time;
1412 * \brief Returns the finish time of a task
1414 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1415 * If the state is not completed yet, the returned value is an
1416 * estimation of the task finish time. This value can fluctuate
1417 * until the task is completed.
1419 * \param task: a task
1420 * \return the start time of this task
1422 double SD_task_get_finish_time(SD_task_t task)
1424 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1425 return surf_workstation_model->
1426 action_get_finish_time(task->surf_action);
1428 return task->finish_time;
1433 void SD_task_distribute_comp_amdahl(SD_task_t task, int ws_count)
1436 xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1437 "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1438 "Cannot use this function.",
1439 SD_task_get_name(task));
1440 task->computation_amount = xbt_new0(double, ws_count);
1441 task->communication_amount = xbt_new0(double, ws_count * ws_count);
1442 xbt_free(task->workstation_list);
1443 task->workstation_nb = ws_count;
1444 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1446 for(i=0;i<ws_count;i++){
1447 task->computation_amount[i] =
1448 (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1453 /** @brief Auto-schedules a task.
1455 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1456 * allows to specify the task costs at creation, and decouple them from the
1457 * scheduling process where you just specify which resource should deliver the
1460 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e()
1461 * or SD_task_create_comp_seq(). Check their definitions for the exact semantic
1465 * We should create tasks kind for the following categories:
1466 * - Point to point communication (done)
1467 * - Sequential computation (done)
1468 * - group communication (redistribution, several kinds)
1469 * - parallel tasks with no internal communication (one kind per speedup
1470 * model such as Amdahl)
1471 * - idem+ internal communication. Task type not enough since we cannot store
1472 * comm cost alongside to comp one)
1474 void SD_task_schedulev(SD_task_t task, int count,
1475 const SD_workstation_t * list)
1478 SD_dependency_t dep;
1480 xbt_assert(task->kind != 0,
1481 "Task %s is not typed. Cannot automatically schedule it.",
1482 SD_task_get_name(task));
1483 switch (task->kind) {
1484 case SD_TASK_COMP_PAR_AMDAHL:
1485 SD_task_distribute_comp_amdahl(task, count);
1486 case SD_TASK_COMM_E2E:
1487 case SD_TASK_COMP_SEQ:
1488 xbt_assert(task->workstation_nb == count,
1489 "Got %d locations, but were expecting %d locations",
1490 count,task->workstation_nb);
1491 for (i = 0; i < count; i++)
1492 task->workstation_list[i] = list[i];
1493 if (SD_task_get_kind(task)== SD_TASK_COMP_SEQ && !task->computation_amount){
1494 /*This task has failed and is rescheduled. Reset the computation amount*/
1495 task->computation_amount = xbt_new0(double, 1);
1496 task->computation_amount[0] = task->remains;
1498 SD_task_do_schedule(task);
1501 xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1502 SD_task_get_name(task));
1504 if (task->kind == SD_TASK_COMM_E2E) {
1505 XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1506 SD_task_get_name(task),
1507 SD_workstation_get_name(task->workstation_list[0]),
1508 SD_workstation_get_name(task->workstation_list[1]),
1509 task->communication_amount[2]);
1513 /* Iterate over all children and parents being COMM_E2E to say where I am
1514 * located (and start them if runnable) */
1515 if (task->kind == SD_TASK_COMP_SEQ) {
1516 XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1517 SD_task_get_name(task),
1518 SD_workstation_get_name(task->workstation_list[0]),
1519 task->computation_amount[0]);
1521 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1522 SD_task_t before = dep->src;
1523 if (before->kind == SD_TASK_COMM_E2E) {
1524 before->workstation_list[1] = task->workstation_list[0];
1526 if (before->workstation_list[0] &&
1527 (__SD_task_is_schedulable(before)
1528 || __SD_task_is_not_scheduled(before))) {
1529 SD_task_do_schedule(before);
1531 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1532 SD_task_get_name(before),
1533 SD_workstation_get_name(before->workstation_list[0]),
1534 SD_workstation_get_name(before->workstation_list[1]),
1535 before->communication_amount[2]);
1539 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1540 SD_task_t after = dep->dst;
1541 if (after->kind == SD_TASK_COMM_E2E) {
1542 after->workstation_list[0] = task->workstation_list[0];
1543 if (after->workstation_list[1]
1544 && (__SD_task_is_not_scheduled(after)
1545 || __SD_task_is_schedulable(after))) {
1546 SD_task_do_schedule(after);
1548 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1549 SD_task_get_name(after),
1550 SD_workstation_get_name(after->workstation_list[0]),
1551 SD_workstation_get_name(after->workstation_list[1]),
1552 after->communication_amount[2]);
1558 /* Iterate over all children and parents being MXN_1D_BLOCK to say where I am
1559 * located (and start them if runnable) */
1560 if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1561 XBT_VERB("Schedule computation task %s on %d workstations. %.f flops"
1562 " will be distributed following Amdahl's Law",
1563 SD_task_get_name(task), task->workstation_nb,
1564 task->computation_amount[0]);
1565 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1566 SD_task_t before = dep->src;
1567 if (before->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1568 if (!before->workstation_list){
1569 XBT_VERB("Sender side of Task %s is not scheduled yet",
1570 SD_task_get_name(before));
1571 before->workstation_list = xbt_new0(SD_workstation_t, count);
1572 before->workstation_nb = count;
1573 XBT_VERB("Fill the workstation list with list of Task '%s'",
1574 SD_task_get_name(task));
1575 for (i=0;i<count;i++)
1576 before->workstation_list[i] = task->workstation_list[i];
1578 XBT_VERB("Build communication matrix for task '%s'",
1579 SD_task_get_name(before));
1581 double src_start, src_end, dst_start, dst_end;
1582 src_nb = before->workstation_nb;
1584 before->workstation_list = (SD_workstation_t*) xbt_realloc(
1585 before->workstation_list,
1586 (before->workstation_nb+count)*sizeof(s_SD_workstation_t));
1587 for(i=0; i<count; i++)
1588 before->workstation_list[before->workstation_nb+i] =
1589 task->workstation_list[i];
1591 before->workstation_nb += count;
1592 xbt_free(before->computation_amount);
1593 xbt_free(before->communication_amount);
1594 before->computation_amount = xbt_new0(double,
1595 before->workstation_nb);
1596 before->communication_amount = xbt_new0(double,
1597 before->workstation_nb*
1598 before->workstation_nb);
1600 for(i=0;i<src_nb;i++){
1601 src_start = i*before->amount/src_nb;
1602 src_end = src_start + before->amount/src_nb;
1603 for(j=0; j<dst_nb; j++){
1604 dst_start = j*before->amount/dst_nb;
1605 dst_end = dst_start + before->amount/dst_nb;
1606 XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)",
1607 SD_workstation_get_name(before->workstation_list[i]),
1608 SD_workstation_get_name(before->workstation_list[src_nb+j]),
1609 src_start, src_end, dst_start, dst_end);
1610 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1611 before->communication_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1613 before->communication_amount[i*(src_nb+dst_nb)+src_nb+j] =
1614 MIN(src_end, dst_end) - MAX(src_start, dst_start);
1616 XBT_VERB("==> %.2f",
1617 before->communication_amount[i*(src_nb+dst_nb)+src_nb+j]);
1621 if (__SD_task_is_schedulable(before) ||
1622 __SD_task_is_not_scheduled(before)) {
1623 SD_task_do_schedule(before);
1625 ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1626 SD_task_get_name(before),before->amount, src_nb, dst_nb);
1631 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1632 SD_task_t after = dep->dst;
1633 if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1634 if (!after->workstation_list){
1635 XBT_VERB("Receiver side of Task '%s' is not scheduled yet",
1636 SD_task_get_name(after));
1637 after->workstation_list = xbt_new0(SD_workstation_t, count);
1638 after->workstation_nb = count;
1639 XBT_VERB("Fill the workstation list with list of Task '%s'",
1640 SD_task_get_name(task));
1641 for (i=0;i<count;i++)
1642 after->workstation_list[i] = task->workstation_list[i];
1645 double src_start, src_end, dst_start, dst_end;
1647 dst_nb = after->workstation_nb;
1648 after->workstation_list = (SD_workstation_t*) xbt_realloc(
1649 after->workstation_list,
1650 (after->workstation_nb+count)*sizeof(s_SD_workstation_t));
1651 for(i=after->workstation_nb - 1; i>=0; i--)
1652 after->workstation_list[count+i] = after->workstation_list[i];
1653 for(i=0; i<count; i++)
1654 after->workstation_list[i] = task->workstation_list[i];
1656 after->workstation_nb += count;
1658 xbt_free(after->computation_amount);
1659 xbt_free(after->communication_amount);
1661 after->computation_amount = xbt_new0(double, after->workstation_nb);
1662 after->communication_amount = xbt_new0(double,
1663 after->workstation_nb*
1664 after->workstation_nb);
1666 for(i=0;i<src_nb;i++){
1667 src_start = i*after->amount/src_nb;
1668 src_end = src_start + after->amount/src_nb;
1669 for(j=0; j<dst_nb; j++){
1670 dst_start = j*after->amount/dst_nb;
1671 dst_end = dst_start + after->amount/dst_nb;
1672 XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)",
1673 i, j, src_start, src_end, dst_start, dst_end);
1674 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1675 after->communication_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1677 after->communication_amount[i*(src_nb+dst_nb)+src_nb+j] =
1678 MIN(src_end, dst_end)- MAX(src_start, dst_start);
1680 XBT_VERB("==> %.2f",
1681 after->communication_amount[i*(src_nb+dst_nb)+src_nb+j]);
1685 if (__SD_task_is_schedulable(after) ||
1686 __SD_task_is_not_scheduled(after)) {
1687 SD_task_do_schedule(after);
1689 ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1690 SD_task_get_name(after),after->amount, src_nb, dst_nb);
1698 /** @brief autoschedule a task on a list of workstations
1700 * This function is very similar to SD_task_schedulev(),
1701 * but takes the list of workstations to schedule onto as separate parameters.
1702 * It builds a proper vector of workstations and then call SD_task_schedulev()
1704 void SD_task_schedulel(SD_task_t task, int count, ...)
1707 SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1709 va_start(ap, count);
1710 for (i = 0; i < count; i++) {
1711 list[i] = va_arg(ap, SD_workstation_t);
1714 SD_task_schedulev(task, count, list);