examples/deprecated/simdag/scheduling/sd_scheduling.c

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