1 /* Copyright (c) 2006-2016. 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. */
7 #include "src/simdag/simdag_private.h"
8 #include "simgrid/simdag.h"
9 #include "xbt/sysdep.h"
10 #include "xbt/dynar.h"
11 #include "src/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->flops_amount = NULL;
59 task->bytes_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 = (SD_task_t)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++;
93 TRACE_sd_task_create(task);
98 static XBT_INLINE SD_task_t SD_task_create_sized(const char *name,
99 void *data, double amount,
102 SD_task_t task = SD_task_create(name, data, amount);
103 task->bytes_amount = xbt_new0(double, ws_count * ws_count);
104 task->flops_amount = xbt_new0(double, ws_count);
105 task->workstation_nb = ws_count;
106 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
110 /** @brief create a end-to-end communication task that can then be auto-scheduled
112 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
113 * allows to specify the task costs at creation, and decouple them from the
114 * scheduling process where you just specify which resource should deliver the
117 * A end-to-end communication must be scheduled on 2 hosts, and the amount
118 * specified at creation is sent from hosts[0] to hosts[1].
120 SD_task_t SD_task_create_comm_e2e(const char *name, void *data,
123 SD_task_t res = SD_task_create_sized(name, data, amount, 2);
124 res->bytes_amount[2] = amount;
125 res->kind = SD_TASK_COMM_E2E;
127 TRACE_category("COMM_E2E");
128 TRACE_sd_set_task_category(res, "COMM_E2E");
133 /** @brief create a sequential computation task that can then be auto-scheduled
135 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
136 * allows to specify the task costs at creation, and decouple them from the
137 * scheduling process where you just specify which resource should deliver the
140 * A sequential computation must be scheduled on 1 host, and the amount
141 * specified at creation to be run on hosts[0].
143 * \param name the name of the task (can be \c NULL)
144 * \param data the user data you want to associate with the task (can be \c NULL)
145 * \param flops_amount amount of compute work to be done by the task
146 * \return the new SD_TASK_COMP_SEQ typed task
148 SD_task_t SD_task_create_comp_seq(const char *name, void *data,
151 SD_task_t res = SD_task_create_sized(name, data, flops_amount, 1);
152 res->flops_amount[0] = flops_amount;
153 res->kind = SD_TASK_COMP_SEQ;
155 TRACE_category("COMP_SEQ");
156 TRACE_sd_set_task_category(res, "COMP_SEQ");
161 /** @brief create a parallel computation task that can then be auto-scheduled
163 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
164 * allows to specify the task costs at creation, and decouple them from the
165 * scheduling process where you just specify which resource should deliver the
168 * A parallel computation can be scheduled on any number of host.
169 * The underlying speedup model is Amdahl's law.
170 * To be auto-scheduled, \see SD_task_distribute_comp_amdahl has to be called
172 * \param name the name of the task (can be \c NULL)
173 * \param data the user data you want to associate with the task (can be \c NULL)
174 * \param flops_amount amount of compute work to be done by the task
175 * \param alpha purely serial fraction of the work to be done (in [0.;1.[)
176 * \return the new task
178 SD_task_t SD_task_create_comp_par_amdahl(const char *name, void *data,
179 double flops_amount, double alpha)
181 xbt_assert(alpha < 1. && alpha >= 0.,
182 "Invalid parameter: alpha must be in [0.;1.[");
184 SD_task_t res = SD_task_create(name, data, flops_amount);
186 res->kind = SD_TASK_COMP_PAR_AMDAHL;
188 TRACE_category("COMP_PAR_AMDAHL");
189 TRACE_sd_set_task_category(res, "COMP_PAR_AMDAHL");
194 /** @brief create a complex data redistribution task that can then be
197 * Auto-scheduling mean that the task can be used with SD_task_schedulev().
198 * This allows to specify the task costs at creation, and decouple them from
199 * the scheduling process where you just specify which resource should
202 * A data redistribution can be scheduled on any number of host.
203 * The assumed distribution is a 1D block distribution. Each host owns the same
204 * share of the \see amount.
205 * To be auto-scheduled, \see SD_task_distribute_comm_mxn_1d_block has to be
207 * \param name the name of the task (can be \c NULL)
208 * \param data the user data you want to associate with the task (can be
210 * \param amount amount of data to redistribute by the task
211 * \return the new task
213 SD_task_t SD_task_create_comm_par_mxn_1d_block(const char *name, void *data,
216 SD_task_t res = SD_task_create(name, data, amount);
217 res->workstation_list=NULL;
218 res->kind = SD_TASK_COMM_PAR_MXN_1D_BLOCK;
220 TRACE_category("COMM_PAR_MXN_1D_BLOCK");
221 TRACE_sd_set_task_category(res, "COMM_PAR_MXN_1D_BLOCK");
227 * \brief Destroys a task.
229 * The user data (if any) should have been destroyed first.
231 * \param task the task you want to destroy
232 * \see SD_task_create()
234 void SD_task_destroy(SD_task_t task)
236 XBT_DEBUG("Destroying task %s...", SD_task_get_name(task));
238 __SD_task_remove_dependencies(task);
239 /* if the task was scheduled or runnable we have to free the scheduling parameters */
240 if (__SD_task_is_scheduled_or_runnable(task))
241 __SD_task_destroy_scheduling_data(task);
242 if (task->state_set != NULL) /* would be null if just created */
243 xbt_swag_remove(task, task->state_set);
245 xbt_swag_remove(task, sd_global->return_set);
247 xbt_free(task->name);
249 if (task->surf_action != NULL)
250 surf_action_unref(task->surf_action);
252 xbt_free(task->workstation_list);
253 xbt_free(task->bytes_amount);
254 xbt_free(task->flops_amount);
256 TRACE_sd_task_destroy(task);
258 xbt_mallocator_release(sd_global->task_mallocator,task);
259 sd_global->task_number--;
261 XBT_DEBUG("Task destroyed.");
265 * \brief Returns the user data of a task
268 * \return the user data associated with this task (can be \c NULL)
269 * \see SD_task_set_data()
271 void *SD_task_get_data(SD_task_t task)
277 * \brief Sets the user data of a task
279 * The new data can be \c NULL. The old data should have been freed first
280 * if it was not \c NULL.
283 * \param data the new data you want to associate with this task
284 * \see SD_task_get_data()
286 void SD_task_set_data(SD_task_t task, void *data)
292 * \brief Sets the rate of a task
294 * This will change the network bandwidth a task can use. This rate
295 * cannot be dynamically changed. Once the task has started, this call
296 * is ineffective. This rate depends on both the nominal bandwidth on
297 * the route onto which the task is scheduled (\see
298 * SD_task_get_current_bandwidth) and the amount of data to transfer.
300 * To divide the nominal bandwidth by 2, the rate then has to be :
301 * rate = bandwidth/(2*amount)
303 * \param task a \see SD_TASK_COMM_E2E task (end-to-end communication)
304 * \param rate the new rate you want to associate with this task.
306 void SD_task_set_rate(SD_task_t task, double rate)
308 xbt_assert(task->kind == SD_TASK_COMM_E2E,
309 "The rate can be modified for end-to-end communications only.");
310 if(task->start_time<0) {
313 XBT_WARN("Task %p has started. Changing rate is ineffective.", task);
318 * \brief Returns the state of a task
321 * \return the current \ref e_SD_task_state_t "state" of this task:
322 * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
323 * \see e_SD_task_state_t
325 e_SD_task_state_t SD_task_get_state(SD_task_t task)
330 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
332 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
334 xbt_swag_remove(task, task->state_set);
336 case SD_NOT_SCHEDULED:
337 task->state_set = sd_global->not_scheduled_task_set;
340 task->state_set = sd_global->schedulable_task_set;
343 task->state_set = sd_global->scheduled_task_set;
346 task->state_set = sd_global->runnable_task_set;
349 task->state_set = sd_global->in_fifo_task_set;
352 task->state_set = sd_global->running_task_set;
353 task->start_time = surf_action_get_start_time(task->surf_action);
356 task->state_set = sd_global->done_task_set;
357 task->finish_time = surf_action_get_finish_time(task->surf_action);
360 jedule_log_sd_event(task);
364 task->state_set = sd_global->failed_task_set;
367 xbt_die( "Invalid state");
369 xbt_swag_insert(task, task->state_set);
370 task->state = new_state;
372 if (task->watch_points & new_state) {
373 XBT_VERB("Watch point reached with task '%s'!", SD_task_get_name(task));
374 sd_global->watch_point_reached = 1;
375 SD_task_unwatch(task, new_state); /* remove the watch point */
380 * \brief Returns the name of a task
383 * \return the name of this task (can be \c NULL)
385 const char *SD_task_get_name(SD_task_t task)
390 /** @brief Allows to change the name of a task */
391 void SD_task_set_name(SD_task_t task, const char *name)
393 xbt_free(task->name);
394 task->name = xbt_strdup(name);
397 /** @brief Returns the dynar of the parents of a task
400 * \return a newly allocated dynar comprising the parents of this task
403 xbt_dynar_t SD_task_get_parents(SD_task_t task)
409 parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
410 xbt_dynar_foreach(task->tasks_before, i, dep) {
411 xbt_dynar_push(parents, &(dep->src));
416 /** @brief Returns the dynar of the parents of a task
419 * \return a newly allocated dynar comprising the parents of this task
421 xbt_dynar_t SD_task_get_children(SD_task_t task)
424 xbt_dynar_t children;
427 children = xbt_dynar_new(sizeof(SD_task_t), NULL);
428 xbt_dynar_foreach(task->tasks_after, i, dep) {
429 xbt_dynar_push(children, &(dep->dst));
435 * \brief Returns the amount of workstations involved in a task
437 * Only call this on already scheduled tasks!
440 int SD_task_get_workstation_count(SD_task_t task)
442 return task->workstation_nb;
446 * \brief Returns the list of workstations involved in a task
448 * Only call this on already scheduled tasks!
451 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
453 return task->workstation_list;
457 * \brief Returns the total amount of work contained in a task
460 * \return the total amount of work (computation or data transfer) for this task
461 * \see SD_task_get_remaining_amount()
463 double SD_task_get_amount(SD_task_t task)
469 * \brief Sets the total amount of work of a task
470 * For sequential typed tasks (COMP_SEQ and COMM_E2E), it also sets the
471 * appropriate values in the flops_amount and bytes_amount arrays
472 * respectively. Nothing more than modifying task->amount is done for paralle
473 * typed tasks (COMP_PAR_AMDAHL and COMM_PAR_MXN_1D_BLOCK) as the distribution
474 * of the amount of work is done at scheduling time.
477 * \param amount the new amount of work to execute
479 void SD_task_set_amount(SD_task_t task, double amount)
481 task->amount = amount;
482 if (task->kind == SD_TASK_COMP_SEQ)
483 task->flops_amount[0] = amount;
484 if (task->kind == SD_TASK_COMM_E2E)
485 task->bytes_amount[2] = amount;
489 * \brief Returns the alpha parameter of a SD_TASK_COMP_PAR_AMDAHL task
491 * \param task a parallel task assuming Amdahl's law as speedup model
492 * \return the alpha parameter (serial part of a task in percent) for this task
494 double SD_task_get_alpha(SD_task_t task)
496 xbt_assert(SD_task_get_kind(task) == SD_TASK_COMP_PAR_AMDAHL,
497 "Alpha parameter is not defined for this kink of task");
503 * \brief Returns the remaining amount work to do till the completion of a task
506 * \return the remaining amount of work (computation or data transfer) of this task
507 * \see SD_task_get_amount()
509 double SD_task_get_remaining_amount(SD_task_t task)
511 if (task->surf_action)
512 return surf_action_get_remains(task->surf_action);
514 return task->remains;
517 int SD_task_get_kind(SD_task_t task)
522 /** @brief Displays debugging informations about a task */
523 void SD_task_dump(SD_task_t task)
525 unsigned int counter;
526 SD_dependency_t dependency;
529 XBT_INFO("Displaying task %s", SD_task_get_name(task));
530 statename = bprintf("%s %s %s %s %s %s %s %s",
531 (task->state == SD_NOT_SCHEDULED ? "not scheduled" :
533 (task->state == SD_SCHEDULABLE ? "schedulable" : ""),
534 (task->state == SD_SCHEDULED ? "scheduled" : ""),
535 (task->state == SD_RUNNABLE ? "runnable" :
537 (task->state == SD_IN_FIFO ? "in fifo" : ""),
538 (task->state == SD_RUNNING ? "running" : ""),
539 (task->state == SD_DONE ? "done" : ""),
540 (task->state == SD_FAILED ? "failed" : ""));
541 XBT_INFO(" - state: %s", statename);
544 if (task->kind != 0) {
545 switch (task->kind) {
546 case SD_TASK_COMM_E2E:
547 XBT_INFO(" - kind: end-to-end communication");
549 case SD_TASK_COMP_SEQ:
550 XBT_INFO(" - kind: sequential computation");
552 case SD_TASK_COMP_PAR_AMDAHL:
553 XBT_INFO(" - kind: parallel computation following Amdahl's law");
555 case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
556 XBT_INFO(" - kind: MxN data redistribution assuming 1D block distribution");
559 XBT_INFO(" - (unknown kind %d)", task->kind);
564 XBT_INFO(" - tracing category: %s", task->category);
566 XBT_INFO(" - amount: %.0f", SD_task_get_amount(task));
567 if (task->kind == SD_TASK_COMP_PAR_AMDAHL)
568 XBT_INFO(" - alpha: %.2f", task->alpha);
569 XBT_INFO(" - Dependencies to satisfy: %d", task->unsatisfied_dependencies);
570 if (!xbt_dynar_is_empty(task->tasks_before)) {
571 XBT_INFO(" - pre-dependencies:");
572 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
573 XBT_INFO(" %s", SD_task_get_name(dependency->src));
576 if (!xbt_dynar_is_empty(task->tasks_after)) {
577 XBT_INFO(" - post-dependencies:");
578 xbt_dynar_foreach(task->tasks_after, counter, dependency) {
579 XBT_INFO(" %s", SD_task_get_name(dependency->dst));
584 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
585 void SD_task_dotty(SD_task_t task, void *out)
587 unsigned int counter;
588 SD_dependency_t dependency;
589 FILE *fout = (FILE*)out;
590 fprintf(fout, " T%p [label=\"%.20s\"", task, task->name);
591 switch (task->kind) {
592 case SD_TASK_COMM_E2E:
593 case SD_TASK_COMM_PAR_MXN_1D_BLOCK:
594 fprintf(fout, ", shape=box");
596 case SD_TASK_COMP_SEQ:
597 case SD_TASK_COMP_PAR_AMDAHL:
598 fprintf(fout, ", shape=circle");
601 xbt_die("Unknown task type!");
603 fprintf(fout, "];\n");
604 xbt_dynar_foreach(task->tasks_before, counter, dependency) {
605 fprintf(fout, " T%p -> T%p;\n", dependency->src, dependency->dst);
609 /* Destroys a dependency between two tasks.
611 static void __SD_task_dependency_destroy(void *dependency)
613 xbt_free(((SD_dependency_t)dependency)->name);
614 xbt_free(dependency);
618 * \brief Adds a dependency between two tasks
620 * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
621 * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
623 * \param name the name of the new dependency (can be \c NULL)
624 * \param data the user data you want to associate with this dependency (can be \c NULL)
625 * \param src the task which must be executed first
626 * \param dst the task you want to make depend on \a src
627 * \see SD_task_dependency_remove()
629 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
633 unsigned long length;
636 SD_dependency_t dependency;
638 dynar = src->tasks_after;
639 length = xbt_dynar_length(dynar);
643 "Cannot add a dependency between task '%s' and itself",
644 SD_task_get_name(src));
646 if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_schedulable(src)
647 && !__SD_task_is_scheduled_or_runnable(src) && !__SD_task_is_running(src))
649 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE"
651 SD_task_get_name(src));
653 if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_schedulable(dst)
654 && !__SD_task_is_scheduled_or_runnable(dst))
656 "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
657 SD_task_get_name(dst));
659 XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s",
660 SD_task_get_name(src), SD_task_get_name(dst));
661 for (i = 0; i < length && !found; i++) {
662 xbt_dynar_get_cpy(dynar, i, &dependency);
663 found = (dependency->dst == dst);
664 XBT_DEBUG("Dependency %lu: dependency->dst = %s", i,
665 SD_task_get_name(dependency->dst));
670 "A dependency already exists between task '%s' and task '%s'",
671 SD_task_get_name(src), SD_task_get_name(dst));
673 dependency = xbt_new(s_SD_dependency_t, 1);
675 dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
676 dependency->data = data;
677 dependency->src = src;
678 dependency->dst = dst;
680 /* src must be executed before dst */
681 xbt_dynar_push(src->tasks_after, &dependency);
682 xbt_dynar_push(dst->tasks_before, &dependency);
684 dst->unsatisfied_dependencies++;
687 /* if the task was runnable, then dst->tasks_before is not empty anymore,
688 so we must go back to state SD_SCHEDULED */
689 if (__SD_task_is_runnable(dst)) {
691 ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
692 SD_task_get_name(dst));
693 __SD_task_set_state(dst, SD_SCHEDULED);
697 * \brief Returns the name given as input when dependency has been created..
700 * \param dst a task depending on \a src
703 const char *SD_task_dependency_get_name(SD_task_t src, SD_task_t dst){
705 SD_dependency_t dependency;
707 xbt_dynar_foreach(src->tasks_after, i, dependency){
708 if (dependency->dst == dst)
709 return dependency->name;
715 * \brief Indicates whether there is a dependency between two tasks.
718 * \param dst a task depending on \a src
720 * If src is NULL, checks whether dst has any pre-dependency.
721 * If dst is NULL, checks whether src has any post-dependency.
723 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
725 unsigned int counter;
726 SD_dependency_t dependency;
728 xbt_assert(src != NULL
730 "Invalid parameter: both src and dst are NULL");
734 xbt_dynar_foreach(src->tasks_after, counter, dependency) {
735 if (dependency->dst == dst)
739 return xbt_dynar_length(src->tasks_after);
742 return xbt_dynar_length(dst->tasks_before);
748 * \brief Remove a dependency between two tasks
751 * \param dst a task depending on \a src
752 * \see SD_task_dependency_add()
754 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
758 unsigned long length;
761 SD_dependency_t dependency;
763 /* remove the dependency from src->tasks_after */
764 dynar = src->tasks_after;
765 length = xbt_dynar_length(dynar);
767 for (i = 0; i < length && !found; i++) {
768 xbt_dynar_get_cpy(dynar, i, &dependency);
769 if (dependency->dst == dst) {
770 xbt_dynar_remove_at(dynar, i, NULL);
776 "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
777 SD_task_get_name(src), SD_task_get_name(dst),
778 SD_task_get_name(dst), SD_task_get_name(src));
780 /* remove the dependency from dst->tasks_before */
781 dynar = dst->tasks_before;
782 length = xbt_dynar_length(dynar);
785 for (i = 0; i < length && !found; i++) {
786 xbt_dynar_get_cpy(dynar, i, &dependency);
787 if (dependency->src == src) {
788 xbt_dynar_remove_at(dynar, i, NULL);
789 __SD_task_dependency_destroy(dependency);
790 dst->unsatisfied_dependencies--;
795 /* should never happen... */
797 "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
798 SD_task_get_name(dst), SD_task_get_name(src),
799 SD_task_get_name(src), SD_task_get_name(dst));
801 /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
803 if (dst->unsatisfied_dependencies == 0) {
804 if (__SD_task_is_scheduled(dst))
805 __SD_task_set_state(dst, SD_RUNNABLE);
807 __SD_task_set_state(dst, SD_SCHEDULABLE);
810 if (dst->is_not_ready == 0)
811 __SD_task_set_state(dst, SD_SCHEDULABLE);
813 /* __SD_print_dependencies(src);
814 __SD_print_dependencies(dst); */
818 * \brief Returns the user data associated with a dependency between two tasks
821 * \param dst a task depending on \a src
822 * \return the user data associated with this dependency (can be \c NULL)
823 * \see SD_task_dependency_add()
825 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
829 unsigned long length;
832 SD_dependency_t dependency;
834 dynar = src->tasks_after;
835 length = xbt_dynar_length(dynar);
837 for (i = 0; i < length && !found; i++) {
838 xbt_dynar_get_cpy(dynar, i, &dependency);
839 found = (dependency->dst == dst);
842 THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'",
843 SD_task_get_name(src), SD_task_get_name(dst));
844 return dependency->data;
847 /* temporary function for debugging */
848 static void __SD_print_watch_points(SD_task_t task)
850 static const int state_masks[] =
851 { SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE,
854 static const char *state_names[] =
855 { "schedulable", "scheduled", "running", "runnable", "done",
860 XBT_INFO("Task '%s' watch points (%x): ", SD_task_get_name(task),
864 for (i = 0; i < 5; i++) {
865 if (task->watch_points & state_masks[i])
866 XBT_INFO("%s ", state_names[i]);
871 * \brief Adds a watch point to a task
873 * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
874 * task becomes the one given in argument. The
875 * watch point is then automatically removed.
878 * \param state the \ref e_SD_task_state_t "state" you want to watch
879 * (cannot be #SD_NOT_SCHEDULED)
880 * \see SD_task_unwatch()
882 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
884 if (state & SD_NOT_SCHEDULED)
886 "Cannot add a watch point for state SD_NOT_SCHEDULED");
888 task->watch_points = task->watch_points | state;
889 /* __SD_print_watch_points(task); */
893 * \brief Removes a watch point from a task
896 * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
897 * \see SD_task_watch()
899 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
901 xbt_assert(state != SD_NOT_SCHEDULED,
902 "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
904 task->watch_points = task->watch_points & ~state;
905 /* __SD_print_watch_points(task); */
909 * \brief Returns an approximative estimation of the execution time of a task.
911 * The estimation is very approximative because the value returned is the time
912 * the task would take if it was executed now and if it was the only task.
914 * \param task the task to evaluate
915 * \param workstation_nb number of workstations on which the task would be executed
916 * \param workstation_list the workstations on which the task would be executed
917 * \param flops_amount computation amount for each workstation
918 * \param bytes_amount communication amount between each pair of workstations
921 double SD_task_get_execution_time(SD_task_t task,
923 const SD_workstation_t *
925 const double *flops_amount,
926 const double *bytes_amount)
928 double time, max_time = 0.0;
930 xbt_assert(workstation_nb > 0, "Invalid parameter");
932 /* the task execution time is the maximum execution time of the parallel tasks */
934 for (i = 0; i < workstation_nb; i++) {
936 if (flops_amount != NULL)
938 SD_workstation_get_computation_time(workstation_list[i],
941 if (bytes_amount != NULL)
942 for (j = 0; j < workstation_nb; j++) {
944 SD_route_get_communication_time(workstation_list[i],
951 if (time > max_time) {
958 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
960 if (!__SD_task_is_not_scheduled(task) && !__SD_task_is_schedulable(task))
961 THROWF(arg_error, 0, "Task '%s' has already been scheduled",
962 SD_task_get_name(task));
964 /* update the task state */
965 if (task->unsatisfied_dependencies == 0)
966 __SD_task_set_state(task, SD_RUNNABLE);
968 __SD_task_set_state(task, SD_SCHEDULED);
972 * \brief Schedules a task
974 * The task state must be #SD_NOT_SCHEDULED.
975 * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
976 * i.e. when its dependencies are satisfied.
978 * \param task the task you want to schedule
979 * \param workstation_count number of workstations on which the task will be executed
980 * \param workstation_list the workstations on which the task will be executed
981 * \param flops_amount computation amount for each workstation
982 * \param bytes_amount communication amount between each pair of workstations
983 * \param rate task execution speed rate
984 * \see SD_task_unschedule()
986 void SD_task_schedule(SD_task_t task, int workstation_count,
987 const SD_workstation_t * workstation_list,
988 const double *flops_amount,
989 const double *bytes_amount, double rate)
991 int communication_nb;
992 task->workstation_nb = 0;
994 xbt_assert(workstation_count > 0, "workstation_nb must be positive");
996 task->workstation_nb = workstation_count;
1000 task->flops_amount = (double*)xbt_realloc(task->flops_amount,
1001 sizeof(double) * workstation_count);
1002 memcpy(task->flops_amount, flops_amount,
1003 sizeof(double) * workstation_count);
1005 xbt_free(task->flops_amount);
1006 task->flops_amount = NULL;
1009 communication_nb = workstation_count * workstation_count;
1011 task->bytes_amount = (double*)xbt_realloc(task->bytes_amount,
1012 sizeof(double) * communication_nb);
1013 memcpy(task->bytes_amount, bytes_amount,
1014 sizeof(double) * communication_nb);
1016 xbt_free(task->bytes_amount);
1017 task->bytes_amount = NULL;
1020 task->workstation_list = (SD_workstation_t*)
1021 xbt_realloc(task->workstation_list,
1022 sizeof(SD_workstation_t) * workstation_count);
1023 memcpy(task->workstation_list, workstation_list,
1024 sizeof(SD_workstation_t) * workstation_count);
1026 SD_task_do_schedule(task);
1030 * \brief Unschedules a task
1032 * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
1033 * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
1034 * Call SD_task_schedule() to schedule it again.
1036 * \param task the task you want to unschedule
1037 * \see SD_task_schedule()
1039 void SD_task_unschedule(SD_task_t task)
1041 if (task->state_set != sd_global->scheduled_task_set &&
1042 task->state_set != sd_global->runnable_task_set &&
1043 task->state_set != sd_global->running_task_set &&
1044 task->state_set != sd_global->failed_task_set)
1045 THROWF(arg_error, 0,
1046 "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
1047 SD_task_get_name(task));
1049 if (__SD_task_is_scheduled_or_runnable(task) /* if the task is scheduled or runnable */
1050 && ((task->kind == SD_TASK_COMP_PAR_AMDAHL) ||
1051 (task->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK))) { /* Don't free scheduling data for typed tasks */
1052 __SD_task_destroy_scheduling_data(task);
1053 xbt_free(task->workstation_list);
1054 task->workstation_list=NULL;
1055 task->workstation_nb = 0;
1058 if (__SD_task_is_running(task)) /* the task should become SD_FAILED */
1059 surf_action_cancel(task->surf_action);
1061 if (task->unsatisfied_dependencies == 0)
1062 __SD_task_set_state(task, SD_SCHEDULABLE);
1064 __SD_task_set_state(task, SD_NOT_SCHEDULED);
1066 task->remains = task->amount;
1067 task->start_time = -1.0;
1070 /* Destroys the data memorized by SD_task_schedule.
1071 * Task state must be SD_SCHEDULED or SD_RUNNABLE.
1073 static void __SD_task_destroy_scheduling_data(SD_task_t task)
1075 if (!__SD_task_is_scheduled_or_runnable(task)
1076 && !__SD_task_is_in_fifo(task))
1077 THROWF(arg_error, 0,
1078 "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
1079 SD_task_get_name(task));
1081 xbt_free(task->flops_amount);
1082 xbt_free(task->bytes_amount);
1083 task->flops_amount = task->bytes_amount = NULL;
1086 /* Runs a task. This function is directly called by __SD_task_try_to_run if
1087 * the task doesn't have to wait in FIFOs. Otherwise, it is called by
1088 * __SD_task_just_done when the task gets out of its FIFOs.
1090 void __SD_task_really_run(SD_task_t task)
1096 xbt_assert(__SD_task_is_runnable_or_in_fifo(task),
1097 "Task '%s' is not runnable or in a fifo! Task state: %d",
1098 SD_task_get_name(task), (int)SD_task_get_state(task));
1099 xbt_assert(task->workstation_list != NULL,
1100 "Task '%s': workstation_list is NULL!",
1101 SD_task_get_name(task));
1103 XBT_DEBUG("Really running task '%s'", SD_task_get_name(task));
1104 int host_nb = task->workstation_nb;
1106 /* set this task as current task for the workstations in sequential mode */
1107 for (i = 0; i < host_nb; i++) {
1108 if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
1109 SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1110 sg_host_sd(task->workstation_list[i])->current_task = task;
1111 xbt_assert(__SD_workstation_is_busy(task->workstation_list[i]),
1112 "The workstation should be busy now");
1116 XBT_DEBUG("Task '%s' set as current task for its workstations",
1117 SD_task_get_name(task));
1119 /* start the task */
1121 /* Copy the elements of the task into the action */
1122 hosts = xbt_new(sg_host_t, host_nb);
1124 for (i = 0; i < host_nb; i++)
1125 hosts[i] = task->workstation_list[i];
1127 double *flops_amount = xbt_new0(double, host_nb);
1128 double *bytes_amount = xbt_new0(double, host_nb * host_nb);
1131 if(task->flops_amount)
1132 memcpy(flops_amount, task->flops_amount, sizeof(double) *
1134 if(task->bytes_amount)
1135 memcpy(bytes_amount, task->bytes_amount,
1136 sizeof(double) * host_nb * host_nb);
1138 task->surf_action = surf_host_model_execute_parallel_task((surf_host_model_t)surf_host_model,
1145 surf_action_set_data(task->surf_action, task);
1147 XBT_DEBUG("surf_action = %p", task->surf_action);
1150 TRACE_surf_action(task->surf_action, task->category);
1152 __SD_task_destroy_scheduling_data(task); /* now the scheduling data are not useful anymore */
1153 __SD_task_set_state(task, SD_RUNNING);
1154 xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
1155 SD_task_get_name(task), (int)SD_task_get_state(task));
1159 /* Tries to run a task. This function is called by SD_simulate() when a
1160 * scheduled task becomes SD_RUNNABLE (i.e., when its dependencies are
1162 * If one of the workstations where the task is scheduled on is busy (in
1163 * sequential mode), the task doesn't start.
1164 * Returns whether the task has started.
1166 int __SD_task_try_to_run(SD_task_t task)
1171 SD_workstation_t workstation;
1173 xbt_assert(__SD_task_is_runnable(task),
1174 "Task '%s' is not runnable! Task state: %d",
1175 SD_task_get_name(task), (int)SD_task_get_state(task));
1178 for (i = 0; i < task->workstation_nb; i++) {
1179 can_start = can_start &&
1180 !__SD_workstation_is_busy(task->workstation_list[i]);
1183 XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1185 if (!can_start) { /* if the task cannot start and is not in the FIFOs yet */
1186 for (i = 0; i < task->workstation_nb; i++) {
1187 workstation = task->workstation_list[i];
1188 if (sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1189 XBT_DEBUG("Pushing task '%s' in the FIFO of workstation '%s'",
1190 SD_task_get_name(task),
1191 SD_workstation_get_name(workstation));
1192 xbt_fifo_push(sg_host_sd(workstation)->task_fifo, task);
1195 __SD_task_set_state(task, SD_IN_FIFO);
1196 xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1197 SD_task_get_name(task), (int)SD_task_get_state(task));
1198 XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1200 __SD_task_really_run(task);
1206 /* This function is called by SD_simulate when a task is done.
1207 * It updates task->state and task->action and executes if necessary the tasks
1208 * which were waiting in FIFOs for the end of `task'
1210 void __SD_task_just_done(SD_task_t task)
1213 SD_workstation_t workstation;
1215 SD_task_t candidate;
1216 int candidate_nb = 0;
1217 int candidate_capacity = 8;
1218 SD_task_t *candidates;
1221 xbt_assert(__SD_task_is_running(task),
1222 "The task must be running! Task state: %d",
1223 (int)SD_task_get_state(task));
1224 xbt_assert(task->workstation_list != NULL,
1225 "Task '%s': workstation_list is NULL!",
1226 SD_task_get_name(task));
1229 candidates = xbt_new(SD_task_t, 8);
1231 __SD_task_set_state(task, SD_DONE);
1232 surf_action_unref(task->surf_action);
1233 task->surf_action = NULL;
1235 XBT_DEBUG("Looking for candidates");
1237 /* if the task was executed on sequential workstations,
1238 maybe we can execute the next task of the FIFO for each workstation */
1239 for (i = 0; i < task->workstation_nb; i++) {
1240 workstation = task->workstation_list[i];
1241 XBT_DEBUG("Workstation '%s': access_mode = %d",
1242 SD_workstation_get_name(workstation), (int)sg_host_sd(workstation)->access_mode);
1243 if (sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1244 xbt_assert(sg_host_sd(workstation)->task_fifo != NULL,
1245 "Workstation '%s' has sequential access but no FIFO!",
1246 SD_workstation_get_name(workstation));
1247 xbt_assert(sg_host_sd(workstation)->current_task =
1248 task, "Workstation '%s': current task should be '%s'",
1249 SD_workstation_get_name(workstation),
1250 SD_task_get_name(task));
1252 /* the task is over so we can release the workstation */
1253 sg_host_sd(workstation)->current_task = NULL;
1255 XBT_DEBUG("Getting candidate in FIFO");
1256 candidate = (SD_task_t)
1257 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1258 (sg_host_sd(workstation)->task_fifo));
1260 if (candidate != NULL) {
1261 XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1262 xbt_assert(__SD_task_is_in_fifo(candidate),
1263 "Bad state of candidate '%s': %d",
1264 SD_task_get_name(candidate),
1265 (int)SD_task_get_state(candidate));
1268 XBT_DEBUG("Candidate in fifo: %p", candidate);
1270 /* if there was a task waiting for my place */
1271 if (candidate != NULL) {
1272 /* Unfortunately, we are not sure yet that we can execute the task now,
1273 because the task can be waiting more deeply in some other
1274 workstation's FIFOs ...
1275 So we memorize all candidate tasks, and then we will check for each
1276 candidate whether or not all its workstations are available. */
1278 /* realloc if necessary */
1279 if (candidate_nb == candidate_capacity) {
1280 candidate_capacity *= 2;
1281 candidates = (SD_task_t*)
1282 xbt_realloc(candidates,
1283 sizeof(SD_task_t) * candidate_capacity);
1286 /* register the candidate */
1287 candidates[candidate_nb++] = candidate;
1288 candidate->fifo_checked = 0;
1293 XBT_DEBUG("Candidates found: %d", candidate_nb);
1295 /* now we check every candidate task */
1296 for (i = 0; i < candidate_nb; i++) {
1297 candidate = candidates[i];
1299 if (candidate->fifo_checked) {
1300 continue; /* we have already evaluated that task */
1303 xbt_assert(__SD_task_is_in_fifo(candidate),
1304 "Bad state of candidate '%s': %d",
1305 SD_task_get_name(candidate), (int)SD_task_get_state(candidate));
1307 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1308 workstation = candidate->workstation_list[j];
1310 /* I can start on this workstation if the workstation is shared
1311 or if I am the first task in the FIFO */
1312 can_start = sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SHARED_ACCESS
1314 xbt_fifo_get_item_content(xbt_fifo_get_first_item
1315 (sg_host_sd(workstation)->task_fifo));
1318 XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1321 /* now we are sure that I can start! */
1323 for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1324 workstation = candidate->workstation_list[j];
1326 /* update the FIFO */
1327 if (sg_host_sd(workstation)->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1328 candidate = (SD_task_t)xbt_fifo_shift(sg_host_sd(workstation)->task_fifo); /* the return value is stored just for debugging */
1329 XBT_DEBUG("Head of the FIFO: '%s'",
1331 NULL) ? SD_task_get_name(candidate) : "NULL");
1332 xbt_assert(candidate == candidates[i],
1333 "Error in __SD_task_just_done: bad first task in the FIFO");
1335 } /* for each workstation */
1337 /* finally execute the task */
1338 XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1339 (int)SD_task_get_state(candidate));
1340 __SD_task_really_run(candidate);
1343 ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1344 SD_task_get_name(candidate), candidate->state_set,
1345 sd_global->running_task_set, __SD_task_is_running(candidate));
1346 xbt_assert(__SD_task_is_running(candidate),
1347 "Bad state of task '%s': %d",
1348 SD_task_get_name(candidate),
1349 (int)SD_task_get_state(candidate));
1350 XBT_DEBUG("Okay, the task is running.");
1353 candidate->fifo_checked = 1;
1354 } /* for each candidate */
1356 xbt_free(candidates);
1360 * Remove all dependencies associated with a task. This function is called
1361 * when the task is destroyed.
1363 static void __SD_task_remove_dependencies(SD_task_t task)
1365 /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1366 because each one is stored twice */
1367 SD_dependency_t dependency;
1368 while (!xbt_dynar_is_empty(task->tasks_before)) {
1369 xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1370 SD_task_dependency_remove(dependency->src, dependency->dst);
1373 while (!xbt_dynar_is_empty(task->tasks_after)) {
1374 xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1375 SD_task_dependency_remove(dependency->src, dependency->dst);
1380 * \brief Returns the start time of a task
1382 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1384 * \param task: a task
1385 * \return the start time of this task
1387 double SD_task_get_start_time(SD_task_t task)
1389 if (task->surf_action)
1390 return surf_action_get_start_time(task->surf_action);
1392 return task->start_time;
1396 * \brief Returns the finish time of a task
1398 * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1399 * If the state is not completed yet, the returned value is an
1400 * estimation of the task finish time. This value can fluctuate
1401 * until the task is completed.
1403 * \param task: a task
1404 * \return the start time of this task
1406 double SD_task_get_finish_time(SD_task_t task)
1408 if (task->surf_action) /* should never happen as actions are destroyed right after their completion */
1409 return surf_action_get_finish_time(task->surf_action);
1411 return task->finish_time;
1416 void SD_task_distribute_comp_amdahl(SD_task_t task, int ws_count)
1419 xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1420 "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1421 "Cannot use this function.",
1422 SD_task_get_name(task));
1423 task->flops_amount = xbt_new0(double, ws_count);
1424 task->bytes_amount = xbt_new0(double, ws_count * ws_count);
1425 xbt_free(task->workstation_list);
1426 task->workstation_nb = ws_count;
1427 task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1429 for(i=0;i<ws_count;i++){
1430 task->flops_amount[i] =
1431 (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1436 /** @brief Auto-schedules a task.
1438 * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1439 * allows to specify the task costs at creation, and decouple them from the
1440 * scheduling process where you just specify which resource should deliver the
1443 * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e()
1444 * or SD_task_create_comp_seq(). Check their definitions for the exact semantic
1448 * We should create tasks kind for the following categories:
1449 * - Point to point communication (done)
1450 * - Sequential computation (done)
1451 * - group communication (redistribution, several kinds)
1452 * - parallel tasks with no internal communication (one kind per speedup
1453 * model such as Amdahl)
1454 * - idem+ internal communication. Task type not enough since we cannot store
1455 * comm cost alongside to comp one)
1457 void SD_task_schedulev(SD_task_t task, int count,
1458 const SD_workstation_t * list)
1461 SD_dependency_t dep;
1463 xbt_assert(task->kind != 0,
1464 "Task %s is not typed. Cannot automatically schedule it.",
1465 SD_task_get_name(task));
1466 switch (task->kind) {
1467 case SD_TASK_COMP_PAR_AMDAHL:
1468 SD_task_distribute_comp_amdahl(task, count);
1469 case SD_TASK_COMM_E2E:
1470 case SD_TASK_COMP_SEQ:
1471 xbt_assert(task->workstation_nb == count,
1472 "Got %d locations, but were expecting %d locations",
1473 count,task->workstation_nb);
1474 for (i = 0; i < count; i++)
1475 task->workstation_list[i] = list[i];
1476 if (SD_task_get_kind(task)== SD_TASK_COMP_SEQ && !task->flops_amount){
1477 /*This task has failed and is rescheduled. Reset the flops_amount*/
1478 task->flops_amount = xbt_new0(double, 1);
1479 task->flops_amount[0] = task->remains;
1481 SD_task_do_schedule(task);
1484 xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1485 SD_task_get_name(task));
1487 if (task->kind == SD_TASK_COMM_E2E) {
1488 XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1489 SD_task_get_name(task),
1490 SD_workstation_get_name(task->workstation_list[0]),
1491 SD_workstation_get_name(task->workstation_list[1]),
1492 task->bytes_amount[2]);
1496 /* Iterate over all children and parents being COMM_E2E to say where I am
1497 * located (and start them if runnable) */
1498 if (task->kind == SD_TASK_COMP_SEQ) {
1499 XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1500 SD_task_get_name(task),
1501 SD_workstation_get_name(task->workstation_list[0]),
1502 task->flops_amount[0]);
1504 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1505 SD_task_t before = dep->src;
1506 if (before->kind == SD_TASK_COMM_E2E) {
1507 before->workstation_list[1] = task->workstation_list[0];
1509 if (before->workstation_list[0] &&
1510 (__SD_task_is_schedulable(before)
1511 || __SD_task_is_not_scheduled(before))) {
1512 SD_task_do_schedule(before);
1514 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1515 SD_task_get_name(before),
1516 SD_workstation_get_name(before->workstation_list[0]),
1517 SD_workstation_get_name(before->workstation_list[1]),
1518 before->bytes_amount[2]);
1522 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1523 SD_task_t after = dep->dst;
1524 if (after->kind == SD_TASK_COMM_E2E) {
1525 after->workstation_list[0] = task->workstation_list[0];
1526 if (after->workstation_list[1]
1527 && (__SD_task_is_not_scheduled(after)
1528 || __SD_task_is_schedulable(after))) {
1529 SD_task_do_schedule(after);
1531 ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1532 SD_task_get_name(after),
1533 SD_workstation_get_name(after->workstation_list[0]),
1534 SD_workstation_get_name(after->workstation_list[1]),
1535 after->bytes_amount[2]);
1541 /* Iterate over all children and parents being MXN_1D_BLOCK to say where I am
1542 * located (and start them if runnable) */
1543 if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1544 XBT_VERB("Schedule computation task %s on %d workstations. %.f flops"
1545 " will be distributed following Amdahl's Law",
1546 SD_task_get_name(task), task->workstation_nb,
1547 task->flops_amount[0]);
1548 xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1549 SD_task_t before = dep->src;
1550 if (before->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1551 if (!before->workstation_list){
1552 XBT_VERB("Sender side of Task %s is not scheduled yet",
1553 SD_task_get_name(before));
1554 before->workstation_list = xbt_new0(SD_workstation_t, count);
1555 before->workstation_nb = count;
1556 XBT_VERB("Fill the workstation list with list of Task '%s'",
1557 SD_task_get_name(task));
1558 for (i=0;i<count;i++)
1559 before->workstation_list[i] = task->workstation_list[i];
1561 XBT_VERB("Build communication matrix for task '%s'",
1562 SD_task_get_name(before));
1564 double src_start, src_end, dst_start, dst_end;
1565 src_nb = before->workstation_nb;
1567 before->workstation_list = (SD_workstation_t*) xbt_realloc(
1568 before->workstation_list,
1569 (before->workstation_nb+count)*sizeof(s_SD_workstation_t));
1570 for(i=0; i<count; i++)
1571 before->workstation_list[before->workstation_nb+i] =
1572 task->workstation_list[i];
1574 before->workstation_nb += count;
1575 xbt_free(before->flops_amount);
1576 xbt_free(before->bytes_amount);
1577 before->flops_amount = xbt_new0(double,
1578 before->workstation_nb);
1579 before->bytes_amount = xbt_new0(double,
1580 before->workstation_nb*
1581 before->workstation_nb);
1583 for(i=0;i<src_nb;i++){
1584 src_start = i*before->amount/src_nb;
1585 src_end = src_start + before->amount/src_nb;
1586 for(j=0; j<dst_nb; j++){
1587 dst_start = j*before->amount/dst_nb;
1588 dst_end = dst_start + before->amount/dst_nb;
1589 XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)",
1590 SD_workstation_get_name(before->workstation_list[i]),
1591 SD_workstation_get_name(before->workstation_list[src_nb+j]),
1592 src_start, src_end, dst_start, dst_end);
1593 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1594 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1596 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1597 MIN(src_end, dst_end) - MAX(src_start, dst_start);
1599 XBT_VERB("==> %.2f",
1600 before->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1604 if (__SD_task_is_schedulable(before) ||
1605 __SD_task_is_not_scheduled(before)) {
1606 SD_task_do_schedule(before);
1608 ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1609 SD_task_get_name(before),before->amount, src_nb, dst_nb);
1614 xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1615 SD_task_t after = dep->dst;
1616 if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1617 if (!after->workstation_list){
1618 XBT_VERB("Receiver side of Task '%s' is not scheduled yet",
1619 SD_task_get_name(after));
1620 after->workstation_list = xbt_new0(SD_workstation_t, count);
1621 after->workstation_nb = count;
1622 XBT_VERB("Fill the workstation list with list of Task '%s'",
1623 SD_task_get_name(task));
1624 for (i=0;i<count;i++)
1625 after->workstation_list[i] = task->workstation_list[i];
1628 double src_start, src_end, dst_start, dst_end;
1630 dst_nb = after->workstation_nb;
1631 after->workstation_list = (SD_workstation_t*) xbt_realloc(
1632 after->workstation_list,
1633 (after->workstation_nb+count)*sizeof(s_SD_workstation_t));
1634 for(i=after->workstation_nb - 1; i>=0; i--)
1635 after->workstation_list[count+i] = after->workstation_list[i];
1636 for(i=0; i<count; i++)
1637 after->workstation_list[i] = task->workstation_list[i];
1639 after->workstation_nb += count;
1641 xbt_free(after->flops_amount);
1642 xbt_free(after->bytes_amount);
1644 after->flops_amount = xbt_new0(double, after->workstation_nb);
1645 after->bytes_amount = xbt_new0(double,
1646 after->workstation_nb*
1647 after->workstation_nb);
1649 for(i=0;i<src_nb;i++){
1650 src_start = i*after->amount/src_nb;
1651 src_end = src_start + after->amount/src_nb;
1652 for(j=0; j<dst_nb; j++){
1653 dst_start = j*after->amount/dst_nb;
1654 dst_end = dst_start + after->amount/dst_nb;
1655 XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)",
1656 i, j, src_start, src_end, dst_start, dst_end);
1657 if ((src_end <= dst_start) || (dst_end <= src_start)) {
1658 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1660 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j] =
1661 MIN(src_end, dst_end)- MAX(src_start, dst_start);
1663 XBT_VERB("==> %.2f",
1664 after->bytes_amount[i*(src_nb+dst_nb)+src_nb+j]);
1668 if (__SD_task_is_schedulable(after) ||
1669 __SD_task_is_not_scheduled(after)) {
1670 SD_task_do_schedule(after);
1672 ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1673 SD_task_get_name(after),after->amount, src_nb, dst_nb);
1681 /** @brief autoschedule a task on a list of workstations
1683 * This function is very similar to SD_task_schedulev(),
1684 * but takes the list of workstations to schedule onto as separate parameters.
1685 * It builds a proper vector of workstations and then call SD_task_schedulev()
1687 void SD_task_schedulel(SD_task_t task, int count, ...)
1690 SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1692 va_start(ap, count);
1693 for (i = 0; i < count; i++) {
1694 list[i] = va_arg(ap, SD_workstation_t);
1697 SD_task_schedulev(task, count, list);