Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Merge branch 'master' of git+ssh://scm.gforge.inria.fr//gitroot//simgrid/simgrid
[simgrid.git] / src / simdag / sd_task.c
1 /* Copyright (c) 2006, 2007, 2008, 2009, 2010, 2011. The SimGrid Team.
2  * All rights reserved.                                                     */
3
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. */
6
7 #include "private.h"
8 #include "simdag/simdag.h"
9 #include "xbt/sysdep.h"
10 #include "xbt/dynar.h"
11 #include "instr/instr_private.h"
12
13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
14                                 "Logging specific to SimDag (task)");
15
16 static void __SD_task_remove_dependencies(SD_task_t task);
17 static void __SD_task_destroy_scheduling_data(SD_task_t task);
18
19 void* SD_task_new_f(void)
20 {
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);
24
25   return task;
26 }
27
28 void SD_task_recycle_f(void *t)
29 {
30   SD_task_t task = (SD_task_t) t;
31
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;
41
42   task->marked = 0;
43
44   task->start_time = -1.0;
45   task->finish_time = -1.0;
46   task->surf_action = NULL;
47   task->watch_points = 0;
48
49   /* dependencies */
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;
54
55   /* scheduling parameters */
56   task->workstation_nb = 0;
57   task->workstation_list = NULL;
58   task->computation_amount = NULL;
59   task->communication_amount = NULL;
60   task->rate = -1;
61 }
62
63 void SD_task_free_f(void *t)
64 {
65   SD_task_t task = (SD_task_t)t;
66
67   xbt_dynar_free(&task->tasks_before);
68   xbt_dynar_free(&task->tasks_after);
69   xbt_free(task);
70 }
71
72 /**
73  * \brief Creates a new task.
74  *
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()
80  */
81 SD_task_t SD_task_create(const char *name, void *data, double amount)
82 {
83   SD_task_t task = xbt_mallocator_get(sd_global->task_mallocator);
84
85   /* general information */
86   task->data = data;            /* user data */
87   task->name = xbt_strdup(name);
88   task->amount = amount;
89   task->remains = amount;
90
91   sd_global->task_number++;
92
93 #ifdef HAVE_TRACING
94   task->category = NULL;
95 #endif
96
97   return task;
98 }
99
100 static XBT_INLINE SD_task_t SD_task_create_sized(const char *name,
101                                                  void *data, double amount,
102                                                  int ws_count)
103 {
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);
109   return task;
110 }
111
112 /** @brief create a end-to-end communication task that can then be auto-scheduled
113  *
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
117  * mandatory power.
118  *
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].
121  */
122 SD_task_t SD_task_create_comm_e2e(const char *name, void *data,
123                                   double amount)
124 {
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;
128   return res;
129 }
130
131 /** @brief create a sequential computation task that can then be auto-scheduled
132  *
133  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
134  * allows to specify the task costs at creation, and decouple them from the
135  * scheduling process where you just specify which resource should deliver the
136  * mandatory power.
137  *
138  * A sequential computation must be scheduled on 1 host, and the amount
139  * specified at creation to be run on hosts[0].
140  *
141  * \param name the name of the task (can be \c NULL)
142  * \param data the user data you want to associate with the task (can be \c NULL)
143  * \param amount amount of compute work to be done by the task
144  * \return the new SD_TASK_COMP_SEQ typed task
145  */
146 SD_task_t SD_task_create_comp_seq(const char *name, void *data,
147                                   double amount)
148 {
149   SD_task_t res = SD_task_create_sized(name, data, amount, 1);
150   res->computation_amount[0] = amount;
151   res->kind = SD_TASK_COMP_SEQ;
152   return res;
153 }
154
155 /** @brief create a parallel computation task that can then be auto-scheduled
156  *
157  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
158  * allows to specify the task costs at creation, and decouple them from the
159  * scheduling process where you just specify which resource should deliver the
160  * mandatory power.
161  *
162  * A parallel computation can be scheduled on any number of host.
163  * The underlying speedup model is Amdahl's law. 
164  * To be auto-scheduled, \see SD_task_distribute_comp_amdhal has to be called 
165  * first.
166  * \param name the name of the task (can be \c NULL)
167  * \param data the user data you want to associate with the task (can be \c NULL)
168  * \param amount amount of compute work to be done by the task
169  * \param alpha purely serial fraction of the work to be done (in [0.;1.[)
170  * \return the new task
171  */
172 SD_task_t SD_task_create_comp_par_amdahl(const char *name, void *data,
173                                   double amount, double alpha)
174 {
175   xbt_assert(alpha < 1. && alpha >= 0.,
176               "Invalid parameter: alpha must be in [0.;1.[");
177   
178   SD_task_t res = SD_task_create(name, data, amount);
179   res->alpha = alpha;
180   res->kind = SD_TASK_COMP_PAR_AMDAHL;
181   return res;
182 }
183
184 /** @brief create a complex data redistribution task that can then be 
185  * auto-scheduled
186  *
187  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). 
188  * This allows to specify the task costs at creation, and decouple them from 
189  * the scheduling process where you just specify which resource should 
190  * communicate. 
191  *
192  * A data redistribution can be scheduled on any number of host.
193  * The assumed distribution is a 1D block distribution. Each host owns the same
194  * share of the \see amount. 
195  * To be auto-scheduled, \see SD_task_distribute_comm_mxn_1d_block has to be 
196  * called first.
197  * \param name the name of the task (can be \c NULL)
198  * \param data the user data you want to associate with the task (can be
199  * \c NULL)
200  * \param amount amount of data to redistribute by the task
201  * \return the new task
202  */
203 SD_task_t SD_task_create_comm_par_mxn_1d_block(const char *name, void *data,
204                                                                                            double amount)
205 {
206   SD_task_t res = SD_task_create(name, data, amount);
207   res->workstation_list=NULL;
208   res->kind = SD_TASK_COMM_PAR_MXN_1D_BLOCK;
209   return res;
210 }
211
212 /**
213  * \brief Destroys a task.
214  *
215  * The user data (if any) should have been destroyed first.
216  *
217  * \param task the task you want to destroy
218  * \see SD_task_create()
219  */
220 void SD_task_destroy(SD_task_t task)
221 {
222   XBT_DEBUG("Destroying task %s...", SD_task_get_name(task));
223
224   __SD_task_remove_dependencies(task);
225   /* if the task was scheduled or runnable we have to free the scheduling parameters */
226   if (__SD_task_is_scheduled_or_runnable(task))
227     __SD_task_destroy_scheduling_data(task);
228   if (task->state_set != NULL) /* would be null if just created */
229     xbt_swag_remove(task, task->state_set);
230
231   xbt_swag_remove(task, sd_global->return_set);
232
233   xbt_free(task->name);
234
235   if (task->surf_action != NULL)
236     surf_workstation_model->action_unref(task->surf_action);
237
238   xbt_free(task->workstation_list);
239   xbt_free(task->communication_amount);
240   xbt_free(task->computation_amount);
241
242   xbt_mallocator_release(sd_global->task_mallocator,task);
243   sd_global->task_number--;
244
245 #ifdef HAVE_TRACING
246   if (task->category) xbt_free(task->category);
247 #endif
248
249   XBT_DEBUG("Task destroyed.");
250 }
251
252 /**
253  * \brief Returns the user data of a task
254  *
255  * \param task a task
256  * \return the user data associated with this task (can be \c NULL)
257  * \see SD_task_set_data()
258  */
259 void *SD_task_get_data(SD_task_t task)
260 {
261   return task->data;
262 }
263
264 /**
265  * \brief Sets the user data of a task
266  *
267  * The new data can be \c NULL. The old data should have been freed first
268  * if it was not \c NULL.
269  *
270  * \param task a task
271  * \param data the new data you want to associate with this task
272  * \see SD_task_get_data()
273  */
274 void SD_task_set_data(SD_task_t task, void *data)
275 {
276   task->data = data;
277 }
278
279 /**
280  * \brief Sets the rate of a task
281  *
282  * This will change the percentage of the available power or network bandwidth
283  * a task can use.
284  *
285  * \param task a task
286  * \param rate the new rate you want to associate with this task
287  */
288 void SD_task_set_rate(SD_task_t task, double rate)
289 {
290   task->rate = rate;
291 }
292
293 /**
294  * \brief Returns the state of a task
295  *
296  * \param task a task
297  * \return the current \ref e_SD_task_state_t "state" of this task:
298  * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING, #SD_DONE or #SD_FAILED
299  * \see e_SD_task_state_t
300  */
301 e_SD_task_state_t SD_task_get_state(SD_task_t task)
302 {
303   return task->state;
304 }
305
306 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
307  */
308 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
309 {
310   xbt_swag_remove(task, task->state_set);
311   switch (new_state) {
312   case SD_NOT_SCHEDULED:
313     task->state_set = sd_global->not_scheduled_task_set;
314     break;
315   case SD_SCHEDULABLE:
316     task->state_set = sd_global->schedulable_task_set;
317     break;
318   case SD_SCHEDULED:
319     task->state_set = sd_global->scheduled_task_set;
320     break;
321   case SD_RUNNABLE:
322     task->state_set = sd_global->runnable_task_set;
323     break;
324   case SD_IN_FIFO:
325     task->state_set = sd_global->in_fifo_task_set;
326     break;
327   case SD_RUNNING:
328     task->state_set = sd_global->running_task_set;
329     task->start_time =
330         surf_workstation_model->action_get_start_time(task->surf_action);
331     break;
332   case SD_DONE:
333     task->state_set = sd_global->done_task_set;
334     task->finish_time =
335         surf_workstation_model->action_get_finish_time(task->surf_action);
336     task->remains = 0;
337 #ifdef HAVE_JEDULE
338     jedule_log_sd_event(task);
339 #endif
340     break;
341   case SD_FAILED:
342     task->state_set = sd_global->failed_task_set;
343     break;
344   default:
345     xbt_die( "Invalid state");
346   }
347   xbt_swag_insert(task, task->state_set);
348   task->state = new_state;
349
350   if (task->watch_points & new_state) {
351     XBT_VERB("Watch point reached with task '%s'!", SD_task_get_name(task));
352     sd_global->watch_point_reached = 1;
353     SD_task_unwatch(task, new_state);   /* remove the watch point */
354   }
355 }
356
357 /**
358  * \brief Returns the name of a task
359  *
360  * \param task a task
361  * \return the name of this task (can be \c NULL)
362  */
363 const char *SD_task_get_name(SD_task_t task)
364 {
365   return task->name;
366 }
367
368 /** @brief Allows to change the name of a task */
369 void SD_task_set_name(SD_task_t task, const char *name)
370 {
371   xbt_free(task->name);
372   task->name = xbt_strdup(name);
373 }
374
375 /** @brief Returns the dynar of the parents of a task
376  *
377  * \param task a task
378  * \return a newly allocated dynar comprising the parents of this task
379  */
380
381 xbt_dynar_t SD_task_get_parents(SD_task_t task)
382 {
383   unsigned int i;
384   xbt_dynar_t parents;
385   SD_dependency_t dep;
386
387   parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
388   xbt_dynar_foreach(task->tasks_before, i, dep) {
389     xbt_dynar_push(parents, &(dep->src));
390   }
391   return parents;
392 }
393
394 /** @brief Returns the dynar of the parents of a task
395  *
396  * \param task a task
397  * \return a newly allocated dynar comprising the parents of this task
398  */
399 xbt_dynar_t SD_task_get_children(SD_task_t task)
400 {
401   unsigned int i;
402   xbt_dynar_t children;
403   SD_dependency_t dep;
404
405   children = xbt_dynar_new(sizeof(SD_task_t), NULL);
406   xbt_dynar_foreach(task->tasks_after, i, dep) {
407     xbt_dynar_push(children, &(dep->dst));
408   }
409   return children;
410 }
411
412 /**
413  * \brief Returns the amount of workstations involved in a task
414  *
415  * Only call this on already scheduled tasks!
416  * \param task a task
417  */
418 int SD_task_get_workstation_count(SD_task_t task)
419 {
420   return task->workstation_nb;
421 }
422
423 /**
424  * \brief Returns the list of workstations involved in a task
425  *
426  * Only call this on already scheduled tasks!
427  * \param task a task
428  */
429 SD_workstation_t *SD_task_get_workstation_list(SD_task_t task)
430 {
431   return task->workstation_list;
432 }
433
434 /**
435  * \brief Returns the total amount of work contained in a task
436  *
437  * \param task a task
438  * \return the total amount of work (computation or data transfer) for this task
439  * \see SD_task_get_remaining_amount()
440  */
441 double SD_task_get_amount(SD_task_t task)
442 {
443   return task->amount;
444 }
445
446 /**
447  * \brief Returns the remaining amount work to do till the completion of a task
448  *
449  * \param task a task
450  * \return the remaining amount of work (computation or data transfer) of this task
451  * \see SD_task_get_amount()
452  */
453 double SD_task_get_remaining_amount(SD_task_t task)
454 {
455   if (task->surf_action)
456     return surf_workstation_model->get_remains(task->surf_action);
457   else
458     return task->remains;
459 }
460
461 int SD_task_get_kind(SD_task_t task)
462 {
463   return task->kind;
464 }
465
466 /** @brief Displays debugging informations about a task */
467 void SD_task_dump(SD_task_t task)
468 {
469   unsigned int counter;
470   SD_dependency_t dependency;
471   char *statename;
472
473   XBT_INFO("Displaying task %s", SD_task_get_name(task));
474   statename = bprintf("%s %s %s %s %s %s %s %s",
475                       (task->state & SD_NOT_SCHEDULED ? "not scheduled" :
476                        ""),
477                       (task->state & SD_SCHEDULABLE ? "schedulable" : ""),
478                       (task->state & SD_SCHEDULED ? "scheduled" : ""),
479                       (task->state & SD_RUNNABLE ? "runnable" :
480                        "not runnable"),
481                       (task->state & SD_IN_FIFO ? "in fifo" : ""),
482                       (task->state & SD_RUNNING ? "running" : ""),
483                       (task->state & SD_DONE ? "done" : ""),
484                       (task->state & SD_FAILED ? "failed" : ""));
485   XBT_INFO("  - state: %s", statename);
486   free(statename);
487
488   if (task->kind != 0) {
489     switch (task->kind) {
490     case SD_TASK_COMM_E2E:
491       XBT_INFO("  - kind: end-to-end communication");
492       break;
493     case SD_TASK_COMP_SEQ:
494       XBT_INFO("  - kind: sequential computation");
495       break;
496     case SD_TASK_COMP_PAR_AMDAHL:
497       XBT_INFO("  - kind: parallel computation following Amdahl's law");
498       break;
499     default:
500       XBT_INFO("  - (unknown kind %d)", task->kind);
501     }
502   }
503   XBT_INFO("  - amount: %.0f", SD_task_get_amount(task));
504   XBT_INFO("  - Dependencies to satisfy: %u", task->unsatisfied_dependencies);
505   if (!xbt_dynar_is_empty(task->tasks_before)) {
506     XBT_INFO("  - pre-dependencies:");
507     xbt_dynar_foreach(task->tasks_before, counter, dependency) {
508       XBT_INFO("    %s", SD_task_get_name(dependency->src));
509     }
510   }
511   if (!xbt_dynar_is_empty(task->tasks_after)) {
512     XBT_INFO("  - post-dependencies:");
513     xbt_dynar_foreach(task->tasks_after, counter, dependency) {
514       XBT_INFO("    %s", SD_task_get_name(dependency->dst));
515     }
516   }
517 }
518
519 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
520 void SD_task_dotty(SD_task_t task, void *out)
521 {
522   unsigned int counter;
523   SD_dependency_t dependency;
524   fprintf(out, "  T%p [label=\"%.20s\"", task, task->name);
525   switch (task->kind) {
526   case SD_TASK_COMM_E2E:
527     fprintf(out, ", shape=box");
528     break;
529   case SD_TASK_COMP_SEQ:
530     fprintf(out, ", shape=circle");
531     break;
532   default:
533     xbt_die("Unknown task type!");
534   }
535   fprintf(out, "];\n");
536   xbt_dynar_foreach(task->tasks_before, counter, dependency) {
537     fprintf(out, " T%p -> T%p;\n", dependency->src, dependency->dst);
538   }
539 }
540
541 /* Destroys a dependency between two tasks.
542  */
543 static void __SD_task_dependency_destroy(void *dependency)
544 {
545   xbt_free(((SD_dependency_t)dependency)->name);
546   xbt_free(dependency);
547 }
548
549 /**
550  * \brief Adds a dependency between two tasks
551  *
552  * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
553  * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_RUNNABLE.
554  *
555  * \param name the name of the new dependency (can be \c NULL)
556  * \param data the user data you want to associate with this dependency (can be \c NULL)
557  * \param src the task which must be executed first
558  * \param dst the task you want to make depend on \a src
559  * \see SD_task_dependency_remove()
560  */
561 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
562                             SD_task_t dst)
563 {
564   xbt_dynar_t dynar;
565   int length;
566   int found = 0;
567   int i;
568   SD_dependency_t dependency;
569
570   dynar = src->tasks_after;
571   length = xbt_dynar_length(dynar);
572
573   if (src == dst)
574     THROWF(arg_error, 0,
575            "Cannot add a dependency between task '%s' and itself",
576            SD_task_get_name(src));
577
578   if (!__SD_task_is_not_scheduled(src) && !__SD_task_is_schedulable(src)
579       && !__SD_task_is_scheduled_or_runnable(src) && !__SD_task_is_running(src))
580     THROWF(arg_error, 0,
581            "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE"
582      " or SD_RUNNING",
583            SD_task_get_name(src));
584
585   if (!__SD_task_is_not_scheduled(dst) && !__SD_task_is_schedulable(dst)
586       && !__SD_task_is_scheduled_or_runnable(dst))
587     THROWF(arg_error, 0,
588            "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULABLE, SD_SCHEDULED or SD_RUNNABLE",
589            SD_task_get_name(dst));
590
591   XBT_DEBUG("SD_task_dependency_add: src = %s, dst = %s",
592          SD_task_get_name(src), SD_task_get_name(dst));
593   for (i = 0; i < length && !found; i++) {
594     xbt_dynar_get_cpy(dynar, i, &dependency);
595     found = (dependency->dst == dst);
596     XBT_DEBUG("Dependency %d: dependency->dst = %s", i,
597            SD_task_get_name(dependency->dst));
598   }
599
600   if (found)
601     THROWF(arg_error, 0,
602            "A dependency already exists between task '%s' and task '%s'",
603            SD_task_get_name(src), SD_task_get_name(dst));
604
605   dependency = xbt_new(s_SD_dependency_t, 1);
606
607   dependency->name = xbt_strdup(name);  /* xbt_strdup is cleaver enough to deal with NULL args itself */
608   dependency->data = data;
609   dependency->src = src;
610   dependency->dst = dst;
611
612   /* src must be executed before dst */
613   xbt_dynar_push(src->tasks_after, &dependency);
614   xbt_dynar_push(dst->tasks_before, &dependency);
615
616   dst->unsatisfied_dependencies++;
617   dst->is_not_ready++;
618
619   /* if the task was runnable, then dst->tasks_before is not empty anymore,
620      so we must go back to state SD_SCHEDULED */
621   if (__SD_task_is_runnable(dst)) {
622     XBT_DEBUG
623         ("SD_task_dependency_add: %s was runnable and becomes scheduled!",
624          SD_task_get_name(dst));
625     __SD_task_set_state(dst, SD_SCHEDULED);
626   }
627
628   /*  __SD_print_dependencies(src);
629      __SD_print_dependencies(dst); */
630 }
631
632 /**
633  * \brief Indicates whether there is a dependency between two tasks.
634  *
635  * \param src a task
636  * \param dst a task depending on \a src
637  *
638  * If src is NULL, checks whether dst has any pre-dependency.
639  * If dst is NULL, checks whether src has any post-dependency.
640  */
641 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
642 {
643   unsigned int counter;
644   SD_dependency_t dependency;
645
646   xbt_assert(src != NULL
647               || dst != NULL,
648               "Invalid parameter: both src and dst are NULL");
649
650   if (src) {
651     if (dst) {
652       xbt_dynar_foreach(src->tasks_after, counter, dependency) {
653         if (dependency->dst == dst)
654           return 1;
655       }
656     } else {
657       return xbt_dynar_length(src->tasks_after);
658     }
659   } else {
660     return xbt_dynar_length(dst->tasks_before);
661   }
662   return 0;
663 }
664
665 /**
666  * \brief Remove a dependency between two tasks
667  *
668  * \param src a task
669  * \param dst a task depending on \a src
670  * \see SD_task_dependency_add()
671  */
672 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
673 {
674
675   xbt_dynar_t dynar;
676   int length;
677   int found = 0;
678   int i;
679   SD_dependency_t dependency;
680
681   /* remove the dependency from src->tasks_after */
682   dynar = src->tasks_after;
683   length = xbt_dynar_length(dynar);
684
685   for (i = 0; i < length && !found; i++) {
686     xbt_dynar_get_cpy(dynar, i, &dependency);
687     if (dependency->dst == dst) {
688       xbt_dynar_remove_at(dynar, i, NULL);
689       found = 1;
690     }
691   }
692   if (!found)
693     THROWF(arg_error, 0,
694            "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
695            SD_task_get_name(src), SD_task_get_name(dst),
696            SD_task_get_name(dst), SD_task_get_name(src));
697
698   /* remove the dependency from dst->tasks_before */
699   dynar = dst->tasks_before;
700   length = xbt_dynar_length(dynar);
701   found = 0;
702
703   for (i = 0; i < length && !found; i++) {
704     xbt_dynar_get_cpy(dynar, i, &dependency);
705     if (dependency->src == src) {
706       xbt_dynar_remove_at(dynar, i, NULL);
707       __SD_task_dependency_destroy(dependency);
708       dst->unsatisfied_dependencies--;
709       dst->is_not_ready--;
710       found = 1;
711     }
712   }
713   /* should never happen... */
714   xbt_assert(found,
715               "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
716               SD_task_get_name(dst), SD_task_get_name(src),
717               SD_task_get_name(src), SD_task_get_name(dst));
718
719   /* if the task was scheduled and dst->tasks_before is empty now, we can make it runnable */
720
721   if (dst->unsatisfied_dependencies == 0) {
722     if (__SD_task_is_scheduled(dst))
723       __SD_task_set_state(dst, SD_RUNNABLE);
724     else
725       __SD_task_set_state(dst, SD_SCHEDULABLE);
726   }
727
728   if (dst->is_not_ready == 0)
729     __SD_task_set_state(dst, SD_SCHEDULABLE);
730
731   /*  __SD_print_dependencies(src);
732      __SD_print_dependencies(dst); */
733 }
734
735 /**
736  * \brief Returns the user data associated with a dependency between two tasks
737  *
738  * \param src a task
739  * \param dst a task depending on \a src
740  * \return the user data associated with this dependency (can be \c NULL)
741  * \see SD_task_dependency_add()
742  */
743 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
744 {
745
746   xbt_dynar_t dynar;
747   int length;
748   int found = 0;
749   int i;
750   SD_dependency_t dependency;
751
752   dynar = src->tasks_after;
753   length = xbt_dynar_length(dynar);
754
755   for (i = 0; i < length && !found; i++) {
756     xbt_dynar_get_cpy(dynar, i, &dependency);
757     found = (dependency->dst == dst);
758   }
759   if (!found)
760     THROWF(arg_error, 0, "No dependency found between task '%s' and '%s'",
761            SD_task_get_name(src), SD_task_get_name(dst));
762   return dependency->data;
763 }
764
765 /* temporary function for debugging */
766 static void __SD_print_watch_points(SD_task_t task)
767 {
768   static const int state_masks[] =
769       { SD_SCHEDULABLE, SD_SCHEDULED, SD_RUNNING, SD_RUNNABLE, SD_DONE,
770     SD_FAILED
771   };
772   static const char *state_names[] =
773       { "schedulable", "scheduled", "running", "runnable", "done",
774     "failed"
775   };
776   int i;
777
778   XBT_INFO("Task '%s' watch points (%x): ", SD_task_get_name(task),
779         task->watch_points);
780
781
782   for (i = 0; i < 5; i++) {
783     if (task->watch_points & state_masks[i])
784       XBT_INFO("%s ", state_names[i]);
785   }
786 }
787
788 /**
789  * \brief Adds a watch point to a task
790  *
791  * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
792  * task becomes the one given in argument. The
793  * watch point is then automatically removed.
794  *
795  * \param task a task
796  * \param state the \ref e_SD_task_state_t "state" you want to watch
797  * (cannot be #SD_NOT_SCHEDULED)
798  * \see SD_task_unwatch()
799  */
800 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
801 {
802   if (state & SD_NOT_SCHEDULED)
803     THROWF(arg_error, 0,
804            "Cannot add a watch point for state SD_NOT_SCHEDULED");
805
806   task->watch_points = task->watch_points | state;
807   /*  __SD_print_watch_points(task); */
808 }
809
810 /**
811  * \brief Removes a watch point from a task
812  *
813  * \param task a task
814  * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
815  * \see SD_task_watch()
816  */
817 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
818 {
819   xbt_assert(state != SD_NOT_SCHEDULED,
820               "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
821
822   task->watch_points = task->watch_points & ~state;
823   /*  __SD_print_watch_points(task); */
824 }
825
826 /**
827  * \brief Returns an approximative estimation of the execution time of a task.
828  *
829  * The estimation is very approximative because the value returned is the time
830  * the task would take if it was executed now and if it was the only task.
831  *
832  * \param task the task to evaluate
833  * \param workstation_nb number of workstations on which the task would be executed
834  * \param workstation_list the workstations on which the task would be executed
835  * \param computation_amount computation amount for each workstation
836  * \param communication_amount communication amount between each pair of workstations
837  * \see SD_schedule()
838  */
839 double SD_task_get_execution_time(SD_task_t task,
840                                   int workstation_nb,
841                                   const SD_workstation_t *
842                                   workstation_list,
843                                   const double *computation_amount,
844                                   const double *communication_amount)
845 {
846   double time, max_time = 0.0;
847   int i, j;
848   xbt_assert(workstation_nb > 0, "Invalid parameter");
849
850   /* the task execution time is the maximum execution time of the parallel tasks */
851
852   for (i = 0; i < workstation_nb; i++) {
853     time = 0.0;
854     if (computation_amount != NULL)
855       time =
856           SD_workstation_get_computation_time(workstation_list[i],
857                                               computation_amount[i]);
858
859     if (communication_amount != NULL)
860       for (j = 0; j < workstation_nb; j++) {
861         time +=
862             SD_route_get_communication_time(workstation_list[i],
863                                             workstation_list[j],
864                                             communication_amount[i *
865                                                                  workstation_nb
866                                                                  + j]);
867       }
868
869     if (time > max_time) {
870       max_time = time;
871     }
872   }
873   return max_time;
874 }
875
876 static XBT_INLINE void SD_task_do_schedule(SD_task_t task)
877 {
878   if (!__SD_task_is_not_scheduled(task) && !__SD_task_is_schedulable(task))
879     THROWF(arg_error, 0, "Task '%s' has already been scheduled",
880            SD_task_get_name(task));
881
882   /* update the task state */
883   if (task->unsatisfied_dependencies == 0)
884     __SD_task_set_state(task, SD_RUNNABLE);
885   else
886     __SD_task_set_state(task, SD_SCHEDULED);
887 }
888
889 /**
890  * \brief Schedules a task
891  *
892  * The task state must be #SD_NOT_SCHEDULED.
893  * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
894  * i.e. when its dependencies are satisfied.
895  *
896  * \param task the task you want to schedule
897  * \param workstation_count number of workstations on which the task will be executed
898  * \param workstation_list the workstations on which the task will be executed
899  * \param computation_amount computation amount for each workstation
900  * \param communication_amount communication amount between each pair of workstations
901  * \param rate task execution speed rate
902  * \see SD_task_unschedule()
903  */
904 void SD_task_schedule(SD_task_t task, int workstation_count,
905                       const SD_workstation_t * workstation_list,
906                       const double *computation_amount,
907                       const double *communication_amount, double rate)
908 {
909   int communication_nb;
910   task->workstation_nb = 0;
911   task->rate = -1;
912   xbt_assert(workstation_count > 0, "workstation_nb must be positive");
913
914   task->workstation_nb = workstation_count;
915   task->rate = rate;
916
917   if (computation_amount) {
918     task->computation_amount = xbt_realloc(task->computation_amount,
919                                            sizeof(double) * workstation_count);
920     memcpy(task->computation_amount, computation_amount,
921            sizeof(double) * workstation_count);
922   } else {
923     xbt_free(task->computation_amount);
924     task->computation_amount = NULL;
925   }
926
927   communication_nb = workstation_count * workstation_count;
928   if (communication_amount) {
929     task->communication_amount = xbt_realloc(task->communication_amount,
930                                              sizeof(double) * communication_nb);
931     memcpy(task->communication_amount, communication_amount,
932            sizeof(double) * communication_nb);
933   } else {
934     xbt_free(task->communication_amount);
935     task->communication_amount = NULL;
936   }
937
938   task->workstation_list =
939     xbt_realloc(task->workstation_list,
940                 sizeof(SD_workstation_t) * workstation_count);
941   memcpy(task->workstation_list, workstation_list,
942          sizeof(SD_workstation_t) * workstation_count);
943
944   SD_task_do_schedule(task);
945 }
946
947 /**
948  * \brief Unschedules a task
949  *
950  * The task state must be #SD_SCHEDULED, #SD_RUNNABLE, #SD_RUNNING or #SD_FAILED.
951  * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
952  * Call SD_task_schedule() to schedule it again.
953  *
954  * \param task the task you want to unschedule
955  * \see SD_task_schedule()
956  */
957 void SD_task_unschedule(SD_task_t task)
958 {
959   if (task->state_set != sd_global->scheduled_task_set &&
960       task->state_set != sd_global->runnable_task_set &&
961       task->state_set != sd_global->running_task_set &&
962       task->state_set != sd_global->failed_task_set)
963     THROWF(arg_error, 0,
964            "Task %s: the state must be SD_SCHEDULED, SD_RUNNABLE, SD_RUNNING or SD_FAILED",
965            SD_task_get_name(task));
966
967   if (__SD_task_is_scheduled_or_runnable(task)  /* if the task is scheduled or runnable */
968       &&task->kind == SD_TASK_NOT_TYPED)        /* Don't free scheduling data for typed tasks */
969     __SD_task_destroy_scheduling_data(task);
970
971   if (__SD_task_is_running(task))       /* the task should become SD_FAILED */
972     surf_workstation_model->action_cancel(task->surf_action);
973   else {
974     if (task->unsatisfied_dependencies == 0)
975       __SD_task_set_state(task, SD_SCHEDULABLE);
976     else
977       __SD_task_set_state(task, SD_NOT_SCHEDULED);
978   }
979   task->remains = task->amount;
980   task->start_time = -1.0;
981 }
982
983 /* Destroys the data memorized by SD_task_schedule. Task state must be SD_SCHEDULED or SD_RUNNABLE.
984  */
985 static void __SD_task_destroy_scheduling_data(SD_task_t task)
986 {
987   if (!__SD_task_is_scheduled_or_runnable(task)
988       && !__SD_task_is_in_fifo(task))
989     THROWF(arg_error, 0,
990            "Task '%s' must be SD_SCHEDULED, SD_RUNNABLE or SD_IN_FIFO",
991            SD_task_get_name(task));
992
993   xbt_free(task->computation_amount);
994   xbt_free(task->communication_amount);
995   task->computation_amount = task->communication_amount = NULL;
996 }
997
998 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
999  * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
1000  * the task gets out of its fifos.
1001  */
1002 void __SD_task_really_run(SD_task_t task)
1003 {
1004
1005   int i;
1006   void **surf_workstations;
1007
1008   xbt_assert(__SD_task_is_runnable_or_in_fifo(task),
1009               "Task '%s' is not runnable or in a fifo! Task state: %d",
1010              SD_task_get_name(task), (int)SD_task_get_state(task));
1011   xbt_assert(task->workstation_list != NULL,
1012               "Task '%s': workstation_list is NULL!",
1013               SD_task_get_name(task));
1014
1015
1016
1017   XBT_DEBUG("Really running task '%s'", SD_task_get_name(task));
1018
1019   /* set this task as current task for the workstations in sequential mode */
1020   for (i = 0; i < task->workstation_nb; i++) {
1021     if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
1022         SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1023       task->workstation_list[i]->current_task = task;
1024       xbt_assert(__SD_workstation_is_busy(task->workstation_list[i]),
1025                   "The workstation should be busy now");
1026     }
1027   }
1028
1029   XBT_DEBUG("Task '%s' set as current task for its workstations",
1030          SD_task_get_name(task));
1031
1032   /* start the task */
1033
1034   /* we have to create a Surf workstation array instead of the SimDag
1035    * workstation array */
1036   surf_workstations = xbt_new(void *, task->workstation_nb);
1037
1038   for (i = 0; i < task->workstation_nb; i++)
1039     surf_workstations[i] = task->workstation_list[i]->surf_workstation;
1040
1041   /* It's allowed to pass a NULL vector as cost to mean vector of 0.0 (easing
1042    * user's life). Let's deal with it */
1043 #define cost_or_zero(array,pos) ((array)?(array)[pos]:0.0)
1044
1045   task->surf_action = NULL;
1046   if ((task->workstation_nb == 1)
1047       && (cost_or_zero(task->communication_amount, 0) == 0.0)) {
1048     task->surf_action =
1049         surf_workstation_model->extension.
1050         workstation.execute(surf_workstations[0],
1051                             cost_or_zero(task->computation_amount, 0));
1052   } else if ((task->workstation_nb == 1)
1053              && (cost_or_zero(task->computation_amount, 0) == 0.0)) {
1054
1055     task->surf_action =
1056         surf_workstation_model->extension.
1057         workstation.communicate(surf_workstations[0], surf_workstations[0],
1058                                 cost_or_zero(task->communication_amount,
1059                                              0), task->rate);
1060   } else if ((task->workstation_nb == 2)
1061              && (cost_or_zero(task->computation_amount, 0) == 0.0)
1062              && (cost_or_zero(task->computation_amount, 1) == 0.0)) {
1063     int nb = 0;
1064     double value = 0.0;
1065
1066     for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
1067       if (cost_or_zero(task->communication_amount, i) > 0.0) {
1068         nb++;
1069         value = cost_or_zero(task->communication_amount, i);
1070       }
1071     }
1072     if (nb == 1) {
1073       task->surf_action =
1074           surf_workstation_model->extension.
1075           workstation.communicate(surf_workstations[0],
1076                                   surf_workstations[1], value, task->rate);
1077     }
1078   }
1079 #undef cost_or_zero
1080
1081   if (!task->surf_action) {
1082     double *computation_amount = xbt_new(double, task->workstation_nb);
1083     double *communication_amount = xbt_new(double, task->workstation_nb *
1084                                            task->workstation_nb);
1085
1086     memcpy(computation_amount, task->computation_amount, sizeof(double) *
1087            task->workstation_nb);
1088     memcpy(communication_amount, task->communication_amount,
1089            sizeof(double) * task->workstation_nb * task->workstation_nb);
1090
1091     task->surf_action =
1092         surf_workstation_model->extension.
1093         workstation.execute_parallel_task(task->workstation_nb,
1094                                           surf_workstations,
1095                                           computation_amount,
1096                                           communication_amount,
1097                                           task->rate);
1098   } else {
1099     xbt_free(surf_workstations);
1100   }
1101
1102   surf_workstation_model->action_data_set(task->surf_action, task);
1103
1104   XBT_DEBUG("surf_action = %p", task->surf_action);
1105
1106 #ifdef HAVE_TRACING
1107   if (task->category)
1108     TRACE_surf_action(task->surf_action, task->category);
1109 #endif
1110
1111   __SD_task_destroy_scheduling_data(task);      /* now the scheduling data are not useful anymore */
1112   __SD_task_set_state(task, SD_RUNNING);
1113   xbt_assert(__SD_task_is_running(task), "Bad state of task '%s': %d",
1114              SD_task_get_name(task), (int)SD_task_get_state(task));
1115
1116 }
1117
1118 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_RUNNABLE
1119  * (ie when its dependencies are satisfied).
1120  * If one of the workstations where the task is scheduled on is busy (in sequential mode),
1121  * the task doesn't start.
1122  * Returns whether the task has started.
1123  */
1124 int __SD_task_try_to_run(SD_task_t task)
1125 {
1126
1127   int can_start = 1;
1128   int i;
1129   SD_workstation_t workstation;
1130
1131   xbt_assert(__SD_task_is_runnable(task),
1132               "Task '%s' is not runnable! Task state: %d",
1133              SD_task_get_name(task), (int)SD_task_get_state(task));
1134
1135
1136   for (i = 0; i < task->workstation_nb; i++) {
1137     can_start = can_start &&
1138         !__SD_workstation_is_busy(task->workstation_list[i]);
1139   }
1140
1141   XBT_DEBUG("Task '%s' can start: %d", SD_task_get_name(task), can_start);
1142
1143   if (!can_start) {             /* if the task cannot start and is not in the fifos yet */
1144     for (i = 0; i < task->workstation_nb; i++) {
1145       workstation = task->workstation_list[i];
1146       if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1147         XBT_DEBUG("Pushing task '%s' in the fifo of workstation '%s'",
1148                SD_task_get_name(task),
1149                SD_workstation_get_name(workstation));
1150         xbt_fifo_push(workstation->task_fifo, task);
1151       }
1152     }
1153     __SD_task_set_state(task, SD_IN_FIFO);
1154     xbt_assert(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
1155                SD_task_get_name(task), (int)SD_task_get_state(task));
1156     XBT_DEBUG("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
1157   } else {
1158     __SD_task_really_run(task);
1159   }
1160
1161   return can_start;
1162 }
1163
1164 /* This function is called by SD_simulate when a task is done.
1165  * It updates task->state and task->action and executes if necessary the tasks
1166  * which were waiting in fifos for the end of `task'
1167  */
1168 void __SD_task_just_done(SD_task_t task)
1169 {
1170   int i, j;
1171   SD_workstation_t workstation;
1172
1173   SD_task_t candidate;
1174   int candidate_nb = 0;
1175   int candidate_capacity = 8;
1176   SD_task_t *candidates;
1177   int can_start = 1;
1178
1179   xbt_assert(__SD_task_is_running(task),
1180               "The task must be running! Task state: %d",
1181               (int)SD_task_get_state(task));
1182   xbt_assert(task->workstation_list != NULL,
1183               "Task '%s': workstation_list is NULL!",
1184               SD_task_get_name(task));
1185
1186
1187   candidates = xbt_new(SD_task_t, 8);
1188
1189   __SD_task_set_state(task, SD_DONE);
1190   surf_workstation_model->action_unref(task->surf_action);
1191   task->surf_action = NULL;
1192
1193   XBT_DEBUG("Looking for candidates");
1194
1195   /* if the task was executed on sequential workstations,
1196      maybe we can execute the next task of the fifo for each workstation */
1197   for (i = 0; i < task->workstation_nb; i++) {
1198     workstation = task->workstation_list[i];
1199     XBT_DEBUG("Workstation '%s': access_mode = %d",
1200               SD_workstation_get_name(workstation), (int)workstation->access_mode);
1201     if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1202       xbt_assert(workstation->task_fifo != NULL,
1203                   "Workstation '%s' has sequential access but no fifo!",
1204                   SD_workstation_get_name(workstation));
1205       xbt_assert(workstation->current_task =
1206                   task, "Workstation '%s': current task should be '%s'",
1207                   SD_workstation_get_name(workstation),
1208                   SD_task_get_name(task));
1209
1210       /* the task is over so we can release the workstation */
1211       workstation->current_task = NULL;
1212
1213       XBT_DEBUG("Getting candidate in fifo");
1214       candidate =
1215           xbt_fifo_get_item_content(xbt_fifo_get_first_item
1216                                     (workstation->task_fifo));
1217
1218       if (candidate != NULL) {
1219         XBT_DEBUG("Candidate: '%s'", SD_task_get_name(candidate));
1220         xbt_assert(__SD_task_is_in_fifo(candidate),
1221                     "Bad state of candidate '%s': %d",
1222                     SD_task_get_name(candidate),
1223                     (int)SD_task_get_state(candidate));
1224       }
1225
1226       XBT_DEBUG("Candidate in fifo: %p", candidate);
1227
1228       /* if there was a task waiting for my place */
1229       if (candidate != NULL) {
1230         /* Unfortunately, we are not sure yet that we can execute the task now,
1231            because the task can be waiting more deeply in some other workstation's fifos...
1232            So we memorize all candidate tasks, and then we will check for each candidate
1233            whether or not all its workstations are available. */
1234
1235         /* realloc if necessary */
1236         if (candidate_nb == candidate_capacity) {
1237           candidate_capacity *= 2;
1238           candidates =
1239               xbt_realloc(candidates,
1240                           sizeof(SD_task_t) * candidate_capacity);
1241         }
1242
1243         /* register the candidate */
1244         candidates[candidate_nb++] = candidate;
1245         candidate->fifo_checked = 0;
1246       }
1247     }
1248   }
1249
1250   XBT_DEBUG("Candidates found: %d", candidate_nb);
1251
1252   /* now we check every candidate task */
1253   for (i = 0; i < candidate_nb; i++) {
1254     candidate = candidates[i];
1255
1256     if (candidate->fifo_checked) {
1257       continue;                 /* we have already evaluated that task */
1258     }
1259
1260     xbt_assert(__SD_task_is_in_fifo(candidate),
1261                 "Bad state of candidate '%s': %d",
1262                SD_task_get_name(candidate), (int)SD_task_get_state(candidate));
1263
1264     for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1265       workstation = candidate->workstation_list[j];
1266
1267       /* I can start on this workstation if the workstation is shared
1268          or if I am the first task in the fifo */
1269       can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS
1270           || candidate ==
1271           xbt_fifo_get_item_content(xbt_fifo_get_first_item
1272                                     (workstation->task_fifo));
1273     }
1274
1275     XBT_DEBUG("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1276            can_start);
1277
1278     /* now we are sure that I can start! */
1279     if (can_start) {
1280       for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1281         workstation = candidate->workstation_list[j];
1282
1283         /* update the fifo */
1284         if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1285           candidate = xbt_fifo_shift(workstation->task_fifo);   /* the return value is stored just for debugging */
1286           XBT_DEBUG("Head of the fifo: '%s'",
1287                  (candidate !=
1288                   NULL) ? SD_task_get_name(candidate) : "NULL");
1289           xbt_assert(candidate == candidates[i],
1290                       "Error in __SD_task_just_done: bad first task in the fifo");
1291         }
1292       }                         /* for each workstation */
1293
1294       /* finally execute the task */
1295       XBT_DEBUG("Task '%s' state: %d", SD_task_get_name(candidate),
1296              (int)SD_task_get_state(candidate));
1297       __SD_task_really_run(candidate);
1298
1299       XBT_DEBUG
1300           ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1301            SD_task_get_name(candidate), candidate->state_set,
1302            sd_global->running_task_set, __SD_task_is_running(candidate));
1303       xbt_assert(__SD_task_is_running(candidate),
1304                   "Bad state of task '%s': %d",
1305                   SD_task_get_name(candidate),
1306                  (int)SD_task_get_state(candidate));
1307       XBT_DEBUG("Okay, the task is running.");
1308
1309     }                           /* can start */
1310     candidate->fifo_checked = 1;
1311   }                             /* for each candidate */
1312
1313   xbt_free(candidates);
1314 }
1315
1316 /* 
1317  * Remove all dependencies associated with a task. This function is called 
1318  * when the task is destroyed.
1319  */
1320 static void __SD_task_remove_dependencies(SD_task_t task)
1321 {
1322   /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1323      because each one is stored twice */
1324   SD_dependency_t dependency;
1325   while (!xbt_dynar_is_empty(task->tasks_before)) {
1326     xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1327     SD_task_dependency_remove(dependency->src, dependency->dst);
1328   }
1329
1330   while (!xbt_dynar_is_empty(task->tasks_after)) {
1331     xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1332     SD_task_dependency_remove(dependency->src, dependency->dst);
1333   }
1334 }
1335
1336 /**
1337  * \brief Returns the start time of a task
1338  *
1339  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1340  *
1341  * \param task: a task
1342  * \return the start time of this task
1343  */
1344 double SD_task_get_start_time(SD_task_t task)
1345 {
1346   if (task->surf_action)
1347     return surf_workstation_model->
1348         action_get_start_time(task->surf_action);
1349   else
1350     return task->start_time;
1351 }
1352
1353 /**
1354  * \brief Returns the finish time of a task
1355  *
1356  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1357  * If the state is not completed yet, the returned value is an
1358  * estimation of the task finish time. This value can fluctuate
1359  * until the task is completed.
1360  *
1361  * \param task: a task
1362  * \return the start time of this task
1363  */
1364 double SD_task_get_finish_time(SD_task_t task)
1365 {
1366   if (task->surf_action)        /* should never happen as actions are destroyed right after their completion */
1367     return surf_workstation_model->
1368         action_get_finish_time(task->surf_action);
1369   else
1370     return task->finish_time;
1371 }
1372 /** @brief Blah
1373  *
1374  */
1375 void SD_task_distribute_comp_amdhal(SD_task_t task, int ws_count)
1376 {
1377   int i;
1378   xbt_assert(task->kind == SD_TASK_COMP_PAR_AMDAHL,
1379               "Task %s is not a SD_TASK_COMP_PAR_AMDAHL typed task."
1380               "Cannot use this function.",
1381               SD_task_get_name(task));  
1382               
1383   task->computation_amount = xbt_new0(double, ws_count);
1384   task->communication_amount = xbt_new0(double, ws_count * ws_count);
1385   task->workstation_nb = ws_count;
1386   task->workstation_list = xbt_new0(SD_workstation_t, ws_count);
1387   
1388   for(i=0;i<ws_count;i++){
1389     task->computation_amount[i] = 
1390       (task->alpha + (1 - task->alpha)/ws_count) * task->amount;
1391   }
1392
1393
1394
1395 /** @brief Auto-schedules a task.
1396  *
1397  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1398  * allows to specify the task costs at creation, and decorelate them from the
1399  * scheduling process where you just specify which resource should deliver the
1400  * mandatory power.
1401  *
1402  * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1403  * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1404  * of them.
1405  *
1406  * @todo
1407  * We should create tasks kind for the following categories:
1408  *  - Point to point communication (done)
1409  *  - Sequential computation       (done)
1410  *  - group communication (redistribution, several kinds)
1411  *  - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1412  *  - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1413  */
1414 void SD_task_schedulev(SD_task_t task, int count,
1415                        const SD_workstation_t * list)
1416 {
1417   int i, j;
1418   SD_dependency_t dep;
1419   unsigned int cpt;
1420   xbt_assert(task->kind != 0,
1421               "Task %s is not typed. Cannot automatically schedule it.",
1422               SD_task_get_name(task));
1423   switch (task->kind) {
1424   case SD_TASK_COMP_PAR_AMDAHL:
1425     SD_task_distribute_comp_amdhal(task, count);
1426   case SD_TASK_COMM_E2E:
1427   case SD_TASK_COMP_SEQ:
1428     xbt_assert(task->workstation_nb == count,"Got %d locations, but were expecting %d locations",count,task->workstation_nb);
1429     for (i = 0; i < count; i++)
1430       task->workstation_list[i] = list[i];
1431     SD_task_do_schedule(task);
1432     break;
1433   default:
1434     xbt_die("Kind of task %s not supported by SD_task_schedulev()",
1435             SD_task_get_name(task));
1436   }
1437   if (task->kind == SD_TASK_COMM_E2E) {
1438     XBT_VERB("Schedule comm task %s between %s -> %s. It costs %.f bytes",
1439           SD_task_get_name(task),
1440           SD_workstation_get_name(task->workstation_list[0]),
1441           SD_workstation_get_name(task->workstation_list[1]),
1442           task->communication_amount[2]);
1443
1444   }
1445
1446   /* Iterate over all childs and parent being COMM_E2E to say where I am located (and start them if runnable) */
1447   if (task->kind == SD_TASK_COMP_SEQ) {
1448     XBT_VERB("Schedule computation task %s on %s. It costs %.f flops",
1449           SD_task_get_name(task),
1450           SD_workstation_get_name(task->workstation_list[0]),
1451           task->computation_amount[0]);
1452
1453     xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1454       SD_task_t before = dep->src;
1455       if (before->kind == SD_TASK_COMM_E2E) {
1456         before->workstation_list[1] = task->workstation_list[0];
1457
1458         if (before->workstation_list[0] &&
1459             (__SD_task_is_schedulable(before)
1460              || __SD_task_is_not_scheduled(before))) {
1461           SD_task_do_schedule(before);
1462           XBT_VERB
1463               ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1464                SD_task_get_name(before),
1465                SD_workstation_get_name(before->workstation_list[0]),
1466                SD_workstation_get_name(before->workstation_list[1]),
1467                before->communication_amount[2]);
1468         }
1469       }
1470     }
1471     xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1472       SD_task_t after = dep->dst;
1473       if (after->kind == SD_TASK_COMM_E2E) {
1474         after->workstation_list[0] = task->workstation_list[0];
1475         if (after->workstation_list[1]
1476             && (__SD_task_is_not_scheduled(after)
1477                 || __SD_task_is_schedulable(after))) {
1478           SD_task_do_schedule(after);
1479           XBT_VERB
1480               ("Auto-Schedule comm task %s between %s -> %s. It costs %.f bytes",
1481                SD_task_get_name(after),
1482                SD_workstation_get_name(after->workstation_list[0]),
1483                SD_workstation_get_name(after->workstation_list[1]),
1484                after->communication_amount[2]);
1485
1486         }
1487       }
1488     }
1489   }
1490   /* Iterate over all childs and parent being MXN_1D_BLOC to say where I am located (and start them if runnable) */
1491   if (task->kind == SD_TASK_COMP_PAR_AMDAHL) {
1492     XBT_VERB("Schedule computation task %s on %d workstations. %.f flops"
1493              " will be distributed following Amdahl'Law",
1494           SD_task_get_name(task), task->workstation_nb,
1495           task->computation_amount[0]);
1496     xbt_dynar_foreach(task->tasks_before, cpt, dep) {
1497       SD_task_t before = dep->src;
1498       if (before->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1499         if (!before->workstation_list){
1500           XBT_VERB("Sender side of Task %s is not scheduled yet. Fill the workstation list with receiver side",
1501              SD_task_get_name(before));
1502           before->workstation_list = xbt_new0(SD_workstation_t, count);
1503           before->workstation_nb = count;
1504           for (i=0;i<count;i++)
1505             before->workstation_list[i] = task->workstation_list[i];
1506         } else {
1507           int src_nb, dst_nb;
1508           double src_start, src_end, dst_start, dst_end;
1509           src_nb = before->workstation_nb;
1510           dst_nb = count;
1511           before->workstation_list = (SD_workstation_t*) xbt_realloc(
1512              before->workstation_list,
1513              (before->workstation_nb+count)*sizeof(s_SD_workstation_t));
1514           for(i=0; i<count; i++)
1515             before->workstation_list[before->workstation_nb+i] =
1516                task->workstation_list[i];
1517
1518           before->workstation_nb += count;
1519
1520           before->computation_amount = xbt_new0(double,
1521                                                 before->workstation_nb);
1522           before->communication_amount = xbt_new0(double,
1523                                                   before->workstation_nb*
1524                                                   before->workstation_nb);
1525
1526           for(i=0;i<src_nb;i++){
1527             src_start = i*before->amount/src_nb;
1528             src_end = src_start + before->amount/src_nb;
1529             for(j=0; j<dst_nb; j++){
1530               dst_start = j*before->amount/dst_nb;
1531               dst_end = dst_start + before->amount/dst_nb;
1532               XBT_VERB("(%s->%s): (%.2f, %.2f)-> (%.2f, %.2f)",
1533                   SD_workstation_get_name(before->workstation_list[i]),
1534                   SD_workstation_get_name(before->workstation_list[src_nb+j]),
1535                   src_start, src_end, dst_start, dst_end);
1536               if ((src_end <= dst_start) || (dst_end <= src_start)) {
1537                 before->communication_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1538               } else {
1539                 before->communication_amount[i*(src_nb+dst_nb)+src_nb+j] =
1540                   MIN(src_end, dst_end) - MAX(src_start, dst_start);
1541               }
1542               XBT_VERB("==> %.2f",
1543                  before->communication_amount[i*(src_nb+dst_nb)+src_nb+j]);
1544             }
1545           }
1546
1547           if (__SD_task_is_schedulable(before) ||
1548               __SD_task_is_not_scheduled(before)) {
1549             SD_task_do_schedule(before);
1550             XBT_VERB
1551               ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1552                   SD_task_get_name(before),before->amount, src_nb, dst_nb);
1553             }
1554         }
1555       }
1556     }
1557     xbt_dynar_foreach(task->tasks_after, cpt, dep) {
1558       SD_task_t after = dep->dst;
1559       if (after->kind == SD_TASK_COMM_PAR_MXN_1D_BLOCK){
1560         if (!after->workstation_list){
1561           XBT_VERB("Receiver side of Task %s is not scheduled yet. Fill the workstation list with sender side",
1562               SD_task_get_name(after));
1563           after->workstation_list = xbt_new0(SD_workstation_t, count);
1564           after->workstation_nb = count;
1565           for (i=0;i<count;i++)
1566             after->workstation_list[i] = task->workstation_list[i];
1567         } else {
1568           int src_nb, dst_nb;
1569           double src_start, src_end, dst_start, dst_end;
1570           src_nb = count;
1571           dst_nb = after->workstation_nb;
1572           after->workstation_list = (SD_workstation_t*) xbt_realloc(
1573             after->workstation_list,
1574             (after->workstation_nb+count)*sizeof(s_SD_workstation_t));
1575           for(i=after->workstation_nb - 1; i>=0; i--)
1576             after->workstation_list[count+i] = after->workstation_list[i];
1577           for(i=0; i<count; i++)
1578             after->workstation_list[i] = task->workstation_list[i];
1579
1580           after->workstation_nb += count;
1581
1582           after->computation_amount = xbt_new0(double, after->workstation_nb);
1583           after->communication_amount = xbt_new0(double,
1584                                                  after->workstation_nb*
1585                                                  after->workstation_nb);
1586
1587           for(i=0;i<src_nb;i++){
1588             src_start = i*after->amount/src_nb;
1589             src_end = src_start + after->amount/src_nb;
1590             for(j=0; j<dst_nb; j++){
1591               dst_start = j*after->amount/dst_nb;
1592               dst_end = dst_start + after->amount/dst_nb;
1593               XBT_VERB("(%d->%d): (%.2f, %.2f)-> (%.2f, %.2f)",
1594                   i, j, src_start, src_end, dst_start, dst_end);
1595               if ((src_end <= dst_start) || (dst_end <= src_start)) {
1596                 after->communication_amount[i*(src_nb+dst_nb)+src_nb+j]=0.0;
1597               } else {
1598                 after->communication_amount[i*(src_nb+dst_nb)+src_nb+j] =
1599                    MIN(src_end, dst_end)- MAX(src_start, dst_start);
1600               }
1601               XBT_VERB("==> %.2f",
1602                  after->communication_amount[i*(src_nb+dst_nb)+src_nb+j]);
1603             }
1604           }
1605
1606           if (__SD_task_is_schedulable(after) ||
1607               __SD_task_is_not_scheduled(after)) {
1608             SD_task_do_schedule(after);
1609             XBT_VERB
1610             ("Auto-Schedule redistribution task %s. Send %.f bytes from %d hosts to %d hosts.",
1611               SD_task_get_name(after),after->amount, src_nb, dst_nb);
1612           }
1613          }
1614       }
1615     }
1616   }
1617 }
1618
1619 /** @brief autoschedule a task on a list of workstations
1620  *
1621  * This function is very similar to SD_task_schedulev(),
1622  * but takes the list of workstations to schedule onto as separate parameters.
1623  * It builds a proper vector of workstations and then call SD_task_schedulev()
1624  */
1625 void SD_task_schedulel(SD_task_t task, int count, ...)
1626 {
1627   va_list ap;
1628   SD_workstation_t *list = xbt_new(SD_workstation_t, count);
1629   int i;
1630   va_start(ap, count);
1631   for (i = 0; i < count; i++) {
1632     list[i] = va_arg(ap, SD_workstation_t);
1633   }
1634   va_end(ap);
1635   SD_task_schedulev(task, count, list);
1636   free(list);
1637 }
1638
1639 /**
1640  * \brief Sets the tracing category of a task.
1641  *
1642  * This function should be called after the creation of a
1643  * SimDAG task, to define the category of that task. The first
1644  * parameter must contain a task that was created with the
1645  * function #SD_task_create. The second parameter must contain
1646  * a category that was previously declared with the function
1647  * #TRACE_category.
1648  *
1649  * \param task The task to be considered
1650  * \param category the name of the category to be associated to the task
1651  *
1652  * \see SD_task_get_category, TRACE_category, TRACE_category_with_color
1653  */
1654 void SD_task_set_category (SD_task_t task, const char *category)
1655 {
1656 #ifdef HAVE_TRACING
1657   if (!TRACE_is_enabled()) return;
1658   if (task == NULL) return;
1659   if (category == NULL){
1660     if (task->category) xbt_free (task->category);
1661     task->category = NULL;
1662   }else{
1663     task->category = xbt_strdup (category);
1664   }
1665 #endif
1666 }
1667
1668 /**
1669  * \brief Gets the current tracing category of a task.
1670  *
1671  * \param task The task to be considered
1672  *
1673  * \see SD_task_set_category
1674  *
1675  * \return Returns the name of the tracing category of the given task, NULL otherwise
1676  */
1677 const char *SD_task_get_category (SD_task_t task)
1678 {
1679 #ifdef HAVE_TRACING
1680   return task->category;
1681 #else
1682   return NULL;
1683 #endif
1684 }