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 change_name(SD_task_t task){
 163   SD_task_t child, parent;
 164   xbt_dynar_t children, parents;
 165   char *new_name;
 166
 167   children = SD_task_get_children(task);
 168   parents = SD_task_get_parents(task);
 169
 170   xbt_dynar_get_cpy(children,0,&child);
 171   xbt_dynar_get_cpy(parents,0,&parent);
 172
 173   new_name = bprintf("%s_%s_%s",
 174                      SD_task_get_name(parent),
 175                      SD_task_get_name(task),
 176                      SD_task_get_name(child));
 177
 178   SD_task_set_name (task, new_name);
 179
 180   xbt_dynar_free_container(&children);
 181   xbt_dynar_free_container(&parents);
 182   free(new_name);
 183 }
 184
 185 static void output_xml(FILE *out, xbt_dynar_t dax){
 186   unsigned int i,j, k;
 187   int current_nworkstations;
 188   const int nworkstations = SD_workstation_get_number();
 189   const SD_workstation_t * workstations = SD_workstation_get_list();
 190   SD_task_t task;
 191   SD_workstation_t * list;
 192
 193   fprintf(out,"<?xml version=\"1.0\"?>\n");
 194   fprintf(out,"<grid_schedule>\n");
 195   fprintf(out,"   <grid_info>\n");
 196   fprintf(out,"      <info name=\"nb_clusters\" value=\"1\"/>\n");
 197   fprintf(out,"         <clusters>\n");
 198   fprintf(out,"            <cluster id=\"1\" hosts=\"%d\" first_host=\"0\"/>\n",
 199           nworkstations);
 200   fprintf(out,"         </clusters>\n");
 201   fprintf(out,"      </grid_info>\n");
 202   fprintf(out,"   <node_infos>\n");
 203
 204   xbt_dynar_foreach(dax, i, task){
 205     fprintf(out,"      <node_statistics>\n");
 206     fprintf(out,"         <node_property name=\"id\" value=\"%s\"/>\n",
 207             SD_task_get_name(task));
 208     fprintf(out,"         <node_property name=\"type\" value=\"");
 209     if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ)
 210       fprintf(out,"computation\"/>\n");
 211     if (SD_task_get_kind(task) == SD_TASK_COMM_E2E)
 212       fprintf(out,"transfer\"/>\n");
 213
 214     fprintf(out,"         <node_property name=\"start_time\" value=\"%.3f\"/>\n",
 215             SD_task_get_start_time(task));
 216     fprintf(out,"         <node_property name=\"end_time\" value=\"%.3f\"/>\n",
 217             SD_task_get_finish_time(task));
 218     fprintf(out,"         <configuration>\n");
 219
 220     current_nworkstations = SD_task_get_workstation_count(task);
 221
 222     fprintf(out,"            <conf_property name=\"host_nb\" value=\"%d\"/>\n",
 223             current_nworkstations);
 224
 225     fprintf(out,"            <host_lists>\n");
 226     list = SD_task_get_workstation_list(task);
 227     for (j=0;j<current_nworkstations;j++){
 228       for (k=0;k<nworkstations;k++){
 229         if (!strcmp(SD_workstation_get_name(workstations[k]),
 230                     SD_workstation_get_name(list[j]))){
 231           fprintf(out,"               <hosts start=\"%u\" nb=\"1\"/>\n",k);
 232           fprintf(out,
 233                   "            <conf_property name=\"cluster_id\" value=\"0\"/>\n");
 234           break;
 235         }
 236       }
 237     }
 238     fprintf(out,"            </host_lists>\n");
 239     fprintf(out,"         </configuration>\n");
 240     fprintf(out,"      </node_statistics>\n");
 241   }
 242   fprintf(out,"   </node_infos>\n");
 243   fprintf(out,"</grid_schedule>\n");
 244 }
 245
 246 int main(int argc, char **argv) {
 247   unsigned int cursor, selected_idx=0;
 248   double finish_time, min_finish_time = -1.0;
 249   SD_task_t task, selected_task=NULL;
 250   xbt_dynar_t ready_tasks;
 251   SD_workstation_t workstation, selected_workstation=NULL;
 252   int total_nworkstations=0;
 253   const SD_workstation_t *workstations=NULL;
 254   xbt_dynar_t dax, changed;
 255   FILE *out=NULL;
 256
 257   /* initialisation of SD */
 258   SD_init(&argc, argv);
 259
 260   /* Check our arguments */
 261   if (argc < 3) {
 262     INFO1("Usage: %s platform_file dax_file [jedule_file]", argv[0]);
 263     INFO1("example: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed",
 264           argv[0]);
 265     exit(1);
 266   }
 267   char *tracefilename;
 268   if (argc == 3) {
 269     char *last=strrchr(argv[2],'.');
 270
 271     tracefilename=bprintf("%.*s.jed",
 272                           (int)(last==NULL?strlen(argv[2]):last-argv[2]),
 273                           argv[2]);
 274   } else {
 275     tracefilename = xbt_strdup(argv[3]);
 276   }
 277
 278   /* creation of the environment */
 279   SD_create_environment(argv[1]);
 280
 281   /*  Allocating the workstation attribute */
 282   total_nworkstations = SD_workstation_get_number();
 283   workstations = SD_workstation_get_list();
 284
 285   for(cursor=0; cursor<total_nworkstations; cursor++)
 286     SD_workstation_allocate_attribute(workstations[cursor]);
 287
 288
 289   /* load the DAX file */
 290   dax=SD_daxload(argv[2]);
 291
 292   xbt_dynar_foreach(dax,cursor,task) {
 293     if (SD_task_get_kind(task)==SD_TASK_COMM_E2E){
 294       change_name(task);
 295       SD_task_watch(task,SD_DONE);
 296     } else {
 297       SD_task_watch(task,SD_DONE);
 298     }
 299   }
 300
 301   /* Schedule the root first */
 302   xbt_dynar_get_cpy(dax, 0, &task);
 303   workstation =  SD_task_get_best_workstation(task);
 304   SD_task_schedulel(task, 1, workstation);
 305
 306   while(!xbt_dynar_is_empty((changed = SD_simulate(-1.0)))){
 307     /* Get the set of ready tasks */
 308     ready_tasks= get_ready_tasks(dax);
 309     if (!xbt_dynar_length(ready_tasks)) {
 310       xbt_dynar_free_container(&ready_tasks);
 311       xbt_dynar_free_container(&changed);
 312       /* there is no ready task, let advance the simulation */
 313       continue;
 314     }
 315     /* For each ready task:
 316      * get the workstation that minimizes the completion time.
 317      * select the task that has the minimum completion time on
 318      * its best workstation.
 319      */
 320     xbt_dynar_foreach(ready_tasks, cursor, task){
 321       DEBUG1("%s is ready", SD_task_get_name(task));
 322       workstation =  SD_task_get_best_workstation(task);
 323       finish_time = finish_on_at(task, workstation);
 324       if (min_finish_time == -1. || finish_time < min_finish_time) {
 325         min_finish_time = finish_time;
 326         selected_task = task;
 327         selected_workstation = workstation;
 328         selected_idx = cursor;
 329       }
 330     }
 331
 332     INFO2("Schedule %s on %s", SD_task_get_name(selected_task),
 333           SD_workstation_get_name(selected_workstation));
 334
 335     SD_task_schedulel(selected_task, 1, selected_workstation);
 336     SD_workstation_set_available_at(selected_workstation,
 337                                     min_finish_time);
 338
 339     xbt_dynar_free_container(&ready_tasks);
 340     /* reset the min_finish_time for the next set of ready tasks */
 341     min_finish_time = -1.;
 342     xbt_dynar_free_container(&changed);
 343   }
 344
 345   INFO1("Simulation Time: %f", SD_get_clock());
 346
 347
 348
 349
 350   INFO0("------------------- Produce the trace file---------------------------");
 351   INFO1("Producing the trace of the run into %s",tracefilename);
 352   out = fopen(tracefilename,"w");
 353   xbt_assert1(out,"Cannot write to %s",tracefilename);
 354   free(tracefilename);
 355
 356   output_xml(out, dax);
 357
 358   fclose(out);
 359
 360
 361   xbt_dynar_free_container(&ready_tasks);
 362   xbt_dynar_free_container(&changed);
 363
 364   xbt_dynar_foreach(dax,cursor,task) {
 365     SD_task_destroy(task);
 366   }
 367
 368   for(cursor=0; cursor<total_nworkstations; cursor++)
 369     SD_workstation_free_attribute(workstations[cursor]);
 370
 371   /* exit */
 372   SD_exit();
 373   return 0;
 374 }