examples/simdag/mixtesim/src/heft.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #include "mixtesim_prototypes.h"
   6 #include "list_scheduling.h"
   7
   8 #include "simdag/simdag.h"
   9 #include "xbt/log.h"
  10
  11 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mixtesim_heft, mixtesim,
  12                                 "Logging specific to Mixtesim (heft)");
  13
  14 /* static function prototypes */
  15
  16 static Node *computeNodeList(DAG dag);
  17 static int rankUCompareNode(const void *n1, const void *n2);
  18 static int scheduleList(DAG dag, Node *L);
  19 static void scheduleNode(Node node);
  20
  21 static double computeAverageLinkSpeed();
  22 static double computeAverageLinkLatency();
  23 static double computeAverageExecutionTime(Node node);
  24
  25 static void assignMeanCost(Node node);
  26 static double computeAndAssignRankU(Node node);
  27
  28
  29 static double computeEarliestStartTime(Node node, SD_workstation_t host);
  30 static double computeEarliestFinishTime(Node node, SD_workstation_t host);
  31 static void scheduleNodeOnHost(Node node, SD_workstation_t host);
  32
  33
  34 /*
  35  * HEFT():  Implementation of HEFT
  36  */
  37 int HEFT(DAG dag)
  38 {
  39   Node *L=NULL;
  40
  41   /* Compute mean cost for each node */
  42   assignMeanCost(dag->root);
  43
  44   /* Compute Rank_u for each node */
  45   computeAndAssignRankU(dag->root);
  46
  47   /* Compute the list for the schedule */
  48   if ((L = computeNodeList(dag)) == NULL)
  49     return -1;
  50
  51   /* Schedule */
  52   if (scheduleList(dag,L) == -1)
  53     return -1;
  54
  55   /* Analyze */
  56 /*   if (analyzeSchedule (grid,dag,L) == -1) */
  57 /*     return -1; */
  58
  59   /* Implement the Simgrid schedule */
  60   implementSimgridSchedule(dag,L);
  61
  62   if (L)
  63     free (L);
  64
  65   return 0;
  66 }
  67
  68 static Node *computeNodeList(DAG dag)
  69 {
  70   int i;
  71   int nb_comp_nodes=0;
  72   Node *L=NULL;
  73
  74   for (i=0;i<dag->nb_nodes;i++) {
  75     if (dag->nodes[i]->type != NODE_COMPUTATION)
  76       continue;
  77     L = (Node *)realloc(L,(nb_comp_nodes+1)*sizeof(Node));
  78     L[nb_comp_nodes] = dag->nodes[i];
  79     nb_comp_nodes++;
  80   }
  81
  82   /* sort L by rank_u */
  83   qsort(L,nb_comp_nodes,sizeof(Node),rankUCompareNode);
  84
  85   /* NULL-terminate the list */
  86   L = (Node *)realloc(L,(nb_comp_nodes+1)*sizeof(Node));
  87   L[nb_comp_nodes]=NULL;
  88
  89   return L;
  90 }
  91
  92 /*
  93  * rankUCompareNode()
  94  */
  95 static int rankUCompareNode(const void *n1, const void *n2)
  96 {
  97   double rank_u1, rank_u2;
  98
  99   rank_u1 = NODE_ATTR((*((Node *)n1)))->rank_u;
 100   rank_u2 = NODE_ATTR((*((Node *)n2)))->rank_u;
 101
 102   if (rank_u1 > rank_u2)
 103     return -1;
 104   else if (rank_u1 == rank_u2)
 105     return 0;
 106   else
 107     return 1;
 108 }
 109
 110 /*
 111  * scheduleList()
 112  */
 113 static int scheduleList(DAG dag, Node *L)
 114 {
 115   int i=0;
 116   Node node;
 117
 118   /* Schedules the nodes in the order of list L */
 119   while ((node=L[i++])) {
 120     scheduleNode(node);
 121   }
 122   return 0;
 123 }
 124
 125 /*
 126  * scheduleNode()
 127  *   pick a host
 128  */
 129 static void scheduleNode(Node node)
 130 {
 131   int i;
 132   SD_workstation_t host;
 133   SD_workstation_t best_host;
 134   double EFT;
 135   double min_EFT=-1.0;
 136   int nb_hosts = SD_workstation_get_number();
 137   const SD_workstation_t *hosts = SD_workstation_get_list();
 138
 139   /* pick the best host */
 140   for (i=0;i<nb_hosts;i++) {
 141     host = hosts[i];
 142     /* compute the start_time on that host */
 143     EFT = computeEarliestFinishTime(node, host);
 144 /*     fprintf(stderr,"EFT %s on %s = %f\n",node->sg_task->name, */
 145 /*          host->sg_host->name, EFT); */
 146
 147     /* is it the best one ? */
 148     if ((min_EFT == -1.0)||
 149         (EFT < min_EFT)) {
 150       min_EFT = EFT;
 151       best_host = host;
 152     }
 153   }
 154
 155   scheduleNodeOnHost(node, best_host);
 156
 157   return;
 158 }
 159
 160 /*
 161  * computeAverageLinkSpeed()
 162  */
 163 static double computeAverageLinkSpeed()
 164 {
 165   int i;
 166   double bandwidth, ave;
 167   int nb_links = SD_link_get_number();
 168   const SD_link_t *links = SD_link_get_list();
 169
 170   ave=0.0;
 171   for (i=0;i<nb_links;i++) {
 172     bandwidth = SD_link_get_current_bandwidth(links[i]);
 173     ave += bandwidth;
 174   }
 175   return (ave / nb_links);
 176 }
 177
 178 /*
 179  * computeAverageLinkLatency()
 180  */
 181 static double computeAverageLinkLatency()
 182 {
 183   int i;
 184   double latency, ave;
 185   int nb_links = SD_link_get_number();
 186   const SD_link_t *links = SD_link_get_list();
 187
 188   ave=0.0;
 189   for (i=0;i<nb_links;i++) {
 190     latency = SD_link_get_current_latency(links[i]);
 191     ave += latency;
 192   }
 193   return (ave / nb_links);
 194 }
 195
 196 /*
 197  *computeAverageExecutionTime()
 198  */
 199 static double computeAverageExecutionTime(Node node)
 200 {
 201   int i;
 202   double exec_time, ave;
 203   int nb_hosts = SD_workstation_get_number();
 204   const SD_workstation_t *hosts = SD_workstation_get_list();
 205   double communication_amount = 0.0;
 206
 207   ave=0.0;
 208   for (i=0;i<nb_hosts;i++) {
 209     exec_time =
 210       SD_task_get_execution_time(node->sd_task, 1, &hosts[i],
 211                                  &node->cost, &communication_amount, -1.0);
 212
 213       ave += exec_time;
 214     }
 215
 216   return (ave / nb_hosts);
 217 }
 218
 219 /*
 220  * computeAverageCommunicationTime()
 221  */
 222 static double computeAverageCommunicationTime(Node node)
 223 {
 224   return (computeAverageLinkLatency() +
 225           (node->cost / computeAverageLinkSpeed()));
 226 }
 227
 228 /*
 229  * computeEarliestFinishTime()
 230  */
 231 static double computeEarliestFinishTime(Node node, SD_workstation_t host)
 232 {
 233   double executionTime, EST;
 234   double communication_amount = 0.0;
 235
 236   EST = computeEarliestStartTime(node, host);
 237   executionTime =
 238     SD_task_get_execution_time(node->sd_task, 1, &host, &node->cost,
 239                                &communication_amount, -1.0);
 240
 241   return executionTime + EST;
 242 }
 243
 244 /*
 245  * computeEarliestStartTime()
 246  */
 247 static double computeEarliestStartTime(Node node, SD_workstation_t host)
 248 {
 249   double earliest_start_time=0.0;
 250   int i;
 251   double host_available = HOST_ATTR(host)->first_available;
 252   double data_available;
 253   double transfer_time;
 254   double last_data_available;
 255   Node parent,grand_parent;
 256   SD_workstation_t grand_parent_host;
 257 /*   SD_link_t link; */
 258
 259   if (node->nb_parents != 0) {
 260     /* compute last_data_available */
 261     last_data_available=-1.0;
 262     for (i=0;i<node->nb_parents;i++) {
 263       parent = node->parents[i];
 264
 265       /* No transfers to schedule */
 266       if (parent->type == NODE_ROOT) {
 267         data_available=0.0;
 268         break;
 269       }
 270       /* normal case */
 271       if (parent->type == NODE_TRANSFER) {
 272         if (parent->nb_parents > 1) {
 273           fprintf(stderr,"Warning: transfer has 2 parents\n");
 274         }
 275         grand_parent = parent->parents[0];
 276         grand_parent_host = NODE_ATTR(grand_parent)->host;
 277         transfer_time =
 278           SD_route_get_communication_time(grand_parent_host, host, parent->cost);
 279
 280 /*      link = SD_workstation_route_get_list(grand_parent_host, host)[0]; */
 281
 282 /*      if (link->global_index == -1) { */
 283 /*        /\* it is the local link so transfer_time = 0 *\/ */
 284 /*        transfer_time = 0.0; */
 285 /*      } else { */
 286 /*        transfer_time = SG_getLinkLatency(link->sg_link,  */
 287 /*                                          NODE_ATTR(grand_parent)->finish) +  */
 288 /*          parent->cost/SG_getLinkBandwidth(link->sg_link,  */
 289 /*                                           NODE_ATTR(grand_parent)->finish); */
 290 /*      } */
 291         data_available = NODE_ATTR(grand_parent)->finish + transfer_time;
 292       }
 293
 294       /* no transfer */
 295       if (parent->type == NODE_COMPUTATION) {
 296         data_available = NODE_ATTR(parent)->finish;
 297       }
 298
 299       if (last_data_available < data_available)
 300         last_data_available = data_available;
 301     }
 302
 303     /* return the MAX "*/
 304     earliest_start_time = MAX(host_available,last_data_available);
 305
 306   }
 307   return earliest_start_time;
 308 }
 309
 310
 311 /*
 312  * computeAndAssignRankU()
 313  */
 314 static double computeAndAssignRankU(Node node)
 315 {
 316   int i;
 317   double my_rank_u = 0.0, max_rank_u, current_child_rank_u;
 318   Node child,grand_child;
 319
 320   my_rank_u = NODE_ATTR(node)->mean_cost;
 321   max_rank_u = -1.0;
 322
 323   for (i=0;i<node->nb_children;i++) {
 324     child = node->children[i];
 325
 326     if (node->type == NODE_ROOT)
 327       {
 328         my_rank_u = computeAndAssignRankU(child);
 329       }
 330
 331     if (child->type == NODE_TRANSFER) { /* normal case */
 332       if (child->nb_children > 1) {
 333         fprintf(stderr,"Warning: transfer has 2 children\n");
 334       }
 335       grand_child = child->children[0];
 336       current_child_rank_u = NODE_ATTR(child)->mean_cost +
 337         computeAndAssignRankU(grand_child);
 338       if (max_rank_u < current_child_rank_u)
 339         max_rank_u = current_child_rank_u;
 340     }
 341     else /* child is the end node */
 342       max_rank_u = 0.0;
 343
 344   }
 345
 346   my_rank_u += max_rank_u;
 347
 348   NODE_ATTR(node)->rank_u = my_rank_u;
 349   return my_rank_u ;
 350 }
 351
 352 /*
 353  * assignMeanCost()
 354  */
 355 static void assignMeanCost(Node node)
 356 {
 357   int i;
 358
 359   for (i=0;i<node->nb_children;i++) {
 360     if (node->children[i]->type == NODE_COMPUTATION)
 361       NODE_ATTR(node->children[i])->mean_cost =
 362         computeAverageExecutionTime(node->children[i]);
 363     else
 364       NODE_ATTR(node->children[i])->mean_cost =
 365         computeAverageCommunicationTime(node->children[i]);
 366     assignMeanCost(node->children[i]);
 367   }
 368   return;
 369 }
 370
 371
 372 /*
 373  * scheduleNodeOnHost()
 374  */
 375 static void scheduleNodeOnHost(Node node, SD_workstation_t host)
 376 {
 377   int i;
 378   double data_available, transfer_time,  last_data_available;
 379 /*   SD_link_t link; */
 380   Node parent, grand_parent;
 381   SD_workstation_t grand_parent_host;
 382   double communication_amount = 0.0;
 383
 384   INFO2("Affecting node '%s' to host '%s'", SD_task_get_name(node->sd_task),
 385          SD_workstation_get_name(host));
 386
 387   last_data_available=-1.0;
 388   for (i=0;i<node->nb_parents;i++) {
 389     parent = node->parents[i];
 390
 391     if (parent->type == NODE_ROOT) {/* No transfers to schedule */
 392       data_available=0.0;
 393       break;
 394     }
 395
 396     if (parent->type == NODE_TRANSFER) {  /* normal case */
 397       if (parent->nb_parents > 1) {
 398         fprintf(stderr,"Warning: transfer has 2 parents\n");
 399       }
 400       grand_parent = parent->parents[0];
 401       grand_parent_host = NODE_ATTR(grand_parent)->host;
 402       transfer_time =
 403         SD_route_get_communication_time(grand_parent_host, host, parent->cost);
 404
 405 /*       link = SD_workstation_route_get_list(grand_parent_host, host)[0]; */
 406
 407 /*       if (link->global_index == -1) { */
 408 /*      /\* it is the local link so transfer_time = 0 *\/ */
 409 /*      transfer_time = 0.0; */
 410 /*       } else { */
 411 /*      transfer_time = SG_getLinkLatency(link->sg_link,  */
 412 /*                                        NODE_ATTR(grand_parent)->finish) +  */
 413 /*        parent->cost/SG_getLinkBandwidth(link->sg_link,  */
 414 /*                                         NODE_ATTR(grand_parent)->finish); */
 415 /*       } */
 416
 417       data_available = NODE_ATTR(grand_parent)->finish + transfer_time;
 418     }
 419
 420     /* no transfer */
 421     if (parent->type == NODE_COMPUTATION) {
 422       data_available = NODE_ATTR(parent)->finish;
 423     }
 424
 425     if (last_data_available < data_available)
 426       last_data_available = data_available;
 427   }
 428
 429   /* node attributes */
 430   NODE_ATTR(node)->start=MAX(last_data_available,
 431                   HOST_ATTR(host)->first_available);
 432   NODE_ATTR(node)->finish=NODE_ATTR(node)->start +
 433     SD_task_get_execution_time(node->sd_task, 1, &host, &node->cost,
 434                                &communication_amount, -1.0);
 435 /*     SG_getPrediction(SG_PERFECT, 0.0, NULL,host->sg_host, */
 436 /*                   NODE_ATTR(node)->start,node->cost); */
 437
 438   NODE_ATTR(node)->host = host;
 439   NODE_ATTR(node)->state = LIST_SCHEDULING_SCHEDULED;
 440
 441   /* host attributes */
 442   HOST_ATTR(host)->first_available = NODE_ATTR(node)->finish;
 443
 444   return;
 445 }