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 which a workstation is ready to execute a task */
  22   double available_at;
  23   SD_task_t last_scheduled_task;
  24 };
  25
  26 static void sg_host_allocate_attribute(sg_host_t workstation)
  27 {
  28   void *data;
  29   data = calloc(1, sizeof(struct _WorkstationAttribute));
  30   sg_host_user_set(workstation, data);
  31 }
  32
  33 static void sg_host_free_attribute(sg_host_t workstation)
  34 {
  35   free(sg_host_user(workstation));
  36   sg_host_user_set(workstation, NULL);
  37 }
  38
  39 static double sg_host_get_available_at(sg_host_t workstation)
  40 {
  41   WorkstationAttribute attr =
  42       (WorkstationAttribute) sg_host_user(workstation);
  43   return attr->available_at;
  44 }
  45
  46 static void sg_host_set_available_at(sg_host_t workstation,
  47                                             double time)
  48 {
  49   WorkstationAttribute attr =
  50       (WorkstationAttribute) sg_host_user(workstation);
  51   attr->available_at = time;
  52   sg_host_user_set(workstation, attr);
  53 }
  54
  55 static SD_task_t sg_host_get_last_scheduled_task( sg_host_t workstation){
  56   WorkstationAttribute attr =
  57       (WorkstationAttribute) sg_host_user(workstation);
  58   return attr->last_scheduled_task;
  59 }
  60
  61 static void sg_host_set_last_scheduled_task(sg_host_t workstation,
  62     SD_task_t task){
  63   WorkstationAttribute attr =
  64       (WorkstationAttribute) sg_host_user(workstation);
  65   attr->last_scheduled_task=task;
  66   sg_host_user_set(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, sg_host_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   sg_host_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         xbt_assert(xbt_dynar_length(grand_parents) <2,
 111                    "Error: 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         if (SD_task_get_amount(parent) == 0){
 120           redist_time= 0;
 121         } else {
 122           redist_time =
 123             SD_route_get_latency(grand_parent_workstation_list[0],
 124                                  workstation) +
 125             SD_task_get_amount(parent) /
 126             SD_route_get_bandwidth(grand_parent_workstation_list[0],
 127                                  workstation);
 128         }
 129         data_available =
 130             SD_task_get_finish_time(grand_parent) + redist_time;
 131
 132         xbt_dynar_free_container(&grand_parents);
 133       }
 134
 135       /* no transfer, control dependency */
 136       if (SD_task_get_kind(parent) == SD_TASK_COMP_SEQ) {
 137         data_available = SD_task_get_finish_time(parent);
 138       }
 139
 140       if (last_data_available < data_available)
 141         last_data_available = data_available;
 142
 143     }
 144
 145     xbt_dynar_free_container(&parents);
 146
 147     result = MAX(sg_host_get_available_at(workstation),
 148                last_data_available) +
 149              SD_task_get_amount(task)/sg_host_speed(workstation);
 150   } else {
 151     xbt_dynar_free_container(&parents);
 152
 153     result = sg_host_get_available_at(workstation) +
 154               SD_task_get_amount(task)/sg_host_speed(workstation);
 155   }
 156   return result;
 157 }
 158
 159 static sg_host_t SD_task_get_best_workstation(SD_task_t task)
 160 {
 161   int i;
 162   double EFT, min_EFT = -1.0;
 163   const sg_host_t *workstations = sg_host_list();
 164   int nworkstations = sg_host_count();
 165   sg_host_t best_workstation;
 166
 167   best_workstation = workstations[0];
 168   min_EFT = finish_on_at(task, workstations[0]);
 169
 170   for (i = 1; i < nworkstations; i++) {
 171     EFT = finish_on_at(task, workstations[i]);
 172     XBT_DEBUG("%s finishes on %s at %f",
 173            SD_task_get_name(task),
 174            sg_host_get_name(workstations[i]), EFT);
 175
 176     if (EFT < min_EFT) {
 177       min_EFT = EFT;
 178       best_workstation = workstations[i];
 179     }
 180   }
 181
 182   return best_workstation;
 183 }
 184
 185 static void output_xml(FILE * out, xbt_dynar_t dax)
 186 {
 187   unsigned int i, j, k;
 188   int current_nworkstations;
 189   const int nworkstations = sg_host_count();
 190   const sg_host_t *workstations = sg_host_list();
 191   SD_task_t task;
 192   sg_host_t *list;
 193
 194   fprintf(out, "<?xml version=\"1.0\"?>\n");
 195   fprintf(out, "<grid_schedule>\n");
 196   fprintf(out, "   <grid_info>\n");
 197   fprintf(out, "      <info name=\"nb_clusters\" value=\"1\"/>\n");
 198   fprintf(out, "         <clusters>\n");
 199   fprintf(out,
 200           "            <cluster id=\"1\" hosts=\"%d\" first_host=\"0\"/>\n",
 201           nworkstations);
 202   fprintf(out, "         </clusters>\n");
 203   fprintf(out, "      </grid_info>\n");
 204   fprintf(out, "   <node_infos>\n");
 205
 206   xbt_dynar_foreach(dax, i, task) {
 207     fprintf(out, "      <node_statistics>\n");
 208     fprintf(out, "         <node_property name=\"id\" value=\"%s\"/>\n",
 209             SD_task_get_name(task));
 210     fprintf(out, "         <node_property name=\"type\" value=\"");
 211     if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ)
 212       fprintf(out, "computation\"/>\n");
 213     if (SD_task_get_kind(task) == SD_TASK_COMM_E2E)
 214       fprintf(out, "transfer\"/>\n");
 215
 216     fprintf(out,
 217             "         <node_property name=\"start_time\" value=\"%.3f\"/>\n",
 218             SD_task_get_start_time(task));
 219     fprintf(out,
 220             "         <node_property name=\"end_time\" value=\"%.3f\"/>\n",
 221             SD_task_get_finish_time(task));
 222     fprintf(out, "         <configuration>\n");
 223
 224     current_nworkstations = SD_task_get_workstation_count(task);
 225
 226     fprintf(out,
 227             "            <conf_property name=\"host_nb\" value=\"%d\"/>\n",
 228             current_nworkstations);
 229
 230     fprintf(out, "            <host_lists>\n");
 231     list = SD_task_get_workstation_list(task);
 232     for (j = 0; j < current_nworkstations; j++) {
 233       for (k = 0; k < nworkstations; k++) {
 234         if (!strcmp(sg_host_get_name(workstations[k]),
 235                     sg_host_get_name(list[j]))) {
 236           fprintf(out, "               <hosts start=\"%u\" nb=\"1\"/>\n",
 237                   k);
 238           fprintf(out,
 239                   "            <conf_property name=\"cluster_id\" value=\"0\"/>\n");
 240           break;
 241         }
 242       }
 243     }
 244     fprintf(out, "            </host_lists>\n");
 245     fprintf(out, "         </configuration>\n");
 246     fprintf(out, "      </node_statistics>\n");
 247   }
 248   fprintf(out, "   </node_infos>\n");
 249   fprintf(out, "</grid_schedule>\n");
 250 }
 251
 252 int main(int argc, char **argv)
 253 {
 254   unsigned int cursor;
 255   double finish_time, min_finish_time = -1.0;
 256   SD_task_t task, selected_task = NULL, last_scheduled_task;
 257   xbt_dynar_t ready_tasks;
 258   sg_host_t workstation, selected_workstation = NULL;
 259   int total_nworkstations = 0;
 260   const sg_host_t *workstations = NULL;
 261   xbt_dynar_t dax;
 262   FILE *out = NULL;
 263
 264   /* initialization of SD */
 265   SD_init(&argc, argv);
 266
 267   /* Check our arguments */
 268   xbt_assert(argc > 2, "Usage: %s platform_file dax_file [jedule_file]\n"
 269              "\tExample: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed",
 270              argv[0], argv[0]);
 271
 272   char *last = strrchr(argv[2], '.');
 273   char * tracefilename = bprintf("%.*s.jed",(int) (last == NULL ?
 274                                                    strlen(argv[2]) :
 275                                                    last - argv[2]), argv[2]);
 276   if (argc == 4)
 277     tracefilename = xbt_strdup(argv[3]);
 278
 279   /* creation of the environment */
 280   SD_create_environment(argv[1]);
 281
 282   /*  Allocating the workstation attribute */
 283   total_nworkstations = sg_host_count();
 284   workstations = sg_host_list();
 285
 286   for (cursor = 0; cursor < total_nworkstations; cursor++)
 287     sg_host_allocate_attribute(workstations[cursor]);
 288
 289
 290   /* load the DAX file */
 291   dax = SD_daxload(argv[2]);
 292
 293   xbt_dynar_foreach(dax, cursor, task) {
 294     SD_task_watch(task, SD_DONE);
 295   }
 296
 297   /* Schedule the root first */
 298   xbt_dynar_get_cpy(dax, 0, &task);
 299   workstation = SD_task_get_best_workstation(task);
 300   SD_task_schedulel(task, 1, workstation);
 301
 302   while (!xbt_dynar_is_empty(SD_simulate(-1.0))) {
 303     /* Get the set of ready tasks */
 304     ready_tasks = get_ready_tasks(dax);
 305     if (xbt_dynar_is_empty(ready_tasks)) {
 306       xbt_dynar_free_container(&ready_tasks);
 307       /* there is no ready task, let advance the simulation */
 308       continue;
 309     }
 310     /* For each ready task:
 311      * get the workstation that minimizes the completion time.
 312      * select the task that has the minimum completion time on
 313      * its best workstation.
 314      */
 315     xbt_dynar_foreach(ready_tasks, cursor, task) {
 316       XBT_DEBUG("%s is ready", SD_task_get_name(task));
 317       workstation = SD_task_get_best_workstation(task);
 318       finish_time = finish_on_at(task, workstation);
 319       if (min_finish_time == -1. || finish_time < min_finish_time) {
 320         min_finish_time = finish_time;
 321         selected_task = task;
 322         selected_workstation = workstation;
 323       }
 324     }
 325
 326     XBT_INFO("Schedule %s on %s", SD_task_get_name(selected_task),
 327           sg_host_get_name(selected_workstation));
 328
 329     SD_task_schedulel(selected_task, 1, selected_workstation);
 330
 331     /*
 332      * SimDag allows tasks to be executed concurrently when they can by default.
 333      * Yet schedulers take decisions assuming that tasks wait for resource
 334      * availability to start.
 335      * The solution (well crude hack is to keep track of the last task scheduled
 336      * on a workstation and add a special type of dependency if needed to
 337      * force the sequential execution meant by the scheduler.
 338      * If the last scheduled task is already done, has failed or is a
 339      * predecessor of the current task, no need for a new dependency
 340     */
 341
 342     last_scheduled_task =
 343       sg_host_get_last_scheduled_task(selected_workstation);
 344     if (last_scheduled_task &&
 345   (SD_task_get_state(last_scheduled_task) != SD_DONE) &&
 346   (SD_task_get_state(last_scheduled_task) != SD_FAILED) &&
 347   !SD_task_dependency_exists(
 348      sg_host_get_last_scheduled_task(selected_workstation),
 349      selected_task))
 350       SD_task_dependency_add("resource", NULL,
 351            last_scheduled_task, selected_task);
 352
 353     sg_host_set_last_scheduled_task(selected_workstation, selected_task);
 354
 355     sg_host_set_available_at(selected_workstation, min_finish_time);
 356
 357     xbt_dynar_free_container(&ready_tasks);
 358     /* reset the min_finish_time for the next set of ready tasks */
 359     min_finish_time = -1.;
 360   }
 361
 362   XBT_INFO("Simulation Time: %f", SD_get_clock());
 363
 364
 365
 366
 367   XBT_INFO
 368       ("------------------- Produce the trace file---------------------------");
 369   XBT_INFO("Producing the trace of the run into %s", tracefilename);
 370   out = fopen(tracefilename, "w");
 371   xbt_assert(out, "Cannot write to %s", tracefilename);
 372   free(tracefilename);
 373
 374   output_xml(out, dax);
 375
 376   fclose(out);
 377
 378
 379   xbt_dynar_free_container(&ready_tasks);
 380
 381   xbt_dynar_foreach(dax, cursor, task) {
 382     SD_task_destroy(task);
 383   }
 384   xbt_dynar_free_container(&dax);
 385
 386   for (cursor = 0; cursor < total_nworkstations; cursor++)
 387     sg_host_free_attribute(workstations[cursor]);
 388
 389   /* exit */
 390   SD_exit();
 391   return 0;
 392 }