Logo AND Algorithmique Numérique Distribuée

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