examples/simdag/scheduling/minmin_test.c

   1 /* simple test to schedule a DAX file with the Min-Min algorithm.           */
   2
   3 /* Copyright (c) 2009, 2010. 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 "simdag/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 };
  24
  25 static void SD_workstation_allocate_attribute(SD_workstation_t workstation)
  26 {
  27   void *data;
  28   data = calloc(1, sizeof(struct _WorkstationAttribute));
  29   SD_workstation_set_data(workstation, data);
  30 }
  31
  32 static void SD_workstation_free_attribute(SD_workstation_t workstation)
  33 {
  34   free(SD_workstation_get_data(workstation));
  35   SD_workstation_set_data(workstation, NULL);
  36 }
  37
  38 static double SD_workstation_get_available_at(SD_workstation_t workstation)
  39 {
  40   WorkstationAttribute attr =
  41       (WorkstationAttribute) SD_workstation_get_data(workstation);
  42   return attr->available_at;
  43 }
  44
  45 static void SD_workstation_set_available_at(SD_workstation_t workstation,
  46                                             double time)
  47 {
  48   WorkstationAttribute attr =
  49       (WorkstationAttribute) SD_workstation_get_data(workstation);
  50   attr->available_at = time;
  51   SD_workstation_set_data(workstation, attr);
  52 }
  53
  54
  55 static xbt_dynar_t get_ready_tasks(xbt_dynar_t dax)
  56 {
  57   unsigned int i;
  58   xbt_dynar_t ready_tasks;
  59   SD_task_t task;
  60
  61   ready_tasks = xbt_dynar_new(sizeof(SD_task_t), NULL);
  62   xbt_dynar_foreach(dax, i, task) {
  63     if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ &&
  64         SD_task_get_state(task) == SD_SCHEDULABLE) {
  65       xbt_dynar_push(ready_tasks, &task);
  66     }
  67   }
  68   DEBUG1("There are %lu ready tasks", xbt_dynar_length(ready_tasks));
  69
  70   return ready_tasks;
  71 }
  72
  73 static double finish_on_at(SD_task_t task, SD_workstation_t workstation)
  74 {
  75   unsigned int i;
  76   double data_available = 0.;
  77   double redist_time = 0;
  78   double last_data_available;
  79   SD_task_t parent, grand_parent;
  80   xbt_dynar_t parents, grand_parents;
  81
  82   int grand_parent_nworkstations;
  83   SD_workstation_t *grand_parent_workstation_list;
  84
  85   parents = SD_task_get_parents(task);
  86
  87   if (xbt_dynar_length(parents)) {
  88     /* compute last_data_available */
  89     last_data_available = -1.0;
  90     xbt_dynar_foreach(parents, i, parent) {
  91
  92       /* normal case */
  93       if (SD_task_get_kind(parent) == SD_TASK_COMM_E2E) {
  94         grand_parents = SD_task_get_parents(parent);
  95
  96         if (xbt_dynar_length(grand_parents) > 1) {
  97           ERROR1("Warning: transfer %s has 2 parents",
  98                  SD_task_get_name(parent));
  99         }
 100         xbt_dynar_get_cpy(grand_parents, 0, &grand_parent);
 101
 102         grand_parent_nworkstations =
 103             SD_task_get_workstation_count(grand_parent);
 104         grand_parent_workstation_list =
 105             SD_task_get_workstation_list(grand_parent);
 106         /* Estimate the redistribution time from this parent */
 107         redist_time =
 108             SD_route_get_communication_time(grand_parent_workstation_list
 109                                             [0], workstation,
 110                                             SD_task_get_amount(parent));
 111         data_available =
 112             SD_task_get_finish_time(grand_parent) + redist_time;
 113
 114         xbt_dynar_free_container(&grand_parents);
 115       }
 116
 117       /* no transfer, control dependency */
 118       if (SD_task_get_kind(parent) == SD_TASK_COMP_SEQ) {
 119         data_available = SD_task_get_finish_time(parent);
 120       }
 121
 122       if (last_data_available < data_available)
 123         last_data_available = data_available;
 124
 125     }
 126
 127     xbt_dynar_free_container(&parents);
 128
 129     return MAX(SD_workstation_get_available_at(workstation),
 130                last_data_available) +
 131         SD_workstation_get_computation_time(workstation,
 132                                             SD_task_get_amount(task));
 133   } else {
 134     xbt_dynar_free_container(&parents);
 135
 136     return SD_workstation_get_available_at(workstation) +
 137         SD_workstation_get_computation_time(workstation,
 138                                             SD_task_get_amount(task));
 139   }
 140 }
 141
 142 static SD_workstation_t SD_task_get_best_workstation(SD_task_t task)
 143 {
 144   int i;
 145   double EFT, min_EFT = -1.0;
 146   const SD_workstation_t *workstations = SD_workstation_get_list();
 147   int nworkstations = SD_workstation_get_number();
 148   SD_workstation_t best_workstation;
 149
 150   best_workstation = workstations[0];
 151   min_EFT = finish_on_at(task, workstations[0]);
 152
 153   for (i = 1; i < nworkstations; i++) {
 154     EFT = finish_on_at(task, workstations[i]);
 155     DEBUG3("%s finishes on %s at %f",
 156            SD_task_get_name(task),
 157            SD_workstation_get_name(workstations[i]), EFT);
 158
 159     if (EFT < min_EFT) {
 160       min_EFT = EFT;
 161       best_workstation = workstations[i];
 162     }
 163   }
 164
 165   return best_workstation;
 166 }
 167
 168 static void output_xml(FILE * out, xbt_dynar_t dax)
 169 {
 170   unsigned int i, j, k;
 171   int current_nworkstations;
 172   const int nworkstations = SD_workstation_get_number();
 173   const SD_workstation_t *workstations = SD_workstation_get_list();
 174   SD_task_t task;
 175   SD_workstation_t *list;
 176
 177   fprintf(out, "<?xml version=\"1.0\"?>\n");
 178   fprintf(out, "<grid_schedule>\n");
 179   fprintf(out, "   <grid_info>\n");
 180   fprintf(out, "      <info name=\"nb_clusters\" value=\"1\"/>\n");
 181   fprintf(out, "         <clusters>\n");
 182   fprintf(out,
 183           "            <cluster id=\"1\" hosts=\"%d\" first_host=\"0\"/>\n",
 184           nworkstations);
 185   fprintf(out, "         </clusters>\n");
 186   fprintf(out, "      </grid_info>\n");
 187   fprintf(out, "   <node_infos>\n");
 188
 189   xbt_dynar_foreach(dax, i, task) {
 190     fprintf(out, "      <node_statistics>\n");
 191     fprintf(out, "         <node_property name=\"id\" value=\"%s\"/>\n",
 192             SD_task_get_name(task));
 193     fprintf(out, "         <node_property name=\"type\" value=\"");
 194     if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ)
 195       fprintf(out, "computation\"/>\n");
 196     if (SD_task_get_kind(task) == SD_TASK_COMM_E2E)
 197       fprintf(out, "transfer\"/>\n");
 198
 199     fprintf(out,
 200             "         <node_property name=\"start_time\" value=\"%.3f\"/>\n",
 201             SD_task_get_start_time(task));
 202     fprintf(out,
 203             "         <node_property name=\"end_time\" value=\"%.3f\"/>\n",
 204             SD_task_get_finish_time(task));
 205     fprintf(out, "         <configuration>\n");
 206
 207     current_nworkstations = SD_task_get_workstation_count(task);
 208
 209     fprintf(out,
 210             "            <conf_property name=\"host_nb\" value=\"%d\"/>\n",
 211             current_nworkstations);
 212
 213     fprintf(out, "            <host_lists>\n");
 214     list = SD_task_get_workstation_list(task);
 215     for (j = 0; j < current_nworkstations; j++) {
 216       for (k = 0; k < nworkstations; k++) {
 217         if (!strcmp(SD_workstation_get_name(workstations[k]),
 218                     SD_workstation_get_name(list[j]))) {
 219           fprintf(out, "               <hosts start=\"%u\" nb=\"1\"/>\n",
 220                   k);
 221           fprintf(out,
 222                   "            <conf_property name=\"cluster_id\" value=\"0\"/>\n");
 223           break;
 224         }
 225       }
 226     }
 227     fprintf(out, "            </host_lists>\n");
 228     fprintf(out, "         </configuration>\n");
 229     fprintf(out, "      </node_statistics>\n");
 230   }
 231   fprintf(out, "   </node_infos>\n");
 232   fprintf(out, "</grid_schedule>\n");
 233 }
 234
 235 int main(int argc, char **argv)
 236 {
 237   unsigned int cursor, selected_idx = 0;
 238   double finish_time, min_finish_time = -1.0;
 239   SD_task_t task, selected_task = NULL;
 240   xbt_dynar_t ready_tasks;
 241   SD_workstation_t workstation, selected_workstation = NULL;
 242   int total_nworkstations = 0;
 243   const SD_workstation_t *workstations = NULL;
 244   xbt_dynar_t dax, changed;
 245   FILE *out = NULL;
 246
 247   /* initialization of SD */
 248   SD_init(&argc, argv);
 249
 250   /* Check our arguments */
 251   if (argc < 3) {
 252     INFO1("Usage: %s platform_file dax_file [jedule_file]", argv[0]);
 253     INFO1
 254         ("example: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed",
 255          argv[0]);
 256     exit(1);
 257   }
 258   char *tracefilename;
 259   if (argc == 3) {
 260     char *last = strrchr(argv[2], '.');
 261
 262     tracefilename = bprintf("%.*s.jed",
 263                             (int) (last ==
 264                                    NULL ? strlen(argv[2]) : last -
 265                                    argv[2]), argv[2]);
 266   } else {
 267     tracefilename = xbt_strdup(argv[3]);
 268   }
 269
 270   /* creation of the environment */
 271   SD_create_environment(argv[1]);
 272
 273   /*  Allocating the workstation attribute */
 274   total_nworkstations = SD_workstation_get_number();
 275   workstations = SD_workstation_get_list();
 276
 277   for (cursor = 0; cursor < total_nworkstations; cursor++)
 278     SD_workstation_allocate_attribute(workstations[cursor]);
 279
 280
 281   /* load the DAX file */
 282   dax = SD_daxload(argv[2]);
 283
 284   xbt_dynar_foreach(dax, cursor, task) {
 285     SD_task_watch(task, SD_DONE);
 286   }
 287
 288   /* Schedule the root first */
 289   xbt_dynar_get_cpy(dax, 0, &task);
 290   workstation = SD_task_get_best_workstation(task);
 291   SD_task_schedulel(task, 1, workstation);
 292
 293   while (!xbt_dynar_is_empty((changed = SD_simulate(-1.0)))) {
 294     /* Get the set of ready tasks */
 295     ready_tasks = get_ready_tasks(dax);
 296     if (!xbt_dynar_length(ready_tasks)) {
 297       xbt_dynar_free_container(&ready_tasks);
 298       xbt_dynar_free_container(&changed);
 299       /* there is no ready task, let advance the simulation */
 300       continue;
 301     }
 302     /* For each ready task:
 303      * get the workstation that minimizes the completion time.
 304      * select the task that has the minimum completion time on
 305      * its best workstation.
 306      */
 307     xbt_dynar_foreach(ready_tasks, cursor, task) {
 308       DEBUG1("%s is ready", SD_task_get_name(task));
 309       workstation = SD_task_get_best_workstation(task);
 310       finish_time = finish_on_at(task, workstation);
 311       if (min_finish_time == -1. || finish_time < min_finish_time) {
 312         min_finish_time = finish_time;
 313         selected_task = task;
 314         selected_workstation = workstation;
 315         selected_idx = cursor;
 316       }
 317     }
 318
 319     INFO2("Schedule %s on %s", SD_task_get_name(selected_task),
 320           SD_workstation_get_name(selected_workstation));
 321
 322     SD_task_schedulel(selected_task, 1, selected_workstation);
 323     SD_workstation_set_available_at(selected_workstation, min_finish_time);
 324
 325     xbt_dynar_free_container(&ready_tasks);
 326     /* reset the min_finish_time for the next set of ready tasks */
 327     min_finish_time = -1.;
 328     xbt_dynar_free_container(&changed);
 329   }
 330
 331   INFO1("Simulation Time: %f", SD_get_clock());
 332
 333
 334
 335
 336   INFO0
 337       ("------------------- Produce the trace file---------------------------");
 338   INFO1("Producing the trace of the run into %s", tracefilename);
 339   out = fopen(tracefilename, "w");
 340   xbt_assert1(out, "Cannot write to %s", tracefilename);
 341   free(tracefilename);
 342
 343   output_xml(out, dax);
 344
 345   fclose(out);
 346
 347
 348   xbt_dynar_free_container(&ready_tasks);
 349   xbt_dynar_free_container(&changed);
 350
 351   xbt_dynar_foreach(dax, cursor, task) {
 352     SD_task_destroy(task);
 353   }
 354
 355   for (cursor = 0; cursor < total_nworkstations; cursor++)
 356     SD_workstation_free_attribute(workstations[cursor]);
 357
 358   /* exit */
 359   SD_exit();
 360   return 0;
 361 }