src/simdag/sd_dotloader.c

   1 /* Copyright (c) 2009, 2010. 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 void dot_add_task(Agnode_t * dag_node);
  31 void dot_add_input_dependencies(SD_task_t current_job, Agedge_t * edge);
  32 void dot_add_output_dependencies(SD_task_t current_job, Agedge_t * edge);
  33 xbt_dynar_t SD_dotload_generic(const char * filename);
  34
  35 static double dot_parse_double(const char *string)
  36 {
  37   if (string == NULL)
  38     return -1;
  39   double value = -1;
  40   char *err;
  41
  42   //ret = sscanf(string, "%lg", &value);
  43   errno = 0;
  44   value = strtod(string,&err);
  45   if(errno)
  46   {
  47     XBT_WARN("Failed to convert string to double: %s\n",strerror(errno));
  48     return -1;
  49   }
  50   return value;
  51 }
  52
  53
  54 static int dot_parse_int(const char *string)
  55 {
  56   if (string == NULL)
  57     return -10;
  58   int ret = 0;
  59   int value = -1;
  60
  61   ret = sscanf(string, "%d", &value);
  62   if (ret != 1)
  63     XBT_WARN("%s is not an integer", string);
  64   return value;
  65 }
  66
  67 static xbt_dynar_t result;
  68 static xbt_dict_t jobs;
  69 static xbt_dict_t files;
  70 static xbt_dict_t computers;
  71 static SD_task_t root_task, end_task;
  72 static Agraph_t *dag_dot;
  73 static bool schedule = true;
  74
  75 static void dump_res()
  76 {
  77   unsigned int cursor;
  78   SD_task_t task;
  79   xbt_dynar_foreach(result, cursor, task) {
  80     XBT_INFO("Task %d", cursor);
  81     SD_task_dump(task);
  82   }
  83 }
  84
  85
  86 static void dot_task_free(void *task)
  87 {
  88   SD_task_t t = task;
  89   SD_task_destroy(t);
  90 }
  91
  92 static void dot_task_p_free(void *task)
  93 {
  94   SD_task_t *t = task;
  95   SD_task_destroy(*t);
  96 }
  97
  98 static void TRACE_sd_dotloader (SD_task_t task, const char *category)
  99 {
 100   if (category){
 101     if (strlen (category) != 0){
 102       TRACE_category (category);
 103       SD_task_set_category (task, category);
 104     }
 105   }
 106 }
 107
 108 /** @brief loads a DOT file describing a DAG
 109  *
 110  * See http://www.graphviz.org/doc/info/lang.html
 111  * for more details.
 112  * To obtain information about transfers and tasks, two attributes are
 113  * required : size on task (execution time in Flop) and size on edge
 114  * (the amount of data transfer in bit).
 115  * if they aren't here, there choose to be equal to zero.
 116  */
 117 xbt_dynar_t SD_dotload(const char *filename)
 118 {
 119   SD_dotload_generic(filename);
 120   xbt_dynar_t computer = NULL;
 121   xbt_dict_cursor_t dict_cursor;
 122   char *computer_name;
 123   xbt_dict_foreach(computers,dict_cursor,computer_name,computer){
 124     xbt_dynar_free(&computer);
 125   }
 126   xbt_dict_free(&computers);
 127   return result;
 128 }
 129
 130 xbt_dynar_t SD_dotload_with_sched(const char *filename){
 131   SD_dotload_generic(filename);
 132
 133   if(schedule == true){
 134     xbt_dynar_t computer = NULL;
 135     xbt_dict_cursor_t dict_cursor;
 136     char *computer_name;
 137     const SD_workstation_t *workstations = SD_workstation_get_list ();
 138     xbt_dict_foreach(computers,dict_cursor,computer_name,computer){
 139       int count_computer = dot_parse_int(computer_name);
 140       unsigned int count=0;
 141       SD_task_t task;
 142       SD_task_t task_previous = NULL;
 143       xbt_dynar_foreach(computer,count,task){
 144         // add dependency between the previous and the task to avoid
 145         // parallel execution
 146         if(task != NULL ){
 147           if(task_previous != NULL &&
 148              !SD_task_dependency_exists(task_previous, task))
 149             SD_task_dependency_add(NULL, NULL, task_previous, task);
 150           SD_task_schedulel(task, 1, workstations[count_computer]);
 151           task_previous = task;
 152         }
 153       }
 154       xbt_dynar_free(&computer);
 155     }
 156     xbt_dict_free(&computers);
 157     if(acyclic_graph_detail(result))
 158       return result;
 159     else
 160       XBT_WARN("There is at least one cycle in the provided task graph");
 161   }else{
 162     XBT_WARN("The scheduling is ignored");
 163   }
 164   SD_task_t task;
 165   unsigned int count;
 166   xbt_dynar_t computer = NULL;
 167   xbt_dict_cursor_t dict_cursor;
 168   char *computer_name;
 169   xbt_dict_foreach(computers,dict_cursor,computer_name,computer){
 170     xbt_dynar_free(&computer);
 171   }
 172   xbt_dict_free(&computers);
 173   xbt_dynar_foreach(result,count,task){
 174      SD_task_destroy(task);
 175   }
 176   return NULL;
 177 }
 178
 179 xbt_dynar_t SD_dotload_generic(const char * filename)
 180 {
 181   xbt_assert(filename, "Unable to use a null file descriptor\n");
 182   //dag_dot =  agopen((char*)filename,Agstrictdirected,0);
 183   FILE *in_file = fopen(filename, "r");
 184   dag_dot = agread(in_file, NIL(Agdisc_t *));
 185
 186   result = xbt_dynar_new(sizeof(SD_task_t), dot_task_p_free);
 187   files = xbt_dict_new_homogeneous(&dot_task_free);
 188   jobs = xbt_dict_new_homogeneous(NULL);
 189   computers = xbt_dict_new_homogeneous(NULL);
 190   root_task = SD_task_create_comp_seq("root", NULL, 0);
 191   /* by design the root task is always SCHEDULABLE */
 192   __SD_task_set_state(root_task, SD_SCHEDULABLE);
 193
 194   xbt_dict_set(jobs, "root", root_task, NULL);
 195   xbt_dynar_push(result, &root_task);
 196   end_task = SD_task_create_comp_seq("end", NULL, 0);
 197   xbt_dict_set(jobs, "end", end_task, NULL);
 198
 199   Agnode_t *dag_node = NULL;
 200   for (dag_node = agfstnode(dag_dot); dag_node; dag_node = agnxtnode(dag_dot, dag_node)) {
 201     dot_add_task(dag_node);
 202   }
 203   agclose(dag_dot);
 204   xbt_dict_free(&jobs);
 205
 206   /* And now, post-process the files.
 207    * We want a file task per pair of computation tasks exchanging the file. Duplicate on need
 208    * Files not produced in the system are said to be produced by root task (top of DAG).
 209    * Files not consumed in the system are said to be consumed by end task (bottom of DAG).
 210    */
 211   xbt_dict_cursor_t cursor;
 212   SD_task_t file;
 213   char *name;
 214   xbt_dict_foreach(files, cursor, name, file) {
 215     unsigned int cpt1, cpt2;
 216     SD_task_t newfile = NULL;
 217     SD_dependency_t depbefore, depafter;
 218     if (xbt_dynar_is_empty(file->tasks_before)) {
 219       xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
 220         SD_task_t newfile =
 221             SD_task_create_comm_e2e(file->name, NULL, file->amount);
 222         SD_task_dependency_add(NULL, NULL, root_task, newfile);
 223         SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
 224         xbt_dynar_push(result, &newfile);
 225       }
 226     } else if (xbt_dynar_is_empty(file->tasks_after)) {
 227       xbt_dynar_foreach(file->tasks_before, cpt2, depbefore) {
 228         SD_task_t newfile =
 229             SD_task_create_comm_e2e(file->name, NULL, file->amount);
 230         SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
 231         SD_task_dependency_add(NULL, NULL, newfile, end_task);
 232         xbt_dynar_push(result, &newfile);
 233       }
 234     } else {
 235       xbt_dynar_foreach(file->tasks_before, cpt1, depbefore) {
 236         xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
 237           if (depbefore->src == depafter->dst) {
 238             XBT_WARN
 239                 ("File %s is produced and consumed by task %s. This loop dependency will prevent the execution of the task.",
 240                  file->name, depbefore->src->name);
 241           }
 242           newfile =
 243               SD_task_create_comm_e2e(file->name, NULL, file->amount);
 244           SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
 245           SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
 246           xbt_dynar_push(result, &newfile);
 247         }
 248       }
 249     }
 250   }
 251
 252   /* Push end task last */
 253   xbt_dynar_push(result, &end_task);
 254
 255   /* Free previous copy of the files */
 256   xbt_dict_free(&files);
 257   fclose(in_file);
 258   if (!acyclic_graph_detail(result)) {
 259     XBT_ERROR("The DOT described in %s is not a DAG. It contains a cycle.",
 260               basename((char*)filename));
 261     xbt_dynar_free(&result);
 262     /* (result == NULL) here */
 263   }
 264   return result;
 265 }
 266
 267 /* dot_add_task create a sd_task and all transfers required for this
 268  * task. The execution time of the task is given by the attribute size.
 269  * The unit of size is the Flop.*/
 270 void dot_add_task(Agnode_t * dag_node)
 271 {
 272   char *name = agnameof(dag_node);
 273   SD_task_t current_job;
 274   double runtime = dot_parse_double(agget(dag_node, (char *) "size"));
 275
 276   XBT_DEBUG("See <job id=%s runtime=%s %.0f>", name,
 277         agget(dag_node, (char *) "size"), runtime);
 278   current_job = xbt_dict_get_or_null(jobs, name);
 279   if (current_job == NULL) {
 280     current_job =
 281         SD_task_create_comp_seq(name, NULL , runtime);
 282 #ifdef HAVE_TRACING
 283    TRACE_sd_dotloader (current_job, agget (dag_node, (char*)"category"));
 284 #endif
 285     xbt_dict_set(jobs, name, current_job, NULL);
 286     xbt_dynar_push(result, &current_job);
 287   }
 288   Agedge_t *e;
 289   int count = 0;
 290
 291   for (e = agfstin(dag_dot, dag_node); e; e = agnxtin(dag_dot, e)) {
 292     dot_add_input_dependencies(current_job, e);
 293     count++;
 294   }
 295   if (count == 0 && current_job != root_task) {
 296     SD_task_dependency_add(NULL, NULL, root_task, current_job);
 297   }
 298   count = 0;
 299   for (e = agfstout(dag_dot, dag_node); e; e = agnxtout(dag_dot, e)) {
 300     dot_add_output_dependencies(current_job, e);
 301     count++;
 302   }
 303   if (count == 0 && current_job != end_task) {
 304     SD_task_dependency_add(NULL, NULL, current_job, end_task);
 305   }
 306
 307   if(schedule || XBT_LOG_ISENABLED(sd_dotparse, xbt_log_priority_verbose)){
 308     /* try to take the information to schedule the task only if all is
 309      * right*/
 310     // performer is the computer which execute the task
 311     unsigned long performer = -1;
 312     char * char_performer = agget(dag_node, (char *) "performer");
 313     if (char_performer != NULL)
 314       performer = (long) dot_parse_int(char_performer);
 315
 316     // order is giving the task order on one computer
 317     unsigned long order = -1;
 318     char * char_order = agget(dag_node, (char *) "order");
 319     if (char_order != NULL)
 320       order = (long) dot_parse_int(char_order);
 321     xbt_dynar_t computer = NULL;
 322     //XBT_INFO("performer = %d, order=%d",performer,order);
 323     if(performer != -1 && order != -1){
 324       //necessary parameters are given
 325       computer = xbt_dict_get_or_null(computers, char_performer);
 326       if(computer == NULL){
 327         computer = xbt_dynar_new(sizeof(SD_task_t), NULL);
 328         xbt_dict_set(computers, char_performer, computer, NULL);
 329       }
 330       if(performer < xbt_lib_length(host_lib)){
 331         // the  wanted computer is available
 332         SD_task_t *task_test = NULL;
 333         if(order < computer->used)
 334           task_test = xbt_dynar_get_ptr(computer,order);
 335         if(task_test != NULL && *task_test != NULL && *task_test != current_job){
 336           /*the user gives the same order to several tasks*/
 337           schedule = false;
 338           XBT_VERB("The task %s starts on the computer %s at the position : %s like the task %s",
 339                  (*task_test)->name, char_performer, char_order, current_job->name);
 340         }else{
 341           //the parameter seems to be ok
 342           xbt_dynar_set_as(computer, order, SD_task_t, current_job);
 343         }
 344       }else{
 345         /*the platform has not enough processors to schedule the DAG like
 346         *the user wants*/
 347         schedule = false;
 348         XBT_VERB("The schedule is ignored, there are not enough computers");
 349       }
 350     }
 351     else {
 352       //one of necessary parameters are not given
 353       schedule = false;
 354       XBT_VERB("The schedule is ignored, the task %s is not correctly scheduled", current_job->name);
 355     }
 356   }
 357 }
 358
 359 /* dot_add_output_dependencies create the dependencies between a task
 360  * and a transfers. This is given by the edges in the dot file.
 361  * The amount of data transfers is given by the attribute size on the
 362  * edge. */
 363 void dot_add_input_dependencies(SD_task_t current_job, Agedge_t * edge)
 364 {
 365   SD_task_t file = NULL;
 366   char *name_tail=agnameof(agtail(edge));
 367   char *name_head=agnameof(aghead(edge));
 368   char *name = xbt_malloc((strlen(name_head)+strlen(name_tail)+6)*sizeof(char));
 369   sprintf(name, "%s->%s", name_tail, name_head);
 370   double size = dot_parse_double(agget(edge, (char *) "size"));
 371   XBT_DEBUG("size : %e, get size : %s", size, agget(edge, (char *) "size"));
 372
 373   if (size > 0) {
 374     file = xbt_dict_get_or_null(files, name);
 375     if (file == NULL) {
 376       file = SD_task_create_comm_e2e(name, NULL, size);
 377 #ifdef HAVE_TRACING
 378       TRACE_sd_dotloader (file, agget (edge, (char*)"category"));
 379 #endif
 380       xbt_dict_set(files, name, file, NULL);
 381     } else {
 382       if (SD_task_get_amount(file) != size) {
 383         XBT_WARN("Ignoring file %s size redefinition from %.0f to %.0f",
 384               name, SD_task_get_amount(file), size);
 385       }
 386     }
 387     SD_task_dependency_add(NULL, NULL, file, current_job);
 388   } else {
 389     file = xbt_dict_get_or_null(jobs, name_tail);
 390     if (file != NULL) {
 391       SD_task_dependency_add(NULL, NULL, file, current_job);
 392     }
 393   }
 394   free(name);
 395 }
 396
 397 /* dot_add_output_dependencies create the dependencies between a
 398  * transfers and a task. This is given by the edges in the dot file.
 399  * The amount of data transfers is given by the attribute size on the
 400  * edge. */
 401 void dot_add_output_dependencies(SD_task_t current_job, Agedge_t * edge)
 402 {
 403   SD_task_t file;
 404   char *name_tail=agnameof(agtail(edge));
 405   char *name_head=agnameof(aghead(edge));
 406   char *name = xbt_malloc((strlen(name_head)+strlen(name_tail)+6)*sizeof(char));
 407   sprintf(name, "%s->%s", name_tail, name_head);
 408   double size = dot_parse_double(agget(edge, (char *) "size"));
 409   XBT_DEBUG("size : %e, get size : %s", size, agget(edge, (char *) "size"));
 410
 411   if (size > 0) {
 412     file = xbt_dict_get_or_null(files, name);
 413     if (file == NULL) {
 414       file = SD_task_create_comm_e2e(name, NULL, size);
 415 #ifdef HAVE_TRACING
 416       TRACE_sd_dotloader (file, agget (edge, (char*)"category"));
 417 #endif
 418       xbt_dict_set(files, name, file, NULL);
 419     } else {
 420       if (SD_task_get_amount(file) != size) {
 421         XBT_WARN("Ignoring file %s size redefinition from %.0f to %.0f",
 422               name, SD_task_get_amount(file), size);
 423       }
 424     }
 425     SD_task_dependency_add(NULL, NULL, current_job, file);
 426     if (xbt_dynar_length(file->tasks_before) > 1) {
 427       XBT_WARN("File %s created at more than one location...", file->name);
 428     }
 429   } else {
 430     file = xbt_dict_get_or_null(jobs, name_head);
 431     if (file != NULL) {
 432       SD_task_dependency_add(NULL, NULL, current_job, file);
 433     }
 434   }
 435   free(name);
 436 }