Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Merge branch 'with_java'
[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(NULL);
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     XBT_DEBUG("Considering file '%s' stored in the dictionnary",
316         file->name);
317     if (xbt_dynar_is_empty(file->tasks_before)) {
318       XBT_DEBUG("file '%s' has no source. Add dependency from 'root'",
319           file->name);
320       SD_task_dependency_add(NULL, NULL, root_task, file);
321     } else if (xbt_dynar_is_empty(file->tasks_after)) {
322       XBT_DEBUG("file '%s' has no destination. Add dependency to 'end'",
323           file->name);
324       SD_task_dependency_add(NULL, NULL, file, end_task);
325     }
326     xbt_dynar_push(result, &file);
327   }
328
329   /* Push end task last */
330   xbt_dynar_push(result, &end_task);
331
332   xbt_dict_free(&files);
333   fclose(in_file);
334   if (!acyclic_graph_detail(result)) {
335     XBT_ERROR("The DOT described in %s is not a DAG. It contains a cycle.",
336               basename((char*)filename));
337     xbt_dynar_free(&result);
338     /* (result == NULL) here */
339   }
340   return result;
341 }
342
343 /* dot_add_parallel_task create a sd_task of SD_TASK_COMP_PAR_AMDHAL type and
344  * all transfers required for this task. The execution time of the task is
345  * given by the attribute size. The unit of size is the Flop.*/
346 void dot_add_parallel_task(Agnode_t * dag_node)
347 {
348   char *name = agnameof(dag_node);
349   SD_task_t current_job;
350   double amount = dot_parse_double(agget(dag_node, (char *) "size"));
351   double alpha = dot_parse_double(agget(dag_node, (char *) "alpha"));
352
353   if (alpha == -1.)
354     alpha = 0.0;
355
356   XBT_DEBUG("See <job id=%s amount=%s %.0f alpha=%.2f>", name,
357         agget(dag_node, (char *) "size"), amount, alpha);
358   if (!strcmp(name, "root")){
359     XBT_WARN("'root' node is explicitly declared in the DOT file. Ignore it");
360     return;
361   }
362   if (!strcmp(name, "end")){
363     XBT_WARN("'end' node is explicitly declared in the DOT file. Ignore it");
364     return;
365   }
366
367   current_job = xbt_dict_get_or_null(jobs, name);
368   if (current_job == NULL) {
369     current_job =
370         SD_task_create_comp_par_amdahl(name, NULL , amount, alpha);
371 #ifdef HAVE_TRACING
372    TRACE_sd_dotloader (current_job, agget (dag_node, (char*)"category"));
373 #endif
374     xbt_dict_set(jobs, name, current_job, NULL);
375     xbt_dynar_push(result, &current_job);
376   }
377   Agedge_t *e;
378   int count = 0;
379
380   for (e = agfstin(dag_dot, dag_node); e; e = agnxtin(dag_dot, e)) {
381     dot_add_input_dependencies(current_job, e, parallel);
382     count++;
383   }
384   if (count == 0 && current_job != root_task) {
385     SD_task_dependency_add(NULL, NULL, root_task, current_job);
386   }
387   count = 0;
388   for (e = agfstout(dag_dot, dag_node); e; e = agnxtout(dag_dot, e)) {
389     dot_add_output_dependencies(current_job, e, parallel);
390     count++;
391   }
392   if (count == 0 && current_job != end_task) {
393     SD_task_dependency_add(NULL, NULL, current_job, end_task);
394   }
395 }
396
397 /* dot_add_task create a sd_task and all transfers required for this
398  * task. The execution time of the task is given by the attribute size.
399  * The unit of size is the Flop.*/
400 void dot_add_task(Agnode_t * dag_node)
401 {
402   char *name = agnameof(dag_node);
403   SD_task_t current_job;
404   double runtime = dot_parse_double(agget(dag_node, (char *) "size"));
405
406   XBT_DEBUG("See <job id=%s runtime=%s %.0f>", name,
407         agget(dag_node, (char *) "size"), runtime);
408
409   if (!strcmp(name, "root")){
410     XBT_WARN("'root' node is explicitly declared in the DOT file. Update it");
411     root_task->amount = runtime;
412 #ifdef HAVE_TRACING
413     TRACE_sd_dotloader (root_task, agget (dag_node, (char*)"category"));
414 #endif
415   }
416
417   if (!strcmp(name, "end")){
418     XBT_WARN("'end' node is explicitly declared in the DOT file. Update it");
419     end_task->amount = runtime;
420 #ifdef HAVE_TRACING
421     TRACE_sd_dotloader (end_task, agget (dag_node, (char*)"category"));
422 #endif
423   }
424
425   current_job = xbt_dict_get_or_null(jobs, name);
426   if (!current_job) {
427     current_job =
428         SD_task_create_comp_seq(name, NULL , runtime);
429 #ifdef HAVE_TRACING
430     TRACE_sd_dotloader (current_job, agget (dag_node, (char*)"category"));
431 #endif
432     xbt_dict_set(jobs, name, current_job, NULL);
433     xbt_dynar_push(result, &current_job);
434   }
435   Agedge_t *e;
436   int count = 0;
437
438   for (e = agfstin(dag_dot, dag_node); e; e = agnxtin(dag_dot, e)) {
439     dot_add_input_dependencies(current_job, e, sequential);
440     count++;
441   }
442   if (count == 0 && current_job != root_task) {
443     SD_task_dependency_add(NULL, NULL, root_task, current_job);
444   }
445   count = 0;
446   for (e = agfstout(dag_dot, dag_node); e; e = agnxtout(dag_dot, e)) {
447     dot_add_output_dependencies(current_job, e, sequential);
448     count++;
449   }
450   if (count == 0 && current_job != end_task) {
451     SD_task_dependency_add(NULL, NULL, current_job, end_task);
452   }
453
454   if(schedule || XBT_LOG_ISENABLED(sd_dotparse, xbt_log_priority_verbose)){
455     /* try to take the information to schedule the task only if all is
456      * right*/
457     // performer is the computer which execute the task
458     unsigned long performer = -1;
459     char * char_performer = agget(dag_node, (char *) "performer");
460     if (char_performer != NULL)
461       performer = (long) dot_parse_int(char_performer);
462
463     // order is giving the task order on one computer
464     unsigned long order = -1;
465     char * char_order = agget(dag_node, (char *) "order");
466     if (char_order != NULL)
467       order = (long) dot_parse_int(char_order);
468     xbt_dynar_t computer = NULL;
469     //XBT_INFO("performer = %d, order=%d",performer,order);
470     if(performer != -1 && order != -1){
471       //necessary parameters are given
472       computer = xbt_dict_get_or_null(computers, char_performer);
473       if(computer == NULL){
474         computer = xbt_dynar_new(sizeof(SD_task_t), NULL);
475         xbt_dict_set(computers, char_performer, computer, NULL);
476       }
477       if(performer < xbt_lib_length(host_lib)){
478         // the  wanted computer is available
479         SD_task_t *task_test = NULL;
480         if(order < computer->used)
481           task_test = xbt_dynar_get_ptr(computer,order);
482         if(task_test != NULL && *task_test != NULL && *task_test != current_job){
483           /*the user gives the same order to several tasks*/
484           schedule = false;
485           XBT_VERB("The task %s starts on the computer %s at the position : %s like the task %s",
486                  (*task_test)->name, char_performer, char_order, current_job->name);
487         }else{
488           //the parameter seems to be ok
489           xbt_dynar_set_as(computer, order, SD_task_t, current_job);
490         }
491       }else{
492         /*the platform has not enough processors to schedule the DAG like
493         *the user wants*/
494         schedule = false;
495         XBT_VERB("The schedule is ignored, there are not enough computers");
496       }
497     }
498     else {
499       //one of necessary parameters are not given
500       schedule = false;
501       XBT_VERB("The schedule is ignored, the task %s is not correctly scheduled", current_job->name);
502     }
503   }
504 }
505
506 /* dot_add_output_dependencies create the dependencies between a task
507  * and a transfers. This is given by the edges in the dot file. 
508  * The amount of data transfers is given by the attribute size on the
509  * edge. */
510 void dot_add_input_dependencies(SD_task_t current_job, Agedge_t * edge,
511                                 seq_par_t seq_or_par)
512 {
513   SD_task_t file = NULL;
514   char *name_tail=agnameof(agtail(edge));
515   char *name_head=agnameof(aghead(edge));
516   char *name = xbt_malloc((strlen(name_head)+strlen(name_tail)+6)*sizeof(char));
517   sprintf(name, "%s->%s", name_tail, name_head);
518   double size = dot_parse_double(agget(edge, (char *) "size"));
519   XBT_DEBUG("add input -- edge: %s, size : %e, get size : %s",
520       name, size, agget(edge, (char *) "size"));
521
522   if (size > 0) {
523     file = xbt_dict_get_or_null(files, name);
524     if (file == NULL) {
525       if (seq_or_par == sequential){
526           file = SD_task_create_comm_e2e(name, NULL, size);
527       } else {
528           file = SD_task_create_comm_par_mxn_1d_block(name, NULL, size);
529       }
530 #ifdef HAVE_TRACING
531       TRACE_sd_dotloader (file, agget (edge, (char*)"category"));
532 #endif
533       XBT_DEBUG("add input -- adding %s to the dict as new file", name);
534       xbt_dict_set(files, name, file, NULL);
535     } else {
536       XBT_WARN("%s already exists", name);
537       if (SD_task_get_amount(file) != size) {
538         XBT_WARN("Ignoring file %s size redefinition from %.0f to %.0f",
539               name, SD_task_get_amount(file), size);
540       }
541     }
542     SD_task_dependency_add(NULL, NULL, file, current_job);
543   } else {
544     file = xbt_dict_get_or_null(jobs, name_tail);
545     if (file != NULL) {
546       SD_task_dependency_add(NULL, NULL, file, current_job);
547     }
548   }
549   free(name);
550 }
551
552 /* dot_add_output_dependencies create the dependencies between a
553  * transfers and a task. This is given by the edges in the dot file.
554  * The amount of data transfers is given by the attribute size on the
555  * edge. */
556 void dot_add_output_dependencies(SD_task_t current_job, Agedge_t * edge,
557                                  seq_par_t seq_or_par){
558   SD_task_t file;
559   char *name_tail=agnameof(agtail(edge));
560   char *name_head=agnameof(aghead(edge));
561   char *name = xbt_malloc((strlen(name_head)+strlen(name_tail)+6)*sizeof(char));
562   sprintf(name, "%s->%s", name_tail, name_head);
563   double size = dot_parse_double(agget(edge, (char *) "size"));
564   XBT_DEBUG("add_output -- edge: %s, size : %e, get size : %s",
565       name, size, agget(edge, (char *) "size"));
566
567   if (size > 0) {
568     file = xbt_dict_get_or_null(files, name);
569     if (file == NULL) {
570       if (seq_or_par == sequential){
571           file = SD_task_create_comm_e2e(name, NULL, size);
572       } else {
573           file = SD_task_create_comm_par_mxn_1d_block(name, NULL, size);
574       }
575 #ifdef HAVE_TRACING
576       TRACE_sd_dotloader (file, agget (edge, (char*)"category"));
577 #endif
578       XBT_DEBUG("add output -- adding %s to the dict as new file", name);
579       xbt_dict_set(files, name, file, NULL);
580     } else {
581       XBT_WARN("%s already exists", name);
582       if (SD_task_get_amount(file) != size) {
583         XBT_WARN("Ignoring file %s size redefinition from %.0f to %.0f",
584               name, SD_task_get_amount(file), size);
585       }
586     }
587     SD_task_dependency_add(NULL, NULL, current_job, file);
588     if (xbt_dynar_length(file->tasks_before) > 1) {
589       XBT_WARN("File %s created at more than one location...", file->name);
590     }
591   } else {
592     file = xbt_dict_get_or_null(jobs, name_head);
593     if (file != NULL) {
594       SD_task_dependency_add(NULL, NULL, current_job, file);
595     }
596   }
597   free(name);
598 }