Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Warn the user that declaring explicitly 'root' and/or 'end' task in
[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 && strlen (category)){
109     if (task->category)
110       XBT_DEBUG("Change the category of %s from %s to %s",
111           task->name, task->category, category);
112     else
113       XBT_DEBUG("Set the category of %s to %s",task->name, category);
114     TRACE_category (category);
115     TRACE_sd_set_task_category(task, category);
116   }
117 }
118
119 /** @brief loads a DOT file describing a DAG
120  * 
121  * See http://www.graphviz.org/doc/info/lang.html
122  * for more details.
123  * To obtain information about transfers and tasks, two attributes are
124  * required : size on task (execution time in Flop) and size on edge
125  * (the amount of data transfer in bit).
126  * if they aren't here, there choose to be equal to zero.
127  */
128 xbt_dynar_t SD_dotload(const char *filename)
129 {
130   SD_dotload_generic(filename);
131   xbt_dynar_t computer = NULL;
132   xbt_dict_cursor_t dict_cursor;
133   char *computer_name;
134   xbt_dict_foreach(computers,dict_cursor,computer_name,computer){
135     xbt_dynar_free(&computer);
136   }
137   xbt_dict_free(&computers);
138   return result;
139 }
140
141 xbt_dynar_t SD_dotload_with_sched(const char *filename){
142   SD_dotload_generic(filename);
143
144   if(schedule == true){
145     xbt_dynar_t computer = NULL;
146     xbt_dict_cursor_t dict_cursor;
147     char *computer_name;
148     const SD_workstation_t *workstations = SD_workstation_get_list ();
149     xbt_dict_foreach(computers,dict_cursor,computer_name,computer){
150       int count_computer = dot_parse_int(computer_name);
151       unsigned int count=0;
152       SD_task_t task;
153       SD_task_t task_previous = NULL;
154       xbt_dynar_foreach(computer,count,task){
155         // add dependency between the previous and the task to avoid
156         // parallel execution
157         if(task != NULL ){
158           if(task_previous != NULL &&
159              !SD_task_dependency_exists(task_previous, task))
160             SD_task_dependency_add(NULL, NULL, task_previous, task);
161           SD_task_schedulel(task, 1, workstations[count_computer]);
162           task_previous = task;
163         }
164       }
165       xbt_dynar_free(&computer);
166     }
167     xbt_dict_free(&computers);
168     if(acyclic_graph_detail(result))
169       return result;
170     else
171       XBT_WARN("There is at least one cycle in the provided task graph");
172   }else{
173     XBT_WARN("The scheduling is ignored");
174   }
175   SD_task_t task;
176   unsigned int count;
177   xbt_dynar_t computer = NULL;
178   xbt_dict_cursor_t dict_cursor;
179   char *computer_name;
180   xbt_dict_foreach(computers,dict_cursor,computer_name,computer){
181     xbt_dynar_free(&computer);
182   }
183   xbt_dict_free(&computers);
184   xbt_dynar_foreach(result,count,task){
185      SD_task_destroy(task);
186   }
187   return NULL;
188 }
189
190 xbt_dynar_t SD_PTG_dotload(const char * filename)
191 {
192   xbt_assert(filename, "Unable to use a null file descriptor\n");
193   FILE *in_file = fopen(filename, "r");
194   dag_dot = agread(in_file, NIL(Agdisc_t *));
195
196   result = xbt_dynar_new(sizeof(SD_task_t), dot_task_p_free);
197   files = xbt_dict_new_homogeneous(&dot_task_free);
198   jobs = xbt_dict_new_homogeneous(NULL);
199   computers = xbt_dict_new_homogeneous(NULL);
200   root_task = SD_task_create_comp_par_amdahl("root", NULL, 0., 0.);
201   /* by design the root task is always SCHEDULABLE */
202   __SD_task_set_state(root_task, SD_SCHEDULABLE);
203
204   xbt_dict_set(jobs, "root", root_task, NULL);
205   xbt_dynar_push(result, &root_task);
206   end_task = SD_task_create_comp_par_amdahl("end", NULL, 0., 0.);
207   xbt_dict_set(jobs, "end", end_task, NULL);
208
209   Agnode_t *dag_node = NULL;
210   for (dag_node = agfstnode(dag_dot); dag_node; dag_node = agnxtnode(dag_dot, dag_node)) {
211     dot_add_parallel_task(dag_node);
212   }
213   agclose(dag_dot);
214   xbt_dict_free(&jobs);
215
216   /* And now, post-process the files.
217    * We want a file task per pair of computation tasks exchanging the file. Duplicate on need
218    * Files not produced in the system are said to be produced by root task (top of DAG).
219    * Files not consumed in the system are said to be consumed by end task (bottom of DAG).
220    */
221   xbt_dict_cursor_t cursor;
222   SD_task_t file;
223   char *name;
224   xbt_dict_foreach(files, cursor, name, file) {
225     unsigned int cpt1, cpt2;
226     SD_task_t newfile = NULL;
227     SD_dependency_t depbefore, depafter;
228     if (xbt_dynar_is_empty(file->tasks_before)) {
229       xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
230         SD_task_t newfile =
231             SD_task_create_comm_par_mxn_1d_block(file->name, NULL, file->amount);
232         SD_task_dependency_add(NULL, NULL, root_task, newfile);
233         SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
234         xbt_dynar_push(result, &newfile);
235       }
236     } else if (xbt_dynar_is_empty(file->tasks_after)) {
237       xbt_dynar_foreach(file->tasks_before, cpt2, depbefore) {
238         SD_task_t newfile =
239             SD_task_create_comm_par_mxn_1d_block(file->name, NULL, file->amount);
240         SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
241         SD_task_dependency_add(NULL, NULL, newfile, end_task);
242         xbt_dynar_push(result, &newfile);
243       }
244     } else {
245       xbt_dynar_foreach(file->tasks_before, cpt1, depbefore) {
246         xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
247           if (depbefore->src == depafter->dst) {
248             XBT_WARN
249                 ("File %s is produced and consumed by task %s. This loop dependency will prevent the execution of the task.",
250                  file->name, depbefore->src->name);
251           }
252           newfile =
253               SD_task_create_comm_par_mxn_1d_block(file->name, NULL, file->amount);
254           SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
255           SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
256           xbt_dynar_push(result, &newfile);
257         }
258       }
259     }
260   }
261
262   /* Push end task last */
263   xbt_dynar_push(result, &end_task);
264
265   /* Free previous copy of the files */
266   xbt_dict_free(&files);
267   xbt_dict_free(&computers);
268   fclose(in_file);
269   if (!acyclic_graph_detail(result)) {
270     XBT_ERROR("The DOT described in %s is not a DAG. It contains a cycle.",
271               basename((char*)filename));
272     xbt_dynar_free(&result);
273     /* (result == NULL) here */
274   }
275   return result;
276 }
277
278
279 xbt_dynar_t SD_dotload_generic(const char * filename)
280 {
281   xbt_assert(filename, "Unable to use a null file descriptor\n");
282   //dag_dot =  agopen((char*)filename,Agstrictdirected,0);
283   FILE *in_file = fopen(filename, "r");
284   dag_dot = agread(in_file, NIL(Agdisc_t *));
285
286   result = xbt_dynar_new(sizeof(SD_task_t), dot_task_p_free);
287   files = xbt_dict_new_homogeneous(&dot_task_free);
288   jobs = xbt_dict_new_homogeneous(NULL);
289   computers = xbt_dict_new_homogeneous(NULL);
290   root_task = SD_task_create_comp_seq("root", NULL, 0);
291   /* by design the root task is always SCHEDULABLE */
292   __SD_task_set_state(root_task, SD_SCHEDULABLE);
293
294   xbt_dict_set(jobs, "root", root_task, NULL);
295   xbt_dynar_push(result, &root_task);
296   end_task = SD_task_create_comp_seq("end", NULL, 0);
297   xbt_dict_set(jobs, "end", end_task, NULL);
298
299   Agnode_t *dag_node = NULL;
300   for (dag_node = agfstnode(dag_dot); dag_node; dag_node = agnxtnode(dag_dot, dag_node)) {
301     dot_add_task(dag_node);
302   }
303   agclose(dag_dot);
304   xbt_dict_free(&jobs);
305
306   /* And now, post-process the files.
307    * We want a file task per pair of computation tasks exchanging the file. Duplicate on need
308    * Files not produced in the system are said to be produced by root task (top of DAG).
309    * Files not consumed in the system are said to be consumed by end task (bottom of DAG).
310    */
311   xbt_dict_cursor_t cursor;
312   SD_task_t file;
313   char *name;
314   xbt_dict_foreach(files, cursor, name, file) {
315     unsigned int cpt1, cpt2;
316     SD_task_t newfile = NULL;
317     SD_dependency_t depbefore, depafter;
318     if (xbt_dynar_is_empty(file->tasks_before)) {
319       xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
320         SD_task_t newfile =
321             SD_task_create_comm_e2e(file->name, NULL, file->amount);
322         SD_task_dependency_add(NULL, NULL, root_task, newfile);
323         SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
324         xbt_dynar_push(result, &newfile);
325       }
326     } else if (xbt_dynar_is_empty(file->tasks_after)) {
327       xbt_dynar_foreach(file->tasks_before, cpt2, depbefore) {
328         SD_task_t newfile =
329             SD_task_create_comm_e2e(file->name, NULL, file->amount);
330         SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
331         SD_task_dependency_add(NULL, NULL, newfile, end_task);
332         xbt_dynar_push(result, &newfile);
333       }
334     } else {
335       xbt_dynar_foreach(file->tasks_before, cpt1, depbefore) {
336         xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
337           if (depbefore->src == depafter->dst) {
338             XBT_WARN
339                 ("File %s is produced and consumed by task %s. This loop dependency will prevent the execution of the task.",
340                  file->name, depbefore->src->name);
341           }
342           newfile =
343               SD_task_create_comm_e2e(file->name, NULL, file->amount);
344           SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
345           SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
346           xbt_dynar_push(result, &newfile);
347         }
348       }
349     }
350   }
351
352   /* Push end task last */
353   xbt_dynar_push(result, &end_task);
354
355   /* Free previous copy of the files */
356   xbt_dict_free(&files);
357   fclose(in_file);
358   if (!acyclic_graph_detail(result)) {
359     XBT_ERROR("The DOT described in %s is not a DAG. It contains a cycle.",
360               basename((char*)filename));
361     xbt_dynar_free(&result);
362     /* (result == NULL) here */
363   }
364   return result;
365 }
366
367 /* dot_add_parallel_task create a sd_task of SD_TASK_COMP_PAR_AMDHAL type and
368  * all transfers required for this task. The execution time of the task is
369  * given by the attribute size. The unit of size is the Flop.*/
370 void dot_add_parallel_task(Agnode_t * dag_node)
371 {
372   char *name = agnameof(dag_node);
373   SD_task_t current_job;
374   double amount = dot_parse_double(agget(dag_node, (char *) "size"));
375   double alpha = dot_parse_double(agget(dag_node, (char *) "alpha"));
376
377   if (alpha == -1.)
378     alpha = 0.0;
379
380   XBT_DEBUG("See <job id=%s amount=%s %.0f alpha=%.2f>", name,
381         agget(dag_node, (char *) "size"), amount, alpha);
382   if (!strcmp(name, "root")){
383     XBT_WARN("'root' node is explicitly declared in the DOT file. Ignore it");
384     return;
385   }
386   if (!strcmp(name, "end")){
387     XBT_WARN("'end' node is explicitly declared in the DOT file. Ignore it");
388     return;
389   }
390
391   current_job = xbt_dict_get_or_null(jobs, name);
392   if (current_job == NULL) {
393     current_job =
394         SD_task_create_comp_par_amdahl(name, NULL , amount, alpha);
395 #ifdef HAVE_TRACING
396    TRACE_sd_dotloader (current_job, agget (dag_node, (char*)"category"));
397 #endif
398     xbt_dict_set(jobs, name, current_job, NULL);
399     xbt_dynar_push(result, &current_job);
400   }
401   Agedge_t *e;
402   int count = 0;
403
404   for (e = agfstin(dag_dot, dag_node); e; e = agnxtin(dag_dot, e)) {
405     dot_add_input_dependencies(current_job, e, parallel);
406     count++;
407   }
408   if (count == 0 && current_job != root_task) {
409     SD_task_dependency_add(NULL, NULL, root_task, current_job);
410   }
411   count = 0;
412   for (e = agfstout(dag_dot, dag_node); e; e = agnxtout(dag_dot, e)) {
413     dot_add_output_dependencies(current_job, e, parallel);
414     count++;
415   }
416   if (count == 0 && current_job != end_task) {
417     SD_task_dependency_add(NULL, NULL, current_job, end_task);
418   }
419 }
420
421 /* dot_add_task create a sd_task and all transfers required for this
422  * task. The execution time of the task is given by the attribute size.
423  * The unit of size is the Flop.*/
424 void dot_add_task(Agnode_t * dag_node)
425 {
426   char *name = agnameof(dag_node);
427   SD_task_t current_job;
428   double runtime = dot_parse_double(agget(dag_node, (char *) "size"));
429
430   XBT_DEBUG("See <job id=%s runtime=%s %.0f>", name,
431         agget(dag_node, (char *) "size"), runtime);
432   if (!strcmp(name, "root")){
433     XBT_WARN("'root' node is explicitly declared in the DOT file. Ignore it");
434     return;
435   }
436   if (!strcmp(name, "end")){
437     XBT_WARN("'end' node is explicitly declared in the DOT file. Ignore it");
438     return;
439   }
440   current_job = xbt_dict_get_or_null(jobs, name);
441   if (current_job == NULL) {
442     current_job =
443         SD_task_create_comp_seq(name, NULL , runtime);
444 #ifdef HAVE_TRACING
445     TRACE_sd_dotloader (current_job, agget (dag_node, (char*)"category"));
446 #endif
447     xbt_dict_set(jobs, name, current_job, NULL);
448     xbt_dynar_push(result, &current_job);
449   }
450   Agedge_t *e;
451   int count = 0;
452
453   for (e = agfstin(dag_dot, dag_node); e; e = agnxtin(dag_dot, e)) {
454     dot_add_input_dependencies(current_job, e, sequential);
455     count++;
456   }
457   if (count == 0 && current_job != root_task) {
458     SD_task_dependency_add(NULL, NULL, root_task, current_job);
459   }
460   count = 0;
461   for (e = agfstout(dag_dot, dag_node); e; e = agnxtout(dag_dot, e)) {
462     dot_add_output_dependencies(current_job, e, sequential);
463     count++;
464   }
465   if (count == 0 && current_job != end_task) {
466     SD_task_dependency_add(NULL, NULL, current_job, end_task);
467   }
468
469   if(schedule || XBT_LOG_ISENABLED(sd_dotparse, xbt_log_priority_verbose)){
470     /* try to take the information to schedule the task only if all is
471      * right*/
472     // performer is the computer which execute the task
473     unsigned long performer = -1;
474     char * char_performer = agget(dag_node, (char *) "performer");
475     if (char_performer != NULL)
476       performer = (long) dot_parse_int(char_performer);
477
478     // order is giving the task order on one computer
479     unsigned long order = -1;
480     char * char_order = agget(dag_node, (char *) "order");
481     if (char_order != NULL)
482       order = (long) dot_parse_int(char_order);
483     xbt_dynar_t computer = NULL;
484     //XBT_INFO("performer = %d, order=%d",performer,order);
485     if(performer != -1 && order != -1){
486       //necessary parameters are given
487       computer = xbt_dict_get_or_null(computers, char_performer);
488       if(computer == NULL){
489         computer = xbt_dynar_new(sizeof(SD_task_t), NULL);
490         xbt_dict_set(computers, char_performer, computer, NULL);
491       }
492       if(performer < xbt_lib_length(host_lib)){
493         // the  wanted computer is available
494         SD_task_t *task_test = NULL;
495         if(order < computer->used)
496           task_test = xbt_dynar_get_ptr(computer,order);
497         if(task_test != NULL && *task_test != NULL && *task_test != current_job){
498           /*the user gives the same order to several tasks*/
499           schedule = false;
500           XBT_VERB("The task %s starts on the computer %s at the position : %s like the task %s",
501                  (*task_test)->name, char_performer, char_order, current_job->name);
502         }else{
503           //the parameter seems to be ok
504           xbt_dynar_set_as(computer, order, SD_task_t, current_job);
505         }
506       }else{
507         /*the platform has not enough processors to schedule the DAG like
508         *the user wants*/
509         schedule = false;
510         XBT_VERB("The schedule is ignored, there are not enough computers");
511       }
512     }
513     else {
514       //one of necessary parameters are not given
515       schedule = false;
516       XBT_VERB("The schedule is ignored, the task %s is not correctly scheduled", current_job->name);
517     }
518   }
519 }
520
521 /* dot_add_output_dependencies create the dependencies between a task
522  * and a transfers. This is given by the edges in the dot file. 
523  * The amount of data transfers is given by the attribute size on the
524  * edge. */
525 void dot_add_input_dependencies(SD_task_t current_job, Agedge_t * edge,
526                                 seq_par_t seq_or_par)
527 {
528   SD_task_t file = NULL;
529   char *name_tail=agnameof(agtail(edge));
530   char *name_head=agnameof(aghead(edge));
531   char *name = xbt_malloc((strlen(name_head)+strlen(name_tail)+6)*sizeof(char));
532   sprintf(name, "%s->%s", name_tail, name_head);
533   double size = dot_parse_double(agget(edge, (char *) "size"));
534   XBT_DEBUG("size : %e, get size : %s", size, agget(edge, (char *) "size"));
535
536   if (size > 0) {
537     file = xbt_dict_get_or_null(files, name);
538     if (file == NULL) {
539       if (seq_or_par == sequential){
540           file = SD_task_create_comm_e2e(name, NULL, size);
541       } else {
542           file = SD_task_create_comm_par_mxn_1d_block(name, NULL, size);
543       }
544 #ifdef HAVE_TRACING
545       TRACE_sd_dotloader (file, agget (edge, (char*)"category"));
546 #endif
547       xbt_dict_set(files, name, file, NULL);
548     } else {
549       if (SD_task_get_amount(file) != size) {
550         XBT_WARN("Ignoring file %s size redefinition from %.0f to %.0f",
551               name, SD_task_get_amount(file), size);
552       }
553     }
554     SD_task_dependency_add(NULL, NULL, file, current_job);
555   } else {
556     file = xbt_dict_get_or_null(jobs, name_tail);
557     if (file != NULL) {
558       SD_task_dependency_add(NULL, NULL, file, current_job);
559     }
560   }
561   free(name);
562 }
563
564 /* dot_add_output_dependencies create the dependencies between a
565  * transfers and a task. This is given by the edges in the dot file.
566  * The amount of data transfers is given by the attribute size on the
567  * edge. */
568 void dot_add_output_dependencies(SD_task_t current_job, Agedge_t * edge,
569                                  seq_par_t seq_or_par){
570   SD_task_t file;
571   char *name_tail=agnameof(agtail(edge));
572   char *name_head=agnameof(aghead(edge));
573   char *name = xbt_malloc((strlen(name_head)+strlen(name_tail)+6)*sizeof(char));
574   sprintf(name, "%s->%s", name_tail, name_head);
575   double size = dot_parse_double(agget(edge, (char *) "size"));
576   XBT_DEBUG("size : %e, get size : %s", size, agget(edge, (char *) "size"));
577
578   if (size > 0) {
579     file = xbt_dict_get_or_null(files, name);
580     if (file == NULL) {
581       if (seq_or_par == sequential){
582           file = SD_task_create_comm_e2e(name, NULL, size);
583       } else {
584           file = SD_task_create_comm_par_mxn_1d_block(name, NULL, size);
585       }
586 #ifdef HAVE_TRACING
587       TRACE_sd_dotloader (file, agget (edge, (char*)"category"));
588 #endif
589       xbt_dict_set(files, name, file, NULL);
590     } else {
591       if (SD_task_get_amount(file) != size) {
592         XBT_WARN("Ignoring file %s size redefinition from %.0f to %.0f",
593               name, SD_task_get_amount(file), size);
594       }
595     }
596     SD_task_dependency_add(NULL, NULL, current_job, file);
597     if (xbt_dynar_length(file->tasks_before) > 1) {
598       XBT_WARN("File %s created at more than one location...", file->name);
599     }
600   } else {
601     file = xbt_dict_get_or_null(jobs, name_head);
602     if (file != NULL) {
603       SD_task_dependency_add(NULL, NULL, current_job, file);
604     }
605   }
606   free(name);
607 }