Logo AND Algorithmique Numérique Distribuée

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