Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Merge branch 'master' of git+ssh://scm.gforge.inria.fr//gitroot//simgrid/simgrid
[simgrid.git] / 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   SD_task_t last_scheduled_task;
24 };
25
26 static void SD_workstation_allocate_attribute(SD_workstation_t workstation)
27 {
28   void *data;
29   data = calloc(1, sizeof(struct _WorkstationAttribute));
30   SD_workstation_set_data(workstation, data);
31 }
32
33 static void SD_workstation_free_attribute(SD_workstation_t workstation)
34 {
35   free(SD_workstation_get_data(workstation));
36   SD_workstation_set_data(workstation, NULL);
37 }
38
39 static double SD_workstation_get_available_at(SD_workstation_t workstation)
40 {
41   WorkstationAttribute attr =
42       (WorkstationAttribute) SD_workstation_get_data(workstation);
43   return attr->available_at;
44 }
45
46 static void SD_workstation_set_available_at(SD_workstation_t workstation,
47                                             double time)
48 {
49   WorkstationAttribute attr =
50       (WorkstationAttribute) SD_workstation_get_data(workstation);
51   attr->available_at = time;
52   SD_workstation_set_data(workstation, attr);
53 }
54
55 static SD_task_t SD_workstation_get_last_scheduled_task( SD_workstation_t workstation){
56   WorkstationAttribute attr =
57       (WorkstationAttribute) SD_workstation_get_data(workstation);
58   return attr->last_scheduled_task;
59 }
60
61 static void SD_workstation_set_last_scheduled_task(SD_workstation_t workstation,
62     SD_task_t task){
63   WorkstationAttribute attr =
64       (WorkstationAttribute) SD_workstation_get_data(workstation);
65   attr->last_scheduled_task=task;
66   SD_workstation_set_data(workstation, attr);
67 }
68
69 static xbt_dynar_t get_ready_tasks(xbt_dynar_t dax)
70 {
71   unsigned int i;
72   xbt_dynar_t ready_tasks;
73   SD_task_t task;
74
75   ready_tasks = xbt_dynar_new(sizeof(SD_task_t), NULL);
76   xbt_dynar_foreach(dax, i, task) {
77     if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ &&
78         SD_task_get_state(task) == SD_SCHEDULABLE) {
79       xbt_dynar_push(ready_tasks, &task);
80     }
81   }
82   XBT_DEBUG("There are %lu ready tasks", xbt_dynar_length(ready_tasks));
83
84   return ready_tasks;
85 }
86
87 static double finish_on_at(SD_task_t task, SD_workstation_t workstation)
88 {
89   volatile double result;
90   unsigned int i;
91   double data_available = 0.;
92   double redist_time = 0;
93   double last_data_available;
94   SD_task_t parent, grand_parent;
95   xbt_dynar_t parents, grand_parents;
96
97   SD_workstation_t *grand_parent_workstation_list;
98
99   parents = SD_task_get_parents(task);
100
101   if (!xbt_dynar_is_empty(parents)) {
102     /* compute last_data_available */
103     last_data_available = -1.0;
104     xbt_dynar_foreach(parents, i, parent) {
105
106       /* normal case */
107       if (SD_task_get_kind(parent) == SD_TASK_COMM_E2E) {
108         grand_parents = SD_task_get_parents(parent);
109
110         if (xbt_dynar_length(grand_parents) > 1) {
111           XBT_ERROR("Warning: transfer %s has 2 parents",
112                  SD_task_get_name(parent));
113         }
114         xbt_dynar_get_cpy(grand_parents, 0, &grand_parent);
115
116         grand_parent_workstation_list =
117             SD_task_get_workstation_list(grand_parent);
118         /* Estimate the redistribution time from this parent */
119         redist_time =
120             SD_route_get_communication_time(grand_parent_workstation_list
121                                             [0], workstation,
122                                             SD_task_get_amount(parent));
123         data_available =
124             SD_task_get_finish_time(grand_parent) + redist_time;
125
126         xbt_dynar_free_container(&grand_parents);
127       }
128
129       /* no transfer, control dependency */
130       if (SD_task_get_kind(parent) == SD_TASK_COMP_SEQ) {
131         data_available = SD_task_get_finish_time(parent);
132       }
133
134       if (last_data_available < data_available)
135         last_data_available = data_available;
136
137     }
138
139     xbt_dynar_free_container(&parents);
140
141     result = MAX(SD_workstation_get_available_at(workstation),
142                last_data_available) +
143         SD_workstation_get_computation_time(workstation,
144                                             SD_task_get_amount(task));
145   } else {
146     xbt_dynar_free_container(&parents);
147
148     result = SD_workstation_get_available_at(workstation) +
149         SD_workstation_get_computation_time(workstation,
150                                             SD_task_get_amount(task));
151   }
152   return result;
153 }
154
155 static SD_workstation_t SD_task_get_best_workstation(SD_task_t task)
156 {
157   int i;
158   double EFT, min_EFT = -1.0;
159   const SD_workstation_t *workstations = SD_workstation_get_list();
160   int nworkstations = SD_workstation_get_number();
161   SD_workstation_t best_workstation;
162
163   best_workstation = workstations[0];
164   min_EFT = finish_on_at(task, workstations[0]);
165
166   for (i = 1; i < nworkstations; i++) {
167     EFT = finish_on_at(task, workstations[i]);
168     XBT_DEBUG("%s finishes on %s at %f",
169            SD_task_get_name(task),
170            SD_workstation_get_name(workstations[i]), EFT);
171
172     if (EFT < min_EFT) {
173       min_EFT = EFT;
174       best_workstation = workstations[i];
175     }
176   }
177
178   return best_workstation;
179 }
180
181 static void output_xml(FILE * out, xbt_dynar_t dax)
182 {
183   unsigned int i, j, k;
184   int current_nworkstations;
185   const int nworkstations = SD_workstation_get_number();
186   const SD_workstation_t *workstations = SD_workstation_get_list();
187   SD_task_t task;
188   SD_workstation_t *list;
189
190   fprintf(out, "<?xml version=\"1.0\"?>\n");
191   fprintf(out, "<grid_schedule>\n");
192   fprintf(out, "   <grid_info>\n");
193   fprintf(out, "      <info name=\"nb_clusters\" value=\"1\"/>\n");
194   fprintf(out, "         <clusters>\n");
195   fprintf(out,
196           "            <cluster id=\"1\" hosts=\"%d\" first_host=\"0\"/>\n",
197           nworkstations);
198   fprintf(out, "         </clusters>\n");
199   fprintf(out, "      </grid_info>\n");
200   fprintf(out, "   <node_infos>\n");
201
202   xbt_dynar_foreach(dax, i, task) {
203     fprintf(out, "      <node_statistics>\n");
204     fprintf(out, "         <node_property name=\"id\" value=\"%s\"/>\n",
205             SD_task_get_name(task));
206     fprintf(out, "         <node_property name=\"type\" value=\"");
207     if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ)
208       fprintf(out, "computation\"/>\n");
209     if (SD_task_get_kind(task) == SD_TASK_COMM_E2E)
210       fprintf(out, "transfer\"/>\n");
211
212     fprintf(out,
213             "         <node_property name=\"start_time\" value=\"%.3f\"/>\n",
214             SD_task_get_start_time(task));
215     fprintf(out,
216             "         <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,
223             "            <conf_property name=\"host_nb\" value=\"%d\"/>\n",
224             current_nworkstations);
225
226     fprintf(out, "            <host_lists>\n");
227     list = SD_task_get_workstation_list(task);
228     for (j = 0; j < current_nworkstations; j++) {
229       for (k = 0; k < nworkstations; k++) {
230         if (!strcmp(SD_workstation_get_name(workstations[k]),
231                     SD_workstation_get_name(list[j]))) {
232           fprintf(out, "               <hosts start=\"%u\" nb=\"1\"/>\n",
233                   k);
234           fprintf(out,
235                   "            <conf_property name=\"cluster_id\" value=\"0\"/>\n");
236           break;
237         }
238       }
239     }
240     fprintf(out, "            </host_lists>\n");
241     fprintf(out, "         </configuration>\n");
242     fprintf(out, "      </node_statistics>\n");
243   }
244   fprintf(out, "   </node_infos>\n");
245   fprintf(out, "</grid_schedule>\n");
246 }
247
248 int main(int argc, char **argv)
249 {
250   unsigned int cursor;
251   double finish_time, min_finish_time = -1.0;
252   SD_task_t task, selected_task = NULL, last_scheduled_task;
253   xbt_dynar_t ready_tasks;
254   SD_workstation_t workstation, selected_workstation = NULL;
255   int total_nworkstations = 0;
256   const SD_workstation_t *workstations = NULL;
257   xbt_dynar_t dax, changed;
258   FILE *out = NULL;
259
260   /* initialization of SD */
261   SD_init(&argc, argv);
262
263   /* Check our arguments */
264   if (argc < 3) {
265     XBT_INFO("Usage: %s platform_file dax_file [jedule_file]", argv[0]);
266     XBT_INFO
267         ("example: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed",
268          argv[0]);
269     exit(1);
270   }
271   char *tracefilename;
272   if (argc == 3) {
273     char *last = strrchr(argv[2], '.');
274
275     tracefilename = bprintf("%.*s.jed",
276                             (int) (last ==
277                                    NULL ? strlen(argv[2]) : last -
278                                    argv[2]), argv[2]);
279   } else {
280     tracefilename = xbt_strdup(argv[3]);
281   }
282
283   /* creation of the environment */
284   SD_create_environment(argv[1]);
285
286   /*  Allocating the workstation attribute */
287   total_nworkstations = SD_workstation_get_number();
288   workstations = SD_workstation_get_list();
289
290   for (cursor = 0; cursor < total_nworkstations; cursor++)
291     SD_workstation_allocate_attribute(workstations[cursor]);
292
293
294   /* load the DAX file */
295   dax = SD_daxload(argv[2]);
296
297   xbt_dynar_foreach(dax, cursor, task) {
298     SD_task_watch(task, SD_DONE);
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_is_empty(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       XBT_DEBUG("%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       }
329     }
330
331     XBT_INFO("Schedule %s on %s", SD_task_get_name(selected_task),
332           SD_workstation_get_name(selected_workstation));
333
334     SD_task_schedulel(selected_task, 1, selected_workstation);
335
336     /*
337      * SimDag allows tasks to be executed concurrently when they can by default.
338      * Yet schedulers take decisions assuming that tasks wait for resource
339      * availability to start.
340      * The solution (well crude hack is to keep track of the last task scheduled
341      * on a workstation and add a special type of dependency if needed to
342      * force the sequential execution meant by the scheduler.
343      * If the last scheduled task is already done, has failed or is a 
344      * predecessor of the current task, no need for a new dependency
345     */
346
347     last_scheduled_task = 
348       SD_workstation_get_last_scheduled_task(selected_workstation);
349     if (last_scheduled_task && 
350   (SD_task_get_state(last_scheduled_task) != SD_DONE) &&
351   (SD_task_get_state(last_scheduled_task) != SD_FAILED) &&
352   !SD_task_dependency_exists(
353      SD_workstation_get_last_scheduled_task(selected_workstation),
354      selected_task))
355       SD_task_dependency_add("resource", NULL,
356            last_scheduled_task, selected_task);
357     
358     SD_workstation_set_last_scheduled_task(selected_workstation, selected_task);
359     
360     SD_workstation_set_available_at(selected_workstation, min_finish_time);
361
362     xbt_dynar_free_container(&ready_tasks);
363     /* reset the min_finish_time for the next set of ready tasks */
364     min_finish_time = -1.;
365     xbt_dynar_free_container(&changed);
366   }
367
368   XBT_INFO("Simulation Time: %f", SD_get_clock());
369
370
371
372
373   XBT_INFO
374       ("------------------- Produce the trace file---------------------------");
375   XBT_INFO("Producing the trace of the run into %s", tracefilename);
376   out = fopen(tracefilename, "w");
377   xbt_assert(out, "Cannot write to %s", tracefilename);
378   free(tracefilename);
379
380   output_xml(out, dax);
381
382   fclose(out);
383
384
385   xbt_dynar_free_container(&ready_tasks);
386   xbt_dynar_free_container(&changed);
387
388   xbt_dynar_foreach(dax, cursor, task) {
389     SD_task_destroy(task);
390   }
391   xbt_dynar_free_container(&dax);
392
393   for (cursor = 0; cursor < total_nworkstations; cursor++)
394     SD_workstation_free_attribute(workstations[cursor]);
395
396   /* exit */
397   SD_exit();
398   return 0;
399 }