Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Add dsend_bounded send_with_timeout_bounded
[simgrid.git] / src / simdag / sd_dotloader.c
1 /* Copyright (c) 2009-2013. The SimGrid Team.
2  * All rights reserved.                                                     */
3
4 /* This program is free software; you can redistribute it and/or modify it
5  * under the terms of the license (GNU LGPL) which comes with this package. */
6
7 #include "private.h"
8 #include "simdag/simdag.h"
9 #include "xbt/misc.h"
10 #include "xbt/log.h"
11 #include <stdbool.h>
12 #include <string.h>
13 #include <libgen.h>
14
15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_dotparse, sd, "Parsing DOT files");
16
17 #undef CLEANUP
18
19 #ifdef HAVE_CGRAPH_H
20 #include <graphviz/cgraph.h>
21 #elif HAVE_AGRAPH_H
22 #include <graphviz/agraph.h>
23 #define agnxtnode(dot, node)    agnxtnode(node)
24 #define agfstin(dot, node)      agfstin(node)
25 #define agnxtin(dot, edge)      agnxtin(edge)
26 #define agfstout(dot, node)     agfstout(node)
27 #define agnxtout(dot, edge)     agnxtout(edge)
28 #endif
29
30 typedef enum {
31   sequential =0,
32   parallel
33 } seq_par_t;
34
35 void dot_add_task(Agnode_t * dag_node);
36 void dot_add_parallel_task(Agnode_t * dag_node);
37 void dot_add_input_dependencies(SD_task_t current_job, Agedge_t * edge,
38                                 seq_par_t seq_or_par);
39 void dot_add_output_dependencies(SD_task_t current_job, Agedge_t * edge,
40                                  seq_par_t seq_or_par);
41 xbt_dynar_t SD_dotload_generic(const char * filename);
42
43 static double dot_parse_double(const char *string)
44 {
45   if (string == NULL)
46     return -1;
47   double value = -1;
48   char *err;
49
50   //ret = sscanf(string, "%lg", &value);
51   errno = 0;
52   value = strtod(string,&err);
53   if(errno)
54   {
55     XBT_WARN("Failed to convert string to double: %s\n",strerror(errno));
56     return -1;
57   }
58   return value;
59 }
60
61
62 static int dot_parse_int(const char *string)
63 {
64   if (string == NULL)
65     return -10;
66   int ret = 0;
67   int value = -1;
68
69   ret = sscanf(string, "%d", &value);
70   if (ret != 1)
71     XBT_WARN("%s is not an integer", string);
72   return value;
73 }
74
75 static xbt_dynar_t result;
76 static xbt_dict_t jobs;
77 static xbt_dict_t files;
78 static xbt_dict_t computers;
79 static SD_task_t root_task, end_task;
80 static Agraph_t *dag_dot;
81 static bool schedule = true;
82
83 static void dump_res()
84 {
85   unsigned int cursor;
86   SD_task_t task;
87   xbt_dynar_foreach(result, cursor, task) {
88     XBT_INFO("Task %d", cursor);
89     SD_task_dump(task);
90   }
91 }
92
93
94 static void dot_task_free(void *task)
95 {
96   SD_task_t t = task;
97   SD_task_destroy(t);
98 }
99
100 static void dot_task_p_free(void *task)
101 {
102   SD_task_t *t = task;
103   SD_task_destroy(*t);
104 }
105
106 static void TRACE_sd_dotloader (SD_task_t task, const char *category)
107 {
108   if (category){
109     if (strlen (category) != 0){
110       TRACE_category (category);
111       SD_task_set_category (task, category);
112     }
113   }
114 }
115
116 /** @brief loads a DOT file describing a DAG
117  * 
118  * See http://www.graphviz.org/doc/info/lang.html
119  * for more details.
120  * To obtain information about transfers and tasks, two attributes are
121  * required : size on task (execution time in Flop) and size on edge
122  * (the amount of data transfer in bit).
123  * if they aren't here, there choose to be equal to zero.
124  */
125 xbt_dynar_t SD_dotload(const char *filename)
126 {
127   SD_dotload_generic(filename);
128   xbt_dynar_t computer = NULL;
129   xbt_dict_cursor_t dict_cursor;
130   char *computer_name;
131   xbt_dict_foreach(computers,dict_cursor,computer_name,computer){
132     xbt_dynar_free(&computer);
133   }
134   xbt_dict_free(&computers);
135   return result;
136 }
137
138 xbt_dynar_t SD_dotload_with_sched(const char *filename){
139   SD_dotload_generic(filename);
140
141   if(schedule == true){
142     xbt_dynar_t computer = NULL;
143     xbt_dict_cursor_t dict_cursor;
144     char *computer_name;
145     const SD_workstation_t *workstations = SD_workstation_get_list ();
146     xbt_dict_foreach(computers,dict_cursor,computer_name,computer){
147       int count_computer = dot_parse_int(computer_name);
148       unsigned int count=0;
149       SD_task_t task;
150       SD_task_t task_previous = NULL;
151       xbt_dynar_foreach(computer,count,task){
152         // add dependency between the previous and the task to avoid
153         // parallel execution
154         if(task != NULL ){
155           if(task_previous != NULL &&
156              !SD_task_dependency_exists(task_previous, task))
157             SD_task_dependency_add(NULL, NULL, task_previous, task);
158           SD_task_schedulel(task, 1, workstations[count_computer]);
159           task_previous = task;
160         }
161       }
162       xbt_dynar_free(&computer);
163     }
164     xbt_dict_free(&computers);
165     if(acyclic_graph_detail(result))
166       return result;
167     else
168       XBT_WARN("There is at least one cycle in the provided task graph");
169   }else{
170     XBT_WARN("The scheduling is ignored");
171   }
172   SD_task_t task;
173   unsigned int count;
174   xbt_dynar_t computer = NULL;
175   xbt_dict_cursor_t dict_cursor;
176   char *computer_name;
177   xbt_dict_foreach(computers,dict_cursor,computer_name,computer){
178     xbt_dynar_free(&computer);
179   }
180   xbt_dict_free(&computers);
181   xbt_dynar_foreach(result,count,task){
182      SD_task_destroy(task);
183   }
184   return NULL;
185 }
186
187 xbt_dynar_t SD_PTG_dotload(const char * filename)
188 {
189   xbt_assert(filename, "Unable to use a null file descriptor\n");
190   FILE *in_file = fopen(filename, "r");
191   dag_dot = agread(in_file, NIL(Agdisc_t *));
192
193   result = xbt_dynar_new(sizeof(SD_task_t), dot_task_p_free);
194   files = xbt_dict_new_homogeneous(&dot_task_free);
195   jobs = xbt_dict_new_homogeneous(NULL);
196   computers = xbt_dict_new_homogeneous(NULL);
197   root_task = SD_task_create_comp_par_amdahl("root", NULL, 0., 0.);
198   /* by design the root task is always SCHEDULABLE */
199   __SD_task_set_state(root_task, SD_SCHEDULABLE);
200
201   xbt_dict_set(jobs, "root", root_task, NULL);
202   xbt_dynar_push(result, &root_task);
203   end_task = SD_task_create_comp_par_amdahl("end", NULL, 0., 0.);
204   xbt_dict_set(jobs, "end", end_task, NULL);
205
206   Agnode_t *dag_node = NULL;
207   for (dag_node = agfstnode(dag_dot); dag_node; dag_node = agnxtnode(dag_dot, dag_node)) {
208     dot_add_parallel_task(dag_node);
209   }
210   agclose(dag_dot);
211   xbt_dict_free(&jobs);
212
213   /* And now, post-process the files.
214    * We want a file task per pair of computation tasks exchanging the file. Duplicate on need
215    * Files not produced in the system are said to be produced by root task (top of DAG).
216    * Files not consumed in the system are said to be consumed by end task (bottom of DAG).
217    */
218   xbt_dict_cursor_t cursor;
219   SD_task_t file;
220   char *name;
221   xbt_dict_foreach(files, cursor, name, file) {
222     unsigned int cpt1, cpt2;
223     SD_task_t newfile = NULL;
224     SD_dependency_t depbefore, depafter;
225     if (xbt_dynar_is_empty(file->tasks_before)) {
226       xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
227         SD_task_t newfile =
228             SD_task_create_comm_par_mxn_1d_block(file->name, NULL, file->amount);
229         SD_task_dependency_add(NULL, NULL, root_task, newfile);
230         SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
231         xbt_dynar_push(result, &newfile);
232       }
233     } else if (xbt_dynar_is_empty(file->tasks_after)) {
234       xbt_dynar_foreach(file->tasks_before, cpt2, depbefore) {
235         SD_task_t newfile =
236             SD_task_create_comm_par_mxn_1d_block(file->name, NULL, file->amount);
237         SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
238         SD_task_dependency_add(NULL, NULL, newfile, end_task);
239         xbt_dynar_push(result, &newfile);
240       }
241     } else {
242       xbt_dynar_foreach(file->tasks_before, cpt1, depbefore) {
243         xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
244           if (depbefore->src == depafter->dst) {
245             XBT_WARN
246                 ("File %s is produced and consumed by task %s. This loop dependency will prevent the execution of the task.",
247                  file->name, depbefore->src->name);
248           }
249           newfile =
250               SD_task_create_comm_par_mxn_1d_block(file->name, NULL, file->amount);
251           SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
252           SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
253           xbt_dynar_push(result, &newfile);
254         }
255       }
256     }
257   }
258
259   /* Push end task last */
260   xbt_dynar_push(result, &end_task);
261
262   /* Free previous copy of the files */
263   xbt_dict_free(&files);
264   xbt_dict_free(&computers);
265   fclose(in_file);
266   if (!acyclic_graph_detail(result)) {
267     XBT_ERROR("The DOT described in %s is not a DAG. It contains a cycle.",
268               basename((char*)filename));
269     xbt_dynar_free(&result);
270     /* (result == NULL) here */
271   }
272   return result;
273 }
274
275
276 xbt_dynar_t SD_dotload_generic(const char * filename)
277 {
278   xbt_assert(filename, "Unable to use a null file descriptor\n");
279   //dag_dot =  agopen((char*)filename,Agstrictdirected,0);
280   FILE *in_file = fopen(filename, "r");
281   dag_dot = agread(in_file, NIL(Agdisc_t *));
282
283   result = xbt_dynar_new(sizeof(SD_task_t), dot_task_p_free);
284   files = xbt_dict_new_homogeneous(&dot_task_free);
285   jobs = xbt_dict_new_homogeneous(NULL);
286   computers = xbt_dict_new_homogeneous(NULL);
287   root_task = SD_task_create_comp_seq("root", NULL, 0);
288   /* by design the root task is always SCHEDULABLE */
289   __SD_task_set_state(root_task, SD_SCHEDULABLE);
290
291   xbt_dict_set(jobs, "root", root_task, NULL);
292   xbt_dynar_push(result, &root_task);
293   end_task = SD_task_create_comp_seq("end", NULL, 0);
294   xbt_dict_set(jobs, "end", end_task, NULL);
295
296   Agnode_t *dag_node = NULL;
297   for (dag_node = agfstnode(dag_dot); dag_node; dag_node = agnxtnode(dag_dot, dag_node)) {
298     dot_add_task(dag_node);
299   }
300   agclose(dag_dot);
301   xbt_dict_free(&jobs);
302
303   /* And now, post-process the files.
304    * We want a file task per pair of computation tasks exchanging the file. Duplicate on need
305    * Files not produced in the system are said to be produced by root task (top of DAG).
306    * Files not consumed in the system are said to be consumed by end task (bottom of DAG).
307    */
308   xbt_dict_cursor_t cursor;
309   SD_task_t file;
310   char *name;
311   xbt_dict_foreach(files, cursor, name, file) {
312     unsigned int cpt1, cpt2;
313     SD_task_t newfile = NULL;
314     SD_dependency_t depbefore, depafter;
315     if (xbt_dynar_is_empty(file->tasks_before)) {
316       xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
317         SD_task_t newfile =
318             SD_task_create_comm_e2e(file->name, NULL, file->amount);
319         SD_task_dependency_add(NULL, NULL, root_task, newfile);
320         SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
321         xbt_dynar_push(result, &newfile);
322       }
323     } else if (xbt_dynar_is_empty(file->tasks_after)) {
324       xbt_dynar_foreach(file->tasks_before, cpt2, depbefore) {
325         SD_task_t newfile =
326             SD_task_create_comm_e2e(file->name, NULL, file->amount);
327         SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
328         SD_task_dependency_add(NULL, NULL, newfile, end_task);
329         xbt_dynar_push(result, &newfile);
330       }
331     } else {
332       xbt_dynar_foreach(file->tasks_before, cpt1, depbefore) {
333         xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
334           if (depbefore->src == depafter->dst) {
335             XBT_WARN
336                 ("File %s is produced and consumed by task %s. This loop dependency will prevent the execution of the task.",
337                  file->name, depbefore->src->name);
338           }
339           newfile =
340               SD_task_create_comm_e2e(file->name, NULL, file->amount);
341           SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
342           SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
343           xbt_dynar_push(result, &newfile);
344         }
345       }
346     }
347   }
348
349   /* Push end task last */
350   xbt_dynar_push(result, &end_task);
351
352   /* Free previous copy of the files */
353   xbt_dict_free(&files);
354   fclose(in_file);
355   if (!acyclic_graph_detail(result)) {
356     XBT_ERROR("The DOT described in %s is not a DAG. It contains a cycle.",
357               basename((char*)filename));
358     xbt_dynar_free(&result);
359     /* (result == NULL) here */
360   }
361   return result;
362 }
363
364 /* dot_add_parallel_task create a sd_task of SD_TASK_COMP_PAR_AMDHAL type and
365  * all transfers required for this task. The execution time of the task is
366  * given by the attribute size. The unit of size is the Flop.*/
367 void dot_add_parallel_task(Agnode_t * dag_node)
368 {
369   char *name = agnameof(dag_node);
370   SD_task_t current_job;
371   double amount = dot_parse_double(agget(dag_node, (char *) "size"));
372   double alpha = dot_parse_double(agget(dag_node, (char *) "alpha"));
373
374   if (alpha == -1.)
375     alpha = 0.0;
376
377   XBT_DEBUG("See <job id=%s amount=%s %.0f alpha=%.2f>", name,
378         agget(dag_node, (char *) "size"), amount, alpha);
379   current_job = xbt_dict_get_or_null(jobs, name);
380   if (current_job == NULL) {
381     current_job =
382         SD_task_create_comp_par_amdahl(name, NULL , amount, alpha);
383 #ifdef HAVE_TRACING
384    TRACE_sd_dotloader (current_job, agget (dag_node, (char*)"category"));
385 #endif
386     xbt_dict_set(jobs, name, current_job, NULL);
387     xbt_dynar_push(result, &current_job);
388   }
389   Agedge_t *e;
390   int count = 0;
391
392   for (e = agfstin(dag_dot, dag_node); e; e = agnxtin(dag_dot, e)) {
393     dot_add_input_dependencies(current_job, e, parallel);
394     count++;
395   }
396   if (count == 0 && current_job != root_task) {
397     SD_task_dependency_add(NULL, NULL, root_task, current_job);
398   }
399   count = 0;
400   for (e = agfstout(dag_dot, dag_node); e; e = agnxtout(dag_dot, e)) {
401     dot_add_output_dependencies(current_job, e, parallel);
402     count++;
403   }
404   if (count == 0 && current_job != end_task) {
405     SD_task_dependency_add(NULL, NULL, current_job, end_task);
406   }
407 }
408
409 /* dot_add_task create a sd_task and all transfers required for this
410  * task. The execution time of the task is given by the attribute size.
411  * The unit of size is the Flop.*/
412 void dot_add_task(Agnode_t * dag_node)
413 {
414   char *name = agnameof(dag_node);
415   SD_task_t current_job;
416   double runtime = dot_parse_double(agget(dag_node, (char *) "size"));
417
418   XBT_DEBUG("See <job id=%s runtime=%s %.0f>", name,
419         agget(dag_node, (char *) "size"), runtime);
420   current_job = xbt_dict_get_or_null(jobs, name);
421   if (current_job == NULL) {
422     current_job =
423         SD_task_create_comp_seq(name, NULL , runtime);
424 #ifdef HAVE_TRACING
425    TRACE_sd_dotloader (current_job, agget (dag_node, (char*)"category"));
426 #endif
427     xbt_dict_set(jobs, name, current_job, NULL);
428     xbt_dynar_push(result, &current_job);
429   }
430   Agedge_t *e;
431   int count = 0;
432
433   for (e = agfstin(dag_dot, dag_node); e; e = agnxtin(dag_dot, e)) {
434     dot_add_input_dependencies(current_job, e, sequential);
435     count++;
436   }
437   if (count == 0 && current_job != root_task) {
438     SD_task_dependency_add(NULL, NULL, root_task, current_job);
439   }
440   count = 0;
441   for (e = agfstout(dag_dot, dag_node); e; e = agnxtout(dag_dot, e)) {
442     dot_add_output_dependencies(current_job, e, sequential);
443     count++;
444   }
445   if (count == 0 && current_job != end_task) {
446     SD_task_dependency_add(NULL, NULL, current_job, end_task);
447   }
448
449   if(schedule || XBT_LOG_ISENABLED(sd_dotparse, xbt_log_priority_verbose)){
450     /* try to take the information to schedule the task only if all is
451      * right*/
452     // performer is the computer which execute the task
453     unsigned long performer = -1;
454     char * char_performer = agget(dag_node, (char *) "performer");
455     if (char_performer != NULL)
456       performer = (long) dot_parse_int(char_performer);
457
458     // order is giving the task order on one computer
459     unsigned long order = -1;
460     char * char_order = agget(dag_node, (char *) "order");
461     if (char_order != NULL)
462       order = (long) dot_parse_int(char_order);
463     xbt_dynar_t computer = NULL;
464     //XBT_INFO("performer = %d, order=%d",performer,order);
465     if(performer != -1 && order != -1){
466       //necessary parameters are given
467       computer = xbt_dict_get_or_null(computers, char_performer);
468       if(computer == NULL){
469         computer = xbt_dynar_new(sizeof(SD_task_t), NULL);
470         xbt_dict_set(computers, char_performer, computer, NULL);
471       }
472       if(performer < xbt_lib_length(host_lib)){
473         // the  wanted computer is available
474         SD_task_t *task_test = NULL;
475         if(order < computer->used)
476           task_test = xbt_dynar_get_ptr(computer,order);
477         if(task_test != NULL && *task_test != NULL && *task_test != current_job){
478           /*the user gives the same order to several tasks*/
479           schedule = false;
480           XBT_VERB("The task %s starts on the computer %s at the position : %s like the task %s",
481                  (*task_test)->name, char_performer, char_order, current_job->name);
482         }else{
483           //the parameter seems to be ok
484           xbt_dynar_set_as(computer, order, SD_task_t, current_job);
485         }
486       }else{
487         /*the platform has not enough processors to schedule the DAG like
488         *the user wants*/
489         schedule = false;
490         XBT_VERB("The schedule is ignored, there are not enough computers");
491       }
492     }
493     else {
494       //one of necessary parameters are not given
495       schedule = false;
496       XBT_VERB("The schedule is ignored, the task %s is not correctly scheduled", current_job->name);
497     }
498   }
499 }
500
501 /* dot_add_output_dependencies create the dependencies between a task
502  * and a transfers. This is given by the edges in the dot file. 
503  * The amount of data transfers is given by the attribute size on the
504  * edge. */
505 void dot_add_input_dependencies(SD_task_t current_job, Agedge_t * edge,
506                                 seq_par_t seq_or_par)
507 {
508   SD_task_t file = NULL;
509   char *name_tail=agnameof(agtail(edge));
510   char *name_head=agnameof(aghead(edge));
511   char *name = xbt_malloc((strlen(name_head)+strlen(name_tail)+6)*sizeof(char));
512   sprintf(name, "%s->%s", name_tail, name_head);
513   double size = dot_parse_double(agget(edge, (char *) "size"));
514   XBT_DEBUG("size : %e, get size : %s", size, agget(edge, (char *) "size"));
515
516   if (size > 0) {
517     file = xbt_dict_get_or_null(files, name);
518     if (file == NULL) {
519       if (seq_or_par == sequential){
520           file = SD_task_create_comm_e2e(name, NULL, size);
521       } else {
522           file = SD_task_create_comm_par_mxn_1d_block(name, NULL, size);
523       }
524 #ifdef HAVE_TRACING
525       TRACE_sd_dotloader (file, agget (edge, (char*)"category"));
526 #endif
527       xbt_dict_set(files, name, file, NULL);
528     } else {
529       if (SD_task_get_amount(file) != size) {
530         XBT_WARN("Ignoring file %s size redefinition from %.0f to %.0f",
531               name, SD_task_get_amount(file), size);
532       }
533     }
534     SD_task_dependency_add(NULL, NULL, file, current_job);
535   } else {
536     file = xbt_dict_get_or_null(jobs, name_tail);
537     if (file != NULL) {
538       SD_task_dependency_add(NULL, NULL, file, current_job);
539     }
540   }
541   free(name);
542 }
543
544 /* dot_add_output_dependencies create the dependencies between a
545  * transfers and a task. This is given by the edges in the dot file.
546  * The amount of data transfers is given by the attribute size on the
547  * edge. */
548 void dot_add_output_dependencies(SD_task_t current_job, Agedge_t * edge,
549                                  seq_par_t seq_or_par){
550   SD_task_t file;
551   char *name_tail=agnameof(agtail(edge));
552   char *name_head=agnameof(aghead(edge));
553   char *name = xbt_malloc((strlen(name_head)+strlen(name_tail)+6)*sizeof(char));
554   sprintf(name, "%s->%s", name_tail, name_head);
555   double size = dot_parse_double(agget(edge, (char *) "size"));
556   XBT_DEBUG("size : %e, get size : %s", size, agget(edge, (char *) "size"));
557
558   if (size > 0) {
559     file = xbt_dict_get_or_null(files, name);
560     if (file == NULL) {
561       if (seq_or_par == sequential){
562           file = SD_task_create_comm_e2e(name, NULL, size);
563       } else {
564           file = SD_task_create_comm_par_mxn_1d_block(name, NULL, size);
565       }
566 #ifdef HAVE_TRACING
567       TRACE_sd_dotloader (file, agget (edge, (char*)"category"));
568 #endif
569       xbt_dict_set(files, name, file, NULL);
570     } else {
571       if (SD_task_get_amount(file) != size) {
572         XBT_WARN("Ignoring file %s size redefinition from %.0f to %.0f",
573               name, SD_task_get_amount(file), size);
574       }
575     }
576     SD_task_dependency_add(NULL, NULL, current_job, file);
577     if (xbt_dynar_length(file->tasks_before) > 1) {
578       XBT_WARN("File %s created at more than one location...", file->name);
579     }
580   } else {
581     file = xbt_dict_get_or_null(jobs, name_head);
582     if (file != NULL) {
583       SD_task_dependency_add(NULL, NULL, current_job, file);
584     }
585   }
586   free(name);
587 }