examples/simdag/scheduling/sd_scheduling.c

   1 /* Copyright (c) 2009-2016. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 /* simple test to schedule a DAX file with the Min-Min algorithm.           */
   8 #include <string.h>
   9 #include "simgrid/simdag.h"
  10
  11 #if HAVE_JEDULE
  12 #include "simgrid/jedule/jedule_sd_binding.h"
  13 #endif
  14
  15 XBT_LOG_NEW_DEFAULT_CATEGORY(test, "Logging specific to this SimDag example");
  16
  17 typedef struct _HostAttribute *HostAttribute;
  18 struct _HostAttribute {
  19   /* Earliest time at which a host is ready to execute a task */
  20   double available_at;
  21   SD_task_t last_scheduled_task;
  22 };
  23
  24 static void sg_host_allocate_attribute(sg_host_t host)
  25 {
  26   void *data;
  27   data = calloc(1, sizeof(struct _HostAttribute));
  28   sg_host_user_set(host, data);
  29 }
  30
  31 static void sg_host_free_attribute(sg_host_t host)
  32 {
  33   free(sg_host_user(host));
  34   sg_host_user_set(host, NULL);
  35 }
  36
  37 static double sg_host_get_available_at(sg_host_t host)
  38 {
  39   HostAttribute attr = (HostAttribute) sg_host_user(host);
  40   return attr->available_at;
  41 }
  42
  43 static void sg_host_set_available_at(sg_host_t host, double time)
  44 {
  45   HostAttribute attr = (HostAttribute) sg_host_user(host);
  46   attr->available_at = time;
  47   sg_host_user_set(host, attr);
  48 }
  49
  50 static SD_task_t sg_host_get_last_scheduled_task( sg_host_t host){
  51   HostAttribute attr = (HostAttribute) sg_host_user(host);
  52   return attr->last_scheduled_task;
  53 }
  54
  55 static void sg_host_set_last_scheduled_task(sg_host_t host, SD_task_t task){
  56   HostAttribute attr = (HostAttribute) sg_host_user(host);
  57   attr->last_scheduled_task=task;
  58   sg_host_user_set(host, attr);
  59 }
  60
  61 static xbt_dynar_t get_ready_tasks(xbt_dynar_t dax)
  62 {
  63   unsigned int i;
  64   xbt_dynar_t ready_tasks;
  65   SD_task_t task;
  66
  67   ready_tasks = xbt_dynar_new(sizeof(SD_task_t), NULL);
  68   xbt_dynar_foreach(dax, i, task) {
  69     if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ && SD_task_get_state(task) == SD_SCHEDULABLE) {
  70       xbt_dynar_push(ready_tasks, &task);
  71     }
  72   }
  73   XBT_DEBUG("There are %lu ready tasks", xbt_dynar_length(ready_tasks));
  74
  75   return ready_tasks;
  76 }
  77
  78 static double finish_on_at(SD_task_t task, sg_host_t host)
  79 {
  80   double result;
  81   unsigned int i;
  82   double data_available = 0.;
  83   double redist_time = 0;
  84   double last_data_available;
  85
  86   xbt_dynar_t parents = SD_task_get_parents(task);
  87
  88   if (!xbt_dynar_is_empty(parents)) {
  89     /* compute last_data_available */
  90     SD_task_t parent;
  91     last_data_available = -1.0;
  92     xbt_dynar_foreach(parents, i, parent) {
  93       /* normal case */
  94       if (SD_task_get_kind(parent) == SD_TASK_COMM_E2E) {
  95         xbt_dynar_t grand_parents = SD_task_get_parents(parent);
  96         SD_task_t grand_parent;
  97
  98         xbt_assert(xbt_dynar_length(grand_parents) <2, "Error: transfer %s has 2 parents", SD_task_get_name(parent));
  99
 100         xbt_dynar_get_cpy(grand_parents, 0, &grand_parent);
 101
 102         sg_host_t * grand_parent_host_list = SD_task_get_workstation_list(grand_parent);
 103         /* Estimate the redistribution time from this parent */
 104         if (SD_task_get_amount(parent) <= 1e-6){
 105           redist_time= 0;
 106         } else {
 107           redist_time = SD_route_get_latency(grand_parent_host_list[0], host) +
 108                         SD_task_get_amount(parent) / SD_route_get_bandwidth(grand_parent_host_list[0], host);
 109         }
 110         data_available = 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     xbt_dynar_free_container(&parents);
 125
 126     result = MAX(sg_host_get_available_at(host), last_data_available) + SD_task_get_amount(task)/sg_host_speed(host);
 127   } else {
 128     xbt_dynar_free_container(&parents);
 129
 130     result = sg_host_get_available_at(host) + SD_task_get_amount(task)/sg_host_speed(host);
 131   }
 132   return result;
 133 }
 134
 135 static sg_host_t SD_task_get_best_host(SD_task_t task)
 136 {
 137   const sg_host_t *hosts = sg_host_list();
 138   int nhosts = sg_host_count();
 139   sg_host_t best_host = hosts[0];
 140   double min_EFT = finish_on_at(task, hosts[0]);
 141
 142   for (int i = 1; i < nhosts; i++) {
 143     double EFT = finish_on_at(task, hosts[i]);
 144     XBT_DEBUG("%s finishes on %s at %f", SD_task_get_name(task), sg_host_get_name(hosts[i]), EFT);
 145
 146     if (EFT < min_EFT) {
 147       min_EFT = EFT;
 148       best_host = hosts[i];
 149     }
 150   }
 151   return best_host;
 152 }
 153
 154 int main(int argc, char **argv)
 155 {
 156   unsigned int cursor;
 157   double min_finish_time = -1.0;
 158   SD_task_t task, selected_task = NULL;
 159   xbt_dynar_t ready_tasks;
 160   sg_host_t selected_host = NULL;
 161   char * tracefilename = NULL;
 162
 163   /* initialization of SD */
 164   SD_init(&argc, argv);
 165
 166   /* Check our arguments */
 167   xbt_assert(argc > 2, "Usage: %s platform_file dax_file [jedule_file]\n"
 168              "\tExample: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed", argv[0], argv[0]);
 169
 170   if (argc == 4)
 171     tracefilename = xbt_strdup(argv[3]);
 172
 173   /* creation of the environment */
 174   SD_create_environment(argv[1]);
 175
 176   /*  Allocating the host attribute */
 177   int total_nhosts = sg_host_count();
 178   const sg_host_t *hosts = sg_host_list();
 179
 180   for (cursor = 0; cursor < total_nhosts; cursor++)
 181     sg_host_allocate_attribute(hosts[cursor]);
 182
 183   /* load the DAX file */
 184   xbt_dynar_t dax = SD_daxload(argv[2]);
 185
 186   xbt_dynar_foreach(dax, cursor, task) {
 187     SD_task_watch(task, SD_DONE);
 188   }
 189
 190   /* Schedule the root first */
 191   xbt_dynar_get_cpy(dax, 0, &task);
 192   sg_host_t host = SD_task_get_best_host(task);
 193   SD_task_schedulel(task, 1, host);
 194
 195   while (!xbt_dynar_is_empty(SD_simulate(-1.0))) {
 196     /* Get the set of ready tasks */
 197     ready_tasks = get_ready_tasks(dax);
 198     if (xbt_dynar_is_empty(ready_tasks)) {
 199       xbt_dynar_free_container(&ready_tasks);
 200       /* there is no ready task, let advance the simulation */
 201       continue;
 202     }
 203     /* For each ready task:
 204      * get the host that minimizes the completion time.
 205      * select the task that has the minimum completion time on its best host.
 206      */
 207     xbt_dynar_foreach(ready_tasks, cursor, task) {
 208       XBT_DEBUG("%s is ready", SD_task_get_name(task));
 209       host = SD_task_get_best_host(task);
 210       double finish_time = finish_on_at(task, host);
 211       if (min_finish_time < 0 || finish_time < min_finish_time) {
 212         min_finish_time = finish_time;
 213         selected_task = task;
 214         selected_host = host;
 215       }
 216     }
 217
 218     XBT_INFO("Schedule %s on %s", SD_task_get_name(selected_task), sg_host_get_name(selected_host));
 219     SD_task_schedulel(selected_task, 1, selected_host);
 220
 221     /*
 222      * SimDag allows tasks to be executed concurrently when they can by default.
 223      * Yet schedulers take decisions assuming that tasks wait for resource availability to start.
 224      * The solution (well crude hack is to keep track of the last task scheduled on a host and add a special type of
 225      * dependency if needed to force the sequential execution meant by the scheduler.
 226      * If the last scheduled task is already done, has failed or is a predecessor of the current task, no need for a
 227      * new dependency
 228     */
 229
 230     SD_task_t last_scheduled_task = sg_host_get_last_scheduled_task(selected_host);
 231     if (last_scheduled_task && (SD_task_get_state(last_scheduled_task) != SD_DONE) &&
 232         (SD_task_get_state(last_scheduled_task) != SD_FAILED) &&
 233         !SD_task_dependency_exists(sg_host_get_last_scheduled_task(selected_host), selected_task))
 234       SD_task_dependency_add("resource", NULL, last_scheduled_task, selected_task);
 235
 236     sg_host_set_last_scheduled_task(selected_host, selected_task);
 237     sg_host_set_available_at(selected_host, min_finish_time);
 238
 239     xbt_dynar_free_container(&ready_tasks);
 240     /* reset the min_finish_time for the next set of ready tasks */
 241     min_finish_time = -1.;
 242   }
 243
 244   XBT_INFO("Simulation Time: %f", SD_get_clock());
 245   XBT_INFO("------------------- Produce the trace file---------------------------");
 246   XBT_INFO("Producing a jedule output (if active) of the run into %s", tracefilename?tracefilename:"minmin_test.jed");
 247 #if HAVE_JEDULE
 248   jedule_sd_dump(tracefilename);
 249 #endif
 250   free(tracefilename);
 251
 252   xbt_dynar_free_container(&ready_tasks);
 253
 254   xbt_dynar_foreach(dax, cursor, task) {
 255     SD_task_destroy(task);
 256   }
 257   xbt_dynar_free_container(&dax);
 258
 259   for (cursor = 0; cursor < total_nhosts; cursor++)
 260     sg_host_free_attribute(hosts[cursor]);
 261
 262   /* exit */
 263   SD_exit();
 264   return 0;
 265 }