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