Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
a95be21c2070ad07bd6b8a0b5bbdd18ded57345e
[simgrid.git] / examples / simdag / scheduling / sd_scheduling.c
1 /* Copyright (c) 2009-2016. The SimGrid Team.
2  * All rights reserved.                                                     */
3
4 /* This program is free software; you can redistribute it and/or modify it
5  * under the terms of the license (GNU LGPL) which comes with this package. */
6
7 /* simple test to schedule a DAX file with the Min-Min algorithm.           */
8 #include <string.h>
9 #include "simgrid/simdag.h"
10
11 #if HAVE_JEDULE
12 #include "simgrid/jedule/jedule_sd_binding.h"
13 #endif
14
15 XBT_LOG_NEW_DEFAULT_CATEGORY(test, "Logging specific to this SimDag example");
16
17 typedef struct _HostAttribute *HostAttribute;
18 struct _HostAttribute {
19   /* Earliest time at which a host is ready to execute a task */
20   double available_at;
21   SD_task_t last_scheduled_task;
22 };
23
24 static double sg_host_get_available_at(sg_host_t host)
25 {
26   HostAttribute attr = (HostAttribute) sg_host_user(host);
27   return attr->available_at;
28 }
29
30 static void sg_host_set_available_at(sg_host_t host, double time)
31 {
32   HostAttribute attr = (HostAttribute) sg_host_user(host);
33   attr->available_at = time;
34   sg_host_user_set(host, attr);
35 }
36
37 static SD_task_t sg_host_get_last_scheduled_task( sg_host_t host){
38   HostAttribute attr = (HostAttribute) sg_host_user(host);
39   return attr->last_scheduled_task;
40 }
41
42 static void sg_host_set_last_scheduled_task(sg_host_t host, SD_task_t task){
43   HostAttribute attr = (HostAttribute) sg_host_user(host);
44   attr->last_scheduled_task=task;
45   sg_host_user_set(host, attr);
46 }
47
48 static xbt_dynar_t get_ready_tasks(xbt_dynar_t dax)
49 {
50   unsigned int i;
51   xbt_dynar_t ready_tasks;
52   SD_task_t task;
53
54   ready_tasks = xbt_dynar_new(sizeof(SD_task_t), NULL);
55   xbt_dynar_foreach(dax, i, task) {
56     if (SD_task_get_kind(task) == SD_TASK_COMP_SEQ && SD_task_get_state(task) == SD_SCHEDULABLE) {
57       xbt_dynar_push(ready_tasks, &task);
58     }
59   }
60   XBT_DEBUG("There are %lu ready tasks", xbt_dynar_length(ready_tasks));
61
62   return ready_tasks;
63 }
64
65 static double finish_on_at(SD_task_t task, sg_host_t host)
66 {
67   double result;
68   unsigned int i;
69   double data_available = 0.;
70   double redist_time = 0;
71   double last_data_available;
72
73   xbt_dynar_t parents = SD_task_get_parents(task);
74
75   if (!xbt_dynar_is_empty(parents)) {
76     /* compute last_data_available */
77     SD_task_t parent;
78     last_data_available = -1.0;
79     xbt_dynar_foreach(parents, i, parent) {
80       /* normal case */
81       if (SD_task_get_kind(parent) == SD_TASK_COMM_E2E) {
82         sg_host_t * parent_host= SD_task_get_workstation_list(parent);
83         /* Estimate the redistribution time from this parent */
84         if (SD_task_get_amount(parent) <= 1e-6){
85           redist_time= 0;
86         } else {
87           redist_time = sg_host_route_latency(parent_host[0], host) +
88                         SD_task_get_amount(parent) / sg_host_route_bandwidth(parent_host[0], host);
89         }
90         data_available = SD_task_get_start_time(parent) + redist_time;
91       }
92
93       /* no transfer, control dependency */
94       if (SD_task_get_kind(parent) == SD_TASK_COMP_SEQ) {
95         data_available = SD_task_get_finish_time(parent);
96       }
97
98       if (last_data_available < data_available)
99         last_data_available = data_available;
100     }
101
102     xbt_dynar_free_container(&parents);
103
104     result = MAX(sg_host_get_available_at(host), last_data_available) + SD_task_get_amount(task)/sg_host_speed(host);
105   } else {
106     xbt_dynar_free_container(&parents);
107
108     result = sg_host_get_available_at(host) + SD_task_get_amount(task)/sg_host_speed(host);
109   }
110   return result;
111 }
112
113 static sg_host_t SD_task_get_best_host(SD_task_t task)
114 {
115   sg_host_t *hosts = sg_host_list();
116   int nhosts = sg_host_count();
117   sg_host_t best_host = hosts[0];
118   double min_EFT = finish_on_at(task, hosts[0]);
119
120   for (int i = 1; i < nhosts; i++) {
121     double EFT = finish_on_at(task, hosts[i]);
122     XBT_DEBUG("%s finishes on %s at %f", SD_task_get_name(task), sg_host_get_name(hosts[i]), EFT);
123
124     if (EFT < min_EFT) {
125       min_EFT = EFT;
126       best_host = hosts[i];
127     }
128   }
129   xbt_free(hosts);
130   return best_host;
131 }
132
133 int main(int argc, char **argv)
134 {
135   unsigned int cursor;
136   double min_finish_time = -1.0;
137   SD_task_t task, selected_task = NULL;
138   xbt_dynar_t ready_tasks;
139   sg_host_t selected_host = NULL;
140   char * tracefilename = NULL;
141
142   /* initialization of SD */
143   SD_init(&argc, argv);
144
145   /* Check our arguments */
146   xbt_assert(argc > 2, "Usage: %s platform_file dax_file [jedule_file]\n"
147              "\tExample: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed", argv[0], argv[0]);
148
149   if (argc == 4)
150     tracefilename = xbt_strdup(argv[3]);
151
152   /* creation of the environment */
153   SD_create_environment(argv[1]);
154
155   /*  Allocating the host attribute */
156   int total_nhosts = sg_host_count();
157   sg_host_t *hosts = sg_host_list();
158
159   for (cursor = 0; cursor < total_nhosts; cursor++)
160     sg_host_user_set(hosts[cursor], xbt_new0(struct _HostAttribute, 1));
161
162   /* load the DAX file */
163   xbt_dynar_t dax = SD_daxload(argv[2]);
164
165   xbt_dynar_foreach(dax, cursor, task) {
166     SD_task_watch(task, SD_DONE);
167   }
168
169   /* Schedule the root first */
170   xbt_dynar_get_cpy(dax, 0, &task);
171   sg_host_t host = SD_task_get_best_host(task);
172   SD_task_schedulel(task, 1, host);
173
174   while (!xbt_dynar_is_empty(SD_simulate(-1.0))) {
175     /* Get the set of ready tasks */
176     ready_tasks = get_ready_tasks(dax);
177     if (xbt_dynar_is_empty(ready_tasks)) {
178       xbt_dynar_free_container(&ready_tasks);
179       /* there is no ready task, let advance the simulation */
180       continue;
181     }
182     /* For each ready task:
183      * get the host that minimizes the completion time.
184      * select the task that has the minimum completion time on its best host.
185      */
186     xbt_dynar_foreach(ready_tasks, cursor, task) {
187       XBT_DEBUG("%s is ready", SD_task_get_name(task));
188       host = SD_task_get_best_host(task);
189       double finish_time = finish_on_at(task, host);
190       if (min_finish_time < 0 || finish_time < min_finish_time) {
191         min_finish_time = finish_time;
192         selected_task = task;
193         selected_host = host;
194       }
195     }
196
197     XBT_INFO("Schedule %s on %s", SD_task_get_name(selected_task), sg_host_get_name(selected_host));
198     SD_task_schedulel(selected_task, 1, selected_host);
199
200     /*
201      * SimDag allows tasks to be executed concurrently when they can by default.
202      * Yet schedulers take decisions assuming that tasks wait for resource availability to start.
203      * The solution (well crude hack is to keep track of the last task scheduled on a host and add a special type of
204      * dependency if needed to force the sequential execution meant by the scheduler.
205      * If the last scheduled task is already done, has failed or is a predecessor of the current task, no need for a
206      * new dependency
207     */
208
209     SD_task_t last_scheduled_task = sg_host_get_last_scheduled_task(selected_host);
210     if (last_scheduled_task && (SD_task_get_state(last_scheduled_task) != SD_DONE) &&
211         (SD_task_get_state(last_scheduled_task) != SD_FAILED) &&
212         !SD_task_dependency_exists(sg_host_get_last_scheduled_task(selected_host), selected_task))
213       SD_task_dependency_add("resource", NULL, last_scheduled_task, selected_task);
214
215     sg_host_set_last_scheduled_task(selected_host, selected_task);
216     sg_host_set_available_at(selected_host, min_finish_time);
217
218     xbt_dynar_free_container(&ready_tasks);
219     /* reset the min_finish_time for the next set of ready tasks */
220     min_finish_time = -1.;
221   }
222
223   XBT_INFO("Simulation Time: %f", SD_get_clock());
224   XBT_INFO("------------------- Produce the trace file---------------------------");
225   XBT_INFO("Producing a jedule output (if active) of the run into %s", tracefilename?tracefilename:"minmin_test.jed");
226 #if HAVE_JEDULE
227   jedule_sd_dump(tracefilename);
228 #endif
229   free(tracefilename);
230
231   xbt_dynar_free_container(&ready_tasks);
232
233   xbt_dynar_foreach(dax, cursor, task) {
234     SD_task_destroy(task);
235   }
236   xbt_dynar_free_container(&dax);
237
238   for (cursor = 0; cursor < total_nhosts; cursor++) {
239     free(sg_host_user(hosts[cursor]));
240     sg_host_user_set(hosts[cursor], NULL);
241   }
242
243   xbt_free(hosts);
244   /* exit */
245   SD_exit();
246   return 0;
247 }