Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Simplify the code of typed tasks in simdag by allocating the comm_ and comp_amount...
[simgrid.git] / src / simdag / sd_task.c
1 /* Copyright (c) 2007-2009 Da SimGrid Team.  All rights reserved.           */
2
3 /* This program is free software; you can redistribute it and/or modify it
4  * under the terms of the license (GNU LGPL) which comes with this package. */
5
6 #include "private.h"
7 #include "simdag/simdag.h"
8 #include "xbt/sysdep.h"
9 #include "xbt/dynar.h"
10
11 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_task, sd,
12                                 "Logging specific to SimDag (task)");
13
14 static void __SD_task_remove_dependencies(SD_task_t task);
15 static void __SD_task_destroy_scheduling_data(SD_task_t task);
16
17 /**
18  * \brief Creates a new task.
19  *
20  * \param name the name of the task (can be \c NULL)
21  * \param data the user data you want to associate with the task (can be \c NULL)
22  * \param amount amount of the task
23  * \return the new task
24  * \see SD_task_destroy()
25  */
26 SD_task_t SD_task_create(const char *name, void *data, double amount)
27 {
28
29   SD_task_t task;
30   SD_CHECK_INIT_DONE();
31
32   task = xbt_new(s_SD_task_t, 1);
33
34   /* general information */
35   task->data = data;            /* user data */
36   task->name = xbt_strdup(name);
37   task->kind = 0;
38   task->state_hookup.prev = NULL;
39   task->state_hookup.next = NULL;
40   task->state_set = sd_global->not_scheduled_task_set;
41   task->state = SD_NOT_SCHEDULED;
42   xbt_swag_insert(task, task->state_set);
43
44   task->amount = amount;
45   task->remains = amount;
46   task->start_time = -1.0;
47   task->finish_time = -1.0;
48   task->surf_action = NULL;
49   task->watch_points = 0;
50
51   /* dependencies */
52   task->tasks_before = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
53   task->tasks_after = xbt_dynar_new(sizeof(SD_dependency_t), NULL);
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 = 0;
61
62   sd_global->task_number++;
63
64   return task;
65 }
66
67 /**
68  * \brief Returns the user data of a task
69  *
70  * \param task a task
71  * \return the user data associated with this task (can be \c NULL)
72  * \see SD_task_set_data()
73  */
74 void *SD_task_get_data(SD_task_t task)
75 {
76   SD_CHECK_INIT_DONE();
77   xbt_assert0(task != NULL, "Invalid parameter");
78   return task->data;
79 }
80
81 /**
82  * \brief Sets the user data of a task
83  *
84  * The new data can be \c NULL. The old data should have been freed first
85  * if it was not \c NULL.
86  *
87  * \param task a task
88  * \param data the new data you want to associate with this task
89  * \see SD_task_get_data()
90  */
91 void SD_task_set_data(SD_task_t task, void *data)
92 {
93   SD_CHECK_INIT_DONE();
94   xbt_assert0(task != NULL, "Invalid parameter");
95   task->data = data;
96 }
97
98 /**
99  * \brief Returns the state of a task
100  *
101  * \param task a task
102  * \return the current \ref e_SD_task_state_t "state" of this task:
103  * #SD_NOT_SCHEDULED, #SD_SCHEDULED, #SD_READY, #SD_RUNNING, #SD_DONE or #SD_FAILED
104  * \see e_SD_task_state_t
105  */
106 e_SD_task_state_t SD_task_get_state(SD_task_t task)
107 {
108   SD_CHECK_INIT_DONE();
109   xbt_assert0(task != NULL, "Invalid parameter");
110   return task->state;
111 }
112
113 /* Changes the state of a task. Updates the swags and the flag sd_global->watch_point_reached.
114  */
115 void __SD_task_set_state(SD_task_t task, e_SD_task_state_t new_state)
116 {
117   xbt_swag_remove(task, task->state_set);
118   switch (new_state) {
119   case SD_NOT_SCHEDULED:
120     task->state_set = sd_global->not_scheduled_task_set;
121     break;
122   case SD_SCHEDULED:
123     task->state_set = sd_global->scheduled_task_set;
124     break;
125   case SD_READY:
126     task->state_set = sd_global->ready_task_set;
127     break;
128   case SD_IN_FIFO:
129     task->state_set = sd_global->in_fifo_task_set;
130     break;
131   case SD_RUNNING:
132     task->state_set = sd_global->running_task_set;
133     task->start_time =
134       surf_workstation_model->action_get_start_time(task->surf_action);
135     break;
136   case SD_DONE:
137     task->state_set = sd_global->done_task_set;
138     task->finish_time =
139       surf_workstation_model->action_get_finish_time(task->surf_action);
140     task->remains = 0;
141     break;
142   case SD_FAILED:
143     task->state_set = sd_global->failed_task_set;
144     break;
145   default:
146     xbt_assert0(0, "Invalid state");
147   }
148   xbt_swag_insert(task, task->state_set);
149   task->state = new_state;
150
151   if (task->watch_points & new_state) {
152     INFO1("Watch point reached with task '%s'!", SD_task_get_name(task));
153     sd_global->watch_point_reached = 1;
154     SD_task_unwatch(task, new_state);   /* remove the watch point */
155   }
156 }
157
158 /**
159  * \brief Returns the name of a task
160  *
161  * \param task a task
162  * \return the name of this task (can be \c NULL)
163  */
164 const char *SD_task_get_name(SD_task_t task)
165 {
166   SD_CHECK_INIT_DONE();
167   xbt_assert0(task != NULL, "Invalid parameter");
168   return task->name;
169 }
170
171 /** @brief Returns the dynar of the parents of a task
172  *
173  * \param task a task
174  * \return a newly allocated dynar comprising the parents of this task
175  */
176
177 xbt_dynar_t SD_task_get_parents(SD_task_t task)
178 {
179   unsigned int i;
180   xbt_dynar_t parents;
181   SD_dependency_t dep;
182   SD_CHECK_INIT_DONE();
183   xbt_assert0(task != NULL, "Invalid parameter");
184
185   parents = xbt_dynar_new(sizeof(SD_task_t), NULL);
186   xbt_dynar_foreach(task->tasks_before, i, dep){
187     xbt_dynar_push(parents, &(dep->src));
188   }
189   return parents;
190 }
191
192 /** @brief Returns the dynar of the parents of a task
193  *
194  * \param task a task
195  * \return a newly allocated dynar comprising the parents of this task
196  */
197 xbt_dynar_t SD_task_get_children(SD_task_t task)
198 {
199   unsigned int i;
200   xbt_dynar_t children;
201   SD_dependency_t dep;
202   SD_CHECK_INIT_DONE();
203   xbt_assert0(task != NULL, "Invalid parameter");
204
205   children = xbt_dynar_new(sizeof(SD_task_t), NULL);
206   xbt_dynar_foreach(task->tasks_after, i, dep){
207     xbt_dynar_push(children, &(dep->dst));
208   }
209   return children;
210 }
211
212 /**
213  * \brief Returns the amount of workstations involved in a task
214  *
215  * Only call this on already scheduled tasks!
216  * \param task a task
217  */
218 int SD_task_get_workstation_count(SD_task_t task)
219 {
220   SD_CHECK_INIT_DONE();
221   xbt_assert0(task != NULL, "Invalid parameter");
222   //  xbt_assert1( task->state_set != sd_global->scheduled_task_set, 
223   //           "Unscheduled task %s", task->name);
224   return task->workstation_nb;
225 }
226
227 /**
228  * \brief Returns the list of workstations involved in a task
229  *
230  * Only call this on already scheduled tasks!
231  * \param task a task
232  */
233 SD_workstation_t* SD_task_get_workstation_list(SD_task_t task)
234 {
235   SD_CHECK_INIT_DONE();
236   xbt_assert0(task != NULL, "Invalid parameter");
237   //xbt_assert1( task->state_set != sd_global->scheduled_task_set, 
238   //           "Unscheduled task %s", task->name);
239   return task->workstation_list;
240 }
241
242 /**
243  * \brief Returns the total amount of a task
244  *
245  * \param task a task
246  * \return the total amount of this task
247  * \see SD_task_get_remaining_amount()
248  */
249 double SD_task_get_amount(SD_task_t task)
250 {
251   SD_CHECK_INIT_DONE();
252   xbt_assert0(task != NULL, "Invalid parameter");
253   return task->amount;
254 }
255
256 /**
257  * \brief Returns the remaining amount of a task
258  *
259  * \param task a task
260  * \return the remaining amount of this task
261  * \see SD_task_get_amount()
262  */
263 double SD_task_get_remaining_amount(SD_task_t task)
264 {
265   SD_CHECK_INIT_DONE();
266   xbt_assert0(task != NULL, "Invalid parameter");
267
268   if (task->surf_action)
269     return surf_workstation_model->get_remains(task->surf_action);
270   else
271     return task->remains;
272 }
273
274 /** @brief Displays debugging informations about a task */
275 void SD_task_dump(SD_task_t task)
276 {
277   unsigned int counter;
278   SD_dependency_t dependency;
279
280   INFO1("Displaying task %s",SD_task_get_name(task));
281   INFO1("  - amount: %.0f",SD_task_get_amount(task));
282   if (task->kind!=0) {
283     switch(task->kind){
284     case SD_TASK_COMM_E2E:
285       INFO0("  - kind: end-to-end communication");
286       break;
287     case SD_TASK_COMP_SEQ:
288       INFO0("  - kind: sequential computation");
289       break;
290     default:
291       INFO1("  - (unknown kind %d)",task->kind);
292     }
293   }
294   if (xbt_dynar_length(task->tasks_before)) {
295     INFO0("  - pre-dependencies:");
296     xbt_dynar_foreach(task->tasks_before,counter,dependency) {
297       INFO1("    %s",SD_task_get_name(dependency->src));
298     }
299   }
300   if (xbt_dynar_length(task->tasks_after)) {
301     INFO0("  - post-dependencies:");
302     xbt_dynar_foreach(task->tasks_after,counter,dependency) {
303       INFO1("    %s",SD_task_get_name(dependency->dst));
304     }
305   }
306 }
307 /** @brief Dumps the task in dotty formalism into the FILE* passed as second argument */
308 void SD_task_dotty(SD_task_t task,void* out) {
309   unsigned int counter;
310   SD_dependency_t dependency;
311   fprintf(out, "  T%d [label=\"%.10s\"",(unsigned int)task,task->name);
312   switch(task->kind){
313     case SD_TASK_COMM_E2E:
314       fprintf(out,", shape=box");
315       break;
316     case SD_TASK_COMP_SEQ:
317       fprintf(out,", shape=circle");
318       break;
319   }
320   fprintf(out,"];\n");
321   xbt_dynar_foreach(task->tasks_before,counter,dependency) {
322     fprintf(out," T%d -> T%d;\n",(unsigned int)dependency->src,(unsigned int)dependency->dst);
323   }
324 }
325
326 /* Destroys a dependency between two tasks.
327  */
328 static void __SD_task_dependency_destroy(void *dependency)
329 {
330   if (((SD_dependency_t) dependency)->name != NULL)
331     xbt_free(((SD_dependency_t) dependency)->name);
332   xbt_free(dependency);
333 }
334
335 /**
336  * \brief Adds a dependency between two tasks
337  *
338  * \a dst will depend on \a src, ie \a dst will not start before \a src is finished.
339  * Their \ref e_SD_task_state_t "state" must be #SD_NOT_SCHEDULED, #SD_SCHEDULED or #SD_READY.
340  *
341  * \param name the name of the new dependency (can be \c NULL)
342  * \param data the user data you want to associate with this dependency (can be \c NULL)
343  * \param src the task which must be executed first
344  * \param dst the task you want to make depend on \a src
345  * \see SD_task_dependency_remove()
346  */
347 void SD_task_dependency_add(const char *name, void *data, SD_task_t src,
348                             SD_task_t dst)
349 {
350   xbt_dynar_t dynar;
351   int length;
352   int found = 0;
353   int i;
354   SD_dependency_t dependency;
355
356   SD_CHECK_INIT_DONE();
357   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
358
359   dynar = src->tasks_after;
360   length = xbt_dynar_length(dynar);
361
362   if (src == dst)
363     THROW1(arg_error, 0,
364            "Cannot add a dependency between task '%s' and itself",
365            SD_task_get_name(src));
366
367   if (!__SD_task_is_not_scheduled(src)
368       && !__SD_task_is_scheduled_or_ready(src))
369     THROW1(arg_error, 0,
370            "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
371            SD_task_get_name(src));
372
373   if (!__SD_task_is_not_scheduled(dst)
374       && !__SD_task_is_scheduled_or_ready(dst))
375     THROW1(arg_error, 0,
376            "Task '%s' must be SD_NOT_SCHEDULED, SD_SCHEDULED or SD_READY",
377            SD_task_get_name(dst));
378
379   DEBUG2("SD_task_dependency_add: src = %s, dst = %s", SD_task_get_name(src),
380          SD_task_get_name(dst));
381   for (i = 0; i < length && !found; i++) {
382     xbt_dynar_get_cpy(dynar, i, &dependency);
383     found = (dependency->dst == dst);
384     DEBUG2("Dependency %d: dependency->dst = %s", i,
385            SD_task_get_name(dependency->dst));
386   }
387
388   if (found)
389     THROW2(arg_error, 0,
390            "A dependency already exists between task '%s' and task '%s'",
391            SD_task_get_name(src), SD_task_get_name(dst));
392
393   dependency = xbt_new(s_SD_dependency_t, 1);
394
395   dependency->name = xbt_strdup(name); /* xbt_strdup is cleaver enough to deal with NULL args itself */
396   dependency->data = data;
397   dependency->src = src;
398   dependency->dst = dst;
399
400   /* src must be executed before dst */
401   xbt_dynar_push(src->tasks_after, &dependency);
402   xbt_dynar_push(dst->tasks_before, &dependency);
403
404   /* if the task was ready, then dst->tasks_before is not empty anymore,
405      so we must go back to state SD_SCHEDULED */
406   if (__SD_task_is_ready(dst)) {
407     DEBUG1("SD_task_dependency_add: %s was ready and becomes scheduled!",
408            SD_task_get_name(dst));
409     __SD_task_set_state(dst, SD_SCHEDULED);
410   }
411
412   /*  __SD_print_dependencies(src);
413      __SD_print_dependencies(dst); */
414 }
415
416 /**
417  * \brief Indacates whether there is a dependency between two tasks.
418  *
419  * \param src a task
420  * \param dst a task depending on \a src
421  *
422  * If src is NULL, checks whether dst has any pre-dependency.
423  * If dst is NULL, checks whether src has any post-dependency.
424  */
425 int SD_task_dependency_exists(SD_task_t src, SD_task_t dst)
426 {
427   unsigned int counter;
428   SD_dependency_t dependency;
429
430   SD_CHECK_INIT_DONE();
431   xbt_assert0(src != NULL || dst != NULL, "Invalid parameter: both src and dst are NULL");
432
433   if (src) {
434     if (dst) {
435       xbt_dynar_foreach(src->tasks_after,counter,dependency) {
436         if (dependency->dst == dst)
437           return 1;
438       }
439     } else {
440       return xbt_dynar_length(src->tasks_after);
441     }
442   } else {
443     return xbt_dynar_length(dst->tasks_before);
444   }
445   return 0;
446 }
447
448 /**
449  * \brief Remove a dependency between two tasks
450  *
451  * \param src a task
452  * \param dst a task depending on \a src
453  * \see SD_task_dependency_add()
454  */
455 void SD_task_dependency_remove(SD_task_t src, SD_task_t dst)
456 {
457
458   xbt_dynar_t dynar;
459   int length;
460   int found = 0;
461   int i;
462   SD_dependency_t dependency;
463
464   SD_CHECK_INIT_DONE();
465   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
466
467   /* remove the dependency from src->tasks_after */
468   dynar = src->tasks_after;
469   length = xbt_dynar_length(dynar);
470
471   for (i = 0; i < length && !found; i++) {
472     xbt_dynar_get_cpy(dynar, i, &dependency);
473     if (dependency->dst == dst) {
474       xbt_dynar_remove_at(dynar, i, NULL);
475       found = 1;
476     }
477   }
478   if (!found)
479     THROW4(arg_error, 0,
480            "No dependency found between task '%s' and '%s': task '%s' is not a successor of task '%s'",
481            SD_task_get_name(src), SD_task_get_name(dst),
482            SD_task_get_name(dst), SD_task_get_name(src));
483
484   /* remove the dependency from dst->tasks_before */
485   dynar = dst->tasks_before;
486   length = xbt_dynar_length(dynar);
487   found = 0;
488
489   for (i = 0; i < length && !found; i++) {
490     xbt_dynar_get_cpy(dynar, i, &dependency);
491     if (dependency->src == src) {
492       xbt_dynar_remove_at(dynar, i, NULL);
493       __SD_task_dependency_destroy(dependency);
494       found = 1;
495     }
496   }
497   /* should never happen... */
498   xbt_assert4(found,
499               "SimDag error: task '%s' is a successor of '%s' but task '%s' is not a predecessor of task '%s'",
500               SD_task_get_name(dst), SD_task_get_name(src),
501               SD_task_get_name(src), SD_task_get_name(dst));
502
503   /* if the task was scheduled and dst->tasks_before is empty now, we can make it ready */
504   if (xbt_dynar_length(dst->tasks_before) == 0 && __SD_task_is_scheduled(dst))
505     __SD_task_set_state(dst, SD_READY);
506
507   /*  __SD_print_dependencies(src);
508      __SD_print_dependencies(dst); */
509 }
510
511 /**
512  * \brief Returns the user data associated with a dependency between two tasks
513  *
514  * \param src a task
515  * \param dst a task depending on \a src
516  * \return the user data associated with this dependency (can be \c NULL)
517  * \see SD_task_dependency_add()
518  */
519 void *SD_task_dependency_get_data(SD_task_t src, SD_task_t dst)
520 {
521
522   xbt_dynar_t dynar;
523   int length;
524   int found = 0;
525   int i;
526   SD_dependency_t dependency;
527
528
529   SD_CHECK_INIT_DONE();
530   xbt_assert0(src != NULL && dst != NULL, "Invalid parameter");
531
532   dynar = src->tasks_after;
533   length = xbt_dynar_length(dynar);
534
535   for (i = 0; i < length && !found; i++) {
536     xbt_dynar_get_cpy(dynar, i, &dependency);
537     found = (dependency->dst == dst);
538   }
539   if (!found)
540     THROW2(arg_error, 0, "No dependency found between task '%s' and '%s'",
541            SD_task_get_name(src), SD_task_get_name(dst));
542   return dependency->data;
543 }
544
545 /* temporary function for debugging */
546 static void __SD_print_watch_points(SD_task_t task)
547 {
548   static const int state_masks[] =
549     { SD_SCHEDULED, SD_RUNNING, SD_READY, SD_DONE, SD_FAILED };
550   static const char *state_names[] =
551     { "scheduled", "running", "ready", "done", "failed" };
552   int i;
553
554   INFO2("Task '%s' watch points (%x): ", SD_task_get_name(task),
555         task->watch_points);
556
557
558   for (i = 0; i < 5; i++) {
559     if (task->watch_points & state_masks[i])
560       INFO1("%s ", state_names[i]);
561   }
562 }
563
564 /**
565  * \brief Adds a watch point to a task
566  *
567  * SD_simulate() will stop as soon as the \ref e_SD_task_state_t "state" of this
568  * task becomes the one given in argument. The
569  * watch point is then automatically removed.
570  *
571  * \param task a task
572  * \param state the \ref e_SD_task_state_t "state" you want to watch
573  * (cannot be #SD_NOT_SCHEDULED)
574  * \see SD_task_unwatch()
575  */
576 void SD_task_watch(SD_task_t task, e_SD_task_state_t state)
577 {
578   SD_CHECK_INIT_DONE();
579   xbt_assert0(task != NULL, "Invalid parameter");
580
581   if (state & SD_NOT_SCHEDULED)
582     THROW0(arg_error, 0,
583            "Cannot add a watch point for state SD_NOT_SCHEDULED");
584
585   task->watch_points = task->watch_points | state;
586   /*  __SD_print_watch_points(task); */
587 }
588
589 /**
590  * \brief Removes a watch point from a task
591  *
592  * \param task a task
593  * \param state the \ref e_SD_task_state_t "state" you no longer want to watch
594  * \see SD_task_watch()
595  */
596 void SD_task_unwatch(SD_task_t task, e_SD_task_state_t state)
597 {
598   SD_CHECK_INIT_DONE();
599   xbt_assert0(task != NULL, "Invalid parameter");
600   xbt_assert0(state != SD_NOT_SCHEDULED,
601               "SimDag error: Cannot have a watch point for state SD_NOT_SCHEDULED");
602
603   task->watch_points = task->watch_points & ~state;
604   /*  __SD_print_watch_points(task); */
605 }
606
607 /**
608  * \brief Returns an approximative estimation of the execution time of a task.
609  *
610  * The estimation is very approximative because the value returned is the time
611  * the task would take if it was executed now and if it was the only task.
612  *
613  * \param task the task to evaluate
614  * \param workstation_nb number of workstations on which the task would be executed
615  * \param workstation_list the workstations on which the task would be executed
616  * \param computation_amount computation amount for each workstation
617  * \param communication_amount communication amount between each pair of workstations
618  * \param rate task execution speed rate
619  * \see SD_schedule()
620  */
621 double SD_task_get_execution_time(SD_task_t task,
622                                   int workstation_nb,
623                                   const SD_workstation_t * workstation_list,
624                                   const double *computation_amount,
625                                   const double *communication_amount,
626                                   double rate)
627 {
628   double time, max_time = 0.0;
629   int i, j;
630   SD_CHECK_INIT_DONE();
631   xbt_assert0(task != NULL && workstation_nb > 0 && workstation_list != NULL
632               && computation_amount != NULL
633               && communication_amount != NULL, "Invalid parameter");
634
635   /* the task execution time is the maximum execution time of the parallel tasks */
636
637   for (i = 0; i < workstation_nb; i++) {
638     time =
639       SD_workstation_get_computation_time(workstation_list[i],
640                                           computation_amount[i]);
641
642     for (j = 0; j < workstation_nb; j++) {
643       time +=
644         SD_route_get_communication_time(workstation_list[i],
645                                         workstation_list[j],
646                                         communication_amount[i *
647                                                              workstation_nb +
648                                                              j]);
649     }
650
651     if (time > max_time) {
652       max_time = time;
653     }
654   }
655   return max_time * SD_task_get_amount(task);
656 }
657 static inline void SD_task_do_schedule(SD_task_t task) {
658   SD_CHECK_INIT_DONE();
659
660    if (!__SD_task_is_not_scheduled(task))
661      THROW1(arg_error, 0, "Task '%s' has already been scheduled",
662             SD_task_get_name(task));
663
664  /* update the task state */
665   if (xbt_dynar_length(task->tasks_before) == 0)
666     __SD_task_set_state(task, SD_READY);
667   else
668     __SD_task_set_state(task, SD_SCHEDULED);
669 }
670
671 /**
672  * \brief Schedules a task
673  *
674  * The task state must be #SD_NOT_SCHEDULED.
675  * Once scheduled, a task will be executed as soon as possible in SD_simulate(),
676  * i.e. when its dependencies are satisfied.
677  *
678  * \param task the task you want to schedule
679  * \param workstation_nb number of workstations on which the task will be executed
680  * \param workstation_list the workstations on which the task will be executed
681  * \param computation_amount computation amount for each workstation
682  * \param communication_amount communication amount between each pair of workstations
683  * \param rate task execution speed rate
684  * \see SD_task_unschedule()
685  */
686 void SD_task_schedule(SD_task_t task, int workstation_count,
687                       const SD_workstation_t * workstation_list,
688                       const double *computation_amount,
689                       const double *communication_amount, double rate)
690 {
691   xbt_assert0(workstation_count > 0, "workstation_nb must be positive");
692
693   int communication_nb;
694
695   task->workstation_nb = workstation_count;
696   task->rate = rate;
697
698   task->computation_amount = xbt_new(double, workstation_count);
699   memcpy(task->computation_amount, computation_amount,
700          sizeof(double) * workstation_count);
701
702   communication_nb = workstation_count * workstation_count;
703   task->communication_amount = xbt_new(double, communication_nb);
704   memcpy(task->communication_amount, communication_amount,
705          sizeof(double) * communication_nb);
706
707   task->workstation_list = xbt_new(SD_workstation_t, workstation_count);
708   memcpy(task->workstation_list, workstation_list,
709          sizeof(SD_workstation_t) * workstation_count);
710
711   SD_task_do_schedule(task);
712 }
713 /**
714  * \brief Unschedules a task
715  *
716  * The task state must be #SD_SCHEDULED, #SD_READY, #SD_RUNNING or #SD_FAILED.
717  * If you call this function, the task state becomes #SD_NOT_SCHEDULED.
718  * Call SD_task_schedule() to schedule it again.
719  *
720  * \param task the task you want to unschedule
721  * \see SD_task_schedule()
722  */
723 void SD_task_unschedule(SD_task_t task)
724 {
725   SD_CHECK_INIT_DONE();
726   xbt_assert0(task != NULL, "Invalid parameter");
727
728   if (task->state_set != sd_global->scheduled_task_set &&
729       task->state_set != sd_global->ready_task_set &&
730       task->state_set != sd_global->running_task_set &&
731       task->state_set != sd_global->failed_task_set)
732     THROW1(arg_error, 0,
733            "Task %s: the state must be SD_SCHEDULED, SD_READY, SD_RUNNING or SD_FAILED",
734            SD_task_get_name(task));
735
736   if (__SD_task_is_scheduled_or_ready(task))    /* if the task is scheduled or ready */
737     __SD_task_destroy_scheduling_data(task);
738
739   if (__SD_task_is_running(task))       /* the task should become SD_FAILED */
740     surf_workstation_model->action_cancel(task->surf_action);
741   else
742     __SD_task_set_state(task, SD_NOT_SCHEDULED);
743   task->remains = task->amount;
744   task->start_time = -1.0;
745 }
746
747 /* Destroys the data memorised by SD_task_schedule. Task state must be SD_SCHEDULED or SD_READY.
748  */
749 static void __SD_task_destroy_scheduling_data(SD_task_t task)
750 {
751   SD_CHECK_INIT_DONE();
752   if (!__SD_task_is_scheduled_or_ready(task) && !__SD_task_is_in_fifo(task))
753     THROW1(arg_error, 0,
754            "Task '%s' must be SD_SCHEDULED, SD_READY or SD_IN_FIFO",
755            SD_task_get_name(task));
756
757   xbt_free(task->computation_amount);
758   xbt_free(task->communication_amount);
759 }
760
761 /* Runs a task. This function is directly called by __SD_task_try_to_run if the task
762  * doesn't have to wait in fifos. Otherwise, it is called by __SD_task_just_done when
763  * the task gets out of its fifos.
764  */
765 void __SD_task_really_run(SD_task_t task)
766 {
767
768   int i;
769   void **surf_workstations;
770
771   SD_CHECK_INIT_DONE();
772   xbt_assert0(task != NULL, "Invalid parameter");
773   xbt_assert2(__SD_task_is_ready_or_in_fifo(task),
774               "Task '%s' is not ready or in a fifo! Task state: %d",
775               SD_task_get_name(task), SD_task_get_state(task));
776   xbt_assert1(task->workstation_list != NULL,
777               "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
778
779
780
781   DEBUG1("Really running task '%s'", SD_task_get_name(task));
782
783   /* set this task as current task for the workstations in sequential mode */
784   for (i = 0; i < task->workstation_nb; i++) {
785     if (SD_workstation_get_access_mode(task->workstation_list[i]) ==
786         SD_WORKSTATION_SEQUENTIAL_ACCESS) {
787       task->workstation_list[i]->current_task = task;
788       xbt_assert0(__SD_workstation_is_busy(task->workstation_list[i]),
789                   "The workstation should be busy now");
790     }
791   }
792
793   DEBUG1("Task '%s' set as current task for its workstations",
794          SD_task_get_name(task));
795
796   /* start the task */
797
798   /* we have to create a Surf workstation array instead of the SimDag workstation array */
799   surf_workstations = xbt_new(void *, task->workstation_nb);
800
801   for (i = 0; i < task->workstation_nb; i++) {
802     surf_workstations[i] = task->workstation_list[i]->surf_workstation;
803   }
804
805   task->surf_action = NULL;
806   if ((task->workstation_nb == 1) && (task->communication_amount[0] == 0.0)) {
807     task->surf_action =
808       surf_workstation_model->extension.
809       workstation.execute(surf_workstations[0], task->computation_amount[0]);
810   } else if ((task->workstation_nb == 1)
811              && (task->computation_amount[0] == 0.0)) {
812     task->surf_action =
813       surf_workstation_model->extension.
814       workstation.communicate(surf_workstations[0], surf_workstations[0],
815                               task->communication_amount[0], task->rate);
816   } else if ((task->workstation_nb == 2)
817              && (task->computation_amount[0] == 0.0)
818              && (task->computation_amount[1] == 0.0)) {
819     int nb = 0;
820     double value = 0.0;
821
822     for (i = 0; i < task->workstation_nb * task->workstation_nb; i++) {
823       if (task->communication_amount[i] > 0.0) {
824         nb++;
825         value = task->communication_amount[i];
826       }
827     }
828     if (nb == 1) {
829       task->surf_action =
830         surf_workstation_model->extension.
831         workstation.communicate(surf_workstations[0], surf_workstations[1],
832                                 value, task->rate);
833     }
834   }
835   if (!task->surf_action) {
836     double *computation_amount = xbt_new(double, task->workstation_nb);
837     double *communication_amount = xbt_new(double, task->workstation_nb *
838                                            task->workstation_nb);
839
840     memcpy(computation_amount, task->computation_amount, sizeof(double) *
841            task->workstation_nb);
842     memcpy(communication_amount, task->communication_amount,
843            sizeof(double) * task->workstation_nb * task->workstation_nb);
844
845     task->surf_action =
846       surf_workstation_model->extension.
847       workstation.execute_parallel_task(task->workstation_nb,
848                                         surf_workstations, computation_amount,
849                                         communication_amount, task->amount,
850                                         task->rate);
851   } else {
852     xbt_free(surf_workstations);
853   }
854
855   surf_workstation_model->action_data_set(task->surf_action, task);
856
857   DEBUG1("surf_action = %p", task->surf_action);
858
859   __SD_task_destroy_scheduling_data(task);      /* now the scheduling data are not useful anymore */
860   __SD_task_set_state(task, SD_RUNNING);
861   xbt_assert2(__SD_task_is_running(task), "Bad state of task '%s': %d",
862               SD_task_get_name(task), SD_task_get_state(task));
863
864 }
865
866 /* Tries to run a task. This function is called by SD_simulate() when a scheduled task becomes SD_READY
867  * (ie when its dependencies are satisfied).
868  * If one of the workstations where the task is scheduled on is busy (in sequential mode),
869  * the task doesn't start.
870  * Returns whether the task has started.
871  */
872 int __SD_task_try_to_run(SD_task_t task)
873 {
874
875   int can_start = 1;
876   int i;
877   SD_workstation_t workstation;
878
879   SD_CHECK_INIT_DONE();
880   xbt_assert0(task != NULL, "Invalid parameter");
881   xbt_assert2(__SD_task_is_ready(task),
882               "Task '%s' is not ready! Task state: %d",
883               SD_task_get_name(task), SD_task_get_state(task));
884
885
886   for (i = 0; i < task->workstation_nb; i++) {
887     can_start = !__SD_workstation_is_busy(task->workstation_list[i]);
888   }
889
890   DEBUG2("Task '%s' can start: %d", SD_task_get_name(task), can_start);
891
892   if (!can_start) {             /* if the task cannot start and is not in the fifos yet */
893     for (i = 0; i < task->workstation_nb; i++) {
894       workstation = task->workstation_list[i];
895       if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
896         DEBUG2("Pushing task '%s' in the fifo of workstation '%s'",
897                SD_task_get_name(task), SD_workstation_get_name(workstation));
898         xbt_fifo_push(workstation->task_fifo, task);
899       }
900     }
901     __SD_task_set_state(task, SD_IN_FIFO);
902     xbt_assert2(__SD_task_is_in_fifo(task), "Bad state of task '%s': %d",
903                 SD_task_get_name(task), SD_task_get_state(task));
904     DEBUG1("Task '%s' state is now SD_IN_FIFO", SD_task_get_name(task));
905   } else {
906     __SD_task_really_run(task);
907   }
908
909   return can_start;
910 }
911
912 /* This function is called by SD_simulate when a task is done.
913  * It updates task->state and task->action and executes if necessary the tasks
914  * which were waiting in fifos for the end of `task'
915  */
916 void __SD_task_just_done(SD_task_t task)
917 {
918   int i, j;
919   SD_workstation_t workstation;
920
921   SD_task_t candidate;
922   int candidate_nb = 0;
923   int candidate_capacity = 8;
924   SD_task_t *candidates;
925   int can_start = 1;
926
927   SD_CHECK_INIT_DONE();
928   xbt_assert0(task != NULL, "Invalid parameter");
929   xbt_assert1(__SD_task_is_running(task),
930               "The task must be running! Task state: %d",
931               SD_task_get_state(task));
932   xbt_assert1(task->workstation_list != NULL,
933               "Task '%s': workstation_list is NULL!", SD_task_get_name(task));
934
935
936   candidates = xbt_new(SD_task_t, 8);
937
938   __SD_task_set_state(task, SD_DONE);
939   surf_workstation_model->action_unref(task->surf_action);
940   task->surf_action = NULL;
941
942   DEBUG0("Looking for candidates");
943
944   /* if the task was executed on sequential workstations,
945      maybe we can execute the next task of the fifo for each workstation */
946   for (i = 0; i < task->workstation_nb; i++) {
947     workstation = task->workstation_list[i];
948     DEBUG2("Workstation '%s': access_mode = %d",
949            SD_workstation_get_name(workstation), workstation->access_mode);
950     if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
951       xbt_assert1(workstation->task_fifo != NULL,
952                   "Workstation '%s' has sequential access but no fifo!",
953                   SD_workstation_get_name(workstation));
954       xbt_assert2(workstation->current_task =
955                   task, "Workstation '%s': current task should be '%s'",
956                   SD_workstation_get_name(workstation),
957                   SD_task_get_name(task));
958
959       /* the task is over so we can release the workstation */
960       workstation->current_task = NULL;
961
962       DEBUG0("Getting candidate in fifo");
963       candidate =
964         xbt_fifo_get_item_content(xbt_fifo_get_first_item
965                                   (workstation->task_fifo));
966
967       if (candidate != NULL) {
968         DEBUG1("Candidate: '%s'", SD_task_get_name(candidate));
969         xbt_assert2(__SD_task_is_in_fifo(candidate),
970                     "Bad state of candidate '%s': %d",
971                     SD_task_get_name(candidate),
972                     SD_task_get_state(candidate));
973       }
974
975       DEBUG1("Candidate in fifo: %p", candidate);
976
977       /* if there was a task waiting for my place */
978       if (candidate != NULL) {
979         /* Unfortunately, we are not sure yet that we can execute the task now,
980            because the task can be waiting more deeply in some other workstation's fifos...
981            So we memorize all candidate tasks, and then we will check for each candidate
982            whether or not all its workstations are available. */
983
984         /* realloc if necessary */
985         if (candidate_nb == candidate_capacity) {
986           candidate_capacity *= 2;
987           candidates =
988             xbt_realloc(candidates, sizeof(SD_task_t) * candidate_capacity);
989         }
990
991         /* register the candidate */
992         candidates[candidate_nb++] = candidate;
993         candidate->fifo_checked = 0;
994       }
995     }
996   }
997
998   DEBUG1("Candidates found: %d", candidate_nb);
999
1000   /* now we check every candidate task */
1001   for (i = 0; i < candidate_nb; i++) {
1002     candidate = candidates[i];
1003
1004     if (candidate->fifo_checked) {
1005       continue;                 /* we have already evaluated that task */
1006     }
1007
1008     xbt_assert2(__SD_task_is_in_fifo(candidate),
1009                 "Bad state of candidate '%s': %d",
1010                 SD_task_get_name(candidate), SD_task_get_state(candidate));
1011
1012     for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1013       workstation = candidate->workstation_list[j];
1014
1015       /* I can start on this workstation if the workstation is shared
1016          or if I am the first task in the fifo */
1017       can_start = workstation->access_mode == SD_WORKSTATION_SHARED_ACCESS ||
1018         candidate ==
1019         xbt_fifo_get_item_content(xbt_fifo_get_first_item
1020                                   (workstation->task_fifo));
1021     }
1022
1023     DEBUG2("Candidate '%s' can start: %d", SD_task_get_name(candidate),
1024            can_start);
1025
1026     /* now we are sure that I can start! */
1027     if (can_start) {
1028       for (j = 0; j < candidate->workstation_nb && can_start; j++) {
1029         workstation = candidate->workstation_list[j];
1030
1031         /* update the fifo */
1032         if (workstation->access_mode == SD_WORKSTATION_SEQUENTIAL_ACCESS) {
1033           candidate = xbt_fifo_shift(workstation->task_fifo);   /* the return value is stored just for debugging */
1034           DEBUG1("Head of the fifo: '%s'",
1035                  (candidate != NULL) ? SD_task_get_name(candidate) : "NULL");
1036           xbt_assert0(candidate == candidates[i],
1037                       "Error in __SD_task_just_done: bad first task in the fifo");
1038         }
1039       }                         /* for each workstation */
1040
1041       /* finally execute the task */
1042       DEBUG2("Task '%s' state: %d", SD_task_get_name(candidate),
1043              SD_task_get_state(candidate));
1044       __SD_task_really_run(candidate);
1045
1046       DEBUG4
1047         ("Calling __SD_task_is_running: task '%s', state set: %p, running_task_set: %p, is running: %d",
1048          SD_task_get_name(candidate), candidate->state_set,
1049          sd_global->running_task_set, __SD_task_is_running(candidate));
1050       xbt_assert2(__SD_task_is_running(candidate),
1051                   "Bad state of task '%s': %d", SD_task_get_name(candidate),
1052                   SD_task_get_state(candidate));
1053       DEBUG0("Okay, the task is running.");
1054
1055     }                           /* can start */
1056     candidate->fifo_checked = 1;
1057   }                             /* for each candidate */
1058
1059   xbt_free(candidates);
1060 }
1061
1062 /* Remove all dependencies associated with a task. This function is called when the task is destroyed.
1063  */
1064 static void __SD_task_remove_dependencies(SD_task_t task)
1065 {
1066   /* we must destroy the dependencies carefuly (with SD_dependency_remove)
1067      because each one is stored twice */
1068   SD_dependency_t dependency;
1069   while (xbt_dynar_length(task->tasks_before) > 0) {
1070     xbt_dynar_get_cpy(task->tasks_before, 0, &dependency);
1071     SD_task_dependency_remove(dependency->src, dependency->dst);
1072   }
1073
1074   while (xbt_dynar_length(task->tasks_after) > 0) {
1075     xbt_dynar_get_cpy(task->tasks_after, 0, &dependency);
1076     SD_task_dependency_remove(dependency->src, dependency->dst);
1077   }
1078 }
1079
1080 /**
1081  * \brief Returns the start time of a task
1082  *
1083  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1084  *
1085  * \param task: a task
1086  * \return the start time of this task
1087  */
1088 double SD_task_get_start_time(SD_task_t task)
1089 {
1090   SD_CHECK_INIT_DONE();
1091   xbt_assert0(task != NULL, "Invalid parameter");
1092   if (task->surf_action)
1093     return surf_workstation_model->action_get_start_time(task->surf_action);
1094   else
1095     return task->start_time;
1096 }
1097
1098 /**
1099  * \brief Returns the finish time of a task
1100  *
1101  * The task state must be SD_RUNNING, SD_DONE or SD_FAILED.
1102  * If the state is not completed yet, the returned value is an
1103  * estimation of the task finish time. This value can fluctuate
1104  * until the task is completed.
1105  *
1106  * \param task: a task
1107  * \return the start time of this task
1108  */
1109 double SD_task_get_finish_time(SD_task_t task)
1110 {
1111   SD_CHECK_INIT_DONE();
1112   xbt_assert0(task != NULL, "Invalid parameter");
1113
1114   if (task->surf_action)        /* should never happen as actions are destroyed right after their completion */
1115     return surf_workstation_model->action_get_finish_time(task->surf_action);
1116   else
1117     return task->finish_time;
1118 }
1119
1120 /**
1121  * \brief Destroys a task.
1122  *
1123  * The user data (if any) should have been destroyed first.
1124  *
1125  * \param task the task you want to destroy
1126  * \see SD_task_create()
1127  */
1128 void SD_task_destroy(SD_task_t task)
1129 {
1130   SD_CHECK_INIT_DONE();
1131   xbt_assert0(task != NULL, "Invalid parameter");
1132
1133   DEBUG1("Destroying task %s...", SD_task_get_name(task));
1134
1135   __SD_task_remove_dependencies(task);
1136
1137   /* if the task was scheduled or ready we have to free the scheduling parameters */
1138   if (__SD_task_is_scheduled_or_ready(task))
1139     __SD_task_destroy_scheduling_data(task);
1140
1141   if (task->name != NULL)
1142     xbt_free(task->name);
1143
1144   if (task->surf_action != NULL)
1145     surf_workstation_model->action_unref(task->surf_action);
1146
1147   if (task->workstation_list != NULL)
1148     xbt_free(task->workstation_list);
1149
1150   xbt_dynar_free(&task->tasks_before);
1151   xbt_dynar_free(&task->tasks_after);
1152   xbt_free(task);
1153
1154   sd_global->task_number--;
1155
1156   DEBUG0("Task destroyed.");
1157 }
1158
1159
1160 static inline SD_task_t SD_task_create_sized(const char*name,void*data,double amount,int ws_count) {
1161   SD_task_t task = SD_task_create(name,data,amount);
1162   task->communication_amount = xbt_new0(double,ws_count*ws_count);
1163   task->computation_amount = xbt_new0(double,ws_count);
1164   task->workstation_nb = ws_count;
1165   task->workstation_list = xbt_new0(SD_workstation_t,ws_count);
1166   return task;
1167 }
1168 /** @brief create a end-to-end communication task that can then be auto-scheduled
1169  *
1170  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1171  * allows to specify the task costs at creation, and decorelate them from the
1172  * scheduling process where you just specify which resource should deliver the
1173  * mandatory power.
1174  *
1175  * A end-to-end communication must be scheduled on 2 hosts, and the amount
1176  * specified at creation is sent from hosts[0] to hosts[1].
1177  */
1178 SD_task_t SD_task_create_comm_e2e(const char*name, void *data, double amount) {
1179   SD_task_t res = SD_task_create_sized(name,data,0,2);
1180   res->communication_amount[1] = amount;
1181   res->kind=SD_TASK_COMM_E2E;
1182   return res;
1183 }
1184 /** @brief create a sequential computation task that can then be auto-scheduled
1185  *
1186  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1187  * allows to specify the task costs at creation, and decorelate them from the
1188  * scheduling process where you just specify which resource should deliver the
1189  * mandatory power.
1190  *
1191  * A sequential computation must be scheduled on 1 host, and the amount
1192  * specified at creation to be run on hosts[0].
1193  */
1194 SD_task_t SD_task_create_comp_seq(const char*name, void *data, double amount) {
1195   SD_task_t res = SD_task_create_sized(name,data,0,1);
1196   res->computation_amount[0]=amount;
1197   res->kind=SD_TASK_COMP_SEQ;
1198   return res;
1199 }
1200
1201 /** @brief Auto-schedules a task.
1202  *
1203  * Auto-scheduling mean that the task can be used with SD_task_schedulev(). This
1204  * allows to specify the task costs at creation, and decorelate them from the
1205  * scheduling process where you just specify which resource should deliver the
1206  * mandatory power.
1207  *
1208  * To be auto-schedulable, a task must be created with SD_task_create_comm_e2e() or
1209  * SD_task_create_comp_seq(). Check their definitions for the exact semantic of each
1210  * of them.
1211  *
1212  * @todo
1213  * We should create tasks kind for the following categories:
1214  *  - Point to point communication (done)
1215  *  - Sequential computation       (done)
1216  *  - group communication (redistribution, several kinds)
1217  *  - parallel tasks with no internal communication (one kind per speedup model such as amdal)
1218  *  - idem+ internal communication. Task type not enough since we cannot store comm cost alongside to comp one)
1219  */
1220 void SD_task_schedulev(SD_task_t task, int count, const SD_workstation_t*list) {
1221   int i;
1222   xbt_assert1(task->kind != 0,"Task %s is not typed. Cannot automatically schedule it.",SD_task_get_name(task));
1223   switch(task->kind) {
1224   case SD_TASK_COMM_E2E:
1225   case SD_TASK_COMP_SEQ:
1226     xbt_assert(task->workstation_nb==count);
1227     for (i=0;i<count;i++)
1228       task->workstation_list[i]=list[i];
1229     SD_task_do_schedule(task);
1230     break;
1231   default:
1232     xbt_die(bprintf("Kind of task %s not supported by SD_task_schedulev()",
1233           SD_task_get_name(task)));
1234   }
1235 }
1236 /** @brief autoschedule a task on a list of workstations
1237  *
1238  * This function is very similar to SD_task_schedulev(),
1239  * but takes the list of workstations to schedule onto as separate parameters.
1240  * It builds a proper vector of workstations and then call SD_task_schedulev()
1241  */
1242 void SD_task_schedulel(SD_task_t task, int count, ...) {
1243   va_list ap;
1244   SD_workstation_t *list=xbt_new(SD_workstation_t,count);
1245   int i;
1246   va_start(ap,count);
1247   for (i=0;i<count;i++) {
1248       list[i] = va_arg(ap,SD_workstation_t);
1249   }
1250   va_end(ap);
1251   SD_task_schedulev(task,count,list);
1252   free(list);
1253 }