1 /* simple test to schedule a DAX file with the Min-Min algorithm. */
3 /* Copyright (c) 2009, 2010. The SimGrid Team.
4 * All rights reserved. */
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. */
11 #include "simdag/simdag.h"
16 XBT_LOG_NEW_DEFAULT_CATEGORY(test,
17 "Logging specific to this SimDag example");
19 typedef struct _WorkstationAttribute *WorkstationAttribute;
20 struct _WorkstationAttribute {
21 /* Earliest time at wich a workstation is ready to execute a task */
25 static void SD_workstation_allocate_attribute(SD_workstation_t workstation)
28 data = calloc(1, sizeof(struct _WorkstationAttribute));
29 SD_workstation_set_data(workstation, data);
32 static void SD_workstation_free_attribute(SD_workstation_t workstation)
34 free(SD_workstation_get_data(workstation));
35 SD_workstation_set_data(workstation, NULL);
38 static double SD_workstation_get_available_at(SD_workstation_t workstation)
40 WorkstationAttribute attr =
41 (WorkstationAttribute) SD_workstation_get_data(workstation);
42 return attr->available_at;
45 static void SD_workstation_set_available_at(SD_workstation_t workstation,
48 WorkstationAttribute attr =
49 (WorkstationAttribute) SD_workstation_get_data(workstation);
50 attr->available_at = time;
51 SD_workstation_set_data(workstation, attr);
55 static xbt_dynar_t get_ready_tasks(xbt_dynar_t dax)
58 xbt_dynar_t ready_tasks;
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);
68 XBT_DEBUG("There are %lu ready tasks", xbt_dynar_length(ready_tasks));
73 static double finish_on_at(SD_task_t task, SD_workstation_t workstation)
75 volatile double result;
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;
83 int grand_parent_nworkstations;
84 SD_workstation_t *grand_parent_workstation_list;
86 parents = SD_task_get_parents(task);
88 if (xbt_dynar_length(parents)) {
89 /* compute last_data_available */
90 last_data_available = -1.0;
91 xbt_dynar_foreach(parents, i, parent) {
94 if (SD_task_get_kind(parent) == SD_TASK_COMM_E2E) {
95 grand_parents = SD_task_get_parents(parent);
97 if (xbt_dynar_length(grand_parents) > 1) {
98 XBT_ERROR("Warning: transfer %s has 2 parents",
99 SD_task_get_name(parent));
101 xbt_dynar_get_cpy(grand_parents, 0, &grand_parent);
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 */
109 SD_route_get_communication_time(grand_parent_workstation_list
111 SD_task_get_amount(parent));
113 SD_task_get_finish_time(grand_parent) + redist_time;
115 xbt_dynar_free_container(&grand_parents);
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);
123 if (last_data_available < data_available)
124 last_data_available = data_available;
128 xbt_dynar_free_container(&parents);
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));
135 xbt_dynar_free_container(&parents);
137 result = SD_workstation_get_available_at(workstation) +
138 SD_workstation_get_computation_time(workstation,
139 SD_task_get_amount(task));
144 static SD_workstation_t SD_task_get_best_workstation(SD_task_t task)
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;
152 best_workstation = workstations[0];
153 min_EFT = finish_on_at(task, workstations[0]);
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);
163 best_workstation = workstations[i];
167 return best_workstation;
170 static void output_xml(FILE * out, xbt_dynar_t dax)
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();
177 SD_workstation_t *list;
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");
185 " <cluster id=\"1\" hosts=\"%d\" first_host=\"0\"/>\n",
187 fprintf(out, " </clusters>\n");
188 fprintf(out, " </grid_info>\n");
189 fprintf(out, " <node_infos>\n");
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");
202 " <node_property name=\"start_time\" value=\"%.3f\"/>\n",
203 SD_task_get_start_time(task));
205 " <node_property name=\"end_time\" value=\"%.3f\"/>\n",
206 SD_task_get_finish_time(task));
207 fprintf(out, " <configuration>\n");
209 current_nworkstations = SD_task_get_workstation_count(task);
212 " <conf_property name=\"host_nb\" value=\"%d\"/>\n",
213 current_nworkstations);
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",
224 " <conf_property name=\"cluster_id\" value=\"0\"/>\n");
229 fprintf(out, " </host_lists>\n");
230 fprintf(out, " </configuration>\n");
231 fprintf(out, " </node_statistics>\n");
233 fprintf(out, " </node_infos>\n");
234 fprintf(out, "</grid_schedule>\n");
237 int main(int argc, char **argv)
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;
249 /* initialization of SD */
250 SD_init(&argc, argv);
252 /* Check our arguments */
254 XBT_INFO("Usage: %s platform_file dax_file [jedule_file]", argv[0]);
256 ("example: %s simulacrum_7_hosts.xml Montage_25.xml Montage_25.jed",
262 char *last = strrchr(argv[2], '.');
264 tracefilename = bprintf("%.*s.jed",
266 NULL ? strlen(argv[2]) : last -
269 tracefilename = xbt_strdup(argv[3]);
272 /* creation of the environment */
273 SD_create_environment(argv[1]);
275 /* Allocating the workstation attribute */
276 total_nworkstations = SD_workstation_get_number();
277 workstations = SD_workstation_get_list();
279 for (cursor = 0; cursor < total_nworkstations; cursor++)
280 SD_workstation_allocate_attribute(workstations[cursor]);
283 /* load the DAX file */
284 dax = SD_daxload(argv[2]);
286 xbt_dynar_foreach(dax, cursor, task) {
287 SD_task_watch(task, SD_DONE);
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);
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 */
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.
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;
321 XBT_INFO("Schedule %s on %s", SD_task_get_name(selected_task),
322 SD_workstation_get_name(selected_workstation));
324 SD_task_schedulel(selected_task, 1, selected_workstation);
325 SD_workstation_set_available_at(selected_workstation, min_finish_time);
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);
333 XBT_INFO("Simulation Time: %f", SD_get_clock());
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);
345 output_xml(out, dax);
350 xbt_dynar_free_container(&ready_tasks);
351 xbt_dynar_free_container(&changed);
353 xbt_dynar_foreach(dax, cursor, task) {
354 SD_task_destroy(task);
356 xbt_dynar_free_container(&dax);
358 for (cursor = 0; cursor < total_nworkstations; cursor++)
359 SD_workstation_free_attribute(workstations[cursor]);