examples/simdag/scheduling/minmin_test.c

   1 /* simple test to schedule a DAX file with the Min-Min algorithm.           */
   2
   3 /* Copyright (c) 2009-2015. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #include <stdlib.h>
  10 #include <stdio.h>
  11 #include "simgrid/simdag.h"
  12 #include "xbt/log.h"
  13 #include "xbt/ex.h"
  14 #include <string.h>
  15
  16 XBT_LOG_NEW_DEFAULT_CATEGORY(test,
  17                              "Logging specific to this SimDag example");
  18
  19 typedef struct _WorkstationAttribute *WorkstationAttribute;
  20 struct _WorkstationAttribute {
  21   /* Earliest time at wich a workstation is ready to execute a task */
  22   double available_at;
  23   SD_task_t last_scheduled_task;
  24 };
  25
  26 static void SD_workstation_allocate_attribute(SD_workstation_t workstation)
  27 {
  28   void *data;
  29   data = calloc(1, sizeof(struct _WorkstationAttribute));
  30   SD_workstation_set_data(workstation, data);
  31 }
  32
  33 static void SD_workstation_free_attribute(SD_workstation_t workstation)
  34 {
  35   free(SD_workstation_get_data(workstation));
  36   SD_workstation_set_data(workstation, NULL);
  37 }
  38
  39 static double SD_workstation_get_available_at(SD_workstation_t workstation)
  40 {
  41   WorkstationAttribute attr =
  42       (WorkstationAttribute) SD_workstation_get_data(workstation);
  43   return attr->available_at;
  44 }
  45
  46 static void SD_workstation_set_available_at(SD_workstation_t workstation,
  47                                             double time)
  48 {
  49   WorkstationAttribute attr =
  50       (WorkstationAttribute) SD_workstation_get_data(workstation);
  51   attr->available_at = time;
  52   SD_workstation_set_data(workstation, attr);
  53 }
  54
  55 static SD_task_t SD_workstation_get_last_scheduled_task( SD_workstation_t workstation){
  56   WorkstationAttribute attr =
  57       (WorkstationAttribute) SD_workstation_get_data(workstation);
  58   return attr->last_scheduled_task;
  59 }
  60
  61 static void SD_workstation_set_last_scheduled_task(SD_workstation_t workstation,
  62     SD_task_t task){
  63   WorkstationAttribute attr =
  64       (WorkstationAttribute) SD_workstation_get_data(workstation);
  65   attr->last_scheduled_task=task;
  66   SD_workstation_set_data(workstation, attr);
  67 }
  68
  69 static xbt_dynar_t get_ready_tasks(xbt_dynar_t dax)
  70 {
  71   unsigned int i;
  72   xbt_dynar_t ready_tasks;
  73   SD_task_t task;
  74
  75   ready_tasks = xbt_dynar_new(sizeof(SD_task_t), NULL);
  76   xbt_dynar_foreach(dax, i, task) {
  77     if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ &&
  78         SD_task_get_state(task) == SD_SCHEDULABLE) {
  79       xbt_dynar_push(ready_tasks, &task);
  80     }
  81   }
  82   XBT_DEBUG("There are %lu ready tasks", xbt_dynar_length(ready_tasks));
  83
  84   return ready_tasks;
  85 }
  86
  87 static double finish_on_at(SD_task_t task, SD_workstation_t workstation)
  88 {
  89   volatile double result;
  90   unsigned int i;
  91   double data_available = 0.;
  92   double redist_time = 0;
  93   double last_data_available;
  94   SD_task_t parent, grand_parent;
  95   xbt_dynar_t parents, grand_parents;
  96
  97   SD_workstation_t *grand_parent_workstation_list;
  98
  99   parents = SD_task_get_parents(task);
 100
 101   if (!xbt_dynar_is_empty(parents)) {
 102     /* compute last_data_available */
 103     last_data_available = -1.0;
 104     xbt_dynar_foreach(parents, i, parent) {
 105
 106       /* normal case */
 107       if (SD_task_get_kind(parent) == SD_TASK_COMM_E2E) {
 108         grand_parents = SD_task_get_parents(parent);
 109
 110         if (xbt_dynar_length(grand_parents) > 1) {
 111           XBT_ERROR("Warning: transfer %s has 2 parents",
 112                  SD_task_get_name(parent));
 113         }
 114         xbt_dynar_get_cpy(grand_parents, 0, &grand_parent);
 115
 116         grand_parent_workstation_list =
 117             SD_task_get_workstation_list(grand_parent);
 118         /* Estimate the redistribution time from this parent */
 119         redist_time =
 120             SD_route_get_communication_time(grand_parent_workstation_list
 121                                             [0], workstation,
 122                                             SD_task_get_amount(parent));
 123         data_available =
 124             SD_task_get_finish_time(grand_parent) + redist_time;
 125
 126         xbt_dynar_free_container(&grand_parents);
 127       }
 128
 129       /* no transfer, control dependency */
 130       if (SD_task_get_kind(parent) == SD_TASK_COMP_SEQ) {
 131         data_available = SD_task_get_finish_time(parent);
 132       }
 133
 134       if (last_data_available < data_available)
 135         last_data_available = data_available;
 136
 137     }
 138
 139     xbt_dynar_free_container(&parents);
 140
 141     result = MAX(SD_workstation_get_available_at(workstation),
 142                last_data_available) +
 143         SD_workstation_get_computation_time(workstation,
 144                                             SD_task_get_amount(task));
 145   } else {
 146     xbt_dynar_free_container(&parents);
 147
 148     result = SD_workstation_get_available_at(workstation) +
 149         SD_workstation_get_computation_time(workstation,
 150                                             SD_task_get_amount(task));
 151   }
 152   return result;
 153 }
 154
 155 static SD_workstation_t SD_task_get_best_workstation(SD_task_t task)
 156 {
 157   int i;
 158   double EFT, min_EFT = -1.0;
 159   const SD_workstation_t *workstations = SD_workstation_get_list();
 160   int nworkstations = SD_workstation_get_number();
 161   SD_workstation_t best_workstation;
 162
 163   best_workstation = workstations[0];
 164   min_EFT = finish_on_at(task, workstations[0]);
 165
 166   for (i = 1; i < nworkstations; i++) {
 167     EFT = finish_on_at(task, workstations[i]);
 168     XBT_DEBUG("%s finishes on %s at %f",
 169            SD_task_get_name(task),
 170            SD_workstation_get_name(workstations[i]), EFT);
 171
 172     if (EFT < min_EFT) {
 173       min_EFT = EFT;
 174       best_workstation = workstations[i];
 175     }
 176   }
 177
 178   return best_workstation;
 179 }
 180
 181 static void output_xml(FILE * out, xbt_dynar_t dax)
 182 {
 183   unsigned int i, j, k;
 184   int current_nworkstations;
 185   const int nworkstations = SD_workstation_get_number();
 186   const SD_workstation_t *workstations = SD_workstation_get_list();
 187   SD_task_t task;
 188   SD_workstation_t *list;
 189
 190   fprintf(out, "<?xml version=\"1.0\"?>\n");
 191   fprintf(out, "<grid_schedule>\n");
 192   fprintf(out, "   <grid_info>\n");
 193   fprintf(out, "      <info name=\"nb_clusters\" value=\"1\"/>\n");
 194   fprintf(out, "         <clusters>\n");
 195   fprintf(out,
 196           "            <cluster id=\"1\" hosts=\"%d\" first_host=\"0\"/>\n",
 197           nworkstations);
 198   fprintf(out, "         </clusters>\n");
 199   fprintf(out, "      </grid_info>\n");
 200   fprintf(out, "   <node_infos>\n");
 201
 202   xbt_dynar_foreach(dax, i, task) {
 203     fprintf(out, "      <node_statistics>\n");
 204     fprintf(out, "         <node_property name=\"id\" value=\"%s\"/>\n",
 205             SD_task_get_name(task));
 206     fprintf(out, "         <node_property name=\"type\" value=\"");
 207     if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ)
 208       fprintf(out, "computation\"/>\n");
 209     if (SD_task_get_kind(task) == SD_TASK_COMM_E2E)
 210       fprintf(out, "transfer\"/>\n");
 211
 212     fprintf(out,
 213             "         <node_property name=\"start_time\" value=\"%.3f\"/>\n",
 214             SD_task_get_start_time(task));
 215     fprintf(out,
 216             "         <node_property name=\"end_time\" value=\"%.3f\"/>\n",
 217             SD_task_get_finish_time(task));
 218     fprintf(out, "         <configuration>\n");
 219
 220     current_nworkstations = SD_task_get_workstation_count(task);
 221
 222     fprintf(out,
 223             "            <conf_property name=\"host_nb\" value=\"%d\"/>\n",
 224             current_nworkstations);
 225
 226     fprintf(out, "            <host_lists>\n");
 227     list = SD_task_get_workstation_list(task);
 228     for (j = 0; j < current_nworkstations; j++) {
 229       for (k = 0; k < nworkstations; k++) {
 230         if (!strcmp(SD_workstation_get_name(workstations[k]),
 231                     SD_workstation_get_name(list[j]))) {
 232           fprintf(out, "               <hosts start=\"%u\" nb=\"1\"/>\n",
 233                   k);
 234           fprintf(out,
 235                   "            <conf_property name=\"cluster_id\" value=\"0\"/>\n");
 236           break;
 237         }
 238       }
 239     }
 240     fprintf(out, "            </host_lists>\n");
 241     fprintf(out, "         </configuration>\n");
 242     fprintf(out, "      </node_statistics>\n");
 243   }
 244   fprintf(out, "   </node_infos>\n");
 245   fprintf(out, "</grid_schedule>\n");
 246 }
 247
 248 int main(int argc, char **argv)
 249 {
 250   unsigned int cursor;
 251   double finish_time, min_finish_time = -1.0;
 252   SD_task_t task, selected_task = NULL, last_scheduled_task;
 253   xbt_dynar_t ready_tasks;
 254   SD_workstation_t workstation, selected_workstation = NULL;
 255   int total_nworkstations = 0;
 256   const SD_workstation_t *workstations = NULL;
 257   xbt_dynar_t dax, changed;
 258   FILE *out = NULL;
 259
 260   /* initialization of SD */
 261   SD_init(&argc, argv);
 262
 263   /* Check our arguments */
 264   if (argc < 3) {
 265     XBT_INFO("Usage: %s platform_file dax_file [jedule_file]", argv[0]);
 266     XBT_INFO
 267         ("example: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed",
 268          argv[0]);
 269     exit(1);
 270   }
 271   char *tracefilename;
 272   if (argc == 3) {
 273     char *last = strrchr(argv[2], '.');
 274
 275     tracefilename = bprintf("%.*s.jed",
 276                             (int) (last ==
 277                                    NULL ? strlen(argv[2]) : last -
 278                                    argv[2]), argv[2]);
 279   } else {
 280     tracefilename = xbt_strdup(argv[3]);
 281   }
 282
 283   /* creation of the environment */
 284   SD_create_environment(argv[1]);
 285
 286   /*  Allocating the workstation attribute */
 287   total_nworkstations = SD_workstation_get_number();
 288   workstations = SD_workstation_get_list();
 289
 290   for (cursor = 0; cursor < total_nworkstations; cursor++)
 291     SD_workstation_allocate_attribute(workstations[cursor]);
 292
 293
 294   /* load the DAX file */
 295   dax = SD_daxload(argv[2]);
 296
 297   xbt_dynar_foreach(dax, cursor, task) {
 298     SD_task_watch(task, SD_DONE);
 299   }
 300
 301   /* Schedule the root first */
 302   xbt_dynar_get_cpy(dax, 0, &task);
 303   workstation = SD_task_get_best_workstation(task);
 304   SD_task_schedulel(task, 1, workstation);
 305
 306   while (!xbt_dynar_is_empty((changed = SD_simulate(-1.0)))) {
 307     /* Get the set of ready tasks */
 308     ready_tasks = get_ready_tasks(dax);
 309     if (xbt_dynar_is_empty(ready_tasks)) {
 310       xbt_dynar_free_container(&ready_tasks);
 311       xbt_dynar_free_container(&changed);
 312       /* there is no ready task, let advance the simulation */
 313       continue;
 314     }
 315     /* For each ready task:
 316      * get the workstation that minimizes the completion time.
 317      * select the task that has the minimum completion time on
 318      * its best workstation.
 319      */
 320     xbt_dynar_foreach(ready_tasks, cursor, task) {
 321       XBT_DEBUG("%s is ready", SD_task_get_name(task));
 322       workstation = SD_task_get_best_workstation(task);
 323       finish_time = finish_on_at(task, workstation);
 324       if (min_finish_time == -1. || finish_time < min_finish_time) {
 325         min_finish_time = finish_time;
 326         selected_task = task;
 327         selected_workstation = workstation;
 328       }
 329     }
 330
 331     XBT_INFO("Schedule %s on %s", SD_task_get_name(selected_task),
 332           SD_workstation_get_name(selected_workstation));
 333
 334     SD_task_schedulel(selected_task, 1, selected_workstation);
 335
 336     /*
 337      * SimDag allows tasks to be executed concurrently when they can by default.
 338      * Yet schedulers take decisions assuming that tasks wait for resource
 339      * availability to start.
 340      * The solution (well crude hack is to keep track of the last task scheduled
 341      * on a workstation and add a special type of dependency if needed to
 342      * force the sequential execution meant by the scheduler.
 343      * If the last scheduled task is already done, has failed or is a
 344      * predecessor of the current task, no need for a new dependency
 345     */
 346
 347     last_scheduled_task =
 348       SD_workstation_get_last_scheduled_task(selected_workstation);
 349     if (last_scheduled_task &&
 350   (SD_task_get_state(last_scheduled_task) != SD_DONE) &&
 351   (SD_task_get_state(last_scheduled_task) != SD_FAILED) &&
 352   !SD_task_dependency_exists(
 353      SD_workstation_get_last_scheduled_task(selected_workstation),
 354      selected_task))
 355       SD_task_dependency_add("resource", NULL,
 356            last_scheduled_task, selected_task);
 357
 358     SD_workstation_set_last_scheduled_task(selected_workstation, selected_task);
 359
 360     SD_workstation_set_available_at(selected_workstation, min_finish_time);
 361
 362     xbt_dynar_free_container(&ready_tasks);
 363     /* reset the min_finish_time for the next set of ready tasks */
 364     min_finish_time = -1.;
 365     xbt_dynar_free_container(&changed);
 366   }
 367
 368   XBT_INFO("Simulation Time: %f", SD_get_clock());
 369
 370
 371
 372
 373   XBT_INFO
 374       ("------------------- Produce the trace file---------------------------");
 375   XBT_INFO("Producing the trace of the run into %s", tracefilename);
 376   out = fopen(tracefilename, "w");
 377   xbt_assert(out, "Cannot write to %s", tracefilename);
 378   free(tracefilename);
 379
 380   output_xml(out, dax);
 381
 382   fclose(out);
 383
 384
 385   xbt_dynar_free_container(&ready_tasks);
 386   xbt_dynar_free_container(&changed);
 387
 388   xbt_dynar_foreach(dax, cursor, task) {
 389     SD_task_destroy(task);
 390   }
 391   xbt_dynar_free_container(&dax);
 392
 393   for (cursor = 0; cursor < total_nworkstations; cursor++)
 394     SD_workstation_free_attribute(workstations[cursor]);
 395
 396   /* exit */
 397   SD_exit();
 398   return 0;
 399 }