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