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 int main(int argc, char **argv)
 190 {
 191   unsigned int cursor;
 192   double finish_time, min_finish_time = -1.0;
 193   SD_task_t task, selected_task = NULL, last_scheduled_task;
 194   xbt_dynar_t ready_tasks;
 195   sg_host_t workstation, selected_workstation = NULL;
 196   int total_nworkstations = 0;
 197   const sg_host_t *workstations = NULL;
 198   char * tracefilename = NULL;
 199   xbt_dynar_t dax;
 200
 201   /* initialization of SD */
 202   SD_init(&argc, argv);
 203
 204   /* Check our arguments */
 205   xbt_assert(argc > 2, "Usage: %s platform_file dax_file [jedule_file]\n"
 206              "\tExample: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed", argv[0], argv[0]);
 207
 208   if (argc == 4)
 209     tracefilename = xbt_strdup(argv[3]);
 210
 211   /* creation of the environment */
 212   SD_create_environment(argv[1]);
 213
 214   /*  Allocating the workstation attribute */
 215   total_nworkstations = sg_host_count();
 216   workstations = sg_host_list();
 217
 218   for (cursor = 0; cursor < total_nworkstations; cursor++)
 219     sg_host_allocate_attribute(workstations[cursor]);
 220
 221
 222   /* load the DAX file */
 223   dax = SD_daxload(argv[2]);
 224
 225   xbt_dynar_foreach(dax, cursor, task) {
 226     SD_task_watch(task, SD_DONE);
 227   }
 228
 229   /* Schedule the root first */
 230   xbt_dynar_get_cpy(dax, 0, &task);
 231   workstation = SD_task_get_best_workstation(task);
 232   SD_task_schedulel(task, 1, workstation);
 233
 234   while (!xbt_dynar_is_empty(SD_simulate(-1.0))) {
 235     /* Get the set of ready tasks */
 236     ready_tasks = get_ready_tasks(dax);
 237     if (xbt_dynar_is_empty(ready_tasks)) {
 238       xbt_dynar_free_container(&ready_tasks);
 239       /* there is no ready task, let advance the simulation */
 240       continue;
 241     }
 242     /* For each ready task:
 243      * get the workstation that minimizes the completion time.
 244      * select the task that has the minimum completion time on
 245      * its best workstation.
 246      */
 247     xbt_dynar_foreach(ready_tasks, cursor, task) {
 248       XBT_DEBUG("%s is ready", SD_task_get_name(task));
 249       workstation = SD_task_get_best_workstation(task);
 250       finish_time = finish_on_at(task, workstation);
 251       if (min_finish_time == -1. || finish_time < min_finish_time) {
 252         min_finish_time = finish_time;
 253         selected_task = task;
 254         selected_workstation = workstation;
 255       }
 256     }
 257
 258     XBT_INFO("Schedule %s on %s", SD_task_get_name(selected_task),
 259           sg_host_get_name(selected_workstation));
 260
 261     SD_task_schedulel(selected_task, 1, selected_workstation);
 262
 263     /*
 264      * SimDag allows tasks to be executed concurrently when they can by default.
 265      * Yet schedulers take decisions assuming that tasks wait for resource
 266      * availability to start.
 267      * The solution (well crude hack is to keep track of the last task scheduled
 268      * on a workstation and add a special type of dependency if needed to
 269      * force the sequential execution meant by the scheduler.
 270      * If the last scheduled task is already done, has failed or is a
 271      * predecessor of the current task, no need for a new dependency
 272     */
 273
 274     last_scheduled_task =
 275       sg_host_get_last_scheduled_task(selected_workstation);
 276     if (last_scheduled_task &&
 277   (SD_task_get_state(last_scheduled_task) != SD_DONE) &&
 278   (SD_task_get_state(last_scheduled_task) != SD_FAILED) &&
 279   !SD_task_dependency_exists(
 280      sg_host_get_last_scheduled_task(selected_workstation),
 281      selected_task))
 282       SD_task_dependency_add("resource", NULL,
 283            last_scheduled_task, selected_task);
 284
 285     sg_host_set_last_scheduled_task(selected_workstation, selected_task);
 286
 287     sg_host_set_available_at(selected_workstation, min_finish_time);
 288
 289     xbt_dynar_free_container(&ready_tasks);
 290     /* reset the min_finish_time for the next set of ready tasks */
 291     min_finish_time = -1.;
 292   }
 293
 294   XBT_INFO("Simulation Time: %f", SD_get_clock());
 295
 296   XBT_INFO("------------------- Produce the trace file---------------------------");
 297   XBT_INFO("Producing a jedule output (if active) of the run into %s", tracefilename?tracefilename:"minmin_test.jed");
 298 #ifdef HAVE_JEDULE
 299   jedule_sd_dump(tracefilename);
 300 #endif
 301   free(tracefilename);
 302
 303   xbt_dynar_free_container(&ready_tasks);
 304
 305   xbt_dynar_foreach(dax, cursor, task) {
 306     SD_task_destroy(task);
 307   }
 308   xbt_dynar_free_container(&dax);
 309
 310   for (cursor = 0; cursor < total_nworkstations; cursor++)
 311     sg_host_free_attribute(workstations[cursor]);
 312
 313   /* exit */
 314   SD_exit();
 315   return 0;
 316 }