Logo AND Algorithmique Numérique Distribuée

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