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