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