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