Logo AND Algorithmique Numérique Distribuée

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