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 #endif
  24
  25 void dot_add_task(Agnode_t * dag_node);
  26 void dot_add_input_dependencies(SD_task_t current_job, Agedge_t * edge);
  27 void dot_add_output_dependencies(SD_task_t current_job, Agedge_t * edge);
  28 xbt_dynar_t SD_dotload_generic(const char * filename);
  29
  30 static double dot_parse_double(const char *string)
  31 {
  32     if (string == NULL)
  33           return -1;
  34       double value = -1;
  35         char *err;
  36
  37           //ret = sscanf(string, "%lg", &value);
  38           errno = 0;
  39             value = strtod(string,&err);
  40               if(errno)
  41                   {
  42                         XBT_WARN("Failed to convert string to double: %s\n",strerror(errno));
  43                             return -1;
  44                               }
  45                 return value;
  46 }
  47
  48
  49 static int dot_parse_int(const char *string)
  50 {
  51   if (string == NULL)
  52     return -10;
  53   int ret = 0;
  54   int value = -1;
  55
  56   ret = sscanf(string, "%d", &value);
  57   if (ret != 1)
  58     XBT_WARN("%s is not an integer", string);
  59   return value;
  60 }
  61
  62 static xbt_dynar_t result;
  63 static xbt_dict_t jobs;
  64 static xbt_dict_t files;
  65 static xbt_dict_t computers;
  66 static SD_task_t root_task, end_task;
  67 static Agraph_t *dag_dot;
  68 static bool schedule = true;
  69
  70 static void dump_res()
  71 {
  72   unsigned int cursor;
  73   SD_task_t task;
  74   xbt_dynar_foreach(result, cursor, task) {
  75     XBT_INFO("Task %d", cursor);
  76     SD_task_dump(task);
  77   }
  78 }
  79
  80
  81 static void dot_task_free(void *task)
  82 {
  83   SD_task_t t = task;
  84   SD_task_destroy(t);
  85 }
  86
  87 static void TRACE_sd_dotloader (SD_task_t task, const char *category)
  88 {
  89   if (category){
  90     if (strlen (category) != 0){
  91       TRACE_category (category);
  92       SD_task_set_category (task, category);
  93     }
  94   }
  95 }
  96
  97 /** @brief loads a DOT file describing a DAG
  98  *
  99  * See http://www.graphviz.org/doc/info/lang.html
 100  * for more details.
 101  * To obtain information about transfers and tasks, two attributes are
 102  * required : size on task (execution time in Flop) and size on edge
 103  * (the amount of data transfer in bit).
 104  * if they aren't here, there choose to be equal to zero.
 105  */
 106 xbt_dynar_t SD_dotload(const char *filename)
 107 {
 108   SD_dotload_generic(filename);
 109   xbt_dynar_t computer = NULL;
 110   xbt_dict_cursor_t dict_cursor;
 111   char *computer_name;
 112   xbt_dict_foreach(computers,dict_cursor,computer_name,computer){
 113     xbt_dynar_free(&computer);
 114   }
 115   xbt_dict_free(&computers);
 116   return result;
 117 }
 118
 119 xbt_dynar_t SD_dotload_with_sched(const char *filename){
 120   SD_dotload_generic(filename);
 121
 122   if(schedule == true){
 123     xbt_dynar_t computer = NULL;
 124     xbt_dict_cursor_t dict_cursor;
 125     char *computer_name;
 126     const SD_workstation_t *workstations = SD_workstation_get_list ();
 127     xbt_dict_foreach(computers,dict_cursor,computer_name,computer){
 128       int count_computer = dot_parse_int(computer_name);
 129       unsigned int count=0;
 130       SD_task_t task;
 131       SD_task_t task_previous = NULL;
 132       xbt_dynar_foreach(computer,count,task){
 133         // add dependency between the previous and the task to avoid
 134         // parallel execution
 135         if(task != NULL ){
 136           if(task_previous != NULL &&
 137              !SD_task_dependency_exists(task_previous, task))
 138             SD_task_dependency_add(NULL, NULL, task_previous, task);
 139           SD_task_schedulel(task, 1, workstations[count_computer]);
 140           task_previous = task;
 141         }
 142       }
 143       xbt_dynar_free(&computer);
 144     }
 145     xbt_dict_free(&computers);
 146     if(acyclic_graph_detail(result))
 147       return result;
 148     else
 149       XBT_WARN("There is at least one cycle in the provided task graph");
 150   }else{
 151     XBT_WARN("The scheduling is ignored");
 152   }
 153   return NULL;
 154 }
 155
 156 xbt_dynar_t SD_dotload_generic(const char * filename)
 157 {
 158   xbt_assert(filename, "Unable to use a null file descriptor\n");
 159   //dag_dot =  agopen((char*)filename,Agstrictdirected,0);
 160   FILE *in_file = fopen(filename, "r");
 161   dag_dot = agread(in_file, NIL(Agdisc_t *));
 162
 163   result = xbt_dynar_new(sizeof(SD_task_t), dot_task_free);
 164   files = xbt_dict_new_homogeneous(&dot_task_free);
 165   jobs = xbt_dict_new_homogeneous(NULL);
 166   computers = xbt_dict_new_homogeneous(NULL);
 167   root_task = SD_task_create_comp_seq("root", NULL, 0);
 168   /* by design the root task is always SCHEDULABLE */
 169   __SD_task_set_state(root_task, SD_SCHEDULABLE);
 170
 171   xbt_dict_set(jobs, "root", root_task, NULL);
 172   xbt_dynar_push(result, &root_task);
 173   end_task = SD_task_create_comp_seq("end", NULL, 0);
 174   xbt_dict_set(jobs, "end", end_task, NULL);
 175
 176   Agnode_t *dag_node = NULL;
 177   for (dag_node = agfstnode(dag_dot); dag_node;
 178 #ifdef HAVE_CGRAPH_H
 179        dag_node = agnxtnode(dag_dot, dag_node)
 180 #elif HAVE_AGRAPH_H
 181        dag_node = agnxtnode(dag_node)
 182 #endif
 183        ) {
 184
 185   dot_add_task(dag_node);
 186   }
 187   agclose(dag_dot);
 188   xbt_dict_free(&jobs);
 189
 190   /* And now, post-process the files.
 191    * We want a file task per pair of computation tasks exchanging the file. Duplicate on need
 192    * Files not produced in the system are said to be produced by root task (top of DAG).
 193    * Files not consumed in the system are said to be consumed by end task (bottom of DAG).
 194    */
 195   xbt_dict_cursor_t cursor;
 196   SD_task_t file;
 197   char *name;
 198   xbt_dict_foreach(files, cursor, name, file) {
 199     unsigned int cpt1, cpt2;
 200     SD_task_t newfile = NULL;
 201     SD_dependency_t depbefore, depafter;
 202     if (xbt_dynar_is_empty(file->tasks_before)) {
 203       xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
 204         SD_task_t newfile =
 205             SD_task_create_comm_e2e(file->name, NULL, file->amount);
 206         SD_task_dependency_add(NULL, NULL, root_task, newfile);
 207         SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
 208         xbt_dynar_push(result, &newfile);
 209       }
 210     } else if (xbt_dynar_is_empty(file->tasks_after)) {
 211       xbt_dynar_foreach(file->tasks_before, cpt2, depbefore) {
 212         SD_task_t newfile =
 213             SD_task_create_comm_e2e(file->name, NULL, file->amount);
 214         SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
 215         SD_task_dependency_add(NULL, NULL, newfile, end_task);
 216         xbt_dynar_push(result, &newfile);
 217       }
 218     } else {
 219       xbt_dynar_foreach(file->tasks_before, cpt1, depbefore) {
 220         xbt_dynar_foreach(file->tasks_after, cpt2, depafter) {
 221           if (depbefore->src == depafter->dst) {
 222             XBT_WARN
 223                 ("File %s is produced and consumed by task %s. This loop dependency will prevent the execution of the task.",
 224                  file->name, depbefore->src->name);
 225           }
 226           newfile =
 227               SD_task_create_comm_e2e(file->name, NULL, file->amount);
 228           SD_task_dependency_add(NULL, NULL, depbefore->src, newfile);
 229           SD_task_dependency_add(NULL, NULL, newfile, depafter->dst);
 230           xbt_dynar_push(result, &newfile);
 231         }
 232       }
 233     }
 234   }
 235
 236   /* Push end task last */
 237   xbt_dynar_push(result, &end_task);
 238
 239   /* Free previous copy of the files */
 240   xbt_dict_free(&files);
 241   fclose(in_file);
 242   if(acyclic_graph_detail(result))
 243     return result;
 244   else {
 245     unsigned int cpt;
 246     XBT_ERROR("The DOT described in %s is not a DAG. It contains a cycle.",
 247               basename((char*)filename));
 248     xbt_dynar_foreach(result, cpt, file)
 249       SD_task_destroy(file);
 250      xbt_dynar_free_container(&result);
 251   }
 252   free(dag_dot);
 253   return NULL;
 254 }
 255
 256 /* dot_add_task create a sd_task and all transfers required for this
 257  * task. The execution time of the task is given by the attribute size.
 258  * The unit of size is the Flop.*/
 259 void dot_add_task(Agnode_t * dag_node)
 260 {
 261   char *name = agnameof(dag_node);
 262   SD_task_t current_job;
 263   double runtime = dot_parse_double(agget(dag_node, (char *) "size"));
 264
 265   XBT_DEBUG("See <job id=%s runtime=%s %.0f>", name,
 266         agget(dag_node, (char *) "size"), runtime);
 267   current_job = xbt_dict_get_or_null(jobs, name);
 268   if (current_job == NULL) {
 269     current_job =
 270         SD_task_create_comp_seq(name, NULL , runtime);
 271 #ifdef HAVE_TRACING
 272    TRACE_sd_dotloader (current_job, agget (dag_node, (char*)"category"));
 273 #endif
 274     xbt_dict_set(jobs, name, current_job, NULL);
 275     xbt_dynar_push(result, &current_job);
 276   }
 277   Agedge_t *e;
 278   int count = 0;
 279
 280 #ifdef HAVE_CGRAPH_H
 281   for (e = agfstin(dag_dot, dag_node); e; e = agnxtin(dag_dot, e))
 282 #elif HAVE_AGRAPH_H
 283   for (e = agfstin(dag_node); e; e = agnxtin(e))
 284 #endif
 285   {
 286   dot_add_input_dependencies(current_job, e);
 287   count++;
 288   }
 289   if (count == 0 && current_job != root_task) {
 290     SD_task_dependency_add(NULL, NULL, root_task, current_job);
 291   }
 292   count = 0;
 293 #ifdef HAVE_CGRAPH_H
 294   for (e = agfstout(dag_dot, dag_node); e; e = agnxtout(dag_dot, e))
 295 #elif HAVE_AGRAPH_H
 296   for (e = agfstout(dag_node); e; e = agnxtout(e))
 297 #endif
 298   {
 299
 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 = 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 = 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 }